牛客周赛Round151

今天状态一般可能是放假玩得太开心了吧A了四个题看题吧目录A:运动会字符串处理B:数方格异或运算应用结论与原理C列竖式高精度加法应用D走迷宫BFS二维前缀和E:跷跷板公式推导A:运动会字符串处理纯纯签到题#includebits/stdc.h using namespace std; string s; int main() { int n; cinn; cins; bool flagtrue; int res0; for(int i0;in;i) { if(s[i]|) { if(flag) { flagfalse; res; } else flagtrue; } } coutresendl; return 0; }B:数方格异或运算应用结论与原理这道题永远存在合法解可以直接输出 YES。核心逻辑如下任选一行r和一列c它们的并集共nm-1个单元格其中交点(r,c)只会在总异或中出现一次。因此修改交点的值可以自由控制总异或的结果 设原始总异或为S将a[r][c]修改为v后新的总异或为S ^ a[r][c] ^ v。 令总异或等于目标值x可直接解出v S ^ a[r][c] ^ x。由于异或运算不会让数值位数超过原数的最大位数v必然在0 ~ 1e9范围内完全符合题目要求。#includebits/stdc.h using namespace std; const int N1010; int a[N][N]; int main() { int n,m; cinnm; for(int i1;in;i) { for(int j1;jm;j) { cina[i][j]; } } int x; cinx; int resa[1][1]; for(int i2;in;i)res^a[i][1]; for(int i2;im;i)res^a[1][i]; coutYESendl; res^a[1][1]; res^x; cout1 1 resendl; cout1 1endl; return 0; }C列竖式高精度加法应用这个题的难点在于小数点的操作小数点后面的要统一位数具体步骤字符串拆分读取两个数字字符串去掉小数点后将数字逐位存入数组同时记录小数位数。小数点对齐给小数位数更少的数字末尾补 0让两个数的小数部分右对齐保证百分位加百分位、十分位加十分位。反转数组将数组反转让最低位小数最右侧放在数组开头方便从低位到高位依次相加。模拟进位从低位到高位逐位相加每一位相加结果≥10 时计数 1同时保留进位到高位。#includebits/stdc.h using namespace std; vectorintA,B; vectorintC; string s1,s2; int add(vectorintA,vectorintB) { int nA.size(); int cnt0; int t0; for(int i0;in;i) { int b0; if(iB.size())bB[i]; ttA[i]b; //couttendl; if(t/10) { cnt; } t/10; } return cnt; } int main() { cins1s2; int flag11,flag21; for(int i0;is1.size();i) { if(s1[i].) { flag1s1.size()-i; continue; } A.push_back(s1[i]-0); } for(int i0;is2.size();i) { if(s2[i].) { flag2s2.size()-i; continue; } B.push_back(s2[i]-0); } if(flag1!flag2) { if(flag1flag2) { int nflag1-flag2; while(n) { B.push_back(0); n--; } } else { int nflag2-flag1; while(n) { A.push_back(0); n--; } } } if(A.size()B.size()) { CA; AB; BC; } reverse(A.begin(),A.end()); reverse(B.begin(),B.end()); coutadd(A,B); return 0; }D走迷宫BFS二维前缀和用二维前缀和快速判断矩形内是否有墙再通过BFS 搜索左上角的合法位置是这道题的标准最优解法时间复杂度 O (nm)完全符合数据范围要求。#includebits/stdc.h using namespace std; const int N1010; int n,m,a,b; char w[N][N]; int sum[N][N]; int dx[4]{0,1,-1,0}; int dy[4]{1,0,0,-1}; bool st[N][N]; bool bfs(int sx,int sy,int ex,int ey) { queuepairint,int q; q.push({sx,sy}); st[sx][sy]true; while(q.size()) { auto tq.front(); q.pop(); if(t.firstext.secondey)return true; for(int i0;i4;i) { int nxt.firstdx[i],nyt.seconddy[i]; if(nx1||ny1||nxa-1n||nyb-1m||st[nx][ny])continue; int x2nxa-1,y2nyb-1; int cntsum[x2][y2]-sum[nx-1][y2]-sum[x2][ny-1]sum[nx-1][ny-1]; if(cnt)continue; st[nx][ny]true; q.push({nx,ny}); } } return false; } int main() { int T; cinT; while(T--) { cinnmab; for(int i1;in;i) { for(int j1;jm;j)cinw[i][j]; } for(int i1;in;i) for(int j1;jm;j) sum[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1](w[i][j]#); int sx,sy,ex,ey; for(int i1;in;i) for(int j1;jm;j) { if(w[i][j]S)sxi,syj; if(w[i][j]E)exi,eyj; } for(int i1;in;i) for(int j1;jm;j) st[i][j]false; if(bfs(sx,sy,ex,ey))coutYesendl; else coutNoendl; } return 0; }E:跷跷板公式推导左边力矩 左侧小朋友力矩 左半木板力矩 右边力矩 右侧小朋友力矩 右半木板力矩 平衡条件左边力矩 右边力矩小朋友力矩部分化简后恒等于p * total_w - total_wxtotal_w是小朋友总重量total_wx是所有w_i*x_i的总和和小朋友分布无关。木板力矩部分化简后等于W*p - W*l/2。整理平衡等式最终得到p ( 2*(total_wx - w_i*x_i) W*l ) / ( 2*(total_w - w_i W) )对于赶走第i个小朋友的方案分子必须能被分母整除即p是整数0 ≤ p ≤ l支点必须在木板上满足这两个条件就是合法方案统计总数即可。#includebits/stdc.h using namespace std; typedef long long LL; const int N2e510; LL x[N], w[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; LL l, W; cin n l W; LL total_w 0; __int128 total_wx 0; for(int i1; in; i) { cin x[i] w[i]; total_w w[i]; total_wx (__int128)w[i] * x[i]; } int ans 0; for(int i1; in; i) { __int128 num 2 * (total_wx - (__int128)w[i] * x[i]) (__int128)W * l; __int128 den 2 * (total_w - w[i] W); if(num % den ! 0) continue; __int128 p num / den; if(p 0 p l) ans; } cout ans endl; return 0; }