这场比赛好鬼畜啊,,A题写崩了wa了4遍,心态直接爆炸,本来想弃疗了,结果发现BCD都是傻逼题。。
A. If at first you don't succeed...(容斥原理)
题目大意:
有$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 ;}
if(no <= || no > N) {printf("-1"); return ;}
printf("%d", N - (A + B - C));
return ;
}
B. Getting an A(贪心)
题目大意:
Vasya做了$n$门实验,得分为$2-5$之间的数,他想让自己的平均成绩(总得分除以实验次数)四舍五入后为$5$,问最少需要重做几次实验
Sol
直接贪心,肯定是先重新做得分少的,先排序,枚举的时候判断一下是否已经合格就行了
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + ;
inline int read() {
char c = getchar(); int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int a[MAXN];
int main() {
double N = read(), S = ;
int x = N;
for(int i = ; i <= N; i++) a[i] = read(), S += a[i];
sort(a + , a + x + );
if(S / N >= 4.5) {printf(""); return ;}
for(int i = ; i <= N; i++) {
S -= a[i]; S += ;
if(S / N >= 4.5) {
printf("%d", i); return ;
}
}
return ;
}
C. Candies(二分)
题目大意:
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 = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int N;
bool check(int k) {
int cur = , Ansa = , Ansb = , now = N;
while(now > ) {
if(cur & ) Ansa += min(k, now), now -= min(k, now);
else Ansb += now / , now -= now / ;
cur ^= ;
}
return Ansa >= Ansb;
}
main() {
N = read();
int l = , r = N, ans = ;
check();
while(l <= r) {
int mid = l + r >> ;
if(check(mid)) r = mid - , ans = mid;
else l = mid + ;
}
printf("%I64d", ans);
}
D. Bishwock(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 = ;
char s1[MAXN], s2[MAXN];
int f[MAXN][], g[MAXN];
int getg(int x) {
int ans = ;
for(int i = ; i <= x; i++)
ans = max(ans, g[i]);
return ans;
}
int main() {
scanf("%s %s", s1 + , s2 + );
int N = strlen(s1 + ), ans = ;
for(int i = ; i <= N; i++) {
for(int k = ; k <= ; k++)
f[i][k] = getg(i - );
if(s1[i] == '' && s2[i] == '') {
if(s1[i - ] == '') {
f[i][] = max(f[i][], g[i - ] + );
if(s2[i - ] == '')
f[i][] = max(f[i][], f[i - ][] + );
}
if(s2[i - ] == '') {
f[i][] = max(f[i][], g[i - ] + );
if(s1[i - ] == '')
f[i][] = max(f[i][], f[i - ][] + );
}
}
if(s1[i] == '') {
if(s1[i - ] == '' && s2[i - ] == '')
f[i][] = max(f[i][], g[i - ] + );
}
if(s2[i] == '') {
if(s1[i - ] == '' && s2[i - ] == '')
f[i][] = max(f[i][], g[i - ] + );
}
for(int k = ; k <= ; k++)
g[i] = max(f[i][k], g[i]);
ans = max(ans, g[i]);
}
printf("%d", ans);
return ;
}
总结
战况惨烈。