BZOJ水题大乱斗2

[upd 2016.9.29] 今天好无聊不如来刷排位
[upd 2016.10.22] 干脆在vjudge上屯着吧
[upd 2016.10.23] 周末10题斩~
[upd 2016.10.28] bc89 fst了B,可怜我的RATING
[upd 2016.10.29] 19点做完!撒花

#50/50

题目 解法
2653: middle 经典题,静态数列强制在线询问区间中位数,可持久化线段树+二分
3207: 花神的嘲讽计划Ⅰ 可持久化线段树+uint hash
3932: [CQOI2015]任务查询系统 可持久化线段树,离线处理,单点修改,区间前k大和
2588: Spoj 10628. Count on a tree 可持久化线段树,静态树,强制在线链上第k小
3123: [Sdoi2013]森林 可持久化线段树,森林,强制在线支持连边,链上第k小,把小的树暴力重构就行
3744: Gty的妹子序列 可持久化线段树,强制在线区间逆序对数
3289: Mato的文件管理 莫队,区间逆序对数
1025: [SCOI2009]游戏 \(f{i,j}\)表示前\(i\)个质数中\(\sum_{i=1}^m{p_i ^{m_i}}\) 为j的数的个数,则显然\(f_{i,j}=f_{i-1,j}+\sum_k f_{i-1,j-p^k}\), 初始值\(f_{0,0}=1\),\(ans=\sum_{i=0}^n f_{tot,i}\)
1058: [ZJOI2007]报表统计 开2个set
3930: [CQOI2015]选数 安利 http://blog.csdn.net/popoqqq/article/details/44917831
4451 : [Cerc2015]Frightful Formula fft mod 1e9+7 分块写法 安利http://www.cnblogs.com/clrs97/p/5308851.html 交题在LA7329
1061: [Noi2008]志愿者招募 安利PoPoQQQ的题解[单纯形][http://blog.csdn.net/popoqqq/article/details/44310605]
3112: [Zjoi2013]防守战线 和上题没差,单纯形的对偶就是A换成\(A^T\),b,c对调,n,m互换。\(Ay\ge b,min(Cy)\)
BZOJ 3308/tyvj P1564: 九月的咖啡店 神结论题,只有1, 单个质数的若干幂次,两个质数a,b(\(a<\sqrt n < b\))的幂次的乘积可能取到,附大爷[题解][http://blog.csdn.net/popoqqq/article/details/45725661]
1821: [JSOI2010]Group 部落划分 Group 对点对连边并排序,并查集贪心
3555: [Ctsc2014]企鹅QQ 枚举不同字母的位置,然后2遍hash
3212: Pku3468 A Simple Problem with Integers 呵呵
3680: 吊打XXX 爬山算法http://hzwer.com/4139.html
1193: [HNOI2006]马步距离 大范围搜索,小范围暴搜,假设当前(0,0),目标(x,y)贪心的具体方法:当\(x\ge y,x-4\ge 2y\)时,走\((4,0)\),否则走\((4,2)\)
1876: [SDOI2009]SuperGCD 普通的高精度要处理高精%高精,显然不行,于是使用[stein][http://baike.baidu.com/link?url=QtSt9ZVKwuGIjELH8a3jSuqaVmngX8LDull4siXeR971xC37AK5BTIEOgWNAILEbTJn_PWAEUtMewPiwRm4t3q]加速(Stein算法是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法)
2843: 极地旅行社 LCT裸题!板子里居然没有find_root(),o(︶︿︶)o 唉
2134: 单选错位 期望=可能情况/总情况,单独考虑每道题,\(ans=\sum_1^n{\frac {min(a,b)} {ab} }= \sum_1^n{\frac {1} {max(a,b)} }\),其中a,b为相邻两道题的选项数
1077: [SCOI2008]天平 由于天平重量只有1,2,3我们可以计算2个砝码重量差值的上下界,然后dp,安利http://blog.csdn.net/scyjcp/article/details/52622261
1103: [POI2007]大都市meg dfs手写栈,求出dfs序,然后用树状数组处理前缀和
1303: [CQOI2009]中位数图 暴力从中位数向两边走
1304: [CQOI2009]叶子的染色 显然随便取一个根节点,然后设\(f_{i,j}\)为子树i在点i染颜色j时的最小染色数,显然有\(f_{i,j}=\sum_{v}min(f_{v,j}-1,f_{v,j\bigwedge 1})\)
1305: [CQOI2009]dance跳舞 二分+网络流,将男生成一条容量为k的边\(x\to y\),如果和喜欢的人,就从x走,否则从y走,女生同理。
3171: [Tjoi2013]循环格 循环格是完美的当且仅当每个点入度出度均为1,所以可以建立2分图跑最小费用流。
3442: 学习小组 本来以为是带上下界的最小费用可行流,结果看到了[Tunix][http://www.cnblogs.com/Tunix/p/4354843.html]的解法,可以跑最小费用最大流了
3440: 传球游戏 找出一堆环加外向树,然后各种特判
3444: 最后的晚餐 显然存在大于3个点的环,或者存在点度数>2是无解的。于是发现有解的充要条件是暗恋关系形成链。\(ans=(a+b)!2^b\) 其中a+b是连通块个数,b是点数\(\ge 2\)的链个数,注意重边
4236: JOIOJI 设JOI分别出现x,y,z次,记录前缀的(y-x,z-x)的出现最早位置,扫一遍。
4706: B君的多边形 打表,OEIS - A001003 - super-Catalan numbers or little Schroeder numbers
2741: 【FOTILE模拟赛】L 分块枚举段首+可持久化字典树
4260: Codechef REBXOR 可持久化线段树维护前后缀最优值fa(1).jpg
1019: [SHOI2008]汉诺塔 考虑2种移动方法http://blog.sina.com.cn/s/blog_76f6777d0101b8l1.html
1021: [SHOI2008]Debt 循环的债务 \(f_{i,j,k}\)表示前i种面值分完后,A和B分别有j和k元的最小步数
3439: Kpm的MC密码 反转字符串并把它们丢入字典树,然后用dfs序+主席树求第k大
1044: [HAOI2008]木棍分割 第一问二分答案,第二问dp,滚动数组+双指针优化
1862: [Zjoi2006]GameZ游戏排名系统 同1056
2780: [Spoj]8093 Sevenk Love Oimaster 广义SAM求parent树,dfs序求区间内有多少不同权值
1786: [Ahoi2008]Pair 配对 通过交换法可以发现填入的数单调不降,且k很小,可以用O(nk)的dp解决
1831: [AHOI2008]逆序对 同上
4524: [Cqoi2016]伪光滑数 http://blog.csdn.net/lych_cys/article/details/51158560,
2734: [HNOI2012]集合选数 神奇的dp,http://blog.csdn.net/aarongzk/article/details/50753250
3438: 小M的作物 最大权闭合子图版题
4245: [ONTAK2015]OR-XOR 拆位,贪心,每次留下“可选分割点”的位置的集合
1060: [ZJOI2007]时态同步 \(f_i\)\(i\)为根的子树的最远叶节点距,然后贪心
1053: [HAOI2007]反素数ant 假设x是反质数,设x的约数个数\(\tau(x)=(k1+1)(k2+1)\dots(kn+1)\),和取哪个质数无关,故可认为取的是前k个质数,且k单调不增。。。暴搜
1087: [SCOI2005]互不侵犯King 状压dp