P7444 「EZEC-7」猜排列 这个是 $\textbf{2021.9.10}$ 未完成的最后一题。 就是先找找性质，发现 $f(0)$ 的时候本质上就是不包含 $0$ 的区间个数，不妨设 $0$ 在位置 $i$ 那么显然 $(i - 1) \times (n - i) = f(0)$。最多有两个这样的位置。 而且是对称的。 之后我们考虑进行 $\tt Dp$ 每次记录极大的区间也就是设 $f(i, l, r)$ 表示考虑了 $1 \sim i$ 的位置，极大区间是 $[l, r]$ 的方案数。 然后对于一个位置 $x$ 放在 $l$ 的左边的时候，可以满足 $c_i = (l - x + 1) \times (n - r + 1)$。 为了找到 $x$ 的位置显然 $n - r + 1 | c_i$。 如果出现 $c_i = 0$ 的情况，那么这个位置肯定只能放在 $[l, r]$ 中间，那么我们看一下是否能放即可。 直接讲一下优化，就是将之前的东西打表发现每一个 $dp$ 只有一个 $l$ 是有用的。我们不妨每次记录之前有用的 $l$ 然后用另外一个数组记录 $r$ 进行 ...

[USACO08NOV]Toys G首先可以网络流建图，但是因为 $n$ 的范围很大，所以我们考虑换一种方法。 首先考虑网络流建图的时候我们是考虑拆点之后进行跑流量，对于所有满流的情况我们计算一个最小费用。 我们对于这种情况不妨进行二分答案之后进行判断，显然我们二分的不能直接是答案。我们考虑那个条件我们知道了之后可以进行贪心或者 $\tt Dp$。总共就那么几个条件，只有购买了多少个是不知道的。那么我们就二分买了几个玩具。 简单思考可以发现对于买的玩具数量和花费是一个二次函数，下凸，进行三分。 具体贪心： 首先如果一个方案时间又短又优秀显然只用这个方案，不然两种方案肯定是一个时间短花费多，另一个反之。我们考虑用队列维护又多少没有消毒的，然后每次优先通过时间长的进行消毒，不然我们就使用时间短的进行消毒。 这里有一个问题如果放到了时间短的里面但是没有被使用，之后又可以放到时间长的里面了。 对于这个疑问，我们可以每次将时间短的来更新一下时间长的，之后每次将贡献放到被使用的时候计算即可。 1234567891011121314151617181920212223242526272829 ...

CF150E Freezing with Style 经典的更优复杂度不会，大众分都懂。 就是对于中位数的话进行树上路径合并很难处理，那么我们不妨二分中位数，之后将 $\ge$ 的数作为 $1$，否则就是 $-1$。那么合法的一条路径肯定是权值和 $\ge 0$。 前面取等号是题目的要求。 那么对于一条路径如果其长度是 $\tt len$ 那么我们合法的配对路径的取值范围就是 $\tt[L - len, R - len]$。 因为要使其合法所以我们只要使用这个区间的最大值就好了。如果我们将路径长度从大到小排序，那么这个区间就是逐渐向右移动，本质上就是一个滑动窗口问题。 那么我们合并就可以处理了，具体来说就是将之前子树的信息记录，之后枚举当前子树的中路径的长度（这里相同长度的路径显然只要考虑权值最大的一个）。每次更新一下滑动窗口的区间即可。 最后我们再将当前子树和之前合并就好了。 一些代码中使用的数组： $i$ 的最大权值的节点编号。12345678910111213141516171819202122232425262728293031323334353637383940414 ...

bzoj [Lydsy1708月赛]比特战争 其实不是那么想写，但是这题毕竟困扰了我很久，还是动笔了，可能笔者自己也没有很懂，希望大家能谅解一下。本文仅仅是自己的想法罢了。 对于一个连通分量我们可以考虑两种形式也就是要么其自己内部占领，要么是外面来的士兵占领。 如果是外面来的士兵肯定贪心得选取最小的边。 对于最小的边我们不妨考虑一下最小生成树，如果一个连通分量在最终情况下是被外部占领的，那么肯定是选择一个最下的边。如果其不被占领肯定又是一个子问题。 这里通过观察可以得到一个结论，对于最优的答案存在一种构造方案使得对于一个联通块至多只有最小的边被加入。 对于一个联通块如果是被别人占领显然是加入最小的边。 如果其是内部占领之后和其相邻的所有边都不会因为要占领这个联通块而被加入。 我们直接贪心枚举每条边的加入情况即可。 我们不妨考虑从小到大加边，每次更新答案。对于两个联通块其打通的最小花费是 $\max(\max(w, b_v), b_u) \times \min(a_u, a_v)$。我们维护两个值即可。 123456789101112131415161718192021222324 ...

