Ivanovcraft

摘要： $\large{\text{一千个Oier程序中有一千种树形DP}}$思路都差不多的，但是每个人都有自己的状态定义与转移不妨定义$dp[i][j]$表示，在$i$子树内，偷$j$张画，且不考虑根到$i$父节点路径代价的最短时间$a[i]$表示$i$与其父节点的距离$d[i]$表示$i$到根节点的距离 阅读全文

摘要： 专业跟队形唯一一个有$\LaTeX$的裸的$LCA$，我用的是$Tarjan~LCA$，注意两点相同特判 阅读全文

摘要： 一开始想写$DP$，发现直接转移完全有后效性所以本小蒟蒻写了个最短路每走三步就要吃草是这个题最难搞的地方，我们建图时不妨只对于距离等于三的点连边考虑完全覆盖所有情况，从一个点走一步，两步，然后三步，和直接走三步代价是等价的这样从每个点到与其曼哈顿距离为三的所有点连边即可考虑到终点的答案，对于所有小于 阅读全文

摘要： 暴力水过系列数据范围这么小，就打暴力吧枚举最大公共子矩阵的边长O(n)枚举两个最大公共子矩阵的左上角O(n^4)判断是否相同O(n^2)总复杂度O(n^7)，显然过不了过不了怎么办，删冗余枚举啊一堆优化：1，倒序枚举边长，一旦满足，即为答案2，判断是否相同，一旦不同，跳出去然后就过了 阅读全文

摘要： 个人感觉我的解法比官方题解好理解得多因为是任意一个法向量嘛，不妨设$x=1$然后解一个二元一次方程就可以解决了但是因为要求输出三个整数 代码 阅读全文

摘要： 题目巨简单，主要是给大家翻译一下 给n个数，其中存在1就输出HARD，否则输出EASY，不区分大小写 阅读全文

摘要： 看到全是线段树或者树状数组写法，就来提供一发全网唯一cdq分治三维偏序解法吧容易发现，这个题的查询就是对于每个区间l,r，查询有多少个修改区间li,ri与l,r有交集转化为数学语言，就是查询满足li<=r且ri>=l的修改个数一个二维偏序问题，但是我们发现，这是个动态插入的二维偏序问题_(:з」∠) 阅读全文

摘要： 容易算出这人第一次胜利的概率，第二次的，第三次的……好像可以无限乘下去但是这题精度卡到1e-6不妨设一个eps，当这次胜率小于eps时，就break掉，反正它已经不影响答案了我设的是eps=1e-12 阅读全文

摘要： 提供一种无脑DP做法题目中大概有这么些东西：位置，穿鞋，跑路数据小，那么暴力开数组暴力DP吧设dp[i][j]表示穿着鞋子j，到达位置i是否可行无脑转移枚举位置，正在穿哪双鞋，换成哪双走出去，走几步小的注意事项1，穿这双鞋不能到这个地方就可以直接跳过，它不能用来转移2，如果这只鞋不能满足在这个地方死 阅读全文

摘要： 容易想到，我们可以枚举所有长度为$k$的区间，算出把这段区间全部变成一个值的代价，对于所有区间取最小值即可1，把这段区间变成几可能能够猜出变成中位数，别人都是显然，只有我证了证（太弱了），给出一个简单的证明对于一个序列$S$，设它的中位数为x设序列中有a个数小于x，b个数大于x，c个数等于x设将这段 阅读全文