T1

从0~n-1选k个互不相同的数,和为n的倍数求方案数,$k\leq 1000,n\leq 1e9$

集合划分容斥??单位根反演??

$\sum_{a_i=0}^{n-1}[a_1+a_2+a_3|n]$

$[k|n]$有代数式表达

$[k|n]=\frac{1}{k}\sum_{i=0}^{k-1}w^{in}_k$

证明?

等比数列求和可以知道是

$\frac{w^{kn}_k-1}{w^n_k-1}$

如果前面不成立,那么这个式子就等于0

否则你会发现后面每一项的值都是1,那么就是$k/k=1$

$[y^k]\frac{1}{n}\sum_{i=0}[x^i]\prod_{j=0}^{n-1}(1+x^jy)\sum_{k=0}^{n-1}w_n^{ik }=[y^k]\frac{1}{n}\sum_{i=0}^{n-1}\prod_{j=0}^{n-1}(1+w^{ij}_ny)$

这个左边式子是二元生成函数,我们$x^j$含义是我们的和为$x^j$,$y^k$的含义是我们现在选出多少个这样的数,然后单位根反演确保我们只把那些是n的倍数的x的次幂计入答案,y只有一次因此体现了互不相同

然后我们把$w_{n}^k$带入$x^i$,因为这个系数只能是0/1,同时这个只决定$x^i$系数,而我们关心的是$y^k$系数,所以直接带入即可了

$[y^k]\frac{1}{n}\sum_{i=0}^{n-1}(\prod_{j=0}^{\frac{n}{d}-1}(1+w^{\frac{ij}{d}}_{\frac{n}{d}}y))^d$

然后我们有经典结论

$\prod_{i=0}^{n-1}(x-w^i_n)=x^n-1$

这个式子含义就是我们左边的根都是单位根,右边的根也都是单位根,同时次数相同

$\prod_{i=0}^{n-1}(1+w^i_ny)=w_n^{\frac{n*(n-1)}{2}}\prod_{i=0}^{n-1}(y+w_{n}^i)$

这个提出挺神仙的,因为$w_{n}^i*w_{n}^{n-i}=1$

同时我们又有$w^n$是一个可爱的1,那么当n为偶数前面系数为负数,否则为正数,你感觉一下奇数的时候相当于$n*一个偶数$一定是一个n倍数,n为偶数的时候相当于$\frac{n}{2}*一个奇数$,一定是负的,反正就是一个$(+-1+-y^d)$

最后答案就是

$[y^k]\frac{1}{n}\sum_{i=0}^{n-1}(+-1+-y^\frac{n}{d})^d$

枚举这个d的取值,系数是二项式展开的形式,会对答案贡献$\phi{n/d}$次

然后你就会发现这个贡献其实就是我们之前某步省略了求和号,应该有这个求和号的!

T2

$n,k\leq 1e9 m<p\leq 1e5,pisprime$

首先我们能删就删一定最优,长度为k的连续段能操作掉一定不会更劣

$F(x)$表示我们的答案

$G(x)$表示有多少串自己能删空,但是不能被划分成前后缀删掉...就是$S=S1S2$,S1,S2都不可能被删空

那么有$F(x)=\frac{1}{1-G(x)}$,注意这里没有编号!!

插入k个字符,我们考虑这k个字符会把原来字符串划分成若干段,而且每一小段总可以内部删光,同时也是G类串!!

然后你会发现因为我们按照贪心会尽可能向前删,所以每一段的两头一定不能和最外层字符相同

证明：如果有一小块最外层字符和 S 相同，那么考虑这一小块内部的划分，把它和 S 结合一下即可划分成 S1+S2。否则如果 S 可以被划分成 S1+S2，首先断点必然在某一块之间，根据之前的贪心策略，这一块必然会有一个前缀可以变成更小的块，这与它“不能被划分”矛盾。

普通生成函数为F,G不可拆分的方案数,这里钦定和最外层字符与套在他外面字符不同

$G=(m-1)F^{k-1}x,F=\frac{1}{1-G}$

这两个是有限制的

最后答案就是$\frac{1}{1-mF^{k-1}x}$

因为最外面的字符是没有限制的

$\frac{(m-1)x}{(1-G)^{k-1}}=G$