CF855G Harry Vs Voldemort 根据 $\tt\color{black}{h}\color{red} ater$ 的话，这个东西放到现在有 $2800$。 显然恶评。 就是对于一个 $3$ 元组，我们发现本质就是树上两条路径合并的问题，那么我们像淀粉质一样将每个点作为 $\tt Lca$ 计算答案即可。 那么一开始的答案就是 $ans_u = (n - 1) \times (n - 1) - \sum_{v \in son_u} siz_v \times siz_v - (n - siz_u) \times (n - siz_u)$。 本质上就是考虑不取当前的点，任意的点对，为了方便我们就是考虑到 $(i, i)$ 这样的点对，反正也会减去的。 之后考虑加入一条边就是增加一个环，那么我们对于环中的每一个点的答案本质是相同的，我们对于一个环可以一起计算，不妨设其深度最浅的节点为 $u$，整个环的儿子集合为 $son$，整个环的元素个数是 $s$。 都在环上 $s \times (s - 1) \times (s - 2)$。 一个在环上 $2 \times ( ...

CF804F Fake bullions 说实话这题根据套路应该很容易做出来，但是感觉想要通过思维做出来 $\dots$ 一个二合一的题目。 $\tt Part\ 1$ 首先考虑题目给定的限制，如果 $u \to v$ 而且 $u$ 的第 $i$ 个人有金条，那么 $v$ 中第 $j$ 个人有假金条当且仅当 $S_ux + i = S_vy + j$ 根据 $\tt Lucas$ 定理可以得到符合条件当且仅当 $\gcd(S_u, S_v) | j - i$。 我们考虑这个的传递性，也就是 $\gcd(\text{path}(u, v)) | j - i$。对于竞赛图我们不妨考虑缩点之后再还原。 因为竞赛图缩点之后的特殊性质，每个点都向后面的所有点连边，所以可以直接根据拓扑序列进行计算。 对于一个点因为同余的性质可以得到 $ans_i = \dfrac{ct_{bel_i}\times S_i}{\gcd(bel_i)}$。 $\tt Part\ 2$ 之后我们可以求出每个点的最大值和最小值称其为 $mx_i, mn_i$。 对于一个集合 $B$ 最可能合法的情况就是集合 $B$ ...

CF1299D Around the World就是是否能有为 $0$ 的路径直接会想到线性基，也就是里面的环是可以走或者不走的。 我们写一手暴力发现大小为 $5$ 的线性基的个数不会很多，那么我们可以考虑对于每个联通块存一个线性基。 如果说联通块内部已经有环线性相关那么肯定是不能连边的。 如果线性无关那么考虑题目给出的性质，也就是和 $1$ 相连的环大小最多为 $3$。那么我们对于一个联通块最多有 $2$ 个点和 $1$ 相连。我们进行分类讨论有 $2$ 条边相连的情况。 断掉两条边也就是直接加入即可。 断掉一条边也是同理，枚举一下断掉那条边。 不断边，也就是意味着多一个 $3$ 元环我们需要将其加入并且判断线性关系。 不妨设 $dp(i, j)$ 表示考虑到底 $i$ 个联通块，之前的联通块的连接关系构成的线性基为 $j$。 设当前联通块的线性基是 $B$。 我们所有的情况都可以不加入，所以 $dp(i - 1, j) \to dp(i, j)$。 只有一条边 $dp(i - 1, j) \to dp(i, j \cup B)$。 如果有两条边$$dp(i - 1, j) \t ...

CF762F 其实这个题也不是很复杂。 首先题目背景里说的是一个联通子图！！！ 发现数据范围其实不是很大，我们不妨钦定一个节点为根$S$ 的节点。那么本质上对于 $S$ 中的每一个节点我们都需要对 $T$ 进行一次匹配。 显然因为是联通子图是不可能进行树哈希的，我们考虑进行树形 $Dp$。 不妨考虑设 $f(u, v, S)$ 表示对于 $u \in S, v \in T$ 的情况，已经匹配了 $T$ 中集合 $S$ 的方案数。 但是题目中说明的是无根树，如果再对于 $T$ 钦定一个根的话会产生有些形态没有计算的情况。 所以我们不得不考虑重复计算的情况，也就是一个情况能计算几次。本质就是一个和 $T$ 本质相同的树会被计算几次。 这两个相除即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 ...