首页 > 其他 > 详细

省赛选拔赛解题报告

时间：2016-03-06 01:02:39      阅读：197      评论：0      收藏：0      [点我收藏+]

A题

　　给一个数字，看是否能够分成两个偶数a  b，且a  b 都要大于0。

　　很显然对于一个数字 k , 如果k能够被2整除，整除后有两种情况，要么都是偶数，要么都是奇数，对于都是偶数情况已经满足，对于两个奇数情况，总能够将一个奇数减1，一个奇数加1得到两个偶数。这里考虑特例 2 单独排除即可。

 

 1 #include <stdio.h>
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <string.h>
 5 #include <algorithm>
 6 #define INF 0x3f3f3f3f
 7 #define MAXX 100010
 8 #define LL long long
 9 using namespace std;
10  
11 int main()
12 {
13    LL T, a;
14     while(~scanf("%lld", &T))
15     {
16         while(T--)
17         {
18             scanf("%lld", &a);
19              if(a%2==0 && a!=2)
20                 printf("Yes\n");
21              else
22                 printf("No\n");
23         }
24     }
25 }

B题

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

在很多 RPG (Role-playing Games) 游戏中，迷宫往往是非常复杂的游戏环节。通常来说，我们在走迷宫的时候都需要花非常多的时间来尝试不同的路径。但如果有了算法和计算机的帮助，我们能不能有更快的方式来解决这个问题？我们可以进行一些尝试。
现在我们有一个 N 行 M 列的迷宫。迷宫的每个格子如果是空地则可以站人，如果是障碍则不行。在一个格子上，我们可以一步移动到它相邻的 8 个空地上，但不能离开地图的边界或者跨过两个障碍的夹缝。下图是一个移动规则的示例。
 
技术分享
为了离开迷宫，我们还需要触发迷宫中所有的机关。迷宫里总共有 K 个机关，每个机关都落在一个不同的空地上。如果我们到达了某个机关所在的格子时，这个机关就会被自动触发，并在触发之后立即消失。我们的目标是按顺序触发所有的 K个机关，而当最后一个机关被触发时，我们就可以离开迷宫了。
 

 

Input

输入的第一行是测试数据的组数 T (T ≤ 20)。
对于每组测试数据：第一行包含地图的行数 N (2 ≤ N  ≤ 100)，列数 M(2 ≤ M  ≤ 100) 和机关的数量 K(1 ≤ K ≤10)。接下来 N 行，每行包含 M 个字符，其中字符 ‘#’ 表示障碍，而 ‘.’ 表示空地。接下来一行描述了我们的初始位置 (x, y)，表示我们一开始在第 x 行第 y 列的格子上。这个格子保证是个空地。接下来 K 行，每行给出了一个机关的位置。所有的机关都不会出现在障碍上，并且任意两个机关不会出现在同一个空地上。我们需要按输入给定的顺序触发所有的 K 个机关。

 

Output

对于每组测试数据，输出离开迷宫所需要的最少步数。如果无论如何都不能离开迷宫，输出 -1。

 

Sample Input

3
3 3 2
...
...
...
1 1
1 3
2 2
3 3 1
...
.#.
...
1 1
3 3
2 3 1
..#
.#.
1 1
2 3

Sample Output

3
3
-1

 只要注意 ： 1.起始点不能出现在除了第一个机关外的其它机关位置，不然直接无法走出迷宫。

　　　　　　2.只说不能从两个障碍的夹缝中间走过，并没有说不能从一个障碍和一个机关，或两个机关的夹缝中走过。

