首页 > 代码库 > 【noi 2.7_2987】小兔子捡金币(算法效率)

【noi 2.7_2987】小兔子捡金币(算法效率)

题意:问蛇形回文的访问次序。

解法:很基础的一道题,先算出询问的点处在第几环,再用4个while一个个走一遍这一圈。P.S.我一直想办法想用不用while(),可是真的一直WA!所以用while()既方便又准确,不要小瞧她。

P.P.S.本蒟蒻刷DP刷累了(不会做~(┬_┬)),便来做这题,可惜耗时也不小......

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 #define N 10010
 7 
 8 int n,x,y,xx,yy;
 9 
10 int mmin(int x,int y) {return x<y?x:y;}
11 int judge() {return (x==xx&&y==yy)?1:0;}
12 
13 int solve()
14 {
15     int c=mmin(mmin(x-1,y-1),mmin(n-x,n-y)),t=0;
16     int e=n-1;
17     for (int q=1;q<=c;q++) t+=4*e,e-=2;
18     xx=c+1,yy=c;
19     while (!judge()&&yy<n-c) yy++,t++;
20     while (!judge()&&xx<n-c) xx++,t++;
21     while (!judge()&&yy>c+1) yy--,t++;
22     while (!judge()&&xx>c+1) xx--,t++;
23     return t;
24 }
25 
26 int main()
27 {
28     int T;
29     scanf("%d%d",&T,&n);
30     while (T--)
31     {
32       scanf("%d%d",&x,&y);
33       printf("%d\n",solve());
34     }
35     return 0

 

【noi 2.7_2987】小兔子捡金币(算法效率)