UVALive

题目链接

参考

题意

N*M的网格，一辆车沿着网格线按给定路线走，每个网格里有一个人，人的视线始终看着车，问这些人净转圈数的平方和。

分析

由于车的起点和终点都为左上角，且每个格子里的人永远面对着车，经过多次模拟可发现：每个人的圈数与其所在格子左边向下次数与向上次数的差。于是只需要维护这个次数，对每次行车路线上的右边的格做处理，可以用前缀和的思想来维护，而且因为网格具体规格不确定，可以用vector。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <ctype.h>
#include <queue>
using namespace std;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef long long ll;
vector< vector<int> >v;
int main(){
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int t, m, n, k;
    int kase=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        int dx=1,dy=1;
        int d;
        char dir[3];
        v=vector< vector<int> >(n+10,vector<int>(m+10,0));
        while(k--){
            scanf("%s%d",dir,&d);
            if(dir[0]=='L'){
                dy-=d;
            }else if(dir[0]=='R'){
                dy+=d;
            }else if(dir[0]=='D'){
                v[dx][dy]++;
                v[dx+d][dy]--;
                dx+=d;
            }else if(dir[0]=='U'){
                v[dx][dy]++;
                v[dx-d][dy]-=1;
                dx-=d;
            }
        }

//        for(int i=1;i<=n+1;i++){
//            for(int j=1;j<=m+1;j++)
//                printf("%d",v[i][j]);
//            puts("");
//        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1];
                ans+=(ll)v[i][j]*v[i][j];
            }
        }
        printf("Case #%d: %lld
",++kase,ans);
    }
    return 0;
}