C\(n\timesm\)个人，选择某人的代价是\(a_{i,j}\)，可以使其负责其所在的行/列，问使得所有行列被负责最小代价。\(nm\le10^5\)。若选择\(a_{i,j}\)，看做是第\(i\)行跟第\(j\)列连了一条有向边，你发现最后图的形式是一个基环树森林。但是边是有向的，不难发现如果我们确定了基

C有\(n\)个点，一开始\(s\)点是白色，其余黑色，你可以花费\(p_i\)的代价使\(i\)点的颜色变成\(a_i\)点的颜色。若第\(i\)个点为白色，那么会有\(w_i\)的代价，问贡献减去代价最大是多少。\(n\le5000\)。不难发现这是一个外向基环树的形式。如果\(s\)不在环上，就是一个树

A给出一个\(n\)个顶点的有向图，求有多少个长度小于\(k\)的环（环可以经过重复的结点）。两个环不同当且仅当顶点序列不同。\(n\le35,k\le1e6\)。矩阵乘法模板题。枚举起点，求出走\(\lek\)步到达自己的方案数。只需要记录\(f_i\)表示以\(i\)结尾的路径个数，以及\(g_i\)

A你需要求\(n\timesm\)格子里随机撒\(k\)个点，期望扫多少次使得相邻的格子没有同时有点。\(n\timesm\le80,k\le20\)。直接状压求出方案数即可。B你需要维护一个数组，支持区间求和或执行覆盖操作fori:=ltordoa[i]:=a[i-k]或区间回溯成一开始的数。可持久化平衡

A你在平面上有\(n\)个点，你每次可以从一个点跳到其右下或左上任意的点，|对每个点\(i\)，求所有点到\(i\)至少跳多少次的和。点的坐标值域为\(M=2500\)。\(n\le2.5e5\).我们先考虑某个点，到所有点跳多少次。首先右下，左上都是跳一次即可。我们先考虑右上的点怎么办。我们一定

A每道题有做出的时长\(t\)，价值为\(k\)，你需要求最大的\(c(c\in[0,1])\)：若\(T=\sumt\)，设一道题做出的时间为\(x\)，那么分数为\(f(i,x,c)=k_i(1-\dfrac{cx}{T})\)，在分数和最大的情况下，任意一种办法，使得每道题最终得分大小关系和价值大小关系一样。\(n\le2e5\).明显的二

A一个字符串，你要选最多的区间出来，满足两两不交，且右边的区间必须是左边区间的严格子串。\(n\le5e5\).注意到答案是\(\sqrtn\)级别的。那么我们设计一个dp，设\(f_{i,j}\)表示\([j,j+i-1]\)这个区间以及右边是否能选出\(i\)个。转移只需要检查大区间减去左端点/右端点

A你有一个数组\(a\)，初始为\(0\)，你要使\(a_i\geh_i\)，你可以把任意相邻两个\(a\)，一个加一，另一个加二。问最少操作多少次。\(n,h\le1e6\)。B你需要求大小为\(n\)的环的个数，使得旋转后都不同。你可以选若干个点出来染上\(k\)个颜色中的一个，但是相邻两个点不能都能染颜

A\(n\)个点，有\(m\)种操作\((w,l,r)\)，代表贡献是\(w\)，并消除\([l,r]\)的所有点。操作的条件是必须消除一个点，问最多的贡献是多少。\(n,m\le300\).考虑从小区间开始操作，不难联想到区间dp。\(dp_{i,j}\)代表\([l,r]\)都被消除的最大贡献。对于\(dp_{i,j}\)，我们枚举

A一棵树，\(q\)次询问，每次给定\(x,d_x,y,d_y\)，你需要找到一个\(u\)使得\(dis(u,x)=d_x,dis(v,x)=d_y\)。\(n,q\le1e6\)。稍微转化为对于点\(k\)，找到一个距离为\(d\)的点，使得不走\(x,y\)这边子树。只需要求出每个点距离最远的几个点，且位于不同子树。因为要是存在距离

A一个圆上有\(2n\)个点，你需要选出\(n\)个点对连一条线段，其中一些点对已经被选。问所有点对方案中，联通块个数的和，联通的含义是线段相交，那么两条线段的端点都互相可达。\(n\le300\)。线段相交，把圆放到序列上就是区间相交然而不包含。我们拆贡献，计算每个区间\([l,r]\)的

A你每秒种可以施展一种秘籍\(\{a_i,b_i\}\)，使得后面\(a_i\)秒每秒都造成\(b_i\)伤害。问至少多少秒可以造成\(M\)的伤害。共\(n(n\le3e5)\)种秘籍，\(M\le1e18,a,b\le1e9\).显然可以二分答案，考虑二分\(mid\)，那么我们要造成最多的伤害。贪心，每秒都选择在\(mid\)秒

A已知一个字符串\(n\le1e3\)中的若干信息，：\((x,y,z)\)表示\(x\)后缀和\(y\)后缀的\(\text{LCP}=z\).求满足条件的字典序最小的字符串。已知\(a_{x+i}=a_{y+i}(i<z)\)，考虑维护并查集，一定相同的在一个集合。然后要处理的是\(a_{x+z}\neqa_{y+z}\)。从前往后填即可。

A有\(n\)个序列，每个序列长度\(m_i\)，每个序列的每个数有权值\(c{i,j}\)。\(\summ_i\len\le10^5\).A和B轮流行动，A只能选择一个序列获得其开头数的权值并删去，B只能选择一个序列获得其末尾数的权值并删去。问A,B分别最多获得多少权值。若所有序列长度为偶数，可以证

AAlice和Bob玩一个游戏，Alice先手。有一个长度为偶数的字符串，每次取出该字符串最前或最后的字符并删掉，并把该字符加入自己的字符串末尾。双方都采取最优策略，问谁的字符串字典序更小，或相同。区间dp.\(dp_{i,j}\)表示\([i,j]\)这个区间先手必胜/必败/平局。初始\(dp_{

A有\(n(n\le750)\)个正整数\((a_i\le10^9)\)，你需要删除一些数，使得剩下的数两两加起来都不为质数。若\(a_i+a_j\in\text{prime}\)（这里使用Miller-Rabin即可），将\(i\)和\(j\)连边。我们就是要求一个最大独立集。一般图是求最大独立集是NP问题。但是我们发现去掉所

t1火柴设计\(f[i]\)为\(i\)跟火柴最多的长度，\(g[i]\)为\(i\)根火柴应选哪个放在首位。考虑到前一位的重要性吊打后一位，显然让\(f[i]\)尽量大优先，不然就是\(g[i]\)取大。考虑记忆化搜索（DP）即可。#include<bits/stdc++.h>#defineintlonglong#defineMN100010