T3 同步机器人sync题目描述小C正在测试两个机器人。测试场地是一张 n行m列的网格地图其中字符.表示可以通行的空地,字符#表示不能通行的障碍物.两个机器人分别称为机器人A和机器人B.小C每次可以选择上、下、左、右中的一个方向,并向两个机器人同时发送这条移动指令。收到指令后两个机器人分别按照以下规则行动如果机器人沿指令方向移动一格后仍在地图内并且到达的格子不是障碍物那么它会移动到该格子。否则它会停留在原来的格子。两个机器人的行动互不影响。它们可以同时位于同一个格子也可以同时经过同一个格子。机器人 A 和机器人 B 各有一个目标位置。小 C 希望在某次指令执行完毕后两个机器人同时位于各自的目标位置。请你求出最少需要发送多少条指令。机器人到达目标位置后不会自动停机。如果之后收到的指令能让它移动它仍然会离开目标位置。即 两个机器人动作同步 如果一方无法前进就停止 另一方前进考试过程我选择使用骗分策略 无参考价值正确方式 使用四维数组 前两位存储A机器人位置 后两位存储B机器人位置 总体使用广搜策略寻找一致的最短路径正确代码#includebits/stdc.h #define arr4 arrayint,4 using namespace std; const int N32; int n,m,dis[N][N][N][N],dx[]{0,0,1,-1},dy[]{1,-1,0,0}; char s[N][N]; bool vis[N][N][N][N]; arr4 st,ed; void input(arr4 x){ cinx[0]x[1]x[2]x[3];//输入函数 将机器人的初始位置与终点存入 } arr4 move(arr4 x,int d){ x[0]dx[d],x[1]dy[d]; if(s[x[0]][x[1]]!.) x[0]-dx[d],x[1]-dy[d]; x[2]dx[d],x[3]dy[d]; if(s[x[2]][x[3]]!.) x[2]-dx[d],x[3]-dy[d];//向某方向走一步 然后判断如果此处不可站立就进行回溯 return x; } bool check(arr4 x){ if(s[x[0]][x[1]]!.||s[x[2]][x[3]]!.)return 0; if(vis[x[0]][x[1]][x[2]][x[3]])return 0; return 1; //判断此处能不能走 } void bfs(){ queuearr4q; q.push(st); vis[st[0]][st[1]][st[2]][st[3]]1; while(!q.empty()){ arr4 xq.front(); q.pop(); for(int i0;i4;i){ arr4 tmpmove(x,i); if(!check(tmp)) continue; vis[tmp[0]][tmp[1]][tmp[2]][tmp[3]]1;//标记 dis[tmp[0]][tmp[1]][tmp[2]][tmp[3]]dis[x[0]][x[1]][x[2]][x[3]]1;//记录步数 q.push(tmp); } } } int main(){ int n,m; cinnm; for(int i1;in;i) scanf(%s,s[i]1); input(st);input(ed); bfs(); if(vis[ed[0]][ed[1]][ed[2]][ed[3]])printf(%d,dis[ed[0]][ed[1]][ed[2]][ed[3]]); else printf(-1); }T4 矩阵matrix问题描述现在给你一个n行m列的矩阵矩阵上每个格子有一个整数其中第i行第j列对应的格子上的整数为 g[i][j] 。现在定义该矩阵的一个子矩阵的快乐值为该子矩阵上的所有数字的异或和。一组数字a1,a2...an的异或和为a1 xor a2 xor ... xor an其中xor表示按位异或运算现在问你该矩阵的所有子矩阵的快乐值之和为多少考试过程采用二维数组异或前缀和的方法 通过记录s数组s[sx][sy]s[sx-1][sy]^s[sx][sy-1]^s[sx-1][sy-1]^a[sx][sy]的方法记录异或前缀和 然后使用ls[ex][ey]^s[ex][sy-1]^s[sx-1][ey]^s[sx-1][sy-1]的前缀和公式进行计算#includebits/stdc.h using namespace std; int n,m,a[350][350],s[350][350]; long long sum,l; int main(){ freopen(matrix.in,r,stdin); freopen(matrix.out,w,stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinnm; for(int i1;in;i){ for(int j1;jm;j){ cina[i][j]; } } for(int sx1;sxn;sx){ for(int sy1;sym;sy){ s[sx][sy]s[sx-1][sy]^s[sx][sy-1]^s[sx-1][sy-1]^a[sx][sy]; } } for(int ex1;exn;ex){ for(int ey1;eym;ey){ l0; for(int sx1;sxex;sx){ for(int sy1;syey;sy){ ls[ex][ey]^s[ex][sy-1]^s[sx-1][ey]^s[sx-1][sy-1]; } } suml; } } coutsum\n; }使用大胆的四层嵌套for循环 导致时间超限正确代码我们可以使用拆分的方式 使用上界与下界的方式用一个元素代表一列元素 强行减少一层循环#includebits/stdc.h using namespace std; int n,m,a[350][350],sum[350],b[350]; long long ans,l; int main(){ //freopen(matrix.in,r,stdin); //freopen(matrix.out,w,stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinnm; for(int i1;in;i){ for(int j1;jm;j){ cina[i][j]; } } for(int u1;un;u){ memset(b,0,sizeof(b)); for(int du;dn;d){ for(int j1;jm;j){ b[j]^a[d][j]; sum[j]sum[j-1]^b[j]; } for(int p0;p10;p){ long long cnt[2]{1,0}; for(int j1;jm;j){ int t(sum[j]p)1; ans(1p)*cnt[t^1]; cnt[t]; } } } } coutsum\n; }