5/5
懒啊懒啊~~屯了一堆题没补，GG……
最近要期末考试，博客也搁置很久没有更新了，虽然更新也没人看，但是还是要定期写点东西。
水了一场CF，最大的感想是CF红名果然很难，但是坚持打更重要，所以不要以实力不够为借口，每次还是爆一下肝肛一下CF，万一红名了呢？
在这里我决定每次新的一场CF出来之前，都把题目补好，然后迎接新的CF，最近真的没时间刷题orz，这么蒟蒻还不刷题QAQ
题A Bear and Five Cards
题意：只允许移动两个或者三个相同的t，然后问你剩下最小的和是多少？
题解：水题。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 int t[110]; 15 16 int main() { 17 // freopen("case.in", "r", stdin); 18 int res = 0; 19 for (int i = 0; i < 5; i++) { 20 int x; 21 scanf("%d", &x); 22 t[x]++; 23 res += x; 24 } 25 int tmp = res; 26 for (int i = 0; i <= 100; i++) if (t[i] >= 2) { 27 // cout << i << ' ' << t[i] << endl; 28 res = min(res, tmp - i * min(3, t[i])); 29 } 30 cout << res << endl; 31 return 0; 32 } 代码君
题B Bear and Finding Criminals
题意：给你一串序列，1代表有罪犯，0代表没有，然后给你一个城市a，问你a有多少个距离它的两边的罪犯是确定有的，也就是两边都是1的个数，问你最多能抓多少个罪犯？
题解：简易地说就是统计两边有多少个都是1，然后如果有一边没有就直接统计1的个数。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 110; 15 int ok[maxn]; 16 17 int main() { 18 // freopen("case.in", "r", stdin); 19 int n, a; 20 cin >> n >> a; 21 for (int i = 1; i <= n; i++) { 22 cin >> ok[i]; 23 } 24 int len = min(a - 1, n - a), res = 0; 25 for (int i = 0; i <= len; i++) { 26 if (ok[a + i] & ok[a - i]) { 27 res += (i == 0 ? 1 : 2); 28 } 29 } 30 for (int i = 1; i <= n; i++) if (abs(i - a) > len && ok[i]) { 31 res++; 32 } 33 cout << res << endl; 34 return 0; 35 } 代码君
题C Bear and Prime 100
题意：这是一道人机互动的题目，给你最多20个提问的机会，然后你问一个数是不是要猜的数的因子，然后读取输入是或者不是，然后提问完之后告诉它这个数是不是素数？
题解：对于2~50的素数，如果都没有，显然是素数，因为后面的素数不可能有其他因子，因为这样会超过100，如果有两个，那么显然不是素数，如果只有一个，还要提问一次，因为不确定是p还是p ^ k，所以只要询问有没有是不是p ^ 2作为因子即可。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 110; 15 int ok[maxn], prime[maxn]; 16 17 int main() { 18 // freopen("case.in", "r", stdin); 19 20 for (int i = 2; i <= 100; i++) if (!ok[i]) 21 for (int j = i + i; j <= 100; j += i) ok[j] = 1; 22 23 int yes = 0, p; 24 25 for (int i = 2; i <= 50; i++) if (!ok[i]) { 26 printf("%d\n", i); 27 fflush(stdout); 28 char s[100]; 29 scanf("%s", s); 30 if (strcmp(s, "yes") == 0) { yes++; p = i; } 31 if (yes >= 2) break; 32 } 33 34 int flag = 0; 35 if (yes >= 2) flag = 1; 36 else if (yes == 1 && p * p <= 100) { 37 printf("%d\n", p * p); 38 fflush(stdout); 39 char s[100]; 40 scanf("%s", s); 41 if (strcmp(s, "yes") == 0) flag = 1; 42 } 43 44 flag ? puts("composite") : puts("prime"); 45 fflush(stdout); 46 47 return 0; 48 } 代码君
题D Bear and Tower of Cubes
题意：给你一个数m，然后求一个数x在[0,m]中，然后定义一个计算方式：贪心取最接近的立方数，减去，在贪心取，直到为0。然后这个计算得出的结果要最大，问你满足这个计算得到最大的结果同时x要最大是多少？
题解：蒟蒻不会构造，所以参照了官方题解。
题解表示假设x最近的一个立方数是a，那么x肯定要么是由a或者a - 1来的，如果是有a来的，那么剩余就是m - a^3；如果是由a-1来的，那么肯定不能是m，只能是a^3-1，所以剩余就是a^3-1-(a-1)^3，然后就这样递归下去，据说最多的一层是18，所以放心递归。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 pair<int,ll> res; 7 8 ll my_pow(ll x) { 9 return x * x * x; 10 } 11 12 void dfs(ll cur, int step, ll from) { 13 if (cur == 0) { 14 res = max(res, make_pair(step, from)); 15 return; 16 } 17 ll x = 1; 18 while (my_pow(x + 1) <= cur) ++x; 19 dfs(cur - my_pow(x), step + 1, from + my_pow(x)); 20 if (x - 1 >= 0) 21 dfs(my_pow(x) - my_pow(x - 1) - 1, step + 1, from + my_pow(x - 1)); 22 } 23 24 int main() { 25 // freopen("case.in", "r", stdin); 26 ll n; 27 cin >> n; 28 dfs(n, 0, 0); 29 cout << res.first << ' ' << res.second << endl; 30 } 代码君
题E Bear and Square Grid
题意：给你个n * n的迷宫，x表示障碍，。表示不是障碍，然后就可以割出一个k*k的空间使得这个空间的点都变成不是障碍，问你最大的连通的不是障碍的个数是多少？
题解：如果暴力显然是n^4，n^2枚举这个空间肯定是要的，现在要做的是怎样O（n）地求出当前多出来的连通块的个数，我们实际上只要维护边界的即可。也就是说先固定一个k*k的空间，然后当前答案是k*k，然后把空间内的每个格子所在的连通块的size都减一，然后对于边界我们就求一下连通块的个数即可，注意要标记一下，计算过的不要重复计算，学习一下CF上大神的代码。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 510, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; 6 char maze[maxn][maxn]; 7 int n, k; 8 int id[maxn][maxn], size[maxn * maxn], cur[maxn * maxn]; 9 10 bool inside(int x, int y) { 11 return x >= 0 && x < n && y >= 0 && y < n; 12 } 13 14 void dfs(int x, int y, int num) { 15 id[x][y] = num; 16 size[num]++; 17 for (int i = 0; i < 4; i++) { 18 int xx = x + dx[i], yy = y + dy[i]; 19 if (inside(xx, yy) && maze[xx][yy] == '.' && id[xx][yy] == 0) 20 dfs(xx, yy, num); 21 } 22 } 23 24 void add(int x, int y, int& now, int current) { 25 if (inside(x,y) && maze[x][y] == '.') { 26 int i = id[x][y]; 27 if (cur[i] != current) { 28 cur[i] = current; 29 now += size[i]; 30 } 31 } 32 } 33 34 int main() { 35 // freopen("case.in", "r", stdin); 36 cin >> n >> k; 37 for (int i = 0; i < n; i++) { 38 scanf("%s", maze[i]); 39 } 40 int cnt = 0; 41 for (int i = 0; i < n; i++) 42 for (int j = 0; j < n; j++) 43 if (maze[i][j] == '.' && id[i][j] == 0) dfs(i, j, ++cnt); 44 45 int best = 0, current = 0; 46 for (int nowx = 0; nowx + k <= n; nowx++) { 47 for (int x = nowx; x < nowx + k; x++) for (int y = 0; y < k; y++) --size[id[x][y]]; 48 for (int nowy = 0; nowy + k <= n; nowy++) { 49 int now = k * k; 50 current++; 51 for (int x = nowx; x < nowx + k; x++) { 52 add(x, nowy - 1, now, current); 53 add(x, nowy + k, now, current); 54 } 55 for (int y = nowy; y < nowy + k; y++) { 56 add(nowx - 1, y, now, current); 57 add(nowx + k, y, now, current); 58 } 59 best = max(best, now); 60 if (nowy + k != n) { 61 for (int x = nowx; x < nowx + k; x++) { 62 ++size[id[x][nowy]]; 63 --size[id[x][nowy + k]]; 64 } 65 } 66 } 67 for (int x = nowx; x < nowx + k; x++) for (int y = n - k; y < n; y++) ++size[id[x][y]]; 68 } 69 cout << best << endl; 70 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5589220.html