$\frac{G(1-G)^{k-1}}{m-1}=x$

$H(x)=\frac{x(1-x)^{k-1}}{m-1}$

$H(G)=x$

扩展拉格朗日反演

$F(G(x))=x$

$[x^n]H(F(x))=[x^{n-1}]\frac{1}{n}H'(x)(\frac{x}{G(x)})^n$

这个数位dp就是一个从前向后dp的形式,然后考虑一下有没有进位即可,如果有进位显然是不会进多位的

就是后面那个东西用卢卡斯定理岔开变成若干个组合数的乘积

同样的c也能拆开

每一位大概都是独立的可算的,只有要么$a+i$是一个进位要么i卡到上界会有影响qwq?

糖果

有 n 个人和 m 种糖果，每种糖果分别有 ai 个，每个人每种糖果至多吃一个，最多吃 bi 种糖果。

有 q 次修改，每次可以把某个 ai 或者 bi 加 1 或减 1，每次修改后问是否存在一种方案使得糖果可以被分完。

n,m,q<=3e5

网络流暴力是n+m个点,然后中间连接满二分图,然后每个人都有$b_i$从s流过来,$a_i$流出去

并不需要这么麻烦,只需要贪心的把所有的糖果排序然后人从多的到少的选看这样能不能分完就好了

加入左边没有被割的集合为S,右边没有被割掉的为S

$|S|*|T|+\sum_{i\notin S}a_i+\sum_{i\notin T}b_i$

S*T是因为我们左边剩下多少右边剩下多少就必须割掉

考虑我们枚举这个S,那么$\sum {a_i}$就已经确定了

因为我们要最小割,所以每个b要不要加入的贡献确定,如果加入T产生S的贡献,加入T补产生b的贡献,所以按照$|S|$分开即可

然后怎么对于每个S去维护一个T

不难发现S一定是尽可能丢大的

然后考虑当S比较大的时候,会被丢进去,而当S大的时候他不会被丢进去

如果我们把答案写出来就是$|S|=i$时候的答案写出来

所以只有一个前缀加的影响

$b_i++$相当于在某个S大小$(b_i+1)$时,因为小于他我们会加入一个$b_i$,因此会对于一个答案数组的后缀去加入!

然后我们就可以知道$a_i++$或者$b_i++$都对应了前后缀加减

最后看看全局最小值是不是$a_i$即可

注意因为我们$a_i$排序后是一个阶梯型,又因为每个人本质相同,因此我们只需要对于一个阶梯的末尾的修改改为对于头的修改即可实现相同的效果,所以就能和相对大小不变一样了

普通高中生

使用一个随机数生成器生成序列 $a1,…,an$，生成 i 的概率是$\binom{M}{i} p^i (1-p)^{M-i}$。

给定一个多项式 f 在 $x=0,…,N$ 的点值，并且 f 是个不超过 N 次的多项式。

你需要求出这个随机的方式下，所有满足 $0<=bi<=ai$ 的序列 b，$f(b1+…+bn)$ 的和的期望。

$N<=1e5$

$n,M,p<=998244353$

如果p是一个下降幂的形式,k次那么我们就可以拆成k次的

$\sum_{i=0}i^{k\over}[x^i]Q(x)\\ =Q^{(k)}(1)$

下降幂多项式最经典的应用

你考虑系数实际上是$i^{k\over}a_ix^{i-k}$

再求一下k次下降幂其实就有了$a_i*i^{k\over}$

然后随机一次a之后取b的概率的生成函数$G(x)$

答案就是下面这个东西,其中f就是给定多项式的系数

$\sum_{i=0}^m f(i)[x^i]G^n(x)$

$G^{n^{(k)}}(x)$

相当于我们有n个G(x)排开,然后求导,所有方案乘积求和就是导数

实际上就是每个$G(1),G'(1)...$的对应系数的生成函数,然后求一个n次幂就是我们要的k阶导

$\sum_{i=k}^ji^{k\over}=\frac{(j+1)^{k+1\over}}{k+1}$

写出来

$1*2*3+2*3*4+.....n*(n+1)*(n+2)$

$=\frac{1}{4}(1*2*3*4-0*1*2*3+2*3*4*5-1*2*3*4....)$

