-
ABC248 F
考虑枚举列，两个点一起做，同时这两个点的相互关系影响了联通，也需要加入状态 考虑前 列，删除了 条边，第 列上下两点之间是否连边 讨论 删多少条边，怎么删，是否联通转移， 转移的时候至少要保证一个点在连通块内，同时 只能是类似两横行这样的状态，这样后面 才可以接上让它变联通，同时因为 可能不连通，答案为 当前列不连通 只有一种方式保证联通 当前列联通 ... -
Luogu Simu5 T4
Here’s something encrypted, password is required to continue reading.
-
Luogu Simu5 T3
Here’s something encrypted, password is required to continue reading.
-
Luogu Simu5 T1
Here’s something encrypted, password is required to continue reading.
-
P4940 Portal2
主要麻烦的操作就是清空，我们不妨考虑启发式合并 但是我们发现交换了指针之后，栈整个相当于翻转了，所以我们还需要用一个翻转标记记录是否翻转 同时翻转后就是取栈底了，这是栈做不到的，我们需要的是一个前后都能访问的数据结构，可以想到 这里还有一个 就是用 表示两个 ，而不是 ，这样穿入 ，的时候直接写 就行了，简化代码 12345678910111213141516171819202122... -
P4824 [USACO15FEB] Censoring S
暴力 123456789101112131415string S,T;int main(){ cin>>S>>T; while(1) { int pos=S.find(T); if(!(~pos)) break; S.erase(pos,T.size()); } cout<<S; ... -
P3551 [POI2013] USU-Take-ou
考虑最后一段一定是连续的，我们如果删掉这一段，那么倒数第二段也是连续的 这是一个相同的问题，我们考虑删 次 如何判断当前有连续的 个 和 个 ，显然可以想到前缀和 具体来说，我们维护一个栈，满足前缀条件直接暴力弹栈 注意！！！用前缀和和输入字符串的时候 数组不能共用！！！ 1234567891011121314151617181920212223242526272829303132... -
P2157 [SDOI2009] 学校食堂
简单的情况就是 这就是线性 考虑到 我们可以考虑状压后面人的状态，去除后效性，即 表示 及其后面 个人的状态 同时我们还需要知道上一个人是谁，然后枚举这一次选谁转移，还要再开一维 表示做完了 个人， 和后面 个人的状态是 ，上一个人是 这里用了一个小技巧就是上一个人用 表示，这样就优化了一维 的空间，同时考虑到 可能为负数，还需要加上一个偏移量 这里 ，为什... -
浅谈前后缀思想
前后缀思维T1 01 背包，求去掉第 $i$ 个物品后的最大价值$pre_{i,j} 表示考虑前, i 个的背包，suf_{i,j} 表示考虑后,i 个的背包$$$\max_{j=0}^m pre_{i-1,j}+suf_{i+1,m-j}$$ T2 P7300 [USACO21JAN] No Time to Paint S给定序列 $A$ ，$Q$ 次询问 $[L,R]$ ，每个... -
P7291「EZEC-5」人赢 加强版
显然有 的做法 我们考虑到一个性质对于 的一对 ， 一定劣于 可以分 和 分别在三个区间讨论证明 所以我们可以维护一个类似单调栈的东西 引理 对于 的一个三元组 只用考虑 和 ，因为 考虑到序列一定是上升下降的连续段拼接起来，设当前枚举 xxxxxxxxxx #include<bits/stdc++.h>#define pt putchar(‘ ‘)#de...
