晚自习脑子一团浆糊已经想不动题了啊...还是水题有成就感的啊...
计数器: ## 45
3211: 线段树板子
1412: 最小割板子 我居然还会写dinic真是感动
忘清空dis了也很真实
1696: 车站选址的二维版本, 不能在有牛的地方建牛舍有点蛋疼
CF893F: 求子矩阵最小值, 二维线段树裸体居然没看出来...我居然还会写树套树真是感动...没想到因为在外层线段树上修改了一条链, 所以有可能内层线段树的某个节点被覆盖...WA了一晚上真是感动
具体来说就是我以为因为每个节点只会插入一次, 所以叶子节点直接覆盖就完事了...但是没想到在外层线段树的非叶子节点中的内层线段树上叶子节点可能之前是有值的(有同祖且同深度的节点)
1 | if (!dq) dq = ++cntb, ib[dq].le = le, ib[dq].ri = ri; |
2242: SDOI果然什么题都能出...发现逆元又㕛叒叕不会写了非常真实...学习了一发BSGS感觉非常神仙
1385: 显然我们发现在\(x_{k_1} / x_{k_2} / x_{k_3} /\cdots /x_{k_n}\)加括号后就相当于给原式乘上\((x_{k_2} \cdot x_{k_3}\cdot \cdots \cdot x_{k_n})^2\), 所以直接给\(x_2\cdots x_n\)加括号然后判断就完事了
1786$=$1831: 我们插入的数是递增的: 如果后面的数比前面的数大造成的逆序对不会比前面的数造成的更多; 所以我们可以直接枚举每个点放哪个, 然后用树状数组判断一下放什么数最优就行了
1826$=$1528: 因为每个玩具对答案的贡献是一样的,
先扔掉nex靠后的不会更坏,
所以贪心就行了(unique的时候忘排序了丢人)
1531: 有人想做背包吗?
1008: 没想到倒着来推真是自闭...求出所有不能越狱的情况然后再用总情况减就完事了...
1875: ATP学姐讲矩阵的例题...我居然还记得真是感动...虽然忘了咋做了吧...忘了取模疯狂WA很真实, 递归矩阵快速幂会爆栈更真实...感受一下写完了之后又WA又RE的恐惧...
1297: 把每个点拆成10份, \(I_x\)表示距离\(I\)还有\(x\)距离的地方. 然后矩乘就完事了. 没初始化矩阵为全0非常丢人. 递归的矩阵快速幂不能本地测真是蛋疼...也许我应该换一种写法了...
1054: 有人想写BFS吗?
5301: 莫队板子, 维护一个前缀和的桶
1029: 贪心 难度在于读题
1208: 非得把题目搞的这么恶心有意思吗...
2733: 线段树合并裸题...查询的时候忘了find真是丢人
4034: 树剖板子...乘的时候爆int了丢人
感觉最近写了一堆板子?
4326:
二分最大的时间然后对每一条超过时间的路径上的每一条边的次数都\(+1\), 然后在所有次数为\(\text{超过时间的路径总数}\)的边中找边权最大的一条修改为\(0\),
然后再用最长路径的时间减去这条边的边权看看是否不超过二分的值就完事了.
不用开LL真是良心. 我居然都不会写树上差分了丢人
CF733F: 显然把所有的钱花在一条边上比较划算, 先求一遍MST然后再枚举每一条边看看如果钱全花在他身上会比开始的MST边权和少多少, 我讨厌所有要求输出方案的题, 尤其是我都写完了才看见要输出方案...
4003: 这题看着就麻烦...如果把骑士\(i\)放到\(c_i\)上, 从下到上回溯的时候, 对于每个节点,
我们就可以在子树中找小于\(h_i\)的数,
这些数的个数就是在这个城市牺牲的人数, 把他们赋成INF,
在去掉的同时记录这个节点和\(c_i\)的深度差, 然后子树加或子树乘,
每个骑士只会被去掉一次...然而 \(c_i\)可能会重复...所以要在\(c_i\)下面新建节点而不是直接放在\(c_i\)上...
忘了在区间乘的时候修改区间加标记了...丢人. 被卡空间了...蛋疼.
dfs爆栈了...蛋疼
1935$=$4822: cdq分治板子...
4289: 神仙建图 建完直接最短路 蛋疼... 调了一上午加一晚上感觉并没有改什么东西...心血来潮交了一遍居然A了...绝了...我不知道今天发生了什么...
2929: 有人想写最大流板子吗?
4152: 众所周知我们没必要跨过某个点来连边 最短路打错了丢人
1112: 现在看套路已经很老了...枚举连续\(k\)柱的开头\(i\), 用对顶堆(要可以删除
如multiset<int>)计算\([i, i
+ k - 1]\)中的中位数, 用权值树状数组(下标\(a_i\)的节点值就为\(a_i\))计算比中位数小和比他大的数的和...忘取\(\min\)了丢人......丢人...
2809: 主席树...为什么这题A的人这么多...大家都喜欢写板子吗 = =
1798: 有人想写线段树板子吗?
1924: 把一行和一列当做一个点然后就是tarjan \(\times\)
dp的板子了...写起来略蛋疼...我居然还记得tarjan怎么写真是感动然而还是写挂了
3744: 分块板子...我一开始求成顺序对了...然后我...把整个序列反了过来23333, 忘了处理查找区间不包含任何一块的情况GG了...
1066: 网络流板子...一定要出这么个输入来恶心人吗...
1497: 网络流板子...据zyx学长说这玩意有更nb的做法 然而我忘了GG
3229: 有人听说过一个算法叫GarsiaWachs吗
4552: 套路题没想到真是太遗憾了
4033: 又是套路 左儿子右兄弟似乎写挂了...
1257: 是个神仙题...\(x \% i = x -\lfloor \frac{x}i\rfloor \cdot i\), 所以可以枚举\(\lfloor \frac{x}i\rfloor\), 然后做\(\lfloor \frac{x}i\rfloor\)相等的一段\(i\)的长度的等差数列求和, 公差为\(\lfloor \frac{x}i\rfloor\)
4516: SAM板子...加了文件还过了真是有意思(听说出题人一开始是想出SA神仙题然后大家都写的SAM? 算了SA写这个也不难...)
1207: 全网都是\(m^2\)跑过了我还想啥啊...嗯 第2048个AC的很舒服
4590: 嗯...啥时候SD也给整个这种题啊
1483: 启发式合并一下就好了 不知道为啥我要写set...
2648: 第一次见到卡cdq不卡kdt的...emm...