裂项向消之后就没了

你可以看成离散微积分QAQ

$=\frac{1}{k+1}\sum_{j=k}^M\binom{M}{j}(1-p)^{M-j}p^j(j+1)^{k+1\over}\\ =k!\sum_{j=k}^M\binom{M}{j}(1-p)^{M-j}p^j\binom{j+1}{k+1}\\ =k!\sum_{j=k}^M\binom{M}{j}(1-p)^{M-j}p^j(\binom{j}{k+1}+\binom{j}{k})$

只看第二项我们有

$=k!p^k\binom{M}{k}\sum_{j=0}^{M-k}\binom{M-k}{j}(1-p)^{M-k-j}p^j\\ =k!p^k\binom{M}{k}\\$

然后我们把f插值成下降幂多项式即可....

给定0~n的点值可以直接插出下降幂多项式

$F(x)=\sum_{i=0}^nx^{i\over}a_i$

$F(x)=\sum_{i=0}^n\binom{x}{i}a_i*i!$

二项式反演??

$a_i*i!=\sum_{j=0}^{i}\binom{i}{j}(-1)^{i-j}F(j)$

我们已经有$F(j)$了,因此可以直接而得出来的

因此给出点值可以$O(n\log n)$

江苏省队集训卖弱

求有多少 n 个点 n 条边的有向图，每个点的入度出度都是 1，并且如果 i 到 j 有一条边，必须要满足 j 在 $[i-a+1,i+n-a-1]$ 中。

$n<=1e6,a<=200$

总共 10 组询问。

图一定是一个环

我们画出一个矩形

相当于在这两条黑线上下放上一些格点,使得每一行每一列都恰好有一个点涂黑

这个等价转换相当于行为起点的限制,然后列为终点的限制

这个a很小?

加入没有右上三角形的限制,我们只需要在上半部分选点,每行每列恰好一个

在下面都是a种方法,然后向上会变成a-1,a-2....一直到1.方案数是$a^{n-a}*a!$

设$f_{i,j}$为边长为i的等腰rt三角形里面选出j个格子的方案数,显然剩下的方案是挖掉若干列后的答案

直接容斥右上角选了多少个,因为我们相当那里面选了若干列,直接把他们扣掉$(a-j)^{n-a}(a-j)!(-1)^jf_{a,j}$

容斥式子应该还好,但是这个dp就很烦了...因为是满足限制条件的do

$f_{a,i}=f_{a-1,i}+f_{a-1,i-1}(a-i+1)$

还不错

于是我们一组询问只需要容斥即可

$O(a^2+n+Ta)$

（江苏省队集训）可爱

给定一个字符串 S，定义它的两个长度为 m 的子串相似，当且仅当这两个子串中至多有一个字母不同。

对于每个长度为 m 的子串，求有多少子串和它相似。

$|S|<=1e5$

$lcp+lcs(i+m-1,j+m-1)\geq m-1$

lcp是$lca$

考虑后缀树上启发式合并

当前要合并两颗子树,一个大一个小

因为lca固定,那么lcs要大于等于什么就已经知道了

建立反串的后缀树,那么对于给定一个后缀i,满足$lcs(i,j)\geq k$是一个子树内的点

那么你就会发现小的对于大的统计是一个二维数点,可以直接统计

而大的对于小的统计就是一个枚举小的然后矩形加,因为答案就是单点查询值+已经统计的值,因此这里二维差分一下即可

$O(nlog^2n)$

（江苏省队集训）担心

共有 n 个人参加比赛，这 n 个人站成一排。比赛采用单挑制，每次等概率选出两个相邻的人进行单挑，胜者保留，败者淘汰。每个人的水平是不同的，第 i 个人的水平是 ai。一场单挑如果在水平分别为 a 和 b 的人之间进行，那么前者获胜的概率是 a/(a+b)，后者获胜的概率是 b/(a+b)，不可能平局。这场比赛最终的胜者是最后剩下的唯一的人。

求第 k 个人最后获胜的概率。

$n<=500$

线段树式比赛

我们设$f_{i,j,k}$表示区间$[i,j]$,然后k赢的概率是什么

每次只会合并相邻两个人,所以k一定是在区间内向左打若干个向右打若干个,也就是说这个是独立的,相当于k要在两边分别win,可以把这个划分成

