牛客小白月赛52_题解
A题：
输入后直接判断即可，输入可以用 
函数简化。
注意
可以取 9。
注意
B题：
对于每一个数字从左往右进行进位即可，这里用 除模运算 来判断进位和抹去低位的数字。
如果采用数组模拟的方式将会带来很多边界问题！
如果采用数组模拟的方式将会带来很多边界问题！
C题：
我们将图画下来，把指令 2 与指令 3 都转化为指令 1 的形式，这样就可以发现本题其实就是区间覆盖问题，不过覆盖的是给定区间外的所有点而已。
这样我们可以直接利用差分前缀和的思想将这些补集区间都 +1 ，然后前缀和统计即可。
我们将图画下来，把指令 2 与指令 3 都转化为指令 1 的形式，这样就可以发现本题其实就是区间覆盖问题，不过覆盖的是给定区间外的所有点而已。
这样我们可以直接利用差分前缀和的思想将这些补集区间都 +1 ，然后前缀和统计即可。
D题：
我们可以尝试枚举奶油量最大的蛋糕的奶油量，那么环就会被断开成若干段弧，若这些弧中有某一条弧的饱腹值和大于 s 那么就说明这样的划分是正确的。
而这个“最大奶油量”显然是满足二分性质的，所以直接二分后 check 就好了。
我们可以尝试枚举奶油量最大的蛋糕的奶油量，那么环就会被断开成若干段弧，若这些弧中有某一条弧的饱腹值和大于 s 那么就说明这样的划分是正确的。
而这个“最大奶油量”显然是满足二分性质的，所以直接二分后 check 就好了。
时间复杂度：)
。
注：如果利用尺取的技巧加上单调队列本题可以做到线性解决。
注：如果利用尺取的技巧加上单调队列本题可以做到线性解决。
E题：
查找可以使用二分，枚举每一个数查贡献即可。但若分别对每一个组进行二分必然会超时。
考虑容斥，对每一个数我们可以二分所有匹配的数的个数，然后再将这里的数减去自己组中和自己匹配的数的个数即可。
时间复杂度：%20*log(%5Csum_%7Bi%3D1%7D%5E%7Bi%3Dn%7D%20s_i)%20))
。
考虑容斥，对每一个数我们可以二分所有匹配的数的个数，然后再将这里的数减去自己组中和自己匹配的数的个数即可。
时间复杂度：
注：本题也可以使用树状数组的方式来解决，时间复杂度同上。
F题：
注意到两种方案不同是因为有骑士消耗的能量不同，所以我们从骑士可以消耗的能量入手，对于每种可以被消耗的能量我们应该贪心的选择造成伤害最大的方案（可以理解为为后面的骑士获取更多的选取空间（决策包容性））。这一步可以用普通背包模型来解决。
考虑计算方案数。经过上述转换，问题转换成了每个骑士只能选取某个技能（消耗能量 + 最大伤害）然后击败魔王的方案数了。这一步我们可以通过分组背包模型来解决。
至于总的时间复杂度，在标程中已经标明，细节很多这里不再赘述。
考虑计算方案数。经过上述转换，问题转换成了每个骑士只能选取某个技能（消耗能量 + 最大伤害）然后击败魔王的方案数了。这一步我们可以通过分组背包模型来解决。
至于总的时间复杂度，在标程中已经标明，细节很多这里不再赘述。
参考代码：
A题：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
void solved() {
cin >> n;
int a, b;
int sa = 0, sb = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d:%d", &a, &b);
if(a >= 8) {
if(a == 9 || b > 5) sb ++;
if(b > 0 && b <= 5 && a != 9) sa ++;
}
}
cout << sa << ' ' << sb << endl;
}
int main() {
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
} #include <bits/stdc++.h>
using namespace std;
int n;
int main() {
int ttx; cin >> ttx;
while(ttx --) {
cin >> n;
for(int i = 1, j = 10; i <= 6; i ++, j *= 10) {
if(n % j / (j / 10) >= 5) {
n += j;
n = n / j * j;
}
}
cout << n << endl;
}
return 0;
} C题：
#include <bits/stdc++.h>
using namespace std;
const int N = 1000009;
int n, m;
int a[N];
void solved() {
cin >> n >> m;
int op, x, y;
for(int i = 0; i < m; i ++) {
x = 1, y = n;
scanf("%d", &op);
if(op == 1) scanf("%d%d", &x, &y);
else if (op == 2) scanf("%d", &x);
else scanf("%d", &y);
a[x] --; a[y + 1] ++;
}
int mx = -m;
for(int i = 1; i <= n; i ++) {
a[i] += a[i - 1];
mx = max(mx, a[i]);
}
int sum = 0;
for(int i = 1; i <= n; i ++) if(a[i] == mx) sum ++;
cout << m + mx << ' ' << sum;
}
int main() {
solved();
return 0;
} D题：
二分解法
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
int a[200009], b[200009];
bool check(int x) {
ll sum = 0;
for(int i = 0; i < n; i ++) {
if(b[i] > x) {
if(sum >= m) return true;
sum = 0;
} else sum += a[i];
}
if(sum >= m) return true;
for(int i = 0; i < n; i ++) {
if(b[i] > x) {
if(sum >= m) return true;
break;
} else sum += a[i];
}
return false;
}
void solved() {
cin >> n >> m;
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 0; i < n; i ++) cin >> b[i];
ll sum = 0;
for(int i = 0; i < n; i ++)
sum += a[i];
if(sum < m) {
cout << -1;
return ;
}
int l = 1, r = 1000000000;
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
}
int main() {
// int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
} 单调队列解法（感谢 @沙烬 提供的代码！） #include<iostream>
#include<queue>
#include<vector>
using i64 = long long ;
int main(){
int n, m;
std :: cin >> n >> m;
std :: vector<i64> a(n*2),b(n*2);
for(int i = 0; i < n ; i ++ ){
std :: cin >> a[i];
a[i + n] = a[i];
}
for(int i = 0; i < n ; i ++ ){
std :: cin >> b[i];
b[i + n] = b[i];
}
i64 sum = 0, ans = INT_FAST64_MAX;
for(int i = 0 ; i < n ; i ++){
sum += a[i];
}
if(sum < m){
std :: cout << -1 << std :: endl;
return 0;
}
sum = 0;
std :: deque<i64> qe;
for(int i = 0,j = 0 ; j < 2 * n ; j ++){
sum += a[j];
while(sum - a[i] >= m){
sum -= a[i ++];
}
while(qe.size() && qe.front() < i){
qe.pop_front();
}
while(qe.size() && b[j] >= b[qe.back()]){
qe.pop_back();
}
qe.push_back(j);
if(sum >= m){
ans = std :: min(ans,b[qe.front()]);
}
}
std :: cout << ans << std :: endl;
} E题：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, k;
vector<int> ve[1000009], a;
void solved() {
scanf("%d%d", &n, &k);
int m;
for(int i = 0; i < n; i ++) {
scanf("%d", &m);
int x;
while(m --) {
scanf("%d", &x);
ve[i].push_back(x);
a.push_back(x);
}
sort(ve[i].begin(), ve[i].end());
}
sort(a.begin(), a.end());
ll ans = 0;
for(int i = 0; i < n; i ++) {
m = ve[i].size();
for(int j = 0; j < m; j ++) {
int x = ve[i][j], y = k - x;
ans +=
(a.end() - upper_bound(a.begin(), a.end(), y - 1)) -
(ve[i].end() - upper_bound(ve[i].begin(), ve[i].end(), y - 1));
}
}
ans /= 2;
cout << ans % 998244353;
}
int main() {
// int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
} #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
int n, m;
int fans[3009][3009], ff[3009];
int a[3009], b[3009];
void solved() {
cin >> n >> m;
fans[0][0] = 1;
int s;
for(int ttf = 1; ttf <= n; ttf ++) {
cin >> s;
for(int i = 0; i < s; i ++) cin >> a[i];
for(int i = 0; i < s; i ++) cin >> b[i];
for(int i = 0; i <= 3000; i ++) ff[i] = 0; /// 初始化 dp 数组
for(int i = 0; i < s; i ++) { /// 求出当前骑士花费的每种能量消耗可以造成的最大攻击力
for(int j = 3000; j >= b[i]; j --) {
if(ff[j - b[i]] || j - b[i] == 0)
ff[j] = max(ff[j - b[i]] + a[i], ff[j]);
}
} /// n个骑士总时间复杂度： sum(s) * 3000
for(int i = 0; i <= 3000; i ++) {
if(ff[i] == 0 && i != 0) continue; /// 有些值无法被表示,能被表示的值的量级为 sum(b)
if(ff[i] > m) ff[i] = m; /// 攻击力溢出处理
for(int j = 0; j < ff[i]; j ++) /// 这里是攻击力溢出部分的方案数，需要单独计算
fans[ttf][m] = (fans[ttf][m] + fans[ttf - 1][m - j]) % mod;
for(int j = m; j >= ff[i]; j --) /// 这个 for 和上面一个 for 的总时间复杂度均为： sum(b) * m
fans[ttf][j] = (fans[ttf][j] + fans[ttf - 1][j - ff[i]]) % mod;
} /// n个骑士这里的总时间复杂度： n * 3000
} /// 总时间复杂度： sum(s) * 3000 + n * 3000 + sum(b) * m
cout << fans[n][m];
}
int main() {
// int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
} 最后，本人为不规范的题面和题目中的部分歧义道歉……
安克创新 Anker公司福利 782人发布
