第六周周赛题解

 1 #include
 2 int n;
 3 bool vis[100010];
 4 int main()
 5 {
 6     scanf("%d",&n);
 7     int x;
 8     int now=n;
 9     for(int i=1;i<=n;++i)
10       {
11           scanf("%d",&x);
12           vis[x]=1;
13           if(vis[now])
14             {
15                 printf("%d",now);
16                 --now;
17                 while(vis[now])
18                   {
19                     printf(" %d",now);
20                     --now;
21                   }
22             }
23           printf("\n");
24       }
25     return 0;
26 }

 1 #include
 2 #include
 3 using namespace std;
 4 int n, ai;
 5 int main()
 6 {
 7     scanf("%d", &n);
 8     int maxi = 0;
 9     int sum = 0;
10     for (int i = 0; i )
11     {
12         scanf("%d", &ai);
13         sum += ai;
14         maxi = max(maxi, ai);
15     }
16     int res = maxi * n - sum;
17     printf("%d", res);
18     return 0;
19 }

 1 #include 
 2 #include 
 3 #include<string.h>
 4 using namespace std;
 5 
 6 const int MAX_N = 27;
 7 
 8 const int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
 9 const int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
10 bool visited[MAX_N][MAX_N];
11 struct Step{
12     char x, y;
13 } path[MAX_N];
14 bool success;           //是否成功遍历的标记
15 int cases, p, q;
16 
17 void DFS(int x, int y, int num);
18 
19 int main()
20 {
21     scanf("%d", &cases);
22     for (int c = 1; c <= cases; c++)
23     {
24         success = false;
25         scanf("%d%d", &p, &q);
26         memset(visited, false, sizeof(visited));
27         visited[1][1] = true;    //起点
28         DFS(1, 1, 1);
29         printf("Scenario #%d:\n", c);
30         if (success)
31         {
32             for (int i = 1; i <= p * q; i++)
33                 printf("%c%c", path[i].y, path[i].x);
34             printf("\n");
35         }
36         else
37             printf("impossible\n");
38         if (c != cases)
39             printf("\n");      //注意该题的换行
40     }
41     return 0;
42 }
43 
44 void DFS(int x, int y, int num)
45 {
46     path[num].y = y + 'A' - 1;   //int 转为 char
47     path[num].x = x + '0';
48     if (num == p * q)
49     {
50         success = true;
51         return;
52     }
53     for (int i = 0; i <8; i++)
54     {
55         int nx = x + dx[i];
56         int ny = y + dy[i];
57         if (0 0  q
58             && !visited[nx][ny] && !success)
59         {
60             visited[nx][ny] = true;
61             DFS(nx, ny, num+1);
62             visited[nx][ny] = false;    //撤销该步
63         }
64     }
65 }

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 using namespace std;
 7 const double INF = 1e20;
 8 const int N = 100005;
 9 
10 struct Point
11 {
12     double x;
13     double y;
14 }point[N];
15 int n;
16 int tmpt[N];
17 
18 bool cmpxy(const Point& a, const Point& b)
19 {
20     if(a.x != b.x)
21         return a.x < b.x;
22     return a.y < b.y;
23 }
24 
25 bool cmpy(const int& a, const int& b)
26 {
27     return point[a].y < point[b].y;
28 }
29 
30 double min(double a, double b)
31 {
32     return a  a : b;
33 }
34 
35 double dis(int i, int j)
36 {
37     return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)
38                 + (point[i].y-point[j].y)*(point[i].y-point[j].y));
39 }
40 
41 double Closest_Pair(int left, int right)
42 {
43     double d = INF;
44     if(left==right)
45         return d;
46     if(left + 1 == right)
47         return dis(left, right);
48     int mid = (left+right)>>1;
49     double d1 = Closest_Pair(left,mid);
50     double d2 = Closest_Pair(mid+1,right);
51     d = min(d1,d2);
52     int i,j,k=0;
53     //分离出宽度为d的区间
54     for(i = left; i <= right; i++)
55     {
56         if(fabs(point[mid].x-point[i].x) <= d)
57             tmpt[k++] = i;
58     }
59     sort(tmpt,tmpt+k,cmpy);
60     //线性扫描
61     for(i = 0; i )
62     {
63         for(j = i+1; j )
64         {
65             double d3 = dis(tmpt[i],tmpt[j]);
66             if(d > d3)
67                 d = d3;
68         }
69     }
70     return d;
71 }
72 
73 
74 int main()
75 {
76     while(~scanf("%d",&n))
77     {   for(int i = 0; i )
78             scanf("%lf %lf",&point[i].x,&point[i].y);
79         sort(point,point+n,cmpxy);
80         printf("%lf\n",Closest_Pair(0,n-1));
81     }
82     return 0;
83 }