You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

519 lines
12 KiB
Plaintext

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

基础(65)
巨水无比(4):
1214、3816:2B题; A
1000A+B; A
2462:输出10个1 A
模拟/枚举/暴力(15):
4063傻子模拟; 消失了
1968小学生暴力; A
1218前缀和暴力; A
3856读英文; 消失了
4106直接算; 消失了
1800暴力判断; A
2208暴力判断(要会邻接表); A
1028枚举; A
1789&1830高能暴力; A
2241暴力; A
2120神奇的暴力; A
4145子集暴力; 消失了
4029模拟处理; A
1086DFS树; 不会
1224暴力; A
3444暴力判 A
人类智慧题(17): 以下全是抄的题解
2463输出0或1; A
1192找规律; A
1413奥数; 不会
1432找规律; A
4001数学; A
1022简单博弈; A
2005暴力数学; A
2659数学; A
2173找规律; A
4147手推博弈; 消失了
1228SG函数打表找规律; 不会
1045&3293中位数; A
2222纯手算; A
2467找规律打表; A
3505组合数; A
3858处理小范围 消失了
高精度Python(11):
1213高精度开根;
2656回溯高精度;
2822递推高精度;
2729组合数高精;
1002递推高精;
1089各种高精运算;
1263贪心+高精度;
1876高精度求最大公约数;
1416&1498高精算概率;
1970暴力+高精
排序/贪心/二分(10):
4143排序后判断; 消失了
3850排序后贪心; 消失了
1034贪心; A
2563转化思想后排序; A
3170排序后处理;
1816二分后判断; A
3969二分+贪心; 消失了
1082排序后二分判断;
3671贪心+暴力
其它水(7):
3098卡哈希; A
3214字符串处理;
2456特殊方法; A
2751去重;
2048小范围暴力大范围乱算; A
3668按位处理; A
2660递归计算
图论(91)
搜索(8):
1054BFS; A
1024DFS; A
1295暴力+BFS; A
1053搜索(数学证明);
1306剪枝;
3680模拟退火裸题;
1085A*;
2428模拟退火
最小生成树(7):
1083模板题; A
1821、2429裸题; A
1196二分+最小生成树; A
1050; A
3732+树上倍增;
3624最小生成树+贪心
最短路(14):
1491Floyd+统计; A
1003DP+最短路; A
4152排序后最短路; A
2435DFS找负环; A
1486DFS找负环; A
1001网络流->最短路; A
2763、2662分层图+Dijstra+堆;
1880最短路+拓扑; A
2118转化后最短路;
2165倍增Floyd;
3875SPFA维护DP;
2330差分约束; A
3436差分约束+判负环; A
4144Dijkstra建树处理 消失了
二分图(9):
1854、1191裸题; A
1059、1433SB题; A
3175、2150最大独立点集;
1562二分图求DFS序;
1143Floyd+二分图;
2539KM
网络流(33):这部分比较重要,每道题写出连边方法,方便以后看
1412:源点向所有羊连无穷边羊向狼连流量为1的边所有狼向汇点连无穷边跑最大流
1066:源点向每只蜥蜴连1的边蜥蜴向每个能到的石柱连边如果蜥蜴能到边界向汇点连无穷边跑最大流
1497:裸最小割,源点向所有客户连流量为收益的边,客户向选择的中转站连边,中转站向汇点连流量为花费的边,答案即为总收益减去流量
2561:加入的边为u,v长度L则所有长度大于L的边不能使得uv连通求个最小割即可小于同理
2768、1934:源点向所有资磁切尔西的连流量为1的边所有不资磁切尔西的向汇点连流量为1的边然后每一对朋友互相连流量为1的边跑最大流即可
4177:源点向所有i连一条流量为ai的边表示养牛;
所有i向汇点连一条流量为bi的边表示养羊;
对于每条规则(i,j,k)i和j之间互连流量为k的边;
对于每个(S,a,b)新建一个节点如果a表示养牛源点向该节点连流量为b的点该节点向S中所有点连流量无穷的边;
如果a表示养羊该节点向汇点连流量为b的点S所有点向该点连流量无穷的点答案即为Σa[i]+b[i]-流量
3504:正向跑一遍,反方向再跑一遍最大流,判断即可
2007:懒得看了、、似乎网络流的话要姿势比较好,应该是最短路
3931、1266:最短路判断每条边是否可能在最短路上,若可能则加入,变成最小割模型,跑最大流即可
1565:如果A保护B那么就连一条A-->B的边然后对这个图做拓扑序把环给去掉然后对剩下的点建图如果A保护B则连一条B-->A流量为无穷大的边如果A的点权>0则连一条S-->A流量为A的点权的边如果A得点权<0则连一条A-->T流量为A的点权的绝对值的边就变成了最小割模型用sum-流量即可
2039:源点向每个员工连流量为收益的边每两个员工之间连Ei,j*2的边每个员工i再向汇点连ΣEi,j的边得到最小割模型答案即为sum-流量
1797:首先求一个最大流。有可能在某个最小割中的边(u,v):满流删掉之后在残余网络中找不到u到v的路径。一定在所有最小割中的边(u,v):满流s出发沿残余网络能到uv出发沿残余网络能到t。在残余网络中tarjan求强连通分量。(u,v)两点在同一SCC中说明残余网络中存在u到v路径。s和u在同一scc说明s能到ut和v同一scc说明v能到t。
1305:二分答案ans每个男孩拆成两个点ai和ai'每个女孩拆成两个点bi和bi'源点向每个ai连一条流量为ans的边每个bi向汇点连一条流量为ans的边如果男孩i喜欢女孩jai向bi连一条流量为1的边否则ai'向bi'连一条流量为1的边每个ai向ai'连一条流量为k的边表示最多和k个不喜欢的女孩跳舞;每个bi'向bi连一条流量为k的边如果流量=ans*n则可行l=mid+1,否则r=mid
1189:二分答案time源点向每个人连流量为1的边把门拆成若干个点表示在t时刻可以通过1人每个点向汇点连流量为1的边人向每个time时间内能到达的门连边跑最大流判断是否能让所有人通过即可
3993:二分答案ans源点向每个B连ans*b[i]的边B向每个能打到的A连无穷边A向汇点连a[i]的边若流量等于Σa[i]则符合条件,向下面找,否则向上面找
3158&3275:发现两两关系只会发生在奇数特征值和偶数特征值的点之间,源点向所有偶数特征值的点连流量为价值的边,所有奇数特征值的点向汇点连流量为价值的边,所有偶数特征值的点向有冲突的奇数特征值的点连流量无穷的边,就变成最小割模型,答案为所有收益-流量
1061:神奇的建图,用单纯形做简单点、
2245:源点向每类产品连流量为Ci的边每类产品向能生产该产品的员工连无穷边每个员工在每一段上向汇点连t[i]-t[i-1]流量w[i]费用的边,跑费用流即可
1927:拆点源点向i连一条流量为1费用为0的边向i'连一条流量为1费用为ai的边i'向汇点连一条流量为1费用为0的边;对于每条通道x,y,z假设x<y从x向y'连一条流量为1费用为z的边然后跑费用流
3171:拆点如果相邻两点可以通达i向i'连一条流量为1费用为0的边否则连一条流量为1费用为1的边源点向每个i连一条流量为1的边所有i'向汇点连流量为1的边然后跑费用流
2424:拆点源点向i连一条流量无穷费用di的边表示订货i向i'连一条流量无穷费用为0的边所有i'向汇点连流量ui费用0的边表示卖出所有i向i+1连一条流量S费用m的边表示存储费用然后跑费用流
3130:第一问裸流第二问二分答案每条边的流量为min(z[i],now)如果仍然能满足最大流等于原来值那么r=mid否则l=mid+1
1834:第一问裸流,第二问直接在剩余网络上做费用流
3876:对于每一条边权为z的边x->y:从S到y连一条费用为z流量为1的边 代表这条边至少走一次从x到y连一条费用为z流量为INF的边 代表这条边除了至少走的一次之外还可以随便走。对于每个点x:从x到T连一条费用为0流量为x的出度的边从x到1连一条费用为0流量为INF的边代替原图上的源和汇
1877:拆点源点为1'汇点为n对于每个i和i'连一条流量为1费用为0的边表示只能走一次对于每条有向边(x,y,z)从x'向y连一条流量为1费用为z的边然后跑费用流即可
1221:拆点源点向每个i连一条流量无穷费用f的边表示直接买毛巾每个i向i'连一条流量无穷费用0的边每个i'向t连一条流量为ni费用0的边表示需要的毛巾;
每个i'向i+a连一条流量无穷费用fa的边表示快洗;
每个i'向i+b连一条流量无穷费用fb的边表示慢洗
1070:把M个技术人员拆成N个点第w个点表示给第w个顾客修车时所有顾客需要多等待的时间每个顾客j向每个技术人员mi连一条流量为1费用为k*a[j][i]的边,表示每个顾客对后面顾客造成的影响;源点向每个顾客连流量为1的边每个拆出来的技术人员向汇点连一条流量为1的边
2849:和上题差不多不过每条边要动态加否则要T
1449:假设后面M场比赛两方都是输的对于后面每场比赛每赢一场的收益增加值add=c[i]-(win[i]+1)^2+d[i]-(lose[i]-1)^2-[c[i]-win[i]^2+d[i]-lose[i]^2=2*win[i]*c[i]-2*lose[i]*d[i]+c[i]+d[i]之后win[i]++,lose[i]--。源点向每场比赛连流量为1费用为0的边每场比赛向双方连流量为1费用为0的边每支球队按照上述方法连每条边然后求出费用加上原来收益即可
2668:对于每个点一分为三分为p0,p1,p2对于每个点
如果它是原图中得黑点,连边<p1,p0,c/2,0><p0,p2,(c+1)/2><st,p0,1,0>;
如果它是新图中得黑点,连边<p1,p0,(c+1)/2><p0,p2,c/2,0><p0,ed,1,0>;
如果它在两个图中都是白点,那么连边<p1,p0,c/2,0><p0,p2,c/2,0>。
这样就可以体现出点容量的差异了。
然后对于原图中可以交换的两个点(i,j)连接<pi2,pj1,inf,1>
那么这种边每流过1的流量就意味着(i,j)交换了一次,那么费用就是最终的答案了。
拓扑(3):
4010最小拓扑序;
2535&2109拓扑逆向加边
tarjan(5):
1051:直接tarjan判断强连通分量个数是否为1; A
2438:缩点后ans=入度为0的连通块个数倘若存在只有一个点的连通块它无出边或出边指向的点均能被其它点到达则ans-1; A
1179:缩点后求点权最长路; A
1093缩点后DP统计方案;
1823 2-SAT
树(11):
2783树上DFS+倍增;
1509树上最长链; A
1912两次树上最长链; A
2657奇怪构图后树上最长链;
1787LCA;
2152点分治;
3991虚树动态统计;
2286、3572虚树DP;
1005、1211Prufer编码 A
数据结构(69)
并查集(3):
1015倒着加入并查集; A
1202维护一个数组记录差值; A
4195傻逼并查集 A
基础数据结构(4):
1483链表启发式合并;
1007、3190单调栈;
1293单调队列 A
堆/RMQ(7):
1029贪心+堆; A
1216堆; A
2006RMQ+堆;
1047二维RMQ;
2809可并堆;
2333可并堆各种操作;
4198哈夫曼编码 A
哈希表(4):
1567二分+哈希判重;
3555哈希后排序判断;
3916分类哈希;
3751HASH解方程
分块(8):
2957傻逼分块;
2141、3295动态逆序对;
3744在线求逆序对数;
2821分块+二分;
2038莫队;
3289莫队+树状数组;
3720块状树
树状数组(5):
1012裸题; A
1452三维树状数组;
1878、2743离线树状数组;
1176CDQ分治+树状数组
线段树(3):
1798、3212线段树Lazy;
1067线段树判断
平衡树(17):
1588、3224、1208基本操作;
1503权值操作;
1056、1862Tire+Splay;
1661简单区间操作;
3223、3506Splay翻转;
2733Splay启发式合并;
1858、1500Splay各种操作;
2752平衡树维护多个信息;
1057Set;
1269、1507Rope;
3673、3674可持久化Rope
可持久化(2):
2588DFS序+可持久化线段树;
3123DFS序+可持久化线段树+加边+启发式合并
树套树(2):
3110区间线段树套权值线段树;
3196树套树各种基本操作
K-D树(4):
1941、2648基本操作;
4066K-D树的重建;
3489转化后三维K-D树
树链剖分(3):
3631树剖简单裸题;
1036树剖基本操作;
2243树剖染色;
4196傻逼树剖
LCT(4):
2002、2049LCT裸题;
2157LCT复杂操作;
3669LCT各种操作;
3091LCT各种操作+平衡树维护多个信息
字符串/计算几何/博弈论/其他(19)
KMP(2):
3670KMPnext维护;
3620暴力+KMP
AC自动机(4):
3172模板题;
1212AC自动机+DP;
1030AC自动机+DP;
1444AC自动机+矩乘
后缀数组(2):
1031基本题;
3238后缀数组+单调栈
后缀自动机(3):
3998第K小子串;
2754广义后缀自动机;
3926暴力Tire构建广义
后缀树(1):
4199后缀树裸题
凸包(1):
1027凸包+最短路
随机增量(2):
2823最小圆覆盖;
3564转化后最小圆覆盖
博弈论(1):
1188SG函数
三分(3):
3330三分套三分+保留位数输出;
1857三分套三分;
3874单调性贪心+三分
数论(34)
扩展欧几里得(1):1407
线性筛/欧拉(6):
1607线性筛因数;
3288、2190、2818线性筛欧拉函数;
4173、2705logn求欧拉函数
快速幂/矩阵乘法(9):
1008快速幂; A
1965、2751快速幂+快速乘;
1297、1898图上矩乘加速;
2875、2426矩阵乘法;
1875矩乘拆边构图;
1009KMP+矩乘
高斯消元/线性基(9):
1013、1923高斯消元;
3143高斯消元求期望;
3105、2460、4004拟阵+线性基;
2115找环+线性基;
2844拟阵+线性基;
2337期望高斯
置换群/Poyla(1):
1004置换+背包逆元
裴蜀定理(2):
2257、2299裴蜀定理
BSGS(1):
2242快速幂+逆元+BSGS
卢卡斯定理(1):
1951卢卡斯+孙子;
2111排列组合
莫比乌斯反演(2):
2301容斥+莫比乌斯反演+前缀和;
3994莫比乌斯反演+前缀和
FFT(1):3527模板题
DP(71)
基本DP(31):
2748小学题;
1088初一题;
1207初二题;
1037初三题;
1296、1260基本区间DP;
1025筛DP;
1197SB题;
1084选择DP;
1032错误DP;
1055区间DP;
1042背包DP+容斥;
1806多维DP;
1237递推;
1925、2431DP+前缀和优化;
3174贪心+DP;
1566滚数组DP;
2423推方案DP;
1899递推;
1222神奇转化降维;
1801状压DP转化;
1046DP+贪心;
1991区间推DP;
1044二分+DP;
1786、1831猜想后DP;
1057悬线法;
2298转化为取区间;
1966、3191DP
树形DP(8):
1864树形DP加0或1记染色方案;
1060、4027、1304、4011+朱刘;
1040环+外向树;
1791基环树找直径;
2878基环树判环DP+暴
数位DP(2):
1029基本数位DP;
1833较复杂处理;
3209二进制数位DP
记忆化(6):
1048、1079、3208记忆化;
1090(区间);
1564(区间);
1415(期望);
3810记忆化+卡常
期望DP(4):
1076、4004倒着DP;
2134、4008;
状态压缩(4):
1072、2560子集DP;
1087状压DP;
4197小范围状压
单调性(2):
1499单调队列优化;
1563单调性优化
斜率优化(7):
1010、1911、3437模板题;
1096两个前缀和;
3156;
1567排序+斜率;
3675多维斜率优化
其它优化(3):
1264、3594树状数组优化;
1492CDQ分治优化
695765 Eolv 1000 A
739478 Eolv 2463 A
696662 Eolv 1968 A
739546 Eolv 2456 A
725192 Eolv 1432 A
721629 Eolv 3098 A
703771 Eolv 1192 A
725907 Eolv 1022 A
696223 Eolv 1008 A
741269 Eolv 1257 A
741395 Eolv 2222 A
697459 Eolv 1207 A
725214 Eolv 1800 A
721612 Eolv 3097 A
738374 Eolv 1303 A
724903 Eolv 1012 A
730363 Eolv 2257 A
699301 Eolv 2748
703775 Eolv 1088
740036 Eolv 1029 A
728885 Eolv 3670
728790 Eolv 3680
727945 Eolv 1083 A
728039 Eolv 1293 A
721822 Eolv 1046 A
721270 Eolv 1597
725143 Eolv 3211
727569 Eolv 3668 A
728549 Eolv 1922
741870 Eolv 3629
734646 Eolv 2141
697413 Eolv 1150
732790 Eolv 2002
724051 Eolv 1055
741561 Eolv 1038
727282 Eolv 3669
696193 Eolv 1003 A
723903 Eolv 1058
732567 Eolv 1001 A
695781 Eolv 1051 A
724532 Eolv 1085
725708 Eolv 1857
734436 Eolv 2821
739849 Eolv 3223
739131 Eolv 1588 A
725876 Eolv 1864
739181 Eolv 1208 A
739437 Eolv 1503
724768 Eolv 3224 A