26寒假营第五场 区间覆盖贪心|合并果子|子段和取模|贪心+dp|不变量|二阶差分
智乃的二进制
https://ac.nowcoder.com/acm/contest/120565/A
B
模拟 相邻的反转 注意反斜杠需要转义
int a[200][200];
void solve() {
int n, m;
cin >> n >> m;
rep(i, 1, n) {
rep(j, 1, m) {
if (j == 1) {
if (i == 1) {
a[i][j] = 1;
} else {
a[i][j] = a[i - 1][j] ^ 1;
}
} else {
a[i][j] = a[i][j - 1] ^ 1;
}
}
}
rep(i, 1, n) {
rep(j, 1, m) {
if (a[i][j]) {
cout << '/';
} else {
cout << '\\';
}
}
cout << '\n';
}
}
C
计算几何 实数二分 区间覆盖贪心
注意到所有点都在x轴上，所以点，只有以他为圆心的圆，能覆盖一部分y=r的点时才有意义，更具体来说，一个点可能能覆盖这一段的点，形成一个区间。这个区间的半径
，可以根据圆的半径和
用勾股定理计算出来。
由于时间越多，圆的半径越大，每个点对应的区间越长，我们的目标是选不超过
个区间覆盖整个
，这显然有单调性，考虑二分时间。接下来就是一个贪心，选择最少的区间，覆盖整个
这个贪心类似跳跃游戏，选中一个区间可以看作从
出发，走一步可以到
内的所有点，然后下一步可以借助
内任意点作为起点，问走到
的最小步数。这其实也类似于寒假营第一场的那个
题
思路就是从开始走，走完一个前缀
，维护这个前缀内的点为起点，能到的最远点
，以及当前选中的最后一个区间的右端点
，如果走完了当前选的最后一个区间，则需要再选一个区间，贪心的来讲，应该选目前访问过左端点的区间里，右端点最远的那个区间，于是
void solve() {
int n, k, r, c;
cin >> n >> k >> r >> c;
vi p(n + 1), v(n + 1);
rep(i, 1, n) {
cin >> p[i] >> v[i];
}
db lo = 0, hi = 1e7;
auto check = [&](db mi)->bool{
vi bin(c + 1);
rep(i, 1, n) {
db R = mi * v[i];
int d = sqrt(R * R - r * r);
int l = max(0ll, p[i] - d);
int r = p[i] + d;
bin[l] = max(bin[l], r);
}
int mx = 0, cnt = 0, lim = 0;
rep(i, 0, c - 1) {
mx = max(mx, bin[i]);
if (i == lim) {
cnt++;
lim = mx;
}
}
return lim >= c && cnt <= k;
};
while (hi - lo > eps) {
db mi = (lo + hi) / 2;
if (check(mi))hi = mi;
else lo = mi;
}
cout << fixed << setprecision(10);
cout << lo;
}
D
贪心 map模拟
合并果子的基础上，改成每种重量的果子有个。整体思想还是每次合并最小的两个，但是为了保证复杂度需要每次把重量最小的两类果子都拿出来，一块合并。
由于这两堆果子个数可能不相等，需要分类讨论，可能剩下一类果子还有一些没用到，还要插入回去。以及如果重量最小的果子不止一个，肯定时这一类果子内部合并更优。
需要维护每个重量的果子的个数，每次查询重量最小的果子，这可以set或者map。
void solve() {
int n;
cin >> n;
map<int, int>s;
rep(i, 1, n) {
int c, w;
cin >> c >> w;
s[w] += c;
}
int ans = 0;
while (s.size() > 1 || s.begin()->se > 1) {
auto [w1, c1] = *s.begin();
s.erase(s.begin());
if (c1 > 1) {
s[2 * w1] += c1 / 2;
if (c1 % 2) {
s[w1] = 1;
}
ans += ((c1 / 2 * 2) % M1 * (w1 % M1)) % M1;
ans %= M1;
// cout << w1 << ' ' << ans << '\n';
continue;
}
auto [w2, c2] = *s.begin();
s.erase(s.begin());
int c = min(c1, c2);
ans += (c % M1 * ((w1 + w2) % M1)) % M1;
ans %= M1;
s[w1 + w2] += c;
if (c1 > c) {
s[w1] = c1 - c;
}
if (c2 > c) {
s[w2] = c2 - c;
}
// cout << w1 << ' ' << w2 << ' ' << ans << '\n';
}
cout << ans;
}
E
取模 扫描线前缀和
子数组最大和可以扫描线前缀和，问题是，这里问的子数组和取模后的最大值，如何处理？对于子数组和取模有经典结论，首先还是维护所有前缀和，然后加上前缀和取模，那么的话，
子数组元素和，取模后就是
，也就是可以忽略取模，此时我们枚举确定了
，想要子数组最大，找一个最小的
即可；如果
，那么子数组和取模后是
，此时想要子数组最大，找一个大于
的最小
即可
void solve() {
int n, p;
cin >> n >> p;
int pre = 0, ans = -1;
pii res;
map<int, int>mp;
mp[0] = 0;
rep(i, 1, n) {
int x;
cin >> x;
pre = (pre + x) % p;
auto it = mp.upper_bound(pre);
if (it != mp.end()) {
int v = pre - it->fi + p;
if (v > ans) {
ans = v;
res = {it->se, i - 1};
}
}
pii t = *mp.begin();
if (t.fi <= pre) {
int v = pre - t.fi;
if (v > ans) {
ans = v;
res = {t.se, i - 1};
}
}
mp[pre] = i;
}
cout << res.fi << ' ' << res.se << ' ' << ans;
}
F
贪心+dp/枚举
经典问题，一个容量超大的背包，对于大部分容量，实际上都可以直接贪心，选择性价比最高的物品，对于剩下一点容量，可以来背包dp，或者暴力枚举。唯一的问题就是剩下多少容量来暴力/dp？这题转化完就是有容量2，7，8的三种东西，那么可能有特殊组合的容量不会超过lcm(2,7,8)=56，只留下56来暴力就可以了。这可以推广到一般背包问题，实际上就是，当然，这需要
不太大，一般常见于物品种类不太多的情况，这种时候往往分类讨论可解，但是物品种类少也意味着lcm小，选择贪心+暴力是更简单的写法
void solve() {
int n, a, b;
cin >> n >> a >> b;
vvi t = {
{56 * a / 7, 7, a},
{56 * b / 2, 2, b},
{56 * (a + b) / 8, 8, a + b}
};
sort(t.begin(), t.end());
int c = t[2][1], v = t[2][2];
int cnt = max(0ll, n / c - 100);
int ans = cnt * v;
n -= cnt * c;
vector<int>f(n + 1);
rep(i, 1, n) {
if (i >= 2)f[i] = max(f[i], f[i - 2] + b);
if (i >= 7)f[i] = max(f[i], f[i - 7] + a);
if (i >= 8)f[i] = max(f[i], f[i - 8] + a + b);
}
cout << ans + f[n] << '\n';
}
G
模拟
可以分类讨论，但注意到转移之和但当前状态+当前操作有关，可以转化成自动机，构造一个数组作为自动机的转移表，就可以不用ifelse分类讨论，是更简单的写法
int a[4][6]={
{3,0,1,2,1,3},
{2,3,0,1,2,0},
{1,2,3,0,3,1},
{0,1,2,3,0,2}
};
void solve() {
string s = "0112233445142015320125410214530214510214102302142025101203201451451522302514203214510021454101002532";
int x = 0;
for (char c : s) {
x=a[x][c-'0'];
cout<<x;
}
}
H
不变量
问能否操作到某一个终止状态，一个经典思路是找操作过程中的不变量，如果能到达某个终止状态，那么初态和末态的这个不变量一定是相等的。当然这往往只能作为必要条件，但是很多时候几个必要条件拼一起就能过了。
比如这题就有一些显然的不变量，一次横着一次竖着操作，能把一个2*2矩阵的对角线上一个+2一个-2，剩下位置不变，也就是如果黑白染色的话，黑色格和白色格的元素和都是不变的，所以如果能变成全都一样的，黑色格子的和，要能被黑色格子的个数整除，白色同样。
有这个还不够，注意到一次操作，不改变影响到的行和列的奇偶性，所以每一行的初始奇偶性，要和全变成x后的奇偶相同，，当然
必须要能被
整除。还有别的条件，但有这俩就能过了。
int a[500][500];
void solve() {
int n;
cin >> n;
auto check = [&]()->bool{
int s1 = 0, s2 = 0, c1 = 0, c2 = 0;
int tot = 0;
rep(i, 1, n) {
rep(j, 1, n) {
int x;
cin >> x;
a[i][j] = x;
if ((i + j) % 2) {
s1 += x;
c1++;
} else {
s2 += x;
c2++;
}
tot += x;
}
}
if (tot % (n * n)) {
return 0;
}
int x = tot / n / n;
if (c1 && s1 % c1 || c2 && s2 % c2)return 0;
rep(i, 1, n) {
int sum = 0;
rep(j, 1, n) {
sum += a[i][j];
}
if (sum % 2 != (n * x) % 2) {
return 0;
}
}
rep(j, 1, n) {
int sum = 0;
rep(i, 1, n) {
sum += a[i][j];
}
if (sum % 2 != (n * x) % 2) {
return 0;
}
}
return 1;
};
if (check())cout << "Yes";
else cout << "No";
}
I
二分+二阶差分
每次操作给一个区间增加，增加的值构成一个三角形。也就是能拆成两个等差数列，问最第几次操作后，最大值超过h。只能增不会减，有单调性，考虑二分。区间加等差数列，最后只有一次查询，，选择二阶差分，差分完做两次前缀和就能得到区间加等差数列的效果。只是这个等差数列的修改，需要思考一点，这是唯一难点，这个操作可以封装成一个函数，就比较好做了
转化成差分后，线段树，也能维护区间加等差数列，但是每次只能单点查，如果想查询全局最大值，最后需要一次的查询，整体两个
，会被卡常。这里只有最后一次查询，不是动态修改动态查询，没有必要线段树
void solve() {
int n, m, h;
cin >> n >> m >> h;
vector<pii> b(m + 1);
rep(i, 1, m) {
int p, f;
cin >> p >> f;
b[i] = {p, f};
}
int l = 1, r = m;
auto check = [&](int mid)->bool{
vi s(n + 10);
auto add=[&](int l,int r,int st,int ed,int d)->void{
s[l]+=st;
s[l+1]+=d-st;
s[r+1]-=ed+d;
s[r+2]+=ed;
};
rep(i, 1, mid) {
auto [p, f] = b[i];
int l , r , st , ed;
l = max(p - f + 1, 1ll);
st = f - (p - l);
r = p;
ed = f;
add(l, r, st, ed, 1);
l = p + 1;
r = min(p + f - 1 , n);
st = f - 1;
ed = st - (r - l);
add(l , r , st , ed , -1);
}
rep(i, 1, n) {
s[i] += s[i - 1];
}
int mx = 0;
rep(i, 1, n) {
s[i] += s[i - 1];
mx = max(mx, s[i]);
}
return mx > h;
};
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid))r = mid - 1;
else l = mid + 1;
}
if (l <= m)cout << "Yes\n" << l;
else cout << "No";
}
J
模拟
int a[10][10];
void solve() {
set<int>s;
rep(i, 1, 3) {
rep(j, 1, 3) {
int x;
cin >> x;
a[i][j] = x;
s.insert(x);
}
}
if (s.size() != 9) {
cout << "No\n";
return;
}
s.clear();
rep(i, 1, 3) {
int sum = 0;
rep(j, 1, 3) {
sum += a[i][j];
}
s.insert(sum);
}
rep(i, 1, 3) {
int sum = 0;
rep(j, 1, 3) {
sum += a[j][i];
}
s.insert(sum);
}
s.insert({a[3][1]+a[2][2]+a[1][3]});
s.insert({a[1][1]+a[2][2]+a[3][3]});
if(s.size()==1){
cout<<"Yes\n";
}
else{
cout<<"NO\n";
}
}
）。