BZOJ刷题指南(转)

基础(65)

巨水无比(4):1214、3816:2B题;1000A+B;2462:输出10个1

模拟/枚举/暴力(15):4063*模拟;1968小学生暴力;1218前缀和暴力;3856读英文;4106直接算;1800暴力判断;2208暴力判断(要会邻接表);1028枚举;1789&1830高能暴力;2241暴力;2120神奇的暴力;4145子集暴力;4029模拟处理;1086DFS树;1224暴力;3444暴力判

人类智慧题(17):2463输出0或1;1192找规律;1413奥数;1432找规律;4001数学;1022简单博弈;2005暴力数学;2659数学;2173找规律;4147手推博弈;1228SG函数打表找规律;1045&3293中位数;2222纯手算;2467找规律打表;3505组合数;3858处理小范围

高精度Python(11):1213高精度开根;2656回溯高精度;2822递推高精度;2729组合数高精;1002递推高精;1089各种高精运算;1263贪心+高精度;1876高精度求最大公约数;1416&1498高精算概率;1970暴力+高精

排序/贪心/二分(10):4143排序后判断;3850排序后贪心;1034贪心;2563转化思想后排序;3170排序后处理;1816二分后判断;3969二分+贪心;1082排序后二分判断;3671贪心+暴力

其它水(7):3098卡哈希;3214字符串处理;2456特殊方法;2751去重;2048小范围暴力大范围乱算;3668按位处理;2660递归计算

然后大家会发现小学生在BZOJ其实也能做50题,真的是题目难度最低的一个网站

图论(91)

搜索(8):1054BFS;1024DFS;1295暴力+BFS;1053搜索(数学证明);1306剪枝;3680模拟退火裸题;1085A*;2428模拟退火

最小生成树(7):1083模板题;1821、2429裸题;1196二分+最小生成树;1050;3732+树上倍增;3624最小生成树+贪心

最短路(14):1491Floyd+统计;1003DP+最短路;4152排序后最短路;2435DFS找负环;1486DFS找负环;1001网络流->最短路;2763、2662分层图+Dijstra+堆;1880最短路+拓扑;2118转化后最短路;2165倍增Floyd;3875SPFA维护DP;2330差分约束;3436差分约束+判负环;4144Dijkstra建树处理

二分图(9):1854、1191裸题;1059、1433SB题;3175、2150最大独立点集;1562二分图求DFS序;1143Floyd+二分图;2539KM

网络流(33):这部分比较重要,每道题写出连边方法,方便以后看

1412:源点向所有羊连无穷边,羊向狼连流量为1的边,所有狼向汇点连无穷边跑最大流

1066:源点向每只蜥蜴连1的边,蜥蜴向每个能到的石柱连边,如果蜥蜴能到边界,向汇点连无穷边跑最大流

1497:裸最小割,源点向所有客户连流量为收益的边,客户向选择的中转站连边,中转站向汇点连流量为花费的边,答案即为总收益减去流量

2561:加入的边为u,v长度L,则所有长度大于L的边不能使得u,v连通,求个最小割即可,小于同理

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出发沿残余网络能到u,v出发沿残余网络能到t。在残余网络中tarjan求强连通分量。(u,v)两点在同一SCC中说明残余网络中存在u到v路径。s和u在同一scc说明s能到u,t和v同一scc说明v能到t。

1305:二分答案ans,每个男孩拆成两个点ai和ai',每个女孩拆成两个点bi和bi',源点向每个ai连一条流量为ans的边,每个bi向汇点连一条流量为ans的边,如果男孩i喜欢女孩j,ai向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;2438:缩点后,ans=入度为0的连通块个数,倘若存在只有一个点的连通块,它无出边或出边指向的点均能被其它点到达则ans-1;1179:缩点后求点权最长路;1093缩点后DP统计方案;1823 2-SAT

树(11):2783树上DFS+倍增;1509树上最长链;1912两次树上最长链;2657奇怪构图后树上最长链;1787LCA;2152点分治;3991虚树动态统计;2286、3572虚树DP;1005、1211Prufer编码

数据结构(69)

并查集(3):1015倒着加入并查集;1202维护一个数组记录差值;4195傻逼并查集

基础数据结构(4):1483链表启发式合并;1007、3190单调栈;1293单调队列

堆/RMQ(7):1029贪心+堆;1216堆;2006RMQ+堆;1047二维RMQ;2809可并堆;2333可并堆各种操作;4198哈夫曼编码

哈希表(4):1567二分+哈希判重;3555哈希后排序判断;3916分类哈希;3751HASH解方程

分块(8):2957傻逼分块;2141、3295动态逆序对;3744在线求逆序对数;2821分块+二分;2038莫队;3289莫队+树状数组;3720块状树

树状数组(5):1012裸题;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快速幂;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分治优化

上一篇:CSS-3 RGBA的使用


下一篇:《大型网站系统与JAVA中间件实践》读书笔记-大型网站架构演进