考虑过这些就可以写BFS了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <string>
  4 #include <vector>
  5 #include <map>
  6 #include <string.h>
  7 #include <queue>
  8 using namespace std;
  9  
 10 #define PP pair<int,int>
 11 #define x first
 12 #define y second
 13 #define mk(a,b) make_pair(a,b)
 14  
 15  
 16 int dx1[] = {-1 , 0 , 0 , 1};
 17 int dy1[] = {0 , -1 , 1 , 0};
 18 int dx2[] = {-1 , -1 , 1 , 1};
 19 int dy2[] = {-1 , 1 , -1 , 1};
 20  
 21 int N , M , K;
 22  
 23 PP aim_set[11];
 24  
 25 int _map[110][110];
 26 int val[110][110];
 27  
 28 void init()
 29 {
 30     memset(_map,0,sizeof(_map));
 31     return ;
 32 }
 33 void init2()
 34 {
 35     memset(val,-1,sizeof(val));
 36     return ;
 37 }
 38 int bfs(int beginx , int beginy , int endx , int endy)
 39 {
 40     queue<PP> QQ;
 41     while(!QQ.empty()) QQ.pop();
 42     QQ.push(mk(beginx,beginy));
 43     val[beginx][beginy] = 0;
 44  
 45   
 46  
 47     while(!QQ.empty())
 48     {
 49         PP temp = QQ.front();
 50         QQ.pop();
 51         int nx = temp.x , ny = temp.y;
 52         if(nx == endx && ny == endy) break;//
 53         bool sign[4]; for(int i = 0 ; i < 4 ; i++) sign[i] = 0;
 54  
 55         for(int i = 0 ; i < 4 ; i++)
 56         {
 57             int kx = nx + dx1[i] , ky = ny + dy1[i];
 58             if(_map[kx][ky] != 0) sign[i] = 1;
 59         }
 60         //////////////////////////////
 61         bool block[4]; for(int i = 0 ; i < 4 ; i++) block[i] = 0;
 62         block[0] = (sign[0] || sign[1]);
 63         block[1] = (sign[0] || sign[2]);
 64         block[2] = (sign[1] || sign[3]);
 65         block[3] = (sign[2] || sign[3]);
 66         //////////////////////////////
 67         for(int i = 0 ; i < 4 ; i++)
 68         {
 69             int kx = nx + dx2[i] , ky = ny + dy2[i];
 70             if(_map[kx][ky] == 1 && val[kx][ky] == -1 && block[i])
 71             {
 72                 val[kx][ky] = val[nx][ny] + 1;
 73                 QQ.push(mk(kx,ky));
 74             }
 75         }
 76         for(int i = 0 ; i < 4 ; i++)
 77         {
 78             int kx = nx + dx1[i] , ky = ny + dy1[i];
 79             if(_map[kx][ky] == 1 && val[kx][ky] == -1)
 80             {
 81                 val[kx][ky] = val[nx][ny] + 1;
 82                 QQ.push(mk(kx,ky));
 83             }
 84         }
 85  
 86     }
 87     return val[endx][endy];
 88 }
 89 int main()
 90 {
 91     int T;
 92     while(~scanf("%d",&T))
 93     {
 94         while(T--)
 95         {
 96             init();
 97             scanf("%d %d %d",&N,&M,&K);
 98             getchar();
 99  
100             for(int i = 1 ; i <= N ; i++)
101             {
102                 for(int j = 1; j <= M ; j++)
103                 {
104                     char temp;
105                     scanf("%c",&temp);
106                     temp == ‘.‘ ? _map[i][j] = 1 : _map[i][j] = 0;
107                 }
108                 getchar();
109             }
110             for(int i = 0 ; i <= K ; i++)
111             {
112                 scanf("%d %d",&aim_set[i].x,&aim_set[i].y);
113                 _map[aim_set[i].x][aim_set[i].y] = -1;
114             }
115             int ans = 0;
116             ////////
117             int bx = aim_set[0].x , by = aim_set[0].y;
118             for(int i = 2 ; i <= K ; i++)
119             {
120                 if(bx == aim_set[i].x && by == aim_set[i].y){ans = -1 ; break;}
121             }
122             if(ans < 0) {cout << ans << endl; continue;}
123             /////////
124             for(int i = 1 ; i <= K ; i++)
125             {
126                 int tx = aim_set[i - 1].x , ty = aim_set[i - 1].y;
127                 int px = aim_set[i].x , py = aim_set[i].y;
128  
129                 _map[tx][ty] = 1;
130                 _map[px][py] = 1;
131  
132                 init2();
133                 int temp = bfs(tx , ty , px , py);
134               
135                 if(temp < 0){ans = -1 ; break;}
136                 else ans += temp;
137             }
138             printf("%d\n", ans);
139         }
140     }
141     return 0;
142 }

