- Grouping
随便 DP.
- [PKUSC2018]最大前缀和
考虑加入某一个数会产生什么变化和前缀和的性质。
显然后缀和必须是一个负数。
f, g.
如果是一个负数，显然可以塞在 g 的后面
如果前缀 f 前面是正的，可以塞在 g 的前面。
是正的就塞在 f 的后面，然后这两种可以合并。
- lgj
[l, r] +1 -1 -> 0
考虑差分数组，最后面补一个 0， 那么如果差分全是 0 这个原数组也差不多如此。
那么每次可以配对的选一对 [l, r] 就是差分数组绝对值和除以 2
- 九省联考 2018] 一双木棋 chess
考虑到这个是一个下降的图形。直接搜索似乎就可以过了哥们。
P9145 [THUPC 2023 初赛] 世界杯
绝世好题，我是贺的。
P3523 [POI2011] DYN-Dynamite
二分一下 \(k\).
然后记录一下两个相关 \(f, g\) 就是最远和最近的那个。
然后有几种情况。
-
可以救火 \(f \to -inf\)
-
\(f \to lim\) 表明放在 \(u\) 就是优秀的。 \(g \to 0\)
-
\(g > lim\) 表明救不了自己，要父亲来救。 \(f \tomax(f, 0)\)
P6419 [COCI2014-2015#1] Kamp
手绘好题！
可以画个图，发现不走最长链。
那么考虑换根时维护，这个要记录次长链，然后自己做一做找一找感觉。
- P3588 [POI2015] PUS
17 mins 感觉不错。
学习了很多。
比如说那 \(k\) 个点，我们可以建立超级点 \(s'\) 代表，连剩下的。
然后 \(u_{k} \to (s', -1)\), \(s' \to (segment, 0)\).
然后这个是一个 \(0 / 1\) 图， 可以考虑直接 拓扑排序。
线段树优化建图即可。
- P2627 [USACO11OPEN]Mowing the Lawn G
双倍经验。
- P1848 [USACO12OPEN]Bookshelf G
考虑单调栈预处理 \(h_i\) 产生贡献的位置。
把 dp 数组可以考虑拍到线段树上，然后动态维护 \(f,f +h\) 这两个的最小值，随便打打 tag 就好了。
- P6623 [省选联考 2020 A 卷] 树
不会做，进行了学习。
全局加一就是找到连续的 1 然后将其变为 0 就好了，这个很神奇。
附上一个打包的模板。
#define lc ch[u][0]
#define rc ch[u][1]
namespace trie {
const int maxd = 21, M = N * (maxd + 1);
int cnt = 0, ch[M][2], w[M], xorv[M];
inline int node () { int u = ++ cnt; lc = rc = w[u] = xorv[u] = 0; return u;}
inline void maintain (int u) {
w[u] = xorv[u] = 0;
if (lc) { w[u] += w[lc], xorv[u] ^= xorv[lc] << 1;}
if (rc) { w[u] += w[rc], xorv[u] ^= xorv[rc] << 1 | (w[rc] & 1);}
w[u] = w[u] & 1;
}
inline void insert (int & u, int k, int dep) {
if (! u) u = node();
if (dep > maxd) { w[u] ++; return ; }
insert(ch[u][k & 1], k >> 1, dep + 1), maintain(u);
}
inline int merge (int u, int v) {
if (! u || ! v) return u | v;
w[u] = w[u] + w[v], xorv[u] ^= xorv[v];
lc = merge(lc, ch[v][0]), rc = merge(rc, ch[v][1]);
return u;
}
inline void addone (int u) {
swap(lc, rc);
if (lc) addone(lc);
maintain(u);
}
}
- P3178
今日份弱智。
\(dis_v \times k - dis_u \times k\) 单点修改，区间修改，两颗线段树，我是小丑。
别又降智了哥们。
- P7527
容易弱智。
考虑枚举 l, 然后转化为一个数点问题：
\[[pre_r < l, suf_l > r] \]这样的形式显然很简单，用主席树即可维护 （
标签：总结,ch,return,lc,xorv,int,学习,rc From： https://www.cnblogs.com/Custlo/p/17520816.html