【题解】牛客OI月赛12-普及组
前言
qwq由于题目出现了一些洼点,导致了一些阅读理解上的差错,先说声对不起qwq
语文学的不好,我以后一定好好学
A 被鸽了的课本
只需要判断 和
的大小就好了
考点:无
B 被鸽了的美男老师K
我们模拟一下这个过程,对被埋了的人打标记,然后统计一下相同点的人有多少个,把他们的方向转一下,循环次就行了效率
考点:模拟
坑点:同一个位置可能有两个人,而此时两个人向后转和对穿而过是没有区别的,但是如果是3个人就有区别了。
C 被鸽了的应急理智顶液
我们考虑按位拆分,然后从最高位往下贪心即可,显然一位最多被修改一次。
然后从最高位往下贪心,当前第位增加
可以相当于下一位
增加
。
所以要优先使得高的取满
具体的说: 我们优先使得该位的or = 1, 然后再使得xor = 1。
效率
考点:贪心
坑点: 发现, 因此要开unsigned long long
D 被鸽了的文件清除
考虑表示到i为止,用了j次手动删除,最后一次用的什么删除
考虑转移
空间有点卡考虑滚动数组优化一下
考点:dp
坑点: 要说的话就是要开long long吧
各题代码
A
#include<bits/stdc++.h> using namespace std; #define ll long long inline ll read() { ll x = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch>'9'; ch = getchar()) if(ch == '-') f = -f; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return x * f; } inline void chkmin( int &a, int b ) { if(a > b) a = b; } inline void chkmax( int &a, int b ) { if(a < b) a = b; } #define _ read() #define ln endl int main() { int a = _, b = _, c = _; double a1 = a + b * 0.5; double a2 = (a + b) * (100 - c) * 0.01; if(a1 >= a2) puts("By myself"); else puts("Through school"); }
B
#include<bits/stdc++.h> using namespace std; #define ll long long inline ll read() { ll x = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch>'9'; ch = getchar()) if(ch == '-') f = -f; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return x * f; } inline void chkmin( int &a, int b ) { if(a > b) a = b; } inline void chkmax( int &a, int b ) { if(a < b) a = b; } #define _ read() #define ln endl const int N = 1e3 + 5; int n, t, x[N], b[N], vis[N]; int cnt[N << 1]; int main() { n = _; t = _; for( int i = 0; ++i <= n; ) x[i] = _, b[i] = _, vis[i] = 0; for( int i = 1; i <= t; i++ ) { for( int j = 1; j <= n; j++ ) x[j] = x[j] + (b[j] == 0 ? -1 : 1); for( int j = 1; j <= n; j++ ) if(!vis[j]) cnt[x[j]] = 0; for( int j = 1; j <= n; j++ ) if(!vis[j]) cnt[x[j]]++; for( int j = 1; j <= n; j++ ) if(!vis[j] && cnt[x[j]] > 1) b[j] ^= 1; //掉转方向 for( int j = 1; j <= n; j++ ) if(x[j] <= i) vis[j] = 1; } int tmp = 0; for( int i = 0; ++i <= n; ) tmp += vis[i]; cout << tmp << ln; }
C
#include<bits/stdc++.h> using namespace std; #define ll long long inline ll read() { ll x = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch>'9'; ch = getchar()) if(ch == '-') f = -f; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return x * f; } inline void chkmin( int &a, int b ) { if(a > b) a = b; } inline void chkmax( int &a, int b ) { if(a < b) a = b; } #define _ read() #define ln endl int n, k; int cnt[64], s[64]; unsigned long long ans; int main() { n = _; k = _; for( int i = 0; ++i <= n; ) { ll x = _; int flag = 0; for( int j = 62; j >= 0; j-- ) { int tmp = ((1ll << j) & x)?1:0; flag |= tmp; cnt[j] += tmp; if(flag) s[j]++; } } for( int i = 62; i >= 0; i-- ) { if(s[i] == 0) continue; // cout << i << ln; if(cnt[i]) ans += (1llu << i); else if(k) --k, cnt[i] = 1, ans += (1llu << i); if(cnt[i] & 1) ans += (1llu << i); else if(k) { --k; ans += (1llu << i); } } cout << ans << ln; }
D
#include<bits/stdc++.h> using namespace std; #define ll long long inline ll read() { ll x = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch>'9'; ch = getchar()) if(ch == '-') f = -f; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return x * f; } inline void chkmin( int &a, int b ) { if(a > b) a = b; } inline void chkmax( int &a, int b ) { if(a < b) a = b; } #define _ read() #define ln endl const int N = 1e5 + 5; int n, k, a[N], b[N]; ll dp[2][1005][2]; int main() { n = _; k = _; for( int i = 0; ++i <= n; ) a[i] = _, b[i] = _; dp[1][0][0] = b[1]; for( int i = 1; ++i <= n; ) { dp[i & 1][0][0] = dp[(i - 1) & 1][0][0] + b[i]; for( int j = 1; j <= k; j++ ) { dp[i & 1][j][0] = max(dp[(i - 1) & 1][j][0], dp[(i - 1) & 1][j][1]) + b[i]; dp[i & 1][j][1] = dp[(i - 1) & 1][j - 1][0] + a[i]; } } ll tmp = 0; for( int i = 0; i <= k; i++ ) tmp = max( tmp, dp[n&1][i][0]), tmp = max( tmp, dp[n&1][i][1]); cout << tmp << ln; }
吐槽环节
- 为啥作为签到之一的B通过的最少啊qwq
- 为啥这个出题人语文这么菜啊, 下一场我来出!(复读机, on)
最后的最后
明日方舟官服求加好友~(逃)