题目：一辆车沿着网格线按给定路线走，每个网格里有一个人，人的视线始终看着车，问这些人净转多少圈的平方和。
思路：首先发现，净转就是这个线路绕这个点转了多少圈。然后发现，这个值就是这个网格左边向下的次数，和向上的次数差
这个可以用树状数组的思想，用前缀和，来维护，数组由于边界不确定可以有vector
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> using namespace std; vector<vector<int> >a; int main() { int t,kase=0; int n,m,k; char op[10]; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); a=vector< vector<int> >(n+10,vector<int>(m+10,0)); int dt; int x=1,y=1; while(k--) { scanf("%s",op); scanf("%d",&dt); if(op[0]=='D') { a[x][y]++; // a[x][m+1]--; x+=dt; a[x][y]--; // a[x][m+1]++; } if(op[0]=='R') { y+=dt; } if(op[0]=='L') { y-=dt; } if(op[0]=='U'){ a[x][y]++; // a[x][m+1]--; x-=dt; a[x][y]--; // a[x][m+1]++; } } /* for(int i=1;i<=n+1;i++) { for(int j=1;j<=m+1;j++) { cout << a[i][j] << " "; } cout << endl; }*/ long long sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; sum+=a[i][j]*a[i][j]; } printf("Case #%d: %lld\n",++kase,sum); } return 0; }