1841E Fill the Matrix
刚开始思路错了，以为就从下往上铺
但发现要尽量让横的连续段断开的次数少，每断开一次相当于数量 \(-1\)
所以从宽度最大的矩形开始填，尽量填满
可以用 set 维护当前行的连续段，这一列遇到黑格就 split，去除宽度为 \(1\) 的，同时记录加入的时间戳来计算矩形高度
void split(ll x, ll nw)
{
iter it = lin.upper_bound((seg){x, N, 0});
if(it == lin.begin()) return;
--it;
if(it -> r < x) return;
ll nl = it -> l, nr = it -> r, pre = it -> tim; lin.erase(*it);
if(pre <= n) squ[++cnt] = mp(nr - nl + 1, pre - nw);
else if(nw < n) squ[++cnt] = mp(nr - nl + 1, pre - nw - 1);
if(nl < x - 1) lin.insert((seg){nl, x - 1, nw});
if(x + 1 < nr) lin.insert((seg){x + 1, nr, nw});
}
int main()
{
t = read();
while(t--)
{
n = read();
for(ll i = 0; i <= n; ++i) vec[i].clear();
lin.clear(), tot = n, ans = cnt = 0;
for(ll i = 1; i <= n; ++i) a[i] = read(), vec[a[i]].pb(i);
m = read(), lin.insert((seg){1, n, n + 1});
for(ll i = n; i >= 0; --i)
{
for(ll j : vec[i]) split(j, i);
}
sort(squ + 1, squ + cnt + 1);
for(ll i = cnt; i > 0; --i)
{
if(m == 0) break;
if(m < squ[i].fi * squ[i].se)
{
ans += (squ[i].fi - 1) * (m / squ[i].fi) + (m % squ[i].fi ? m % squ[i].fi - 1 : 0);
break;
}
ans += (squ[i].fi - 1) * squ[i].se, m -= squ[i].fi * squ[i].se;
}
print(ans), putchar('\n');
}
return 0;
}
1842E Tenzing and Triangle
好像跟我们出题小组搬的 T4 撞 idea 了
同样，key observation 是三角形之间不交，否则可以通过调整，花费相同代价覆盖更大面积
转化为下标后，设 \(f(i)\) 表示删完前 \(i\) 行需要的最小代价
枚举第 \(i\) 行摆放的三角形到第 \(j+1\) 行，则 \(f(i)=\min_{j<i}f(j)+A(i-j)+cost(i,j)\)，\(cost(i,j)\) 为 \(j+1\sim i\) 行除三角形外删除剩下点的代价
考虑优化，发现从 \(i-1\) 行到第 \(i\) 行，第 \(k\) 列上的点会对三角形开头在 \(k+1\sim i\) 行的产生贡献
线段树优化 DP，支持区间加，区间查询最小值
ll lson(ll x) {return x << 1;}
ll rson(ll x) {return x << 1 | 1;}
void pushup(ll x) {sum[x] = min(sum[lson(x)], sum[rson(x)]);}
void pushdown(ll x)
{
if(!tag[x]) return;
sum[lson(x)] += tag[x], sum[rson(x)] += tag[x];
tag[lson(x)] += tag[x], tag[rson(x)] += tag[x];
tag[x] = 0;
}
void update(ll l, ll r, ll val, ll nl, ll nr, ll p) // 区间加
{
if(l <= nl && nr <= r)
{
sum[p] += val, tag[p] += val;
return;
}
ll mid = (nl + nr) >> 1;
pushdown(p);
if(mid >= l) update(l, r, val, nl, mid, lson(p));
if(mid < r) update(l, r, val, mid + 1, nr, rson(p));
pushup(p);
}
ll query(ll l, ll r, ll nl, ll nr, ll p)
{
if(l <= nl && nr <= r) return sum[p];
ll mid = (nl + nr) >> 1, res = inf;
pushdown(p);
if(mid >= l) res = min(res, query(l, r, nl, mid, lson(p)));
if(mid < r) res = min(res, query(l, r, mid + 1, nr, rson(p)));
return res;
}
int main()
{
n = read(), k = read(), A = read();
for(ll i = 1; i <= n; ++i)
{
p[i].y = read() + 1, p[i].x = k - read(), p[i].c = read();
vec[p[i].x].pb(p[i]);
}
memset(f, 0x3f, sizeof(f)), f[0] = 0;
for(ll i = 1; i <= k; ++i) // f[i]：完全删除前 i行的点的最小代价，注意到摆放的三角形一定不交
{
ll tot = 0;
for(point j : vec[i])
{
if(j.y < i) update(j.y + 1, i, j.c, 1, k + 1, 1);
tot += j.c; // 当 j>=y 时这个点不能被新增的三角形覆盖，要加上单独删除它的代价
}
f[i] = min(query(1, i, 1, k + 1, 1) + A * i, f[i - 1] + tot); // 找以 i结尾的三角形到 j结束
update(i + 1, i + 1, f[i] - A * i, 1, k + 1, 1);
}
printf("%lld", f[k]);
return 0;
}
CF1839E Decreasing Game
有意思的博弈论题，但我博弈论很差
从简单情况开始考虑什么时候后手必胜
只剩一个数，先手必胜，剩下两个不同数，先手必胜，剩下两个相同数，后手必胜……
对于每次操作，两个数的减少量相同，那么，如果最开始数能划分为两个和相同的集合，则后手能保证每一步让两个集合中的数同时减少，发现最后一步必然剩下两个相同的数，后手必胜
方法也出来了，先背包找出两个集合的划分，当先手取一个集合时，后手取另一个即可
如果先手必胜，先手的博弈方法更简单：随便取
证明：
反证法，设当前数的两个集合的和分别为 \(s_1,s_2,s_1\not= s_2\)，先手取了 \(s_1\) 中的 \(a\)，后手取了 \(b\)，假设 \(a\le b\)
- 如果 \(b\) 在 \(s_2\) 中，则 \(s_1,s_2\) 同时 \(-a\) 必然不相等
- 如果 \(b\) 在 \(s_1\) 中，假设 \(s_1-a-a=s_2\)，则 \(s_1-a=s_2+a\)，把 \(a\) 放在 \(s_2\) 就可以把数划分为两个相同的集合，与先手必胜条件矛盾
void playfirst()
{
for(int i = 1; i <= n; ++i)
{
int id = 0;
for(int j = 1; j <= n; ++j)
if(a[j] > 0) {cout << j << endl, id = j; break;}
cin >> pos;
if(pos == 0 || pos == -1) exit(0);
int mn = min(a[id], a[pos]); a[id] -= mn, a[pos] -= mn;
}
}
void playsecond()
{
int nw = sum[n] / 2;
for(int i = n; i && nw; i = fr[i][nw] - 1, nw -= a[i + 1])
vis[fr[i][nw]] = 1;
for(int i = 1; i <= n; ++i)
{
cin >> pos;
if(pos == 0 || pos == -1) exit(0);
for(int j = 1; j <= n; ++j)
if(a[j] > 0 && vis[j] != vis[pos])
{
int mn = min(a[j], a[pos]);
a[j] -= mn, a[pos] -= mn;
cout << j << endl; break;
}
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i], sum[i] = sum[i - 1] + a[i];
f[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
for(int j = sum[i]; j >= 0; --j)
if(j >= a[i] && f[i - 1][j - a[i]]) f[i][j] = 1, fr[i][j] = i;
else f[i][j] = f[i - 1][j], fr[i][j] = fr[i - 1][j];
}
if(sum[n] % 2 == 0 && f[n][sum[n] / 2]) cout << "Second" << endl, playsecond();
else cout << "First" << endl, playfirst();
return 0;
}
CF1839D Ball Sorting
放一个球，代表着可以改变序列的一段连续段，最后不动的数，一定单调递增
问题转化为在最多能删除 \(k\) 个连续段时，删除最少的数使序列单调递增
设 \(f(i,j)\) 表示强制保留第 \(i\) 个位置，删除 \(j\) 个连续段时删的最少的数
从后往前找到能直接保留的最靠前的数 \(u\)，则 \(f(i,j)=\min_{u\le k< i} f(k,j)\)
否则 \(k\sim i-1\) 的这一段只能被删除，\(f(i,j)=\min_{k<u}f(k,j-1)+i-k-1\)
最后枚举最后一个被钦定保留的位置，注意判断它之后的那段必须删还是可以保留
int main()
{
t = read();
while(t--)
{
n = read(), ans = 1e9;
for(int i = 1; i <= n; ++i) a[i] = read();
memset(f, 0x3f, sizeof(f)), f[0][0] = f[1][0] = 0;
for(int i = 1; i <= n; ++i) f[1][i] = 1, f[0][i] = 0;
for(int i = 2; i <= n; ++i) // f[i][j]：强制当前留下的段以 i结尾，选（最多）j个连续段时选出的最小个数
{
ed = 0; // 题意等价于挖掉最多 k个连续段，使剩下的数单增，让挖去的数的个数最少
for(int u = i - 1; u > 0; --u)
{
if(a[u] > a[u + 1]) {ed = u; break;}
for(int j = 0; j <= n; ++j)
f[i][j] = min(f[i][j], f[u][j]); // 最后 u\sim i可以留下
}
for(int u = ed; u >= 0; --u)
if(a[u] < a[i])
for(int j = 1; j <= n; ++j) // 只保留 i,挖去 u+1\sim i-1
f[i][j] = min(f[i][j], f[u][j - 1] + i - u - 1);
}
for(int i = 1; i <= n; ++i)
{
ans = min(ans, f[n][i]), ed = 0;
for(int j = n - 1; j >= 0; --j) // 最后 j\sim n可以留下
{
if(a[j] > a[j + 1]) {ed = j; break;}
ans = min(ans, f[j][i]);
}
for(int j = ed; j >= 0; --j) ans = min(ans, f[j][i - 1] + n - j); // 挖去 j+1\sim n
print(ans), putchar(' ');
}
putchar('\n');
}
return 0;
}
CF1838D Bracket Walk
这种题没有 key observation 就直接完了……
发现如果左/右括号连续出现了 \(\ge 2\) 个，那么可以在此反复横跳增加很多个括号
否则括号序列一定左右交错，如 \(()()()()\dots\)
用 set 维护奇数位置上出现的右括号，以及偶数位置上出现的左括号，按下标大小排序
- 如果
set为空，则括号序列如上，合法 - 如果
set先出现了奇数位置，则这组右括号必出现 \(\ge 2\) 个且前面只有单个出现的左括号，不合法 - 同理，如果
set最后出现了偶数位置，则这组左括号必出现 \(\ge 2\) 个且后面只有单个出现的右括号，不合法 - 剩下就是合法情况
int main()
{
cin >> n >> q >> (s + 1);
for(int i = 1; i <= n; ++i) a[i] = (s[i] == '(') ? 0 : 1;
if(n & 1) // 多走的步数只能是偶数，两种括号数量不可能相同，无解
{
for(int i = 1; i <= q; ++i) cin >> pos, puts("NO");
return 0;
}
for(int i = 1; i <= n; ++i)
if(!a[i] && i % 2 == 0) brac.insert(i);
else if(a[i] && (i & 1)) brac.insert(i);
for(int i = 1; i <= q; ++i) // 为什么我想不到按奇偶位置分类……
{
cin >> pos, brac.erase(pos);
if(a[pos] == 0)
{
a[pos] = 1;
if(pos & 1) brac.insert(pos);
}
else
{
a[pos] = 0;
if(pos % 2 == 0) brac.insert(pos);
}
if(brac.empty()) puts("YES");
else if(*brac.begin() & 1) puts("NO");
else if(*brac.rbegin() % 2 == 0) puts("NO");
else puts("YES");
}
return 0;
}
CF1837F Editorial for Two
漏了一种简单情况调半天……
枚举两个人的划分点 \(i\)，则变为在 \(1\sim i\) 中选 \(x\) 个，在 \(i+1\sim n\) 个中选 \(k-x\) 个，使两边和的最大值最小
想到贪心调整，每次把 \(a_i\) 放入前半部分的备选集合，如果它比前半部分的已选集合更优则调整
把 \(a_i\) 在后半部分中删除，如果在后半部分的已选集合，则多从备选集合中拿一个补上，保证时刻已选集合总大小为 \(k\)
问题是可能改动后，前半部分多选一些更优
那就直接暴力调整，如果前半部分的和更小就一直换，把后半部分已选集合中最大的拿出来，把前半部分备选集合中最小的加入
这样一共只会调整 \(O(k)\) 次，因为每次只有 \(a_i\) 在后半部分的已选集合中才会出现调整，且每次调整后半部分已选集合的大小减少
这样总共只能减少 \(O(k)\) 次
void clear()
{
ans = inf, tota = totb = 0;
rma.clear(), rmb.clear(), chsa.clear(), chsb.clear();
}
void tzh()
{
while(!rma.empty() && !chsa.empty() && rma.begin() -> fi < chsa.rbegin() -> fi) // 记得调整 A内部！
{
tota += rma.begin() -> fi - chsa.rbegin() -> fi;
chsa.insert(*rma.begin()), rma.insert(*chsa.rbegin());
chsa.erase(*chsa.rbegin()), rma.erase(*rma.begin());
}
while(!rmb.empty() && !chsb.empty() && rmb.begin() -> fi < chsb.rbegin() -> fi)
{
totb += rmb.begin() -> fi - chsb.rbegin() -> fi;
chsb.insert(*rmb.begin()), rmb.insert(*chsb.rbegin());
chsb.erase(*chsb.rbegin()), rmb.erase(*rmb.begin());
}
while(!chsb.empty() && !rma.empty()) // 调整 A,B选的数量，可以证明只会调整 O(k)次
{
if(max(tota + rma.begin() -> fi, totb - chsb.rbegin() -> fi) < max(tota, totb))
{
chsa.insert(*rma.begin()), tota += rma.begin() -> fi, totb -= chsb.rbegin() -> fi;
rmb.insert(*chsb.rbegin()), chsb.erase(*chsb.rbegin()), rma.erase(*rma.begin());
}
else break;
}
while(!chsa.empty() && !rmb.empty())
{
if(max(totb + rmb.begin() -> fi, tota - chsa.rbegin() -> fi) < max(tota, totb))
{
chsb.insert(*rmb.begin()), totb += rmb.begin() -> fi, tota -= chsa.rbegin() -> fi;
rma.insert(*chsa.rbegin()), chsa.erase(*chsa.rbegin()), rmb.erase(*rmb.begin());
}
else break;
}
}
int main()
{
t = read();
while(t--)
{
n = read(), k = read();
clear();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) rmb.insert(mp(a[i], i));
for(int i = 1; i <= k; ++i) chsb.insert(*rmb.begin()), totb += rmb.begin() -> fi, rmb.erase(*rmb.begin());
ans = min(ans, max(tota, totb));
for(int i = 1; i <= n; ++i) // 枚举分界点
{
rma.insert(mp(a[i], i));
if(rmb.find(mp(a[i], i)) != rmb.end()) rmb.erase(mp(a[i], i));
else
{
chsb.erase(mp(a[i], i)), totb -= a[i];
chsa.insert(*rma.begin()), tota += rma.begin() -> fi, rma.erase(*rma.begin());
}
tzh(), ans = min(ans, max(tota, totb));
}
print(ans), putchar('\n');
}
return 0;
}
CF1837E Playoff Fixing
某一局的比赛次序改变，则初始位置也改变
固定了某个人的初始位置，则可以事先计算出它会在哪些场次的比赛中出现，每一局中出现的人也固定了
如果发现有不同人应在同一场比赛的同一位置，冲突无解
如果不是决赛的比赛发现两个人都不再往上走，则无解
从上往下计算每一局的安排方案
- 如果这场比赛两个都空着，则这两个人之间可以换顺序，新增的人也可以随便
- 如果这场比赛空着的是新增的，则新增哪个人可以随便选
- 否则不能产生额外方案
那么，这一局有 \(2^{\text{两个人可换顺序的比赛场数}}\times (\text{可选新增的人的比赛场数})!\) 种安排方法
一局中的比赛之间不能换顺序，因为它们的顺序是由上一局决定的
int main()
{
k = read(), n = (1ll << k), pw[0] = fact[0] = 1, tim[1] = k;
for(ll i = 1; i <= n; ++i) pw[i] = pw[i - 1] * 2 % mod, fact[i] = fact[i - 1] * i % mod;
for(int i = 1; i <= k; ++i)
for(int j = (1 << (i - 1)) + 1; j <= (1 << i); ++j) tim[j] = k - i + 1;
for(int i = 1; i <= n; ++i)
{
a[i] = read();
if(a[i] != -1)
{
ll num = (i - 1) / 2 + (1 << (k - 1)), cur = (i & 1) ^ 1;
for(ll j = 1; j <= tim[a[i]]; cur = (num & 1), num >>= 1, ++j)
{
if(book[num][cur]) {printf("0"); return 0;}
if(j == tim[a[i]] && book[num][cur ^ 1] && tim[book[num][cur ^ 1]] <= j && j < k)
{printf("0"); return 0;}
book[num][cur] = a[i];
}
}
}
for(int i = 1; i <= k; ++i)
{
ll tot = 0, cnt = 0;
for(int j = (1 << (i - 1)); j < (1 << i); ++j)
if(!book[j][0] && !book[j][1]) ++tot, ++cnt;
else if((!book[j][0] && tim[book[j][1]] > k - i + 1) || (!book[j][1] && tim[book[j][0]] > k - i + 1))
++tot;
ans = ans * fact[tot] % mod * pw[cnt] % mod;
}
printf("%lld", ans);
return 0;
}
CF1834E MEX of LCM
好题
固定左端点 \(l\)，则什么时候 \(\mathrm{lcm}\) 会改变呢？
新加入的数 \(a_x\) 必定有原来 \(\mathrm{lcm}\) 中没有的质因子，最小为 \(2\)
也就是说，新的\(\mathrm{lcm}\) 至少为原来的 \(2\) 倍
于是答案有了一个上界 \(O(n\log V)\)，可以从后往前找，维护不同的 \(\mathrm{lcm}\) 的数列，数列长度为 \(O(\log V)\)，在 \(O(n\log V)\) 时间内找出所有的 \(\mathrm{lcm}\)
但评论区证明了更紧的上界：
考虑以 \(l\) 开头的连续段中值域在 \([X,2X)\) 中的 \(\mathrm{lcm}\)，最多只会有 \(1\) 个
那么 \([N+1,2N+2)\) 中最多只能有 \(n\) 个 \(\mathrm{lcm}\)，但区间内已经有了 \(N+1\) 个数，因此必然有一个空隙，答案最大为 \(2N+1\)
int main()
{
t = read();
while(t--)
{
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n * 2 + 1; ++i) book[i] = 0;
cnt = 0;
if(a[n] <= n * 2 + 1) book[a[n]] = 1, f[++cnt] = a[n];
else f[++cnt] = 1;
for(int i = n - 1; i > 0; --i)
{
for(int j = 1; j <= cnt; ++j) lcm[j] = f[j];
idx = 0, ggcd = a[i];
for(int j = 1; j <= cnt; ++j) // 后缀长度逐渐减小，后面的 lcm 是前面的因数
{
ggcd = gcd(ggcd, lcm[j]); // 均摊求 gcd 的复杂度，因为 gcd 只会减小
if(1ll * lcm[j] / ggcd * a[i] <= 2ll * n + 1 && lcm[j] / ggcd * a[i] != f[idx])
f[++idx] = lcm[j] / ggcd * a[i]; // 用后面数结尾的后缀的 lcm 递推前面数的
}
if(f[idx] != a[i] && a[i] <= 2 * n + 1) f[++idx] = a[i];
cnt = idx;
for(int j = 1; j <= cnt; ++j) book[f[j]] = 1;
}
for(int i = 1; i <= n * 2 + 1; ++i)
if(!book[i])
{
print(i), putchar('\n');
break;
}
}
return 0;
}
CF1834F Typewriter
先不考虑修改，发现若 \(p_i< i\)，则一定要重置小车来还原 \(p_i\)
答案下界为 \(\sum_{i=1}^n [p_i<i]\)
构造出答案下界的方案：将大小 \(>1\) 的置换环按 \(p\) 最小值从小到大排序，对一个置换环中元素从 \(p\) 最小到最大操作，调整完这个环后回到最小点，因为最小值从小到大排序，所以可以直接切换到后一个环
再考虑每个数对答案的贡献，将左右移统一为右移，移动步数 \(\in(-n,n)\)，那么每个数至多在 \(2\) 个移动步数的区间产生贡献
于是可以差分计算出对于每个步数的答案
反转就直接反转序列预处理
复杂度 \(O(n+q)\)
void work(int *sum)
{
for(int i = 1; i <= n; ++i)
{
if(a[i] >= i)
{
if(a[i] - i + 1 <= n - i) ++sum[a[i] - i + 1], --sum[n - i + 1];
}
else
{
++sum[0], --sum[n - i + 1];
if(n + a[i] - i + 1 <= n - 1) ++sum[n + a[i] - i + 1];
}
}
for(int i = 1; i < n; ++i) sum[i] += sum[i - 1];
}
int main()
{
n = read();
for(int i = 1; i <= n; ++i) a[i] = read(), num += (int)(a[i] < i);
work(cnt[0]), reverse(a + 1, a + n + 1), work(cnt[1]);
print(cnt[0][0]), putchar('\n'),
q = read();
for(int i = 1; i <= q; ++i)
{
op = read();
if(op == 1)
t = read(), tot[cur] = (tot[cur] + n - t) % n, tot[cur ^ 1] = (tot[cur ^ 1] + t) % n;
else if(op == 2)
t = read(), tot[cur] = (tot[cur] + t) % n, tot[cur ^ 1] = (tot[cur ^ 1] + n - t) % n;
else cur ^= 1;
print(cnt[cur][tot[cur]]), putchar('\n');
}
return 0;
}
CF1855B Longest Divisors Interval
div2B 差点不会做……控诉样例解释误导人
显然 \(n\) 为奇数时答案为 \(1\)，但是我研究了半天样例解释也不明白那个区间是怎么找出来的
换种思路，长度 \(\ge m\) 的区间必然有 \(m\) 的倍数，那么只要找到 \(1\sim x\) 中第一个不是 \(n\) 的因数的元素 \(x\)，则答案最大为 \(x-1\)，而且 \([1,x-1]\) 一定是符合要求的
我还看了半天，为什么 div2B 这么难……
CF1854A2 Dual(hard version)
CF1854B Earn or Unlock
CF1854D Michael and Hotel
CF1852C Ina of the Mountain
如果每个数的大小固定，根据经典的结论，当 \(a_i>a_{i-1}\) 时，会有 \(a_i-a_{i-1}\) 的贡献，意味着 \(a_i\) 不能顺便被前面的摆好
但是现在我们可以增加前面，当 \(a_{j-1}>a_j\) 时，花费的代价是 \(a_j+k-a_{j-1}\)，把 \(j\sim i-1\) 在原来的基础上增加 \(k\)，否则为 \(a_j-a_{j-1}\)，让前面的元素比 \(a_i\) 大，使 \(a_i\) 不再产生贡献，且对 \(i\) 之后的元素没有影响
每个数最多增加一次，差超过 \(k\) 肯定不优
贪心地用小根堆维护代价，每次遇到 \(a_i\le a_{i-1}\) 时，往堆中加入 \(a_i+k-a_{i-1}\)，否则加入 \(a_{i}-a_{i-1}\)，之后取出堆顶，作为当前调整的代价
CF1852D Miriany and Matchstick
CF1852B Imbalanced Arrays
CF1473E Minimum Path
图论转化
这个边的最大，最小值肯定不好记录，一记下就直接炸了
但是想让路径长度最小，发现是去掉一条最长的边又增加一条最短的边
如果我们可以自己指定删除和增加的边，发现刚好与要求吻合
因此，直接记录 \(f(i,0/1/2/3)\) 表示到 \(i\) 点，不修改/增加一条/删除一条/增加且删除一条的最短路，分层图
对于这种把限制转化掉的题目，见的不少了，下次会做吗？
void add(ll u, ll v, ll w)
{
edge[u].pb(mp(v, w)), edge[u].pb(mp(v + n, 0)), edge[u].pb(mp(v + n * 2, w + w)), edge[u].pb(mp(v + n * 3, w));
edge[u + n].pb(mp(v + n, w)), edge[u + n].pb(mp(v + n * 3, w * 2));
edge[u + n * 2].pb(mp(v + n * 2, w)), edge[u + n * 2].pb(mp(v + n * 3, 0));
edge[u + n * 3].pb(mp(v + n * 3, w));
}
CF1801C Music Festival
其实可以直接暴力一点（
把原序列的每个可能产生贡献的子序列拿出来，它一定是到末尾，总个数为 \(O(\sum k_i)\)
这时就必须要求子序列选完了，把它们按最小的元素升序排序，设以子序列 \(i\) 结尾时的最大权值为 \(f_i\)，则 \(f_i=\max_{r_j<l_i}\{f_j+len_i\}\)
然后用树状数组优化
其实还可以把每个 \(a_i\) 处存下哪些序列中包含它，然后递增的考虑每个元素，含有它的序列权值可以直接在原来的基础上增加一个，也可以把它接在前面某个完整序列的末尾，表示这个序列拼接在它后面
注意清空的复杂度
int main()
{
t = read();
while(t--) // 多测清太多，爆零两行泪
{
n = read();
lin.clear();
// for(reg int i = 1; i <= cnt; ++i) lin[i].clear(); 不要这样写！多测如果数据有很多组会 g！
ans = cnt = sum = tot = 0;
for(reg int i = 1; i <= n; ++i)
{
k[i] = read(), a.clear();
for(reg int j = 1; j <= k[i]; ++j) a.pb(read());
last = f[i] = mx[i] = 0;
for(reg int j = 0; j < k[i]; ++j)
if(a[j] > last) lin[a[j]].pb(i), last = a[j];
cnt = max(cnt, last), mx[i] = last;
}
for(reg map<int, vector<int> >::iterator it = lin.begin(); it != lin.end(); ++it)
{
c = it -> first, a = it -> second;
tot = 0;
for(reg int i : a) // 看当前值 c有哪些段中有它
{
f[i] = max(f[i] + 1, sum + 1); // 当前可以往这段之前接，也可以直接在另外的段后面
if(c == mx[i]) tot = max(tot, f[i]);
// 有一段结尾了，可以更新当前已经结束的段的最大权值
}
sum = max(sum, tot); // 更新当前已经结束的段的最大值
}
for(reg int i = 1; i <= n; ++i) ans = max(ans, f[i]);
print(ans), putchar('\n');
}
return 0;
}
CF1801D The way home
又是边跑最短路边 DP
首先肯定想尽量在 \(w\) 大的地方演出，问题是不知道后面的花费，就不知道应该在当前演出多少场
但为什么一定要在那时才演出呢？这完全等价与先走，等钱不够时，从经过的地方中找 \(w\) 最大的再演出
代价延迟计算的思想很重要
跑最短路的同时记录经过的 \(w\) 最大的点和已经演出的次数与剩余钱数，优先从堆中取出演出次数少，然后是剩余钱数多的状态
发现钱不够了，就计算额外演出的次数
struct node
{
ll mny, tim, id, best;
inline void init() {tim = inf, mny = id = best = 0;}
bool operator <(const node &c)const // 堆中重载运算符，优先考虑当前次数少且钱多的状态
{
if(tim != c.tim) return tim > c.tim;
if(mny != c.mny) return mny < c.mny;
}
bool operator !=(const node &c)const
{
return mny != c.mny || tim != c.tim;
}
}f[810][810];
inline node mn(node a, node b)
{
if(a.tim < b.tim || (a.tim == b.tim && a.mny > b.mny)) return a;
return b;
}
inline void dij()
{
priority_queue<node> heap;
for(reg ll i = 1; i <= n; ++i)
for(reg ll j = 1; j <= n; ++j) f[i][j].init();
f[1][1] = (node){p, 0, 1, 1}, heap.push(f[1][1]);
while(!heap.empty()) // 用 dij 的思想在图上 DP
{
node t = heap.top(); heap.pop();
if(f[t.id][t.best] != t) continue; // 不是这个状态的最优，跳过
for(reg pll i : edge[t.id])
{
if(i.se > t.mny) // 需要额外表演，但最核心的想法是表演可以看作是钱不够了再在前面能拿更多钱的地方表演，延后计算
{
ll nw = t.best, ci = (i.se - t.mny + w[nw] - 1) / w[nw], res = ci * w[nw] + t.mny - i.se;
if(w[i.fi] > w[nw]) nw = i.fi;
heap.push((node){res, t.tim + ci, i.fi, nw});
f[i.fi][nw] = mn(f[i.fi][nw], (node){res, t.tim + ci, i.fi, nw});
}
else
{
ll nw = (w[i.fi] > w[t.best]) ? i.fi : t.best;
heap.push((node){t.mny - i.se, t.tim, i.fi, nw});
f[i.fi][nw] = mn(f[i.fi][nw], (node){t.mny - i.se, t.tim, i.fi, nw});
}
}
}
}