第一题(A)就不用发了,把公式看懂就可以了。
大家的分数不外乎在0,20,60,100之间。
先来看一看数据范围:
20%: |S| * T <= 10^6, q = 1
40%: |S| * T <= 10^6, q <= 10^5
60%: |S|, T <= 10^5, q <= 10^5
100%: 1 <= T,n,m <= 10^9, 1 <= x <= n, 1 <= y <= m. 1<= q, |S| <= 10^5
爆零的该扪心自问了
纯模拟(三重循环)能拿20分 当q到了10的5次方就TLE了
60分看来比20分厉害不少 代码差不多是这样的:
#include<cstring> #include<cstdio> using namespace std; int n,m,t; int q; char s[100001]; int main() { scanf("%d%d%d ",&n,&m,&t); int h=1; int x=0,y=0; while(1){ char a; a=getchar(); if(a==' ') break; if(a=='U') x--; if(a=='D') x++; if(a=='L') y--; if(a=='R') y++; s[h]=a; h++; } x*=t,y*=t; scanf("%d",&q); for(int i=1;i<=q;i++){ int sx,sy; scanf("%d%d",&sx,&sy); sx+=x; sy+=y; if(sx>n) sx%=n; if(sy>m) sy%=m; if(sx<1) sx=n-(-sx)%n; if(sy<1) sy=m-(-sy)%m; printf("%d %d ",sx,sy); } return 0; }
核心部分已经对了,其实就是求余。给大家科普一下:在数学中,余数必须是非负的,并且小于除数。也就是说,理论上(-10)÷3=-4...2,因为满足3×(-4)+2=-10。但遗憾的是,C++中,(-10)%3得出的结果是-1。所以sx=n-(-sx)%n,sy同理。
为什么只拿60分?哦,那是因为没开long long!!!10^9*10^5=10^14
正解如下:
#include<cstring> #include<cstdio> using namespace std; int n,m,t; int q; char s[100001]; int main() { scanf("%d%d%d ",&n,&m,&t); int h=1; long long x=0,y=0; while(1){ char a; a=getchar(); if(a==' ') break; if(a=='U') x--; if(a=='D') x++; if(a=='L') y--; if(a=='R') y++; s[h]=a; h++; } x*=t,y*=t; scanf("%d",&q); for(int i=1;i<=q;i++){ long long sx,sy; scanf("%lld%lld",&sx,&sy); sx+=x; sy+=y; if(sx>n) sx%=n; if(sy>m) sy%=m; if(sx<1) sx=n-(-sx)%n; if(sy<1) sy=m-(-sy)%m; printf("%lld %lld ",sx,sy); } return 0; }
(本题解与DJY_01略有不同,双箭齐发)