首页 > 代码库 > UVALive - 7139（差分+模拟）
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+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\n",++kase,ans); } return 0;}
UVALive - 7139（差分+模拟）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。