Codeforces Round #491 (Div. 2)部分题解
这场比赛好鬼畜啊,,A题写崩了wa了4遍,心态直接爆炸,本来想弃疗了,结果发现BCD都是傻逼题。。
(容斥原理)
题目大意:
有$N$个人参加了考试,考试完成后在通过的人中,有$A$个人去了第一个酒店聚会,有$B$个人去了第二个酒店聚会,有$C$个人同时去了两个酒店聚会。
问有多少个人没有通过考试(主角没有通过考试)
Sol
小学生容斥,参加了聚会的肯定有$A+B-C$个人,用$N$减去这个数就是不合格的喽
一开始wa了4发心态爆炸然后加了一坨特判A了。。
#include<cstdio> using namespace std; int main() { int A, B, C, N; scanf("%d %d %d %d", &A, &B, &C, &N); int no = N - (A + B - C); if(A >= N || B >= N || C >= N || (C > A) || (C > B)) {printf("-1"); return 0;} if(no <= 0 || no > N) {printf("-1"); return 0;} printf("%d", N - (A + B - C)); return 0; }
(贪心)
题目大意:
Vasya做了$n$门实验,得分为$2-5$之间的数,他想让自己的平均成绩(总得分除以实验次数)四舍五入后为$5$,问最少需要重做几次实验
Sol
直接贪心,肯定是先重新做得分少的,先排序,枚举的时候判断一下是否已经合格就行了
#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 1e5 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int a[MAXN]; int main() { double N = read(), S = 0; int x = N; for(int i = 1; i <= N; i++) a[i] = read(), S += a[i]; sort(a + 1, a + x + 1); if(S / N >= 4.5) {printf("0"); return 0;} for(int i = 1; i <= N; i++) { S -= a[i]; S += 5; if(S / N >= 4.5) { printf("%d", i); return 0; } } return 0; }
(二分)
题目大意:
Vasya有$n$个糖果,在开始的时候 Vasya 选择了一个整数$k$,表示他每天会吃$k$个糖果,Petya想偷吃一部分糖果,他每天会吃当前数量的$10\%$(下去整)的糖果
注意:若Vasya应该吃糖果且不满$k$,Vasya会全吃掉。若Petya吃糖果时数量不满$10$个,则Petya不会吃糖果
输出最小的$k$,使得$Vasya$至少吃掉一半的糖果
Sol
很显然$k$有单调性,直接二分即可
因为$Petya$每次会吃掉$10\%$的糖果,因此吃糖果的过程会很快,直接模拟即可
#include<cstdio> #include<algorithm> #define int long long using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N; bool check(int k) { int cur = 1, Ansa = 0, Ansb = 0, now = N; while(now > 0) { if(cur & 1) Ansa += min(k, now), now -= min(k, now); else Ansb += now / 10, now -= now / 10; cur ^= 1; } return Ansa >= Ansb; } main() { N = read(); int l = 1, r = N, ans = 0; check(3); while(l <= r) { int mid = l + r >> 1; if(check(mid)) r = mid - 1, ans = mid; else l = mid + 1; } printf("%I64d", ans); }
(dp)
题目大意:
Bishwock是一种特殊的棋,它的放置规则如下所示(类似于俄罗斯方块)
给出一个$2*n$的初始局面,问最多能放多少个棋(X代表此处不能放,0代表次数可以放)
Sol
rank1的代码神奇啊,学不来
我只会暴力dp,设$f[i][j]$表示到第$i$行,状态为$j$(一共四种状态)的最大值,$g[i]$表示第$i$行所有状态的最大值(对f[i][1/2/3/4]取max)
转移的时候判断一下可以从哪里转移而来
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAXN = 1001; char s1[MAXN], s2[MAXN]; int f[MAXN][5], g[MAXN]; int getg(int x) { int ans = 0; for(int i = 1; i <= x; i++) ans = max(ans, g[i]); return ans; } int main() { scanf("%s %s", s1 + 1, s2 + 1); int N = strlen(s1 + 1), ans = 0; for(int i = 2; i <= N; i++) { for(int k = 1; k <= 4; k++) f[i][k] = getg(i - 1); if(s1[i] == '0' && s2[i] == '0') { if(s1[i - 1] == '0') { f[i][2] = max(f[i][2], g[i - 2] + 1); if(s2[i - 1] == '0') f[i][2] = max(f[i][2], f[i - 1][1] + 1); } if(s2[i - 1] == '0') { f[i][3] = max(f[i][3], g[i - 2] + 1); if(s1[i - 1] == '0') f[i][3] = max(f[i][3], f[i - 1][4] + 1); } } if(s1[i] == '0') { if(s1[i - 1] == '0' && s2[i - 1] == '0') f[i][4] = max(f[i][4], g[i - 2] + 1); } if(s2[i] == '0') { if(s1[i - 1] == '0' && s2[i - 1] == '0') f[i][1] = max(f[i][1], g[i - 2] + 1); } for(int k = 1; k <= 4; k++) g[i] = max(f[i][k], g[i]); ans = max(ans, g[i]); } printf("%d", ans); return 0; }
总结
战况惨烈。
上一篇: python之初识函数
下一篇: 软件License许可设计思路
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion
-
Codeforces Round #487 (Div. 2)
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #649 (Div. 2) C-Ehab and Prefix MEXs
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Codeforces Round #659 (Div. 2) A. Common Prefixes(字符串,思维)
-
Codeforces Round #610 (Div. 2)
-
Codeforces Round #670 (Div. 2)
-
Codeforces Round #665 (Div. 2)