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 "); 21 else 22 printf("No "); 23 } 24 } 25 }
B题
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 ", ans); 139 } 140 } 141 return 0; 142 }
C题
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,F 题留坑
D题:据说是个排列组合题,然而我对期望值概率方面不懂深入。
F题:状态压缩dp,留坑,不了解。
E题
直接按题意模拟,这里盗用A神代码
1 #include <iostream> 2 #include <fstream> 3 #include <cstring> 4 #include <climits> 5 #include <deque> 6 #include <cmath> 7 #include <queue> 8 #include <stack> 9 #include <list> 10 #include <map> 11 #include <set> 12 #include <utility> 13 #include <sstream> 14 #include <complex> 15 #include <string> 16 #include <vector> 17 #include <cstdlib> 18 #include <cstdio> 19 #include <ctime> 20 #include <bitset> 21 #include <functional> 22 #include <algorithm> 23 24 using namespace std; 25 26 int trH(char str[]) { 27 int val = 0; 28 int len = strlen(str); 29 for (int i = 0; i < len - 1; ++i) { 30 val = val * 16; 31 if (str[i] >= '0' && str[i] <= '9') { 32 val += str[i] - '0'; 33 } 34 else { 35 if (str[i] >= 'a' && str[i] <= 'z') { 36 val += str[i] - 'a' + 10; 37 } 38 else { 39 val += str[i] - 'A' + 10; 40 } 41 } 42 } 43 return val; 44 } 45 46 int trB(char str[]) { 47 int val = 0; 48 int len = strlen(str); 49 for (int i = 0; i < len - 1; ++i) { 50 val = val * 2 + str[i] - '0'; 51 } 52 return val; 53 } 54 55 int trD(char str[]) { 56 int val = 0; 57 int len = strlen(str); 58 for (int i = 0; i < len; ++i) { 59 val = val * 10 + str[i] - '0'; 60 } 61 return val; 62 } 63 64 pair <int, int> reg[4]; 65 66 int main() { 67 int t; 68 scanf("%d", &t); 69 while (t--) { 70 int n; 71 scanf("%d", &n); 72 for (int i = 0; i < 4; ++i) { 73 reg[i].first = reg[i].second = 0; 74 } 75 char op[10], s1[10], s2[10], s[35]; 76 for (int i = 1; i <= n; ++i) { 77 scanf("%s", op); 78 if (!strcmp(op, "MUL")) { 79 scanf("%s", s1); 80 int reg_id = s1[0] - 'A'; 81 char reg_ty = s1[1]; 82 long long v1, v2; 83 if (reg_ty == 'H') { 84 // 8 bit higher reg 85 v1 = reg[0].first; 86 v2 = reg[reg_id].second; 87 } 88 else if (reg_ty == 'L') { 89 // 8bit lower reg 90 v1 = reg[0].first; 91 v2 = reg[reg_id].first; 92 } 93 else { 94 // 16 bit reg 95 v1 = reg[0].second * 256 + reg[0].first; 96 v2 = reg[reg_id].second * 256 + reg[reg_id].first; 97 } 98 long long res = v1 * v2; 99 if (reg_ty == 'X') { 100 reg[0].second = res % 65536 / 256; 101 reg[0].first = res % 65536 % 256; 102 reg[3].second = res / 65536 / 256; 103 reg[3].first = res / 65536 % 256; 104 } 105 else { 106 reg[0].second = res / 256; 107 reg[0].first = res % 256; 108 } 109 } 110 else { 111 scanf("%s", s); 112 int id; 113 int reg1_id, reg1_ty; 114 int len = strlen(s); 115 reg1_id = s[0] - 'A'; 116 reg1_ty = s[1]; 117 int val; 118 if (s[3] >= 'A' && s[3] <= 'Z') { 119 int reg2_id = s[3] - 'A'; 120 char reg2_ty = s[4]; 121 if (reg2_ty == 'H') { 122 val = reg[reg2_id].second; 123 } 124 else if (reg2_ty == 'L') { 125 val = reg[reg2_id].first; 126 } 127 else { 128 val = reg[reg2_id].second * 256 + reg[reg2_id].first; 129 } 130 } 131 else { 132 char tmp[30]; 133 int x = 0; 134 for (int i = 3; i < len; ++i) { 135 tmp[x++] = s[i]; 136 } 137 tmp[x] = '