题面 首先考虑，如果所有圆的交是一个面积而不是一个点，那么一定不优。因为可以通过调整，把一些圆从交往外拖的方式，让交的面积进行很多次贡献，答案肯定变优。所以边界的交一定是一个点。 如图，我们现在相当于是在给每个圆分配一个角度（例如圆 $C$ 的 $\ang KNO$），使得角度的和是 $2\pi$ 同时面积的并尽量大。 对于同一个圆来说，如果半径和角度都确定，显然当 $ON,KN$ 相等的时候也就是对称的时候面积取到最值。这种情况下，也就是面积的上界是 \begin{aligned} S(\ ...

一个非常重要的观察： \sqrt{1 + x^2} < \sqrt{(1+x)^2}也就是，对于一个点，我们一定会找一个距离最近的有点的行最远的位置，如果有多个，就找是否存在一个位置最近的有点的行只有一边有点，且这里可以和这一行错开，这样可以让距离变大一些。所以，两个点实际上的距离可以变成以行号差做第一关键字，列号差做第二关键字的距离。虽然大致思路是这样，但是其实这个东西有很多细节，如果用 set 维护会显得非常难写，于是考虑线段树维护。 我们对每一个线段树的节点维护出这个节点所代表的区间内的 ...

首先在边上建点，于是距离就从 $k$ 变成了 $2k$。 距离变成偶数后，对于两个位置，它们可达的条件就是从其中一个走 $k$ 另一个走 $k$ 能到的点有交。 首先考虑以每个点作为中转点可以到达的点。也就是只要某一步到达了这个点就一定可以通过转驿站来走到的点。做法是把所有驿站加入队列距离设置为 $0$ 进行一次 bfs 。考虑当我们从一个点到达另一个已经访问过的点，那么这两个点所对应的联通块可以直接合并，因为总是可以通过这两个点的初始驿站互相到达。如果当前点与最近的驿站的距离已经超过了 $k$ ...

感觉这个结论题好神仙啊，开始还以为是 $\max,+$ 凸包之类的东西没想到是结论题。。 一个结论：对于一个选择 $k$ 个数的最优状态，一定不存在多于 $1$ 个序列被选了一部分。 我们设有两个序列选了一部分 $a_p,a_q$ ，同时设两个序列分别选择了 $t_p,t_q$ ，我们可以设 $a_{p,t_p+1} \le a_{q,t_q+1}$ 。 然后考虑，如果我们调整 $k$ 个数从 $p$ 到 $q$ 内，于是更改量就是 \sum_{i=1}^k a_{q,t_q + i} - \ ...

考虑这个限制本质上就是限制了 $i$ 在 $a_i$ 后被选，也就是如果从 $i$ 向 $a_i$ 连边，然后就是必须先选择祖先再选择儿子的一个选择点的问题，使得最后 $\sum{iA_i}$ 尽量大。如果存在环，显然无解。 我们考虑全局最小的点，我们显然可以把它合并到它的父亲上，因为在选择它的父亲后选择这个点本身一定是最优的决策。如果一直合并，我们会得到很多的联通块。但是如何确定两个块谁先被合并？我们考虑合并 $W,V$ 的代价： v \to u : \sum_{v \in V} w_vp_ ...

部分分很好做。如果任意两个展会都不在同一天举行，也就是对展会按照时间进行排序后，问题就可以转化成选择一个子序列，使得最后的权值尽量大。而且不难发现新加入一个点只和之前最后的一个点的权值有关，可以很简单地写出方程： f[i] = \max\{f[j] - cost(j,i) + w_i\}然后可以分成从上游来还是从下游来： f[i] = \max\{f[j] - (L_j - L_i) U + w_i\} (L_j > L_i)\\ f[i] = \max\{f[j] - (L_i - L_j ...

由于没有 OJ 只能写题意了 题意： 给定一个长度为 $n$ 的序列，求区间 $[l,r]$ 内的 $a < b$ 满足 $\frac{\sum_{i=a}^b A_i}{b-a}$ 最大 也就是区间和除以区间长度减 $1$ 尽量小。 显然可以考虑前缀和，然后就是 $\frac{S_b - S_{a-1}}{b-a}$ 。我们考虑每个点维护两类点，一类 $A(a,S_a)$ 一类 $B(b,S_{b-1})$。 然后问题就转化成了区间内选择一个靠前的 $B$ 类点，一个靠后的 $A$ ...

AGC006已单独开坑。 CF1083A显然，点权减边权最大的路径上不可能存在让油量变成 $0$ 的一段。所以找点权减边权最大的路径，这个可以直接 $dp$。 CF1083B首先，我们把 $s,t$ 都直接拿一遍肯定是前两步的最优操作。相当于除了 $s,t$ 的 $lcp$ 其他部分都拿了两遍。 然后可以直接把 $lcp$ 给丢掉了。现在，对于 $s$ 的每一个 $0$ 位置，我们如果在这里放 $1$ ，我们可以有 $1$ 个贡献为 $n-i+1$ 的串，一个贡献为 $n-i$ 的串，两个贡献为 ...

AGC002已经单独开题解写了就不放在这里了（ CF1179C看题就会了贪心。。最后那个线段树卡了好久。。不会找最后一个大于 $0$ 的位置是不是没救了啊。。 考虑贪心，我们把 $a_i,b_i$ 放到数轴上，然后从后往前扫。扫到一个 $b_i$ 就给维护的值 -1 ，扫到 $a_i$ 就 +1 ，也就是做一个类似括号匹配的东西。我们要找到的就是第一个位置，满足这个位置的值大于 $0$ 。 所以我们直接开一棵值域上的线段树。把 $b_i$ 的修改看成删除一个 $b_i$ 再加入一个新的，也就是前 ...

AGC001F已单独写题解就不粘过来了。 Gym101806T根据某知名贪心，先给 $L$ 加上 $D$ ，然后按照 $L$ 排序，可以得到一个正确的顺序，最后答案的序列一定是在这个顺序下选取的。 相当于我们需要选择一个最长子序列，满足这个子序列任意一段前缀的和小于等于这个位置的 $L$ 。 这个问题类似于 LIS 。有一种直接贪心的做法。我们考虑对当前位置，维护出满足当前位置以及之前所有位置的限制的的最长的子序列，且满足 $\sum D$ 尽量小。 我们用堆维护当前子序列中所有的 $D$ 。每 ...

AGC006D非常有意思的一个题。 直接做复杂度是 $O(n^2)$ 的而且看不出什么优化空间。 “中位数”的题往往和二分答案有关，因为这样可以转化成区间内 $0/1$ 的个数。这个题，可以先二分答案，设二分出来的值是 $x$ ，我们尝试判断第一层的数是否 $\le x$ 。我们把所有 $\le x$ 的数设置为 $0$ ，把剩下的数设置为 $1$ 。不难发现这个序列在进行操作后得到的序列的 $01$ 含义是不变的。现在我们转化成了一个 $01$ 序列进行操作，最后堆顶的数是 $0$ 还是 $1 ...

A STring操作这么多次。。显然能消的 ST 都没了变成了 TTT...TSSS...S 。不难发现其实就是括号匹配，直接拿栈匹配就行了。 B Minimum Sum按最小值来分治即可。每次贡献就是左右两端长度加 $1$ 的乘积。 复杂度 $O(n\log n)$，需要预处理 ST 表。 C Tree Restoring考虑这 $n$ 个数字中最大的，必然是直径长度。然后我们先把直径画出来： 不难发现，对于 $[\lceil\frac d 2\rceil,d]$ 的长度我们至少的有两个点， ...

神仙题。 考虑一个 $n$ 个点的树的情况怎么处理。 首先进行一次转化，树是一个二分图，于是就进行一次二分图染色。不难发现新图上两端颜色不同当且仅当原图两端颜色相同，所以我们可以把操作从同色翻转变成异色反转，也就是我们进行的操作其实就是在新图上移动黑色点。抄一个官方题解的图： 然后问题就变成了一棵树，有一些位置是黑色点，一些位置是白色点，我们每次要移动一个黑色点到相邻的白色点，最后要让所有黑色点归位。 对于树的情况，如果黑点白点数量不同，必然无解。 这是一个经典模型，首先答案是有下界的。我们随 ...

A Wanna go back home判一下 S,N ，W,E 是否同时存在或者同时不存在即可。 B Simplified mahjong考虑一种贪心，从 $1$ 到 $n$ 逐个操作，我们假定已经把 $1\sim n-1$ 给操作完了，并且 $1\sim n-1$ 的位置如果剩余奇数就会留下 $1$ 。对于 $n$ 这个位置，可以贪心一下，尽量和前面的剩下的那个先配对。如果这个位置是奇数，那么配对了必然是优秀的。否则，如果这个位置是偶数，那么这个位置本身就变成了奇数，只能往后操作，这里相当于 ...

AGC002C找到一个结两边和不小于 $L$ 然后把剩下的依次删除即可。如果不存在显然无解。 AGC002 D首先一种不动脑子的做法，直接建 kruskal 重构树然后二分 + 倍增跳即可。复杂度 $O(n\log^2 n)$ 。 然后，通过整体二分 + 可撤销并查集也可以做。但是可撤销并查集无法路径压缩，所以也是 $O(n\log^2 n)$。 然后其实是可以做到单 $\log$ 的。 如果我们按照 bfs 的顺序来做整体二分。如果当前加入的边超过了我们期望的边，那么就删掉所有边重做。不难发现 ...

首先考虑求出原排列的逆置换，设为 $Q$ ，于是交换就变成了如果 $|Q_i - Q_{i+1}| < k$ 那么可以交换相邻的两个元素。 于是，对于任意 $i,j$ 如果满足 $|Q_i - Q_j| < k$ 那么他们的相对顺序一定无法改变。 而且可以证明，如果两个排列 $Q,P$ 中所有元素的相对位置的关系是一样的，那么一定可以从 $Q$ 移到 $P$ 。考虑这种情况下的一次移动就可以让逆序减少 $1$ 。有限步的操作后一定可以让 $Q$ 成为 $P$ （画一下发现很对）。 于 ...

题目 首先嘛，这个 $b$ 放到这里就是吓人的，明显这个式子就是 \sum_{i=0}^n a^i \binom{nk}{ik}考虑 $a=1$ 怎么做，也就是 \sum_{i=0}^n \binom{nk}{ik}这个东西可以单位根反演，但是不难发现也可以循环卷积来做。也就是 (x+1)^{nk}在长度为 $k$ 的情况下做循环卷积的 $[x^0]$ 系数。 这个东西有一个优美的结论：在长度为 $k$ 的情况下做循环卷积等价于 [x^0] (x+1)^{nk} \pmod{x^k - ...

CF388D对于一个不同的线性基，对应着一种不同的 Perfect Set 。只要线性基能异或出来的数都得在 Perfect Set 里面。 于是考虑一个数位 $dp$ ，设 $dp[i][j][0/1]$ 表示当前考虑到了第 $i$ 位，已经有 $j$ 个位的线性基填过数，到现在最高位是否贴着上界的方案数量。 我们考虑第 $i-1$ 位。 $k = 0$ 这一位可以随便填或者不填。如果这一位填了 $1$ ，那么之前位的这一位都不能有值。转移系数是 $1$ 。如果这一位不填 $1$ ，之前 ...

P5901 regions按颜色数量进行根号分治。离线下来，对于出现次数 $\le \sqrt n$ 的点作为下方点的情况，我们处理出这个点到根路径上每种颜色数量，那么对于一次询问，我们只会在这个询问的下方点进行一次询问，这里下方点数量是 $O(\sqrt n)$ 的。然后考虑出现次数 $> \sqrt n$ 的点作为下方点。对于每个点处理出子树内的出现次数 $> \sqrt n$ 的点的数量，然后从每个上方点查询即可。每个点最多只会进行 $O(\sqrt n)$ 次这种询问。复杂度 ...

C 秋天的第一杯奶茶以下复杂度默认 $n,m,q$ 同阶。 考虑询问 $[x,y]$ ，差分一下就是区间 $[1,x-1]$ 的修改对 $[x,y]$ 的询问的影响（记作 $[1,x-1][x,y]$）。 然后可以直接莫队一下，这个往左往右加入拿 BIT 维护即可。复杂度 $O(n\sqrt n \log n)$ ，期望得分 $85\sim 95$ 、 这种东西的优化很类似于区间逆序对。考虑再次差分，变成 $[1,x - 1][1,y] - [1,x - 1][1,x - 1]$ ，也就是进行完 ...

草关机没保存。。重写一遍。。 CF1434D题解证明了答案的一端一定是直径的一端。 于是对每个点维护它到根的距离以及它到根的路径的颜色即可。相当于区间反转，全局 $0$ 位置最大值。线段树维护即可。 CF1423F$k > n$ 与 $k < n$ 的情况显然。 考虑一个不变的量，在修改前后 $\sum i a_i \bmod n$ 是不会改变的。于是可以猜这么个结论，并且手动打表后发现没啥问题。 CF1406E考虑先把所有小于 $\sqrt n$ 的质因子删除。然后枚举每个 $\ ...

密码不难发现取对就做完了。 挑战基本上一样的原题：Complete the Projects (hard version) 首先，对于 $a_i \le b_i$ 的，我们选择了也不会有什么损失，直接按照 $a_i$ 排序从小到大拿就好了。 对于 $a_i > b_i$ 怎么处理呢？可以猜几个贪心结论但是会发现都是错的。我们考虑，如果已经知道了要选择的物品是哪些，设为 $(A_i,t_i)$ ，其中 $t_i = a_i - b_i$ ，也就是在选择这个物品后所损失的血量。我们能否找到一 ...

CF576D Flights for Regular Customers考虑从小到大加入边，一个众所周知的结论是邻接矩阵的 $k$ 次幂就相当于走 $k$ 次后的路径条数。在这里我们只关心 $k$ 步后能否走到一个点，于是是 $01$ 矩阵。每加入一条边就进行一次矩阵快速幂，然后加入下一条边。 考虑如何计算答案。当且仅当加入一条边后在 $n$ 步内能走到终点，才说明可以走到终点，每加入一条边后判一下能否 $n$ 步内走到终点即可。 CF1187D Subarray Sorting大概有两个做法， ...

T1 食堂计划最短路图是一张拓扑图，并且只要再这个图上走出的路径就一定是最短路。 于是考虑一个 $dp$ ：设 $dp[u][v]$ 表示当前一个路径结尾在 $u$ 另一个在 $v$ 的方案数量。但是直接转移会出现重点。 我们考虑转移的时候限制如果从 $(u,v) \to (x,v)$ ，必须要有 $dis_u < dis_v \or (dis_u = dis_v \and i < j)$ 才行。唯一可能走出重点的情况就是其中一个点走到了一个根到 $v$ 路径上的点，但是如果这种情况 ...

（多数都是水题 最优贸易缩点，拓扑排序，然后考虑 $dp$ 出 Mn 表示 $1$ 到这个位置的最小买入价格，然后用在下一个位置卖出的收益更新一下 $dp$ 。 其中 $dp[u]$ 表示 $1 \to u$ 路径上最大的差价，用上面说的方式更新即可。 Road Construction缩边双，会得到一个树，不难发现链接两个点就把这两个点所在边双在树上的路径给合并到同一个边双。 然后发现拿叶子最优，然后可以猜结论答案是叶子个数除以二上取整。 每轮找公共祖先最靠上的缩起来就好了。 矿场搭建考虑缩点 ...

contest A 二次剩余明显，当 $|x-m| \ge 320$ 的时候，这个二次函数的值必然大于了 $10^5$ ，但是 $k \le 10^5$ ，于是我们往两边枚举 $O(\sqrt n)$ 个，对于每个值维护一个堆即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include "iostream"#incl ...

目前做的这四个题里面最神仙的一个。 考虑任意枚举一对合法点，然后画出下面这种图： 不难发现，直线上方的点之间距离必然不超过 $d$ ，直线下方两个点之间距离仍然不超过 $d$ 。 于是我们只用考虑上下点之间的关系，我们可以对上下距离大于 $d$ 的点连边，表示这俩点不可一起选。于是我们相当于求这个二分图的最大独立集，二分图的最大独立集就是最大点覆盖的补集，最大点覆盖可以在二分图匹配的网络上转成最小割做。 最小割输出方案：从 $S$ 开始在残量网络 dfs 一次，对访问到的点打标记，这些访问到的 ...

考虑对于一个位置，如果它不是 $s,e$ ，那么这个位置必然有一个入度一个出度。也就是说一个位置的方案有从右边进入，从左边进入，向左边出去，向右边出去。 我们考虑当前已经填完了前 $i$ 个位置，到现在为止还剩 $j$ 个向左的边和 $k$ 个向右的边。不难发现，如果这个点不是 $s,e$ 的一种，那么对于任何一种填这个点边的方案，要么使向左的、向右的边的个数同时 $+1,-1$ 要么使向左、向右的边的个数不变，分别对应： 然后如果新增的点是 $s$ ，那么只能是 如果新增的点是 $t$ ， ...

一个很妙的优化。 我们考虑 $\binom{x + y}{x}$ 的组合意义，是从 $(0,0)$ 到 $(x,y)$ 的方案数量。于是考虑这个式子本质上就是求 $(0,0)$ 到 $(a_i+a_j,b_i+b_j)$ 的路径数量。 这个东西看起来也不太能做。但是发现我们可以给它变成求 $(-a_i,-b_i)$ 到 $(a_j,b_j)$ 的方案数量。这个东西就可以 $dp$ 了，设 $dp[x][y]$ 表示 所有点到 $(x,y)$ 的方案数量。初始给 $(-a_i,-b_i)$ 设为 ...

考虑这个旋转操作，本质上就是把一个字符往左移动一些位。 如果两个字符串每个字符的数量相等，那么如果从左到右逐一归位必然可以构造出一组解，当然如果数量不同那肯定没法归位。 然后不难发现本质上就是一个匹配问题，我们固定一些 $S$ 中的位置，这些位置必须满足在 $T$ 中的相对顺序和在 $S$ 中一样，只归位剩下的，不难发现必然也是一组解。 相当于我们现在要找一个类似 LCS 的东西。但是会发现它和 LCS 是有差别的直接拿 LCS 不太对。因为当有一个 $S$ 中的位置和 $T$ 中的一个位置 $ ...