T3 同步机器人（sync）

题目描述

小C正在测试两个机器人。测试场地是一张 n行m列的网格地图，其中字符.表示可以通行的空地,字符#表示不能通行的障碍物.两个机器人分别称为机器人A和机器人B.小C每次可以选择上、下、左、右中的一个方向,并向两个机器人同时发送这条移动指令。收到指令后，两个机器人分别按照以下规则行动：如果机器人沿指令方向移动一格后仍在地图内，并且到达的格子不是障碍物，那么它会移动到该格子。否则，它会停留在原来的格子。两个机器人的行动互不影响。它们可以同时位于同一个格子，也可以同时经过同一个格子。机器人 A 和机器人 B 各有一个目标位置。小 C 希望在某次指令执行完毕后，两个机器人同时位于各自的目标位置。请你求出最少需要发送多少条指令。机器人到达目标位置后不会自动停机。如果之后收到的指令能让它移动，它仍然会离开目标位置。

即 两个机器人动作同步 如果一方无法前进就停止 另一方前进

考试过程

我选择使用骗分策略 无参考价值

正确方式 使用四维数组 前两位存储A机器人位置 后两位存储B机器人位置 总体使用广搜策略寻找一致的最短路径

正确代码

#include<bits/stdc++.h>
#define arr4 array<int,4>
using namespace std;
const int N=32;
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){
	cin>>x[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(){
	queue<arr4>q;
	q.push(st);
	vis[st[0]][st[1]][st[2]][st[3]]=1;
	while(!q.empty()){
		arr4 x=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			arr4 tmp=move(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;
	cin>>n>>m;
	for(int i=1;i<=n;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]）的方法记录异或前缀和 然后使用l+=s[ex][ey]^s[ex][sy-1]^s[sx-1][ey]^s[sx-1][sy-1]的前缀和公式进行计算：

#include<bits/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);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int sx=1;sx<=n;sx++){
		for(int sy=1;sy<=m;sy++){
			s[sx][sy]=s[sx-1][sy]^s[sx][sy-1]^s[sx-1][sy-1]^a[sx][sy];
		}
	}
	for(int ex=1;ex<=n;ex++){
		for(int ey=1;ey<=m;ey++){
			l=0;
			for(int sx=1;sx<=ex;sx++){
				for(int sy=1;sy<=ey;sy++){
					l+=s[ex][ey]^s[ex][sy-1]^s[sx-1][ey]^s[sx-1][sy-1];
				}
			}
			sum+=l;
			
		}
	}
	cout<<sum<<'\n';
} 

使用大胆的四层嵌套for循环 导致时间超限

正确代码

我们可以使用拆分的方式 使用上界与下界的方式用一个元素代表一列元素 强行减少一层循环：

#include<bits/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);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int u=1;u<=n;u++){
		memset(b,0,sizeof(b));
		for(int d=u;d<=n;d++){
			for(int j=1;j<=m;j++){
				b[j]^=a[d][j];
				sum[j]=sum[j-1]^b[j];
			}
			for(int p=0;p<10;p++){
				long long cnt[2]={1,0};
				for(int j=1;j<=m;j++){
					int t=(sum[j]>>p)&1;
					ans+=(1<<p)*cnt[t^1];
					cnt[t]++;
				}
			}
		}
	}
	cout<<sum<<'\n';
}