03-30

摘要： 前置知识 基环树，二分 思路 首先可以想到，选择集合次数应该被修改次数最多的点决定，所以题目实际要求是使最大操作次数最小。 经典二分模型，问题变为在每个点不超过 \(mid\) 的次修改后是否可以变为单调不降的序列。对于这个问题，考虑贪心，每个点都尽量选比前一个数大的最小值。先图论建模，对于每个值域 阅读全文

摘要： 前置知识 定积分（少量），分治。 定积分就是求函数 \(f(x)\) 在区间 \([a,b]\) 中的图像包围的面积。（有正负，\(x\) 轴上为正，否则为负)。 应用范围 给你一个定积分求它的值。 思路 考虑小学的时候如何求一些不规则的图形的面积，我们可以划分成规则的图形求出面积在加起来。 我们常 阅读全文

摘要： P9020 [USACO23JAN] Mana Collection P - 洛谷 首先我们可以发现贡献实际上是 \(ti_um_u\) ( \(ti_u\) 表示最后一次到达 \(u\) 的时间) ，但是最后到达性质没有最先到达好，所以将贡献转化为 \((s-ti_u)m_u\)（ \(ti_u\ 阅读全文

摘要： 前置知识 简单dp，循环，二进制。 应用范围 高维前缀和，子集和，超集和，FWT。 思路 我们以高维前缀和(注意每一位只有0/1)为例来思考。 高维前缀和 先给出一维前缀和的形式的求法。 for(int i=1;i<=n;i++) sum[i]+=sum[i-1]; 二维前缀和（非容斥写法，但是显然 阅读全文

摘要： A 只考虑特殊物品，然后枚举一下就好了。 B 被博弈论薄纱了，首先我们可以发现对于初始情况有两种是不合法的，比如有两对相等的值或有一对相等的值但是值减一是存在的，我们可以先特判掉这种情况，然后我们可以发现最后答案一定是变成 \(0,1,...,n-1\) 的样子结束，所以我们可以考虑中间操作了多少次 阅读全文

摘要： T1 其实是个简单题，但是我比较唐，所以导致一直没有用暴力打表，以为有更好的办法，所以导致浪费了大量时间，显然的是考虑有几组平行的直线，算它们对答案的影响即可。我们可以考虑为二维背包问题，用dp做就好了，时间复杂度有点不对，没关系，\(n\le120\) 打表就行了。 T2 更愚蠢的错误，首先我发现 阅读全文

摘要： AT_abc411_g [ABC411G] Count Cycles - 洛谷 题解 AT_arc200_c [ARC200C] Movie Theater - 洛谷 题解 CF2115B Gellyfish and Camellia Japonica - 洛谷 题解 CF1416D Graph a 阅读全文

摘要： 模拟网络流 对于一些题目，我们或许可以发现可以用网络流建模，但是一看数据范围网络流又跑不了的时候。就可以思考是否有特殊性质，用别的算法模拟网络流。 模拟最大流 最常用的套路就是最大流与最小割的互相转化。常用来模拟的算法有 \(dp\) 贪心甚至可以直接枚举。 CF724E Goods transpo 阅读全文

摘要： Day1 个人认为可能是最难的一天。 第一题是字符串，因为前段时间一直在加训 SAM，感觉SAM至少能做一些部分分出来，所以就可能思考了比较久的 T1，但是对于T1字典序最小的要求我只有一个时间复杂度比较劣的二分hash做法而且写起来非常的复杂，就留到了最后写。对于T2一开始是完全没有思路，在做完了 阅读全文

摘要： 平面图 定义 可以在平面内画出一个图而边没有任何交叉（公共端点相交不算），则是平面图。这种画法叫平面表示。 性质 设 \(G\) 是带 \(e\) 条边和 \(v\) 个顶点的连通平面简单图。设 \(r\) 为平面图表示中的面数，则 \(r=e-v+2\) 。（具体证明见离散6.7.2） 每个平面图 阅读全文