总分：
第一题：30分钟，100分，第二题：30分钟，100分
第三题：1.5小时，50分，第四题：30分钟，10分
第一题和第二题成功AC，于是又用bfs做第三题，得了50分，第四题不会，然后骗分
第一题：
一道十分简单的题：
AC代码：
#include<iostream> #include<cstdio> using namespace std; int n,p[10],cnt; struct node{ int a,b,c,d; }x[100005]; int main(){ freopen("fourd.in","r",stdin); freopen("fourd.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>x[i].a>>x[i].b>>x[i].c>>x[i].d; } for(int i=1;i<=8;i++){ cin>>p[i]; } for(int i=1;i<=n;i++){ if(x[i].a>=p[1]&&x[i].a<=p[5]&&x[i].b>=p[2]&&x[i].b<=p[6]&&x[i].c>=p[3]&&x[i].c<=p[7]&&x[i].d>=p[4]&&x[i].d<=p[8]){ cnt++; } } cout<<cnt; return 0; } //20min+10min第二题：
也是一道非常简单的模拟：思路：能和成就合成
AC代码：
#include<iostream> #include<cstdio> using namespace std; int n,a,m,t[1000005],ans[1000005],x,q; int main(){ freopen("fit.in","r",stdin); freopen("fit.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a; t[a]++; } for(int i=1;i<=n;i++){ ans[i]=t[i]; t[i+1]=t[i+1]+t[i]/2; } cin>>q; while(q--){ cin>>x; cout<<ans[x]<<"\n"; } return 0; } //15min+10min第三题：
题意：
有两个机器人，在可能不同也可能相同的起点前往可能不同也可能相同的终点，你要给这两个机器人指令让他们共同上、下、左、右。但是不会走出边界和碰到障碍物，问最少的指令个数。
这道题一看就是BFS，但怎么BFS，这是我们就要结合题目，我们发现这两个机器人要同时进行移动（注意遇到障碍物或到达地图边界一个机器人不移动，另一个机器人移动），于是BFS要有4个元素，vis要用四维数组，AC代码如下：
#include<iostream> #include<queue> #include<cstdio> using namespace std; int n,m,x,y,xx,yy,fx[]={0,0,1,-1},fy[]={-1,1,0,0},cnt,pa,pb,qa,qb,dis[35][35][35][35]; char a[35][35]; bool vis[35][35][35][35]; queue<int> qx,qy,qxx,qyy; void bfs(int x,int y,int xx,int yy){ qx.push(x),qy.push(y),qxx.push(xx),qyy.push(yy); vis[x][y][xx][yy]=1; while(!qx.empty()){ int X=qx.front(),Y=qy.front(),XX=qxx.front(),YY=qyy.front(); qx.pop(),qy.pop(),qxx.pop(),qyy.pop(); for(int i=0;i<4;i++){ int ax=X+fx[i],ay=Y+fy[i],axx=XX+fx[i],ayy=YY+fy[i]; if(ax>n||ax<1||ay>m||ay<1||a[ax][ay]!='.'){ //C1 ax=X,ay=Y; } if(axx>n||axx<1||ayy>m||ayy<1||a[axx][ayy]!='.'){ axx=XX,ayy=YY; } if(vis[ax][ay][axx][ayy]==0){ //C2 qx.push(ax),qy.push(ay),qxx.push(axx),qyy.push(ayy); vis[ax][ay][axx][ayy]=1; dis[ax][ay][axx][ayy]=dis[X][Y][XX][YY]+1; } } } } int main(){ //freopen("sync.in","r",stdin); //freopen("sync.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]; } } cin>>x>>y>>xx>>yy; cin>>pa>>pb>>qa>>qb; bfs(x,y,xx,yy); if(vis[pa][pb][qa][qb]==1){ //C3 cout<<dis[pa][pb][qa][qb]; } else{ cout<<"-1"; } return 0; }C1：在BFS中，这里判断的是，如果按照方向走后出了地图或走到了障碍物上，就回到之前的位置
C2既然前面已经判定了机器人不走的情况，那现在就应该判断机器人能不能走的情况，所以只有当前这个位置没有被访问过时，才会访问
C3：当这两个机器人的终点都被访问过时，才能输出值，否则输出-1
第四题：
给你一个矩阵，求所有子矩阵上的所有数字的异或和的总和
然后这个题很显然用暴力（枚举左上和右下的坐标）会TLE，所以要进行降维打击，就是把四层循环变成三层循环，思路是这样的：
1.用两层循环，枚举一个是上界，一个是下界，每次循环求出sum。
这道题要用二进制拆分，因为二进制的每一位作异或都不会影响下一位。
我们想，如果sum[ R ] ^ sum[ L-1 ] ==1，就可以得到sum[ L-1]==1^sum[ R ]
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,a[305][305],b[305]; long long sum[305],ans,x; 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 i=1;i<=n;i++){ memset(b,0,sizeof(b)); for(int j=i;j<=n;j++){ for(int k=1;k<=m;k++){ b[k]^=a[j][k]; //D1 sum[k]=sum[k-1]^b[k]; } for(int p=1;p<=10;p++){ long long t[5]={1}; //D2 for(int k=1;k<=m;k++){ x=(sum[k]>>(p-1))&1; //D3 ans+=(1<<(p-1))*t[x^1]; //D4 t[x]++; } } } } cout<<ans; return 0; }D1：当下界往下时，每一列都会出现一个新数，这时只须异或上就行
D2：这是一个桶数组，因为二进制只有0和1，所以t[5]就行
D3：这是取第p位
D4：这一位加的贡献可能不只是1，还跟第几位有关，所以(1<<(p-1))*t[x^1]