$f_{i,k,k}*f_{k,j,k}$

所以我们记$l(i,j)$表示左端点胜出的概率,$r(i,j)$表示右端点胜出概率

然后考虑这两个怎么计算

把$[i+1,j]$拆分成若干区间,每个区间的胜者都可以和1比

设最后一个区间为$[k,j]$,那么贡献就是$l(i,k-1)*\sum_{p=k}^jr(k,p)l(p,j)\frac{a_i}{a_i+a_p}$

你观察一下这个,我们要保证这两个区间能分裂开,也就是说能合并最后长度为a的区间和长度为n-a的区间,概率是$\frac{1}{(n-1)!}\binom{n-2}{a-1}(a-1)!(n-a-1)!=\frac{1}{n-1}$

相当于我们最后一次决策是固定的,前n-2次决策可以任意分配给整个操作序列,然后每一组内的决策也可以任意进行!

这个式子可以自行展开化简定是这样的

$l(i,j)=\frac{1}{j-i}\sum_{k=i+1}^jl(i,k-1)*\sum_{p=k}^jr(k,p)l(p,j)\frac{a_i}{a_i+a_p}$

相当于钦定左边区间给i打,然后右边区间枚举一个胜者再和i打被i爆锤了

交换求和顺序

$l(i,j)=\frac{1}{j-i}\sum_{p=i+1}^jl(p,j)\frac{a_i}{a_i+a_p}\sum_{k=i+1}^pr(k,p)l(i,k-1)$

我们计算$g(i,p)$表示右边那个式子,不难发现这个一定只会涉及l(i,j)子状态,就能$O(n^3)$了

string

给定一个只包含字母 A，B，C，D 的字符串 T。

用串 T 构造出一个新的串 S 的构造方法是进行多次操作，每次从 T 中选出一段连续的子串，加入到 S 的后面。

显然对于一个串 S，它的构造方法不止一种，所以定义 S 的构造代价为最少的操作次数。

求构造一个长度为 n 的串的最大构造代价。

n<=1e18,|T|<=1e5，保证 T 含有所有四个字母。

给定T,S怎么计算代价?

T建立sam,S每次贪心的在这个节点上跑,不行就回跳

那么现在相当于找到一个代价为i是最短的S长度是什么

然后考虑记录现在代价为i,下一个接上的字母必须为j,最短的S的长度

那么就可以变成记录(a,b)表示子串开头为a然后结尾为b的这样一个T中最短串长度是什么

然后这是一个矩阵,就可以矩阵乘法来优化这个dp转移了

$f_{s}$表示开头为s,然后代价为i的最短长度,转移就相当于枚举一个$min (s,k)$转移到$f_k$即可

硬币游戏

有 n 堆硬币，每堆恰好有三个硬币，从上到下价值分别为 $ai,bi,ai$（即第一个和第三个价值相同）。拿走一个硬币必须先拿走它上面所有硬币。

对于每个 1<=k<=3n，求出恰好拿走 k 个硬币获得的最大价值。

$n<=1e7$

拆成两个硬币,一个是$a_i$,一个是$a_i+b_i$代价为2,然后我们要选取代价为k

拆成$\frac{a_i+b_i}{2}$,代价为1

然后如果选了最大k个正好卡到两个1之间,我们就把前缀代价为1的最小值拿掉放进去或者后缀为1的最大值放进去弃掉另一个

撤回

给定一个字符串 S，有 Q 组询问，每组询问给定一个字符串 T 和四个正整数 a,b,l,r，求多少个 S[l,r] 中的子串 P 满足 lcp(P,T)>=a 且 lcs(P,T)>=b。

|S|,∑|T|,Q<=1e5

大概就是没有$[l,r]$限制,相当于对于S建立SAM,然后拿T长度为$a$的前缀匹配一下,会匹配到一个节点,然后只有所有这个节点的子树内的节点合法钦定为红点leftpos

同时对于长度为b的后缀也跑一下,也只有这些节点合法,钦定这些为蓝点rightpos

如果暴力我们就把这些位置都拿出,然后统计答案相当于对于一个蓝点统计前面有多少红点然后求和即可

注意如果a<b我们就reverse一下变成a>b的情况

