题解 | #北华大学计算机程序设计算法提高训练营个人赛（无L）#
洛姐打题日记
https://ac.nowcoder.com/acm/contest/37219/A
北华大学计算机程序设计算法提高训练营个人赛（无L）
题面相当有意思了，题目感觉出的也挺好，L防ak题吧这也太难了
A-洛姐打题日记
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string s;
cin>>s;
if(s=="AC")cout<<"Accepted";
else if(s=="WA")cout<<"Wrong Answer";
else if(s=="RE")cout<<"Runtime Error";
else if(s=="TLE")cout<<"Time Limit Exceeded";
else if(s=="PE")cout<<"Presentation Error";
else if(s=="MLE")cout<<"Memory Limit Exceeded";
else cout<<"Compile Error";
return 0;
}
B-鸡兔同笼
问题解析
设有a个鸡，b个兔子。方程就是a+b=H和a*x+b *y=F。解方程即可。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
void solve()
{
int x,y,h,f;
cin>>x>>y>>h>>f;
int b=(h*x-f)/(x-y);
int a=h-b;
cout<<a<<" "<<b<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
C-小杜的签到
问题解析
把数组升序排序后得到的就是最大值，乘上-1（或把数组降序排序后再算一遍）得到的就是最小值。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin>>n;
vector<int>v(n);
for(int i=0;i<n;i++)cin>>v[i];
sort(v.begin(),v.end());
int sum=0;
for(int i=1;i<n;i++)
{
sum+=v[i]-v[i-1];
}
cout<<-1*sum<<" "<<sum<<endl;
return 0;
}
D-我超！原！
问题解析
一开始还想着完全背包，一看复杂度就肯定不是。
直接贪心模拟，先等差数列前n项和算出需要多少经验才能升到x级，但是要注意初始是1级，所以我们算的是前x-1项和。再算一下我们全部资源有多少经验，如果全部资源都用上经验也不够就输出QAQ。
直接贪心，能用20000的就用，用完了或用了会超就用5000，再是1000，最后离升满级就差不到1000经验，我们再看1000的有没有，没有用5000，再没有用20000。
但是有一点，比如所需经验是17000，5000的有4个，1000的有1个，如果我们用了三个5000后用一个1000的，这样还剩1000经验才到目标，此时1000的用完了，我们只能用5000的，超出经验4000，但我们要是一开始就用4个5000的，那超出经验3000。所以我们在算的过程中可以多加一个步骤，我们不继续细分而是直接用当前档次升满级看需要多少经验。最后这两种途径的取最小值即可。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll n, m, a, b, c;
cin >> n >> m >> a >> b >> c;
ll res = 1000 * (n-1) + ((n-2) * (n - 1)) / 2 * m;
ll ans = a * 20000 + b * 5000 + c * 1000;
if (res > ans)
{
cout << "QAQ" << endl;
return 0;
}
ans=1e18;
if (a * 20000 >= res)
{
a -= res / 20000;
res %= 20000;
if(a>0)ans=min(ans,20000-res);
}
else
{
res -= a * 20000;
a = 0;
}
if (b * 5000 >= res)
{
b -= res / 5000;
res %= 5000;
if(b>0)ans=min(ans,5000-res);
}
else
{
res -= b * 5000;
b = 0;
}
if (c * 1000 >= res)
{
c -= res / 1000;
res %= 1000;
if(c>0)ans=min(ans,1000-res);
}
else
{
res -= c * 1000;
c = 0;
}
if (res == 0)cout << res << endl;
else if (c != 0)cout << min(ans,1000 - res) << endl;
else if (b != 0)cout << min(ans,5000 - res) << endl;
else if (a != 0)cout << min(ans,20000 - res) << endl;
return 0;
}
E-佳乐的迷宫
问题解析
可以先把入口的位置都记录下来，然后我们以出口位置进行bfs(dfs)，看那些位置是出口能走到的，那么对应的，这个位置就是能走到出口的，我们再去判断之前那些出口位置有哪些是出口能走到的即可。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
int st[1050][1050];
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<string>v(n);
for (int i = 0; i < n; i++)cin >> v[i];
vector<PII>ans(k);
for (int i = 0; i < k; i++)cin >> ans[i].first >> ans[i].second;
int x, y;
cin >> x >> y;
queue<PII>que;
que.push({ x,y });
st[x][y] = 1;
while (!que.empty())
{
int len = que.size();
for (int i = 0; i < len; i++)
{
auto t = que.front();
que.pop();
for (int j = 0; j < 4; j++)
{
int a = t.first + dx[j], b = t.second + dy[j];
if (a >= 1 && b >= 1 && a <= n && b <= m &&v[a-1][b-1] == '.' && st[a ][b] == 0)
{
st[a ][b] = 1;
que.push({ a,b });
}
}
}
}
vector<int>res;
int cnt = 0;
for (auto i : ans)
{
cnt++;
if (st[i.first][i.second])
{
res.push_back(cnt);
}
}
cout << res.size() << endl;
for (auto i : res)cout << i << " ";
return 0;
}
F-三四五
问题解析
升级办nim游戏，这里先说一个nim游戏的必胜秘诀，如果你每次能拿最多x个石头，那么只要总石头数不是（x+1）的倍数，你就可以赢，如果是则必输。
所以只要第一堆石头是4的倍数or第二堆是5的倍数or第三堆是6的倍数，那么这堆石头我们肯定会输。但这题不是单纯的看是否必输or必赢，而是看谁先输，比如石头数是1，100，20，虽然第二堆石头是5的倍数，我们必输，但是第一堆石头只有1个，我们拿完后对面就直接输了，第一堆石头可以在第一轮分出胜负，而第二堆要20轮才能分出胜负，显然是我们赢。所以我们要看，输最快会在第几轮输，赢最快会在第几轮赢，谁小，那就说明我们会赢（输）。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
void solve()
{
int a,b,c;
cin>>a>>b>>c;
bool flag=true;
int winer=1e9,loser=1e9;
if(a%4==0)loser=min(loser,a/4);
else winer=min(winer,a/4);
if(b%5==0)loser=min(loser,b/5);
else winer=min(winer,b/5);
if(c%6==0)loser=min(loser,c/6);
else winer=min(winer,c/6);
if(winer<loser)cout<<"(^-^)"<<endl;
else cout<<"(T-T)"<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
G-杰哥的疑问
问题解析
可以用哈希表记录一下每个数的出现次数，然后对于一个数x来说，能和他相加后等于m的数肯定是m-x。那我们只要看m-x这个数出现了多少次，且x又出现了多少次，就可以知道x和m-x一共可以组合出多少个满足条件的数对。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,m,x,cnt=0;
cin>>n>>m;
unordered_map<int,int>mymap;
for(int i=0;i<n;i++)
{
cin>>x;
cnt+=mymap[m-x];
mymap[x]++;
}
cout<<cnt;
return 0;
}
H-墨染的斯汀木
问题解析
为了方便，我们可以先把没被污染的字符串全部变成小写字母的形式，然后我们再根据第一个字符串中大小写的情况来还原字符串即可。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string a,b,s,c;
cin>>a>>b;
int n=a.size(),m;
for(auto i:b)
{
if(i>='a'&&i<='z')c+=i;
else
{
c+=(i+32);
c+=(i+32);
}
}
m=c.size();
int l=0,r=0;
while(l<n&&r<m)
{
if(a[l]=='?'||(a[l]>='a'&&a[l]<='z'))s+=c[r++];
else
{
s+=(c[r]-32);
r+=2;
}
l++;
}
cout<<s<<endl;
return 0;
}
I-Darling（Easy.)和J-Darling（Hard.）
问题解析
i题数据类型教少，建图之后对于每次询问我们都跑一便bfs来求最近的异性即可。
每次向和自己链接的其它点看去，如果这个点和我们的性别不同，那根据bfs特性，这个就是我们最近的异性，如果周围没有异性，那我们就把和自己相邻的点再送去下一轮bfs，同时步数+1。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
unordered_map<int,vector<int>>mymap;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,m,t,x,y;
cin>>n>>m>>t;
vector<int>sex(n+1);
for(int i=1;i<=n;i++)cin>>sex[i];
for(int i=0;i<m;i++)
{
cin>>x>>y;
mymap[x].push_back(y);
mymap[y].push_back(x);
}
while(t--)
{
int res=0;
cin>>x;
queue<int>que;
que.push(x);
y=-1;
vector<int>st(1001);
while(!que.empty())
{
res++;
int len=que.size();
for(int i=0;i<len;i++)
{
int tt = que.front();
que.pop();
for(auto j:mymap[tt])
{
if(st[j]==0)
{
if(sex[j]!=sex[x])
{
//找到了，我们直接结束bfs
y=res;
break;
}
else
{
que.push(j);
st[j]=1;
}
}
}
if(y!=-1)break;
}
if(y!=-1)break;
}
cout<<y<<endl;
}
return 0;
}
至于j题，数据提到了1e6，这样再用上面的方法肯定会t。但还是可以用bfs来写。
我们可以把问题分成两部分：给性别为0的找最近的1，给性别为1的找最近的0。用一个二维数组f来存结果：f[i] [0]表示i到最近的0的距离，f[i] [1]表示i到最近的1的距离。
求哪个性别，就可以先遍历全部的点，把那个性别的点存入队列里，并且把f[i] [当前性别]设为0，因为里它最近的这个性别就是他自己。再进行bfs，我们只bfs到哪些性别和我们不同的点上，如果j是和i相连且性别不同的点，那么就有：
f[j] [当前性别]=f[i] [当前性别]+1；（注意当前性别不是说j的性别，而是我们现在求的性别）
这样在k次询问时，我们可以先判断询问的点是哪个性别，再去对应的数组找结果。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e6 + 50, MOD = 1e9 + 7;
unordered_map<int, vector<int>>mymap;
int f[N][2], sex[N];
int n, m, t, x, y;
void bfs(int x)
{
queue<int>que;
for(int i=1;i<=n;i++)
if (sex[i] == x)
{
que.push(i);
f[i][x] = 0;
}
while (!que.empty())
{
int ans = que.front();
que.pop();
for (auto i : mymap[ans])
{
if (f[i][x] == -1 && sex[i] != x)
{
f[i][x] = f[ans][x] + 1;
que.push(i);
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> t;
for (int i = 1; i <= n; i++)cin >> sex[i];
for (int i = 0; i < m; i++)
{
cin >> x >> y;
mymap[x].push_back(y);
mymap[y].push_back(x);
}
memset(f, -1, sizeof f);
bfs(0);
bfs(1);
while (t--)
{
cin >> x;
if (sex[x])
{
cout << f[x][0] << endl;
}
else cout << f[x][1] << endl;
}
return 0;
}
K-小杜返校记
问题解析
按照舱位和时间找对应的手续费率pi，计算式：*n=n(1-pi/100)**。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<vector<double>>v(3,vector<double>(3));
double money;
int h=0;
cin>>money>>h;
string s,fw;
cin>>s>>fw;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cin>>v[i][j];
int x;
if(s[0]=='F')x=0;
else if(s[0]=='B')x=1;
else x=2;
if(h>=336)money=money;
else if(h>=48)money=money*(1-v[x][0]/100);
else if(h>=4)money=money*(1-v[x][1]/100);
else money=money*(1-v[x][2]/100);
cout << fixed << setprecision(2) << money << endl;
return 0;
}
美团公司氛围 1908人发布
投递哔哩哔哩等公司10个岗位