BZOJ 水题50乱做

[TOC]
1051: [HAOI2006]受欢迎的牛
显然受欢迎的牛一定在一个强连通分量里,缩点后看看有没有出度为0的点,如果有多个那么无解
4690: Never Wait for Weights
加权并查集
1269: [AHOI2006]文本编辑器editor
rope的使用方法http://blog.csdn.net/iamzky/article/details/38348653
1031: [JSOI2007]字符加密Cipher
后缀数组裸题
3238: [Ahoi2013]差异
后缀数组裸题
1041: [HAOI2008]圆上的整点
数学题,求\(a^2+b^2=c^2\)(c已知),a,b的正整数解个数
http://blog.csdn.net/csyzcyj/article/details/10044629
1014: [JSOI2008]火星人prefix
splay+hash+二分
1069: [SCOI2007]最大土地面积
平面土地上有N个点,选择其中的四个点,求围成的多边形最大面积。
n<=2000
求凸包,O(n^2)枚举对角线,两侧的点有决策单调性,用一个指针O(1)求
1090: [SCOI2003]字符串折叠
区间dp
3998: [TJOI2015]弦论
SAM


1066: [SCOI2007]蜥蜴
网络流,拆点
1015: [JSOI2008]星球大战starwar
倒着并查集
4443: [Scoi2015]小凸玩矩阵
网络流,动态加边/二分都行
1067: [SCOI2007]降雨量
线段树/RMQ都行,要分类讨论
1042: [HAOI2008]硬币购物
我们先算出不考虑限制时的方案数\(f_s\),如果一个硬币超出限制,那么至少要使用\(d_i+1\)次,此时答案为\(f_{s-c_i*(d_i+1)}\),我们可以用容斥定理解决问题
2298: [HAOI2011]problem a
考虑一个人的话:“有ai个人分数比我高,bi个人分数比我低”等价于“我的排名在\([L,R]\)区间中,这个区间中人的成绩相同“,然后就可以变成线段覆盖问题,贪心即可。
4653: [Noi2016]区间
将区间按长度排序,枚举最长区间长度,显然最短区间长度满足单调性,只需要确认“m个区间共同包含至少一个位置”,用线段树维护最大值即可。
1192: [HNOI2006]鬼谷子的钱袋
k个钱袋最多能凑出\(2^k-1\)的所有钱数
1800: [Ahoi2009]fly 飞行棋
暴力。
1856: [Scoi2010]字符串
回顾卡特兰数的推导过程,发现\(ans=C(n+m,n)-C(n+m,n+1)\)


1801: [Ahoi2009]chess 中国象棋
炮的攻击范围为,横行竖行,跳过一个棋子打一个,距离不限
故原题为求\(n*m\)的矩阵中同行同列只能放至多2个炮的方案数
\(f_{i,j,k}\)表示到第i行,j列放了一个,k列放了2个的方案数
4641: 基因改造
在允许置换的情况下kmp是可以的,hash应该也行
我觉得我应该改改KMP的模板了。。
4602: [Sdoi2016]齿轮
dfs走一遍
3926: [Zjoi2015]诸神眷顾的幻想乡
由于叶子节点不超过20个,所以可以用SAM。
注意拷贝叶子节点时只拷贝c个节点不然会TLE.
4627: [BeiJing2016]回转寿司
线段树裸题
4619: [Wf2016]Swap Space
贪心,证明看得不是很懂
http://www.cnblogs.com/gangding/p/5705400.html
1016: [JSOI2008]最小生成树计数
回忆Kruskal的建立方法,显然每个长度后图的连通性是一定的,具有相同权值的边不会超过10条,dfs就行。
1061: [Noi2008]志愿者招募
经典的问题
https://www.byvoid.com/blog/noi-2008-employee/
3295: [Cqoi2011]动态逆序对
cdq,三维偏序(白书原题)
3996: [TJOI2015]线性代数
经过一堆变形我们发现\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n} B_{i,j}a_i a_j-\sum_{i=1}^nC_ia_i\)
我们把这转化为最大权闭合子图最小割
答案=所有点正权值之和-最小割
3875: [Ahoi2014]骑士游戏
令f_i为杀死i的最小代价,那么有\(f_i=min(K_i,\sum_v{f_{v_i}})\)
状态之前的转移有环,我们考虑《SPFA算法的优化及应用》中提到的算法


3997: [TJOI2015]组合数学
安利Dilworth定理:http://blog.csdn.net/popoqqq/article/details/45171469
4448: [Scoi2015]情报传递
询问离线,树链剖分
1070: [SCOI2007]修车
费用流经典模型
http://www.cnblogs.com/Sky-Grey/p/3862019.html
4418: [Shoi2013]扇形面积并
扫描线,用树状数组+二分判断
1406: [AHOI2007]密码箱
\(x^2=1 \mod n\)等价于\(n|(x-1)(x+1)\)然后暴力枚举因子就行
1038: [ZJOI2008]瞭望塔
半平面交,把分段点(包括边界)取出来
2618: [Cqoi2006]凸多边形
拆成一堆直线半平面交
4517: [Sdoi2016]排列计数
错排公式\(D(0)=1,D(1)=0,D(i)=(i-1)(D(i-1)+D(i-2))\)
有个求一段阶乘的逆元的小技巧

4516: [Sdoi2016]生成魔咒
1.裸sam+map
2.求出反序后字符串的SA,每次添加一个字符串,考虑其对height前后字符串的影响
4514: [Sdoi2016]数字配对
我们发现两个数能配对,则它们分解质因子后的数的个数奇偶性不同,我们可以建出二分图,费用流乱搞


2243: [SDOI2011]染色
树链刨分,把情况转成子节点到父节点的两条链会比较好讨论
3531: [Sdoi2014]旅行
树链剖分,拆成n棵树。记得动态开点减少结点数
3631: [JLOI2014]松鼠的新家
对于加法操作差分,将对链的操作转换为点始末节点的操作,避免后效性,在子节点\(s_i\)+1表示从它开始到根节点均+1,最后统计一遍就行
4034: [HAOI2015]T2
树链剖分时,可用dfs序剖分

3626: [LNOI2014]LCA
操作离线,然后

后加每个点的时候是把从这个点到根的路径的点权全部+1
然后查询就是查询某个点到根的路径的点权和

1191: [HNOI2006]超级英雄Hero
二分图匹配
1143: [CTSC2008]祭祀river
用floyd求传递闭包,建图,原题求最长反链=最小链覆盖
证明:http://www.bubuko.com/infodetail-664202.html
路径不能相交的最小路径覆盖可以用二分图做
路径可以相交的最小路径覆盖(也就是最小链覆盖)可以用floyd求传递闭包建图,转成前面那个用二分图做
2227: [Zjoi2011]看电影(movie)
公式题:ans=(k+1)^(n-1)*(k-n+1)/k^n
神一般的证明:http://www.cnblogs.com/devilpi/articles/3817691.html
1179: [Apio2009]Atm
tarjen缩点+跑一遍dij
4419: [Shoi2013]发微博
用户没有传递性(SB读错题),只有直接关系能看到信息
差分后得到,\(ans_i=t2-t1+t3-t4+...+t_n-t_{n-1}\)暴力维护