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

【noi 2.7_2987】小兔子捡金币（算法效率）

2024-08-17 00:17:02   222人阅读

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

解法：很基础的一道题，先算出询问的点处在第几环，再用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】小兔子捡金币（算法效率）


联系
我们