C题

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

技术分享

 

Input

技术分享

 

Output

技术分享

 

Sample Input

1
2

Sample Output

Alice

找规律得到似乎判断谁赢只要是否能被 7 整除 ＝ ＝ （好扯淡）
 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5  
 6 int main()
 7 {
 8     int n  ,t;
 9     cin >> t;
10     while(t--)
11     {
12         cin >> n;
13         if(n % 7 == 0)
14             cout << "Bob" << endl;
15         else
16             cout << "Alice" << endl;
17     }   
18     return 0;
19 }

D,E,F 题留坑

D题：据说是个排列组合题，然而我对期望值概率方面不懂深入。

E题：大模拟题，代码量大然而并不难。

F题：状态压缩dp，留坑，不了解。

 

G题

Time Limit: 3 Sec  Memory Limit: 128 MB

Description

技术分享

 

Input

技术分享

 

Output

技术分享

 

Sample Input

1
3 4 4
Q 1 1 1 1
Q 1 1 3 2
M 1 1 3
Q 1 1 3 4

Sample Output

2
21
55

按要求操作矩阵，可以先进行预处理，设置数组sum[i][j] 表示 初始情况下对角线(1,1) 到 (i,j) 所表示的矩形内的和。当修改(x,y)的值时，我们修改sum[x][y] 到 sum[n][m]的值（两层for）即可。任意所给询问Q bx by ex ey 答案为 sum[ex][ey] - sum[bx-1][ey] - sum[ex][by-1] + sum[bx-1][by-1];

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4  
 5 using namespace std;
 6  
 7 int sum[1010][1010];
 8 int a[1010][1010];
 9  
10 void init(int n , int m)
11 {
12     memset(sum,0,(n+10)*(m+10)*sizeof(int));
13     memset(a,0,(n+10)*(m+10)*sizeof(int));
14  
15     for(int i = 1 ; i <= n ; i++)
16     {
17         for(int j = 1 ; j <= m ;j++)
18         {
19             sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + (i+j);
20             a[i][j] = i + j;
21         }
22     }
23     return ;
24 }
25  
26  
27 int Q(int bx , int by , int ex , int ey)
28 {
29     return (sum[ex][ey] - sum[bx-1][ey] - sum[ex][by-1] + sum[bx-1][by-1]);
30 }
31  
32 void M(int x , int y , int val , int n , int m)
33 {
34     for(int i = x ; i <= n ; i++) for(int j = y ; j <= m ; j++)
35     {
36         sum[i][j] += val - a[x][y];
37     }
38     a[x][y] = val;
39     return ;
40 }
41  
42 int main()
43 {
44     int T;
45     while(~scanf("%d",&T))
46     {
47         while(T--)
48         {
49             int n , m , q;
50             scanf("%d %d %d",&n,&m,&q);
51             init(n,m);
52  
53             for(int i = 0 ; i < q ; i++)
54             {
55                 char op[10];
56                 scanf("%s",op);
57                 if(op[0] == ‘Q‘)
58                 {
59                     int a , b , c , d ;
60                     scanf("%d %d %d %d",&a,&b,&c,&d);
61                     printf("%d\n", Q(a,b,c,d));
62                 }
63                 else
64                 {
65                     int a , b , c;
66                     scanf("%d %d %d",&a,&b,&c);
67                     M(a,b,c,n,m);
68                 }
69             }
70         }
71     }
72  
73     return 0;
74  
75 }

H题留坑

I题

Time Limit: 1 Sec  Memory Limit: 128 MB

 

Description

 

技术分享

 

 

Input

 

技术分享

 

 

Output

 

技术分享

 

 

Sample Input

 

2
2 3
111
000
90
3 3
111
101
111
180

 

Sample Output

 

01
01
01
111
101
111

 

 仅仅需要考虑 0 90 180 270 ，找到规律后旋转输出即可，（长变宽 ， 宽变长）。

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5  
 6 char s[60][60];
 7  
 8 int main()
 9 {
10     int n;
11     cin >> n;
12         while(n--)
13         {
14             int a , b;
15             cin >> a >> b;
16             for(int i = 0 ; i < a ; i++)
17             {
18                 for(int j = 0 ; j < b ; j++)
19                 {
20                     cin >> s[i][j];
21                 }
22                 getchar();
23             }               
24             int m;
25             cin >> m;
26             if(m == 0)
27             {
28                 for(int i = 0 ; i < a ; i++)
29                 {
30                     for(int j = 0 ; j < b ; j++)
31                     {
32                         cout << s[i][j];
33                     }
34                     if(i != a - 1)
35                         cout << endl;
36                 }
37             }
38             if(m == 90)
39             {
40                 for(int i = 0 ; i < b ; i++)
41                 {
42                     for(int j = a - 1 ; j >= 0 ; j--)
43                     {
44                         cout << s[j][i]   ;
45                     }
46                     if(i != b - 1)
47                         cout << endl;
48                 }
49             }
50             if(m == 180)
51             {
52                 for(int i = a - 1 ; i  >= 0 ; i--)
53                 {
54                     for(int j = b - 1 ; j >= 0 ; j--)
55                     {
56                         cout << s[i][j];
57                     }
58                     if(i != 0)
59                         cout << endl;
60                 }
61             }
62             if(m == 270)
63             {
64                 for(int i = b - 1 ; i >= 0 ; i--)
65                 {
66                     for(int j = 0 ; j < a ; j++)
67                     {
68                         cout << s[j][i];
69                     }
70                     if(i != 0)
71                         cout << endl;
72                 }
73             }
74                 cout << endl;
75         }
76     return 0;
77 }

J题

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

技术分享

 

Input

技术分享

 

Output

技术分享

 

Sample Input

3
1
10
3
10 5 3
1 2
1 3
5
1 2 3 4 5
3 1
2 1
2 4
2 5

Sample Output

Yes
No
Yes

 最保险的做法应该是写dfs，从1开始，然而这题数据给的并不严格，可以用数组做完。

 1 #include <iostream>
 2 #include <cstdio>
 3  
 4 using namespace std;
 5  
 6 int val[110];
 7 int l[110];
 8 int r[110];
 9  
10 void init()
11 {
12     for(int i = 0 ; i < 110 ; i++)
13     {
14         l[i] = i ; r[i] = i;    val[i] = 0; 
15     }
16     return ;
17 }
18  
19 void link(int fa , int son)
20 {
21     if(l[fa] == fa)
22     {l[fa] = son; return ;}
23     if(r[fa] == fa)
24     {r[fa] = son; return ;}
25  
26     return;
27 }
28  
29 int check_max(int point)
30 {
31     int ans = val[point];
32     if(l[point] != point){ans = max(ans , check_max(l[point]));}
33     if(r[point] != point){ans = max(ans , check_max(r[point]));}
34     return ans;
35 }
36  
37 bool cal(int aim)
38 {
39     int max_num = 0;
40     if(l[aim] != aim){max_num = max(max_num , check_max(l[aim]));}
41     if(r[aim] != aim){max_num = max(max_num , check_max(r[aim]));}
42     //cout << " ==  " << aim << "  ==   " << max_num << endl;
43     if(max_num == 0) return 1;
44     if(val[aim] <= max_num) return 1;
45     return 0;
46 }
47  
48 int main()
49 {
50     int T;
51     while(~scanf("%d",&T)) while(T--)
52     {
53         init();
54         int n;
55         scanf("%d",&n);
56         for(int i = 1 ; i <= n ; i++)
57         {
58             scanf("%d",&val[i]);
59         }
60         for(int i = 0 ; i < n - 1 ; i++)
61         {
62             int a , b;
63             scanf("%d%d",&a,&b);
64             a > b ? link(b,a) : link(a,b);
65         }
66  
67         bool flag = 1;
68  
69         for(int i = 1 ; i <= n ; i++)
70         {
71             flag = cal(i);
72             if(!flag) break;
73         }
74  
75         printf("%s\n", flag ? "Yes" : "No");
76     }
77     return 0;
78 }

 

省赛选拔赛解题报告

原文：http://www.cnblogs.com/ticsmtc/p/5246382.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！