UVALive – 7139（差分+模拟）

题目链接

参考

题意

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+;
const int inf=0x3f3f3f3f;
const int mod=1e9+;
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=;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k);
        int dx=,dy=;
        int d;
        char dir[];
        v=vector< vector<int> >(n+,vector<int>(m+,));
        while(k--){
            scanf("%s%d",dir,&d);
            if(dir[]=='L'){
                dy-=d;
            }else if(dir[]=='R'){
                dy+=d;
            }else if(dir[]=='D'){
                v[dx][dy]++;
                v[dx+d][dy]--;
                dx+=d;
            }else if(dir[]=='U'){
                v[dx][dy]++;
                v[dx-d][dy]-=;
                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=;
        for(int i=;i<=n;i++){
            for(int j=;j<=m;j++){
                v[i][j]+=v[i-][j]+v[i][j-]-v[i-][j-];
                ans+=(ll)v[i][j]*v[i][j];
            }
        }
        printf("Case #%d: %lld\n",++kase,ans);
    }
    return ;
}