zhouzixuan的博客最后一次写板子了
zhouzixuan的板子包括：
1.上下界最小流 uoj217 完成
2.最小树形图 bzoj4349 完成
3.半平面交 bzoj4445 完成
4.带花树匹配 uoj79 完成
5.后缀数组 uoj131 完成
6.Miller_Rabin & Rho poj1811 完成
7.最小割树 bzoj4519 完成
8.可持久化treap
9.回文自动机 Ural 2040 完成
10.单纯形法 uoj179 完成
11.欧拉回路 uoj117 完成
12.树同构 bzoj 4337 完成
13.2-SAT 完成
14.树的计数 完成
15.组合数取模 完成
16.同余方程组 完成
17.dominator tree 完成
18.matrix-tree定理 完成
19.最小圆覆盖 完成
给你们说个笑话，我到现在还没有AC一道题答题TAT
NOI基本是要考得了，所以再不练练就要狗带了
记录一下解题的心得和技巧
基本都是口胡哒
【题目大意】：
给出一个N*M的矩阵，选择不超过K条长度在[lmin,lmax]的路径，设长度为L
1.如果路径上连起来的数字是质数那么得分L^c1否则为1
2.如果路径上连起来的数字是会文书那么得分L^c2否则为1
如果两个都为1那么本次总得分为0否则为两次得分之和
选择一条路径后路径上的数字会消失，然后上面的方格为下落
求最大得分
【题目解法】：
Task1：直接手完，一开始还玩错了，最优解只需要两步即可
Task2：n m比较小，写了个Miller_Rabin暴力跑跑就可以拿9分辣 然后就不会了，看了看标解感觉很有道理啊TAT
Task3：只有质数可以得分，因此需要找到500个长度为18的质数，直接Miller_Rabin+dfs爆搜即可，几乎是秒出的
Task4：和Task3是一样的
Task5：和Task2一样爆搜即可
Task6：发现只有1和2并且只有回文串有分且长度为1000，暴力枚举回文中心的两个点然后dfs暴力扩展即可
Task7：和Task6几乎一样，只不过有2 3 4三种数字，拿Task6的程序跑就可以了
Task8：只有回文串有分，并且大部分都是5 6两种数字并且相邻的一定是不同的，一开始直接把整个图遍历了一遍发现有坏点TAT，然后暴力一下遇到坏点就枚举下一步的方向，然后尽量先走上面的再走下面的
Task9：左右两边几乎对称，用类似Task6的方法，两边对称着扩展即可
Task10：发现有333个3*3的循环组成，直接对称走就可以了，每一个3*3的循环用如下方法走就好
1 -> 2 9
| ^
v |
4 <- 3 8
| ^
v |
5 -> 6 -> 7【题目大意】：
给出10个程序的暴力和极限数据
你需要根据暴力写出较优的程序然后跑出极限数据
【题目解法】：
Task1：快速乘（其实我是懒得用计算器了）
Task2：化简一下式子变成矩阵乘法+快速幂
Task3：1/2/3/4次方和，上网搜了一发公式A掉了，正解应该是高斯消元或者矩乘
Task4：给出一个黑白的网格图，求：1.白色点对的个数 2.距离某个白色点最近的黑色点 第一问找出点为n个后直接就是N*(N-1)辣 第二问把所有黑色点放进队列bfs一发就好
Task5：给出一个黑白的网格图，求白色矩形的个数。对于每个点处理出它向下延伸的最长白色长度L，对于每个行扫过去的时候对L维护一个单调递增的栈就好
Task6：不懂啊...
Task7：智障数独不想写TAT
Task8：貌似是组合数搞搞？不会
Task9：喜闻乐见的“常识”题
Task10：暴力检索，统计一下最后的贡献就好【题目大意】：
给出若干个事件，有三种类型：
1.把某一个变量 +/- 常量或某个变量
2.条件跳转：给出两个量（常量或变量）进行比较，如果第一个小于第二个则跳转到第x个事件否则跳转到第y个事件（x y给出）
3.选择跳转：选择调到x或y中的某一个（x y给出）
任务：使得一号变量最大
【题目解法】：
据说是历年NOI最水提答
首先注意一个事实：所有点的跳转都是无环的（因此可以直接暴力每个跳转然后跑几年应该可以A掉～）
Task1：发现每个选择跳转都是向后面跳并且选择的次数很少，直接暴力dfs判断每次跳转哪个就好
Task2：和Task1一样，不过有24个跳转，暴力一下，20s不到就出解了
Task3：有若干个大块，每个大块有若干个小块，每个小块是把3-12这10个变量+一个随机整数，每个小块可选可不选，每个大块处理完之后把这10个变量的绝对值加给一号变量然后清零，也就是说大块之间的抉择和代价是独立的。因此对于每个大块，我们考虑暴力枚举10个变量最后的符号：(1)如果是正号，那么原来+的数就是正贡献原来-的数就是负贡献 (2)如果最后的符号是负号，那么原来是+的就是负贡献，原来是-的就是正贡献。然后对于每个小块贪心找到最优贡献时的跳转方式就好。
Task4：有两个变量，仔细观察发现第二个变量初始为5000，然后每次可以选择这样的事件：第二个变量减去一个整数，第一个变量加上一个数。然后第二个变量不能减出负数。显然是个背包问题，把每个事件抽象出来做一遍背包就好。注意输出路径时，如果某个时候剩余的背包容量小于当前物品的重量是不用输出跳转方式的，因为他会直接跳过这个物品。（一开始多输出了这一步调了一个小时TAT）
Task5：还是背包问题，不过对于某个物品，如果不能选或者选择不选那么他会跳转到下一个指定的物品。因为没有环的存在，因此可以沿用dp解决。定义f[i][j]表示后面i个物品花费j的空间能得到的最大价值，然后对于每个物品枚举选还是不选，设next[i]表示i物品不选是跳转的位置：如果i物品不选那么从f[next[i]][...]转移，如果选的话就从f[i+1][...]转移就好
Task6：和Task5相同，不过初始容量变成10000。反正下面跑没有空间限制直接大力2000*10000的数组就好
Task7&Task8&Task9&Task10：这几个点我是一起写的。他其实是Task3和Task5的结合版，就是Task3里面的每个大块也可以选或者不选，选的话需要付出一定代价，不选的话跳转到下一个指定的物品。分离出所有大块，对每个大块里面的小块用Task3的贪心就好。最后背包一发就好辣～【题目描述】：
给出一个可执行文件lost，里面包含10种不同功能
给出10个in文件每个包含10组数据，用lost只能输出第一组
可以构造一些数据规模不超过第一组的小数据让lost运行
根据判断对每个in输出out，每个in的每一组结果1分
【题目解法】：
30s内把每个in的第一行求出来就有10分辣
Task1：发现是一个26个字母的映射，把每个字母当成in输进去就可以得到映射辣
Task2：不会啊TAT 看了题解发现是求2016x^2+4x+10 (mod 233333)的结果
Task3：还是不会 正解是给出圆的面积求半径下取整
Task4：构造一些小数据发现是：给出无向图，求每个连通块点数平方之和
Task5：喜闻乐见的树终于出现辣...构造小数据发现：给出一棵树和m次询问，每次询问两个点路径边权之和，m个数异或起来输出，我个智障还写了倍增+LCA，直接暴力其实就可以了
Task6：还是喜闻乐见的树，跟Task5基本一样，只不过把路径和改成路径最小值
Task7：据说是sigma(sigma(gcd(i,j)) 1<=i,j<=n TAT这怎么看出来哒。容斥一发就好
Task8：给出n个数，求本质不同的的非空连续子序列的个数？！woc，根本看不出啊TAT 后缀数组完事
Task9：构造小数据发现：求n个点两两欧几里德距离最小值 n<=1000000 写个O(N^2)的暴力加一点优化就过了
Task10：送分，输出10个"invalid input!"完事【题目描述】：
给出若干个程序，每次指定两个程序A B，需要你构造数据使得A不超时B超时
有两个子问题：1.最短路 2.地图染色
对于每个Task还有限制：构造的数据中包含的数字个数不超过T
每个程序会有一个计数器在某些位置会让计数器+1，如果计数器>10^6即为超时
【题目解法】：
Task1：A=floyd B=dijkstra T=107。很明显构造一个101个点的空图floyd就超时了
Task2：A=floyd B=BellmanFord T=2222。不难发现给出的BellmanFord算法是每次遍历所有的边，如果无法更新就退出。那么我们尽量构造出这样的图：每次只让一个点能更新，这样我们就需要更新n-1次，每次遍历O(M)次，然后在询问10次就TLE辣。所以我们构造1~n的链，方向倒过来，然后构造950条1-2的重边即可
Task3：A=BellmanFord B=floyd T=105。跟Task1一样啊
Task4：A=dijkstra B=floyd T=157。神构造。我们直到dijkstra对负权的边的贪心是由bug的，也就是说对于每个点到t的最短路，我们使得第一条出去的边不是从这个点出去最短的边，这样就能走出许多没用的东西。具体构造方法见：http://wronganswer.blog.uoj.ac/blog/1641 反正我是没有想到TAT
Task5：A=dijkstra B=BellmanFord T=1016。沿用Task2的方法，令n=300 m=335就没了
Task6：A=BellmanFord B=dijkstra T=143。T卡的非常紧啊。用Task4的神构造，询问变成6次就刚刚好
Task7：地图染色问题。看了看给的程序发现是暴力？！woc，随机一个数据就超时了
Task8：地图染色问题。让这个SB程序不超时（写的这么渣居然还要不超时TAT）其实很好构造，随便构造一条链，然后每隔两个连一条边，这样X=3很快就能搜出来了【题目描述】：
给出一个有向图
求关于边的子集个数是的这个子集内无环
【题目解法】：
首先tarjan一遍求出：强连通分量个数，每个强连通分量中包含的点数和非自环的边数
Task1：发现除了自环以外其他边随便选都不会出环。因此统计非自环的边的数量cnt，答案为2^cnt
Task2：发现有若干个强连通分量，然后每个里面边比较少，对每个连通分量暴力然后乘起来就好。对于非联通快内的边选和不选都可以
Task3：发现n=m，因此每个联通块都是一个独立的大环，对于一个环答案为2^x-1，每个计算一下乘起来就好
Task4：不会。只发现了每个点都是想[i-7,i+7]这个区间内连边，感觉可以暴力状压连通性，但是目测空间时间会炸起来
Task5：和Task2一样
Task6：有向完全图。考虑不存在环那么一定是DAG。直接dp，f[i]表示i个点的答案，然后枚举DAG的汇点容斥一下就好
Task7：n=12。状压dp，利用奇偶性容斥，用dfs转移复杂度O(3^N)
Task8：n=20。拿Task7的程序跑了几分钟，开个O2常数优化一下就好
Task9：不会
Task10：不会【题目描述】：
pps又开始dota视频直播了！
一群每天被pps虐的蒟蒻决定学习pps的操作技术，他们把pps在这局放的技能记录了下来，每个技能用一个字符表示。经过研究，蒟蒻们发现字典序更大的连招威力更大。于是所有蒟蒻都想学习pps最强的连招。但是他们太弱了，不能学会整个视频里的连招，只能学会陈老师一段区间间内的连招，可是这个他们求不出，于是只好向你求助。为了蒟蒻们不再被pps虐（怎么可能），请你帮帮他们。
简化题意：
给你一个字符串，每次询问你一段区间的字典序最大的子串。
【题目解法】：
考虑离线处理
设右端点为r，然后用set维护[l,r] (l<=r)的答案
容易发现[l,r]的答案随着l的增加单调不减
因此在set里面lower_bound一下就好了
性质+：在set里面，任意两个位置i<j满足s[i,r]>s[j,r]
考虑r->r+1是set的变化
考虑两个后缀有s[i,n]>s[j,n] (i<j)
显然有s[i,k]>s[j,k] (k>=j) 因此j不可能成为答案
因此考虑那些s[i,n]<s[j,n] (i<j)的后缀
设他们的lcp=L，显然：
1.在(j<=k<j+L)的时候有 s[i,k]>s[j,k]
2.在(k>=j+L)的时候有 s[i,k]<s[j,k]
根据性质可知当r=j+L的时候需要把i删去
我们成这样的情况为i伴随j（题解里面是这么说的）
同时我们需要递归的把伴随i的，伴随伴随i的，...全部递归删去
考虑证明：
假设k伴随i，i伴随j
1.k已经被删去，那么就不用管了
2.k未被删去，显然有s[k,n]<s[i,n]<s[j,n]即k伴随j
由于k未被删去有：k+lcp(s[k,n],s[i,n])>j+lcp(s[i,n],s[j,n])
因此k与j的lcp就是lcp(s[i,n],s[j,n])，因此当r=j+lcp(s[i,n],s[j,n]) k要被删去
得证
最后考虑对于每一个点我们只需要找到最早被删去的时刻
对后缀维护一个单调栈，每次加入后缀s[r+1,n]的时候和栈尾元素比较即可
每个点只会被删除一次，插入一次
复杂度O(N log N)【写在前面】：
很久之前就想填的坑
既然市选都考挂了，就来填填坑好了
【参考】：http://www.csie.ntnu.edu.tw/~u91029/Half-planeIntersection.html
http://blog.csdn.net/non_cease/article/details/7820361
【定义】：
什么是半平面？顾名思义就是半个平面
更准确一点的定义：二维平面上一条直线将平面分成两个部分，其中一个部分就是半平面
如果有多条直线，那么这些直线对应半平面的交集就是半平面交
注意，对于题目给出的直线，有可能不能形成有界的区域，但是我们可以根据题目数据范围认为的规定一个非常大的边界即可
如何快速求出半平面交，以及有什么用处呢？这就是以下将涉及的内容
【增量法】：
考虑我们认为加入边界后，使得半平面交一定是一个凸多边形（很好证明：因为你根本画不出凹多边形的情况）
因此，我么考虑加入一个新的半平面，然后对于凸多边形上的每一个点判断是否在该半平面中，然后判断该直线和凸多边形的边是否有交点，并且把存在于半平面中的点和交点加入新的多边形集合中，最终构造出的凸多边形就是加入该半平面后的半平面交
复杂度O(N^2) 算法是在线的
【随机增量法】：
在增量法的基础上加上对初始半平面顺序的随机洗牌
可以证明：每回合期望加入2个点，删除n/i个点，因此复杂度为O(N log N)
然而这样就不是在线的算法了
【队列法】：
其实我并不知道这种算法的名字，好像是朱泽园自创的？
1.初始将两个半平面加入双端队列
2.加入新的半平面时，从左端和右端分别弹出，直到两个半平面构成的交点在当前半平面中，然后加入新的半平面
3.现在需要将双端队列两端的半平面拼起来，因此需要对两边分别判断，直到一段的前两个的交点在另一端队首半平面内
复杂度O(N log N)
【直线方程求半平面交】：
在给出一些直线求线性规划可行区域时往往需要注意Ax+By+C=0中A B C的符号问题
因此我们不妨考虑取直线上的两个点作为向量，然后默认向量的左边为半平面
因此需要根据A B C讨论一下
【例题】：
poj1755 半平面交求线性规划可行域【题目大意】：
A省有一条东西向的公路经常堵车，为解决这一问题，省政府对此展开了调查。调查后得知，这条公路两侧有很多村落，每个村落里都住着很多个信仰c教的教徒，每周日都会开着自家的车沿公路到B地去“膜拜”他们的教主，这便是堵车的原因。详细调查显示：这里总共有N个村落，并且它们都在B地的东边。编号为i的村落住有Ri个信仰c教的教徒，距离B地的距离为Ti（单位：公里）。为解决这一问题，A省政府决定在这条公路下修建一条地下快速铁路来缓解交通，并沿线修建若干个车站（B地会修建终点站，不算车站）。每名教徒都会先往B地方向开车（如果他所在村庄处恰好有车站就不必开车了），到最近的一个快速铁路车站时换乘（如果直接开到B地就不用换乘了），再通过快速铁路到B地。但A政府遇到一个难题：修建多少个车站以及在哪修建车站。一个修建车站的方案中，如果修建过多的车站则会花费过多的钱，但修建的车站少了或者修建的位置不对又会导致公路的拥堵。A政府为了协调这两方面，采用评分的方式来衡量一个方案的好坏（分数越大方案越坏）：每修建一个车站会增加m的分数，在某一次“膜拜”中（只考虑去，不考虑返回），每导致1个教徒开车行驶1公里会增加1分。现请你设计一个修建车站的方案，使得分数最小。请输出这个最小的分数。
【题目解法】：
首先，修建车站肯定是在某个村落里
那么我们按照T排序
令f[i]表示前i个村落建立若干个车站且i点必须要建的最小分数
f[i]=min(f[j]+sigma(R[k]*(T[k]-T[i])))+m (j<k<=i)
令sumT[i]表示R[i]*T[i]的前缀和，sum[i]表示R[i]的前缀和，则：
f[i]=min(f[j]+sumT[i]-sumT[j]-T[i]*(sum[i]-sum[j]))+m
=min(f[j]-sumT[j]+T[i]*sum[j])+sumT[i]-T[i]*sum[i]+m
然后把(sum[j],f[j]-sumT[j])看成平面上一个点，用一个斜率为T[i]的直线从负无穷去截他
然后因为sum[j]单调递增
因此用单调队列维护一个下凸壳即可
复杂度O(N)【题目描述】：
给定方程
X1+X2+. +Xn=M
我们对第l..N1个变量进行一些限制：
Xl < = A
X2 < = A2
Xn1 < = An1
我们对第n1 + 1..n1+n2个变量进行一些限制：
Xn1+l > = An1+1
Xn1+2 > = An1+2
Xnl+n2 > = Anl+n2
求：在满足这些限制的前提下，该方程正整数解的个数。
答案可能很大，请输出对p取模后的答案，也即答案除以p的余数。
【题目解法】：
考虑对于n个未知数和为m的正整数解的组数，根据插板法答案就是C(m-1,n-1)
现在考虑有限制的情况
如果限制是>=，那么我们将m减去(A-1)，然后这个未知数就变成正整数限制了
考虑限制是<=，那么直接做不好求，我们不妨考虑>的情况，显然我们把m减去A，就变成正整数限制了
然后把不符合的情况减去即可
当然在做的过程中可能会出现组合数对任意数取模，因此需要扩展Lucas
复杂度O(2^N*(logM/logP))
写了一下午TAT【题目描述】：
你去找某bm玩，到了门口才发现要打开他家的大门不是一件容易的事……
他家的大门外有n个站台，用1到n的正整数编号。你需要对每个站台访问一定次数以后大门才能开启。站台之间有m个单向的传送门，通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门，你就需要乘坐公共汽车，并花费1单位的钱。值得庆幸的是，任意两个站台之间都有公共汽车直达。
现在给你每个站台必须访问的次数Fi，对于站台i，你必须恰好访问Fi次（不能超过）。
我们用u、v、w三个参数描述一个传送门，表示从站台u到站台v有一个最多可以使用w次的传送门（不一定要使用w次）。值得注意的是，对于任意一对传送门(u1,v1)和(u2,v2)，如果有u1<u2，则有v1≤v2；如果有v1<v2，则有u1≤u2；且u1=u2和v1=v2不同时成立。
你可以从任意的站台开始，从任意的站台结束。出发去开始的站台需要花费1单位的钱。你需要求出打开大门最少需要花费多少单位的钱。
【题目解法】：
看到题目我们可以直接暴力费用流：
首先原点S 汇点T
S拆点S1 S2，连边(S1,S2,1,1)
S2向每个点连边(S2,i,INF,0)
每个点向汇点连边 (i,T,Fi,0)
然后对于每个传送门连边(x,y,w,0)
然后每两个点连边(x,y,INF,1)
然后从S1到T跑一遍最小费用最大流
然后我们发现边的级别是O(N^2)的TAT
考虑每个点必须经过Fi次，那么也就是说它的度数就是Fi*2
考虑一条带费用的遍可以对两个点各贡献一个度数
那么总的费用就是sigma(Fi)
然后使用一次传送门可以减少一条边
那么答案就是sigma(Fi)-传送门使用的最多次数
考虑如果求出最多的次数
相当于是对于每个点利用传送门找匹配
每找到一个匹配，那么我们就可以把他们原本需要花的费用省掉
想到于我们需要找到最多的匹配
我们把每个点拆成两个点i i'分别表示入点和出点
显然每个点进入的边和出去的边数都不能超过Fi次
连边(S,i,Fi) (i',T,Fi)
对于传送门连边(x,y',w)
然后最大流即可
复杂度O(Maxflow)【题目描述】：
在一个圆上均匀分布p*q个点{A1，A2，A3…Ap*q}，Ai与Aj的距离为min{abs(i-j)，p*q-abs(i-j)}，在上面选任意个点(可以选0个)，如果选择的点中存在两个点距离为p或q，就会发生排斥反应，求不发生排斥反应的方案总数。
【题目解法】：
不愧是集训队的神题
考虑对于给圆周上的点编号
然后一个点x，他向右走表示x+q，向下走表示x+p
那么就构成了一个q*p的矩阵
然后我们从矩阵中选出一些点使他们两两不相（最后一行和第一行，最后一列和第一列也算相邻）
然后状压dp+矩阵乘法就好了
然后发现每一行不相邻的状态大概100+个
那么复杂度大概就是(100^3 log M)
注意特判m=1的情况【题目描述】：
给定一棵无根树，边权都是1，请去掉一条边并加上一条新边，定义直径为最远的两个点的距离，请输出所有可能的新树的直径的最小值和最大值
【题目解法】：
poi2015最后一坑终于被我填上啦！
为啥波兰人那么喜欢方案...
考虑枚举删掉的边
那么最大值显然就是两颗树的直径拼起来
最小值是两棵树的直径中点拼起来
证明：显然对于一棵树，它能贡献的最大值的最小值一定是直径的一半，如果他向下扩展最大值都不到直径的一半，那么我们找到两条最深的链，把他们拼起来就是直径，然后长度是小于直径的，因此矛盾，所以中点拼起来已经是最优的
显然考虑求出对于每一条树边，断掉他后上半部分和下半部分的直径
首先定义三元组(x,y,from,val)
如果对应的是直径，那么x y对应直径的端点，from对应来自哪个儿子，val对应长度，
如果对应的是链，那么from对应儿子编号，y对应链的末端编号，val代表长度
考虑我们从下往上dp，统计出：
1.往下走长度前三大的链
2.儿子子树中长度前两大的直径
3.这个点所在子树对应的直径
然后我们从上往下dp，统计出：
1.连着某个点向上走的最长长度，这个可以用fa节点的信息更新
2.某个点断开他与fa的连边后，上半部分的直径，我们分情况考虑
1.不经过fa，显然可以有断开fa和爷爷边后上半部分的直径，以及fa的儿子（不包括该儿子）中的直径更新
2.经过fa，可以有两个儿子中的深度拼起来，或者最大的儿子和该点连着向上的长度更新
最后扫一遍得到答案后，O(N)扫一遍链的中点
复杂度O(N)【题目描述】：
给定 n 个点，m 条边的无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。
【题目解法】：
考虑dfs出一颗生成树
然后我们记录一下哪些返租边构成偶环，哪些构成奇环
如果图中没有奇环，显然每条边都可以删去（自环的情况后面再说）
考虑哪些返祖边可以被删去：
1.图中存在奇环，但仅存在一个，那么这个奇环的返祖边可以被删去
考虑哪些树边可以被删去（下列条件必须两个都满足）：
1.是所有奇环的并集
2.不属于任何偶环
证明：1显然，考虑2，如果属于某个偶环，因为他也属于某个奇环，那么删了它两个环并起来还是一个奇环，因此不合法
所以我们处理出每一条树边经过它的偶环和奇环个数
然后先处理一些细节：
1.重边，我们把重边当成偶数环看待就好了
2.自环，显然自环必须被删去，因此：
1.如果图中没有奇环，那么只能删去自环
2.如果图中存在奇环，答案为0
奇环和偶环处理直接维护树上前缀和+lca既可以了
然后就一直WA，发现没有把答案sort一遍（居然在cf上面水过了前30个点TAT）
然后改了PE，发现不能输出行末空格
然后改了接着WA，发现如果答案为0，第二行不能多输出一个换行TAT
然后就A了
复杂度O(N+M)
鄂公网安备 42010202000505 号Server time: 2024-11-25 11:03:25