然后我们去分块维护这个东西

散块之间

直接统计

零散之间

也很好算暴力散块然后直接做

块块之间

可以数点,算在某个区间内落在一个子树内的有多少个,可以离线一起算

整块之内

考虑建立一个虚树,然后统计树上两点子树之间的贡献

因为我们只需要定位一个前缀节点代表的子树后缀节点代表的子树两个子树内的两两的答案,而这个可以预处理$f(a,b)$表示a,b子树在这一块内的答案

你会发现相当于$f(a,b)=\sum_{v,u}f(u,v)$

这样的点对会有$O(n)$个,同时我们有$O(\sqrt n)$块,因此我们可以聪明的发现这样是$O(n\sqrt n)$

小学数学

有 n 桶水，第 i 桶里有 i 升水。你可以把一个桶中的水倒向另一桶，记它们的水量分别为 a,b，你需要保证 a>=b，且倒过之后两桶水会分别变成 a-b,2b。

你需要让尽量多的水集中在一个水桶里。

n<=100

首先一定不可能放满

如果都放满了,假设水量为$b*2^a$,b就是技术,每次一定会把一同水到一半加到另一桶上,所以所有桶都一定是b的倍数,有$b=1$

而总和为$\frac{n*(n+1)}{2}$所以如果其为奇数,上界为它-1,否则为它-2

这个上界可以被构造

这个操作相当于两桶水*2然后对于和取模

我们保持一号桶永远是1,二号桶永远是偶数,我们考虑把一桶水加入前两个桶,然后让一号桶达到2号桶的大小然后就翻倍了

然后我们把所有水豆尽可能的向12号桶集中,然后不断的在12之间操作倒来倒去,就一定能达到一个上界,即至多有两个1,到不进来了

原理其实和*2然后取模很像,此时2一定和一个奇数互质,不断乘下去就可以了

操作序列为$O(n^2)$

零一树

2-sat好题

考虑我们设$d_i$为i个树上前缀异或和

然后我们就有d_i\and d_j=0/1

你会发现这个东西很2-sat相当于我们只有异或边,a选0推出b选1,a选1推出b选0,然后也就是每一个连通块知道一个都能推出剩下的信息,拆点类似2sat建边即可

所以方案数就是2^(连通块个数/2-1),你再仔细想想这个东西因为根节点只能选择0,所以要减去1

但是如果暴力做这样要枚举那个$p_i$分界点,所以要分治,每次加入一半的边,可撤销并查集即可

最短路

给定一张 n 个点 m 条边的无向简单连通图，其中每条边都为白色。接下来，对于任意一对点，若在原图中它们之间的最短路为 2，则在它们之间连一条黑边。现在令每条白边的边权为 a，每条黑边的边权为 b，你需要求出在新图中从 1 号点出发到其它所有点的最短路。

$n,m\leq 1e5$

不妨假设原图最短路经过了k跳a边

在$b>=a$

最短路$\frac{k}{2}b+(k\%2)a$

$b<a$

我们只可能全是b,因为上面都只有一个a了

那么我们考虑再全是b的图上01bfs最短路,怎么做呢?

显然不能显式的吧边建出来,考虑隐式建图

考虑每次从队头取出一个点u,然后枚举u的连边v以及v的连边w,如果不存在$(u,w)$的边,我们就把w更新加入队列并删除边$(v,w)$

这个过程等价于三元环计数的过程,同时每次都必然干掉一条边,因此总复杂度是$O(m\sqrt m)$

匹配

有 n 种糖果，每种糖果恰好有两个。现在这 2n 个糖果排成一排，但是你分不清这些糖果哪些是同一种了。有如下两个操作：

1.往口袋里放一颗糖果

2.从口袋里拿出一颗糖果

每次操作之后你都可以知道当前口袋里有多少种不同的糖果。你需要在 $10^6$ 次操作内给这些糖果两两配对（即找出所有同种的）

$n<=43000$

我们可以扫一遍都加入知道每个位置是糖果第一次出现还是第二次出现

然后他们分成两部分,设为第一部分第二部分

然后分治对于第二部分切一半扔进口袋里,然后判断第一部分的哪些糖果出现在里面,如果扔进去总种类数不变说明在左半边出现过否则在右半边

然后把在右边的询问丢到右边在左边的丢到左边相当于整体二分

但是要卡一下常数,就是每次取反一半的状态,然后去判断左边,每次不清空口袋才是$\frac{nlogn}{2}$

这样还是过不了,我们要分析一下切在哪最优,稍稍向左切一点点,就是$(3-\sqrt5)/2$处切最优...

机器人

有一个 n*m 的网格，有些位置上站了机器人，机器人都有朝向，并且视野范围如下：

每个机器人可以最多转 90 度，你需要算出至少转多少个机器人可以使得不存在两个机器人可以互相看见，并给出一组方案。

$n,m<=2000$

考虑我们先把整个图旋转45,然后机器人看的就是一个整的角了,那么只有左下看右上或者左上右下

然后结论就是这个可以分别做,然后加起来就是对的

如何证明?

考虑如果有一个点向右上他要转走,他向左下转看到了一个人,向左上转也看到了一个人,那么你会发现此时这两个人一定能够相互看见,也就是有一个一定会转走,这个人就一定有一个合法方案转了

只有左下和右上怎么办?考虑钦定

你发现就是一个二维dp,找到一个轮廓线,下面朝左下和上面朝右上的尽可能多

然后怎么构造方案啊?

看看那些不动

不动的机器人就不动,动的机器人考虑钦定一个方向,能向左上就左上否则就向右上转,其实就是优先向一个方向转啦

鸽子

求有多少个严格递增的序列 xi，满足 x1=2，且对于任意的 i,j，都有 $x_i^j<(x_j+1)^i$。

答案对一个质数取模。

$n<=1e10$

$2^i\leq x_i<3^i$

$x_i^{\frac{1}{i}}<(x_j+1)^{\frac{1}{j}}$

对于每一个i,$2^i~3^i-1$在$\frac{1}{i}$都可以对应[2,3)区间里一个实数

那么我们一定可以找到一个分界线,使得左边都是黑点右边都是红点

对于一个红点你会发现一定能找到一个分界点使得x和x+1跨过这个区间

因此对于每一个i都能找到,所以最后小区间好答案是一一对应的

考虑求多少个不同的$x^{\frac{1}{i}}_i\in[2,3]$

dp,考虑第i个数会新增多少

$f_i=3^i-2^i-\sum_{j|i,j<i}f(j)$

$f_i=\sum_{j|i}\mu(\frac{i}{j})(3^j-2^j)$

这个是莫反形式可以直接算

$\sum_{i=1}^n\sum_{j|i}\mu(\frac{i}{j})(3^j-2^j)=\sum_{j=1}^n(3^j-2^j)\sum_{ij<=n}\mu(i)$

图

给定一张 n 个点 m 条边的无向联通图和其中一棵生成树，要求删掉正好两条树边和一些非树边，使得图不连通。求最少删掉几条非树边。保证以 1 号点为生成树的根时，非树边的两端的最近公共祖先是 1 号点。

$n,m<=1e5$

考虑连通块会被隔出来,然后

对于根的两颗子树,加入我们割的是两条子树的父边

那么只有这个子树连到外面非另一颗子树的会被算入答案

$f_i+f_j-g(i,j)$,g(i,j)表示子树i,j之间的连边

加入一个点,对于右边的子树贡献是多少

相当于对于右边到根的一条链集体减等于2,然后算右边的全局最小值

对于右边树链剖分,相当于区间加,我们每个线段树记录所有修改信息即可

然后线段树合并得到一整个子树信息,就可知道右边每一个节点的权值

这个区间加有$O(nlogn)$次,所以复杂度为$O(nlog^2n)$

空间时间是同阶的

ARC080F

有无穷个硬币，初始有n个正面向上，其余均正面向下。
你每次可以选择一个奇质数p，并将连续p个硬币都翻转。
问最小操作次数使得所有硬币均正面向下。

n<=200

不妨考虑差分

差分后1的数量一定为偶数,问题变成两两配对使得操作次数尽量少

那么你会发现一次操作会翻转两端l-1和r

1. $|i-j|$为奇质数那么就1步
2. $|i-j|$如果为偶数,一定两步(2=5-3)
3. $|i-j|$为奇非质数,三步(1=7-3-3)

2,3都是哥德巴赫猜想...

(猜想没有被推翻就是正确的)

于是我们把奇偶性变成二分图,然后希望1的情况尽量多就二分图匹配一下,然后剩余的尽量用2,否则没消完就补一次3

代码参考At三题

ARC076F

我会优化建边然后二分图匹配

如果只有 l 的限制，那么显然是按照 l 排序之后每次选最小的没有被占据的。

我们仍然按照 l 排序，每次选最小的没有被占据的，如果没有这样的位置，那么就考虑把之前的一个人“替换”出来，需要被替换出来的人的 r 比当前的 r 小（这样替换出来才有更多的选择空间），如果有多个满足要求显然应该替换 r 最小的出来。

操作完之后还剩下若干个人，并且此时被占据的位置一定是个前缀，因此我们按 r 从大到小排序再贪心即可，此时坐不下的人就没办法了。

可以使用小根堆维护，复杂度 O(n log n)。

Hall定理

hall定理还有一条推论:二分图$G$的最大匹配为$|\rm X|-\max(|X'|-|Nb(X')|)$

|S|-(m-|\and i\in S|)=|S|+|\and i\in S (l_i,r_i)|-m

k个人选不到

等于任选t个人,总有$右边的对应人+k\geq t$

对应人s就是最大的L和最小的R来计算

然我们枚举一个l,在当前的人里面选择t个使得$n-r-t$最小,线段树维护每一个r的对应答案,每次加入一个人相当于区间-1,那个人对应的位置和之前的所有r都减少1,最后询问全局最小值即可

其实就是枚举的L,然后再对应看看哪一个R能最小,因为是任意所以我们找到的是最小值

如果这个最小值都是小于等于0的说明一定可以

代码参考At三题

网格

n*m 的网格，有些格子上有村庄，保证第一行第一列是个村庄。

你需要在格子的边缘上建篱笆，每个格子的每条边都有一个代价，你需要让篱笆形成一个圈把所有村庄围住。

注意一条边两侧可以建两个篱笆，但需要付出两倍的代价，如下图。

你要让花费的总代价最小（例如上图）

$n,m<=400$

太经典了

拆成4个点

把所有村庄设计的点和最短路经过的点全部删除

然后把他们跑一个从左上第一个点到左上第二个点的最短路即可

考虑如下的结论：把所有村庄的左上角到整个网格的左上角的最短路全部标记出来，则必然存在一种最优方案使得篱笆包含了全部的这些最短路。

假设最终答案的区域没有包含所有的最短路，即如右图：

显然把黄色区域添加进去不会使答案变劣。因此不断这么操作就可以把所有最短路都添加进去。

于是可以考虑把每个格点分成四个点，如右图，然后最短路经过的边断开（村庄所在的网格四个点删掉），跑一遍最短路即可。

总复杂度 O(nm log nm)。

AGC018F

给定两棵带标号的有根树，你需要给每个点赋权值，使得每棵子树内部的权值和为 1 或 -1。给出方案或报告无解。

$n≤10^5$

可以算出两棵树上每个点最终的奇偶性!如果对应奇偶性不同就一定无解

一个点是偶数直接权值设置为0

不包含他自己,如果子树内权值为奇数的点一定可以两两配对

就是每棵子树内部先匹配一下如果还剩下一个点没有匹配,就拿出一个点和子树外的点匹配

除了当前一个点,剩下的点权值和都是0,一棵树是满足的,那么两棵树也是一样

我们把一对匹配点连边，把两棵树对应的图合起来，容易发现这是个二分图（因为不会有相邻的两条边来自于同一棵树）。

因此直接黑白染色，黑点填 1，白点填 -1 即可。

做法就是我们把两棵树分别dfs,然后对于奇度数点,直接填0放弃掉,然后子树内两两匹配,拿到最后一个剩下的独立点

然后对于偶度数点,因为每个子树内都只剩下一个独立点,因此把这些点两两匹配,然后拿掉,这个点成为独立点

然后两棵树都这样做,最后把每个匹配成功的连边,然后二分图染色即可

这样一定是二分图,因为一个点在一张图上只会连一条边出去,然后只能通过另一张图的边连回来,又因为我们只有两张图,因此只能有偶环