题目	解法
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	可持久化线段树维护前后缀最优值
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

题目

解法

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

今年下半年赛季第一场比赛，我们去了长春。

Day1：

被强行起了个大早，大约9点出的门，然而比起主席天没亮就出门还是太晚[话说他真的睡了吗]，先是打车去了酒店，然后大巴去了机场，中间耽误了好久，大巴上看到主席在鄂尔多斯~~烤羊腿~~转机的画面……我还是继续睡觉吧……

到了机场已经是接近中午了，由于起得太早没来得及吃早餐（主席：喵~），一行人在机场吃50一份的快餐，可能是由于没糍早餐的报应，lz和mg都糍完了我的那份还在Loading，出门就涱了一波RP。

一路在飞机上睡觉，中途在通辽转机发现主席一伙人已经坐电车~~出去玩了~~找酒店，话说通辽机场阳光好充裕啊去晒日光浴……我还是睡觉吧。。

到了长春才发现自己带的旅行箱完全没用，本来以为零下几十度结果连零都没下¹，到旅店时已经很晚了。本来想在下榻的酒店随便叫份外卖，结果被mg拉出去吃烤肉（为什么是烤肉），中间mg策划我们一行人去看电影（嘛反正我平常是不去这种资本主义横行的地方~~还不是因为穷~~），中间主席跑过来说要一起看，结果为了看电影，我点的最后一道菜只好打包带走

achieve

大晚上看了最晚一场电影看到半夜，话说明天还起得来吗？

Day2：

没有任何悬念的错过了酒店早餐，和主席它们跑去报道，从南边进去以后看到了一片建筑工地差点以为走错地方，向右拐进入一个小门，话说吉大好厉害好大好豪华好奢侈好享受好度假村，校园里居然有网吧游泳池商厦台球馆电影院美食城汉堡王，一行人打算在汉堡王刷关送的饭票，尽管门口有写让用实际上并不让用，然而等知道了这点的时候队都排完了……なるほど，那个告示是故意引人入店的》

下午测试赛，发现我们的校徽被人换掉了-((‵□′))- 。我先看了A，结果由于没看出successive 是连续的意思，结果没做出来……，mg开启手算第二题模式，最后仔细一看发现不是Catalan数吗……实力1A，lz徒手找规律，过掉一到本来好像要gauss期望dp的题，我分类讨论一波，强行过掉C。我们队成功开启·真·无双做题模式，1人1T1A，结果榜单上没有我们，仔细一看交错号了（GG)，交到了中科大（喵）去了

然后我们去了伪满皇宫，由于关门进不去，去了旁边的抗日战争主题博物馆，中间大家走散了，出来的时候，主席骗mg说我还没出来，结果mg已经出来了在出口的树下，，敢情被坑的是我……话说都快比赛了这么掉RP没问题吗~

晚上一行人去万达玩密室逃脱，路上被主席一路tc，我们玩得是星际迷航主题，开局是转盘语音容错率低差评，中途逃生舱把写得英文看成请误触碰（我不是故意的……），中间把密码器当工作人员使用的了（自带跳过重要线索光环），后面不明意义的圆盘需要跳回前几个房间，没注意到不做评价，解方程没有使用Hints好评，最后那个Hash表沦落到用Hint（不好意思说自己是竞赛党了），最后结局开船意义不明（强行凑谜题个数）

Day3：

早上起来随便喝了点豆浆上战场，开局看标题，mg默默给题目打上送分，进阶，不可做题的标签²

，开局mg开始手速题，迅速过了Triangle，忘了n=1时 $/gcd$ 稍微在 Fraction 下欠了一个罚时，我开局看 Binary Indexed Tree不会做³,改看其它题，中途mg开kmp的Sequence I,由于白书kmp板子有点小问题稍微发了点时间，途中我给出了Harmonic Value Description的构造解做法，一共就几行，稍微挽回了一点罚时。

中途我把Ugly Problem 的解构造出来了，由于要用高精，mg让我上Java，然后mg和lz讨论其他题去了，由于之前想当然漏掉几种特判，再加上太久没用java差点交文件时把类名写错，不辛坑了一波队友（我对不起你们），将近1h才过掉这题，此时只剩下一个多小时了。

继续看题发现Sequence II 之前好像在哪里做过，好开心这不是主席树么（主席：喵~）。二话不说敲了10min板子，结果不小心写了动态开节点的线段树的板子（考得这么残念罪魁祸首），最终mg强行主席树手写成功（中途由于节点数开小了re了一发），然后最后剩15min实在写不了题，进入喝茶聊天给其它队制造压力mode。

考完后弦歌队刚飞机先遛了，留下我们和隔壁西电成员讨论题目解法，话说这次考这么惨⁴好伤心啊……败北航队dalao，%%众dalao，这次SJTU出的题目质量不错，但最后没有讲题差评。

晚上去了之前玩密室的万达，要么怎么说人家吉大地理位置好。接下来mg带我们队玩了一波街机厅，然后又去打了台球，中途去吃了日本寿司,mg点的太多结果又剩了一堆没吃完。晚上被mg带去网吧~~玩守望~~学习，话说网吧机子配置好好难怪mg经常去网吧。

Day4：

半夜本来想交Uber，被mg说动走回酒店，结果走了0.5h发现南门校门锁了（bad end），没办法原路返回(0.5 h) ,结果实在受不了打车回去，打车地点离网吧不远sad story. 回到酒店，叫了pizza，结果左等右等pizza就是不来，mg由于手被冻僵了就先去睡了，我等着等着睡着了（最好3点半送到匹萨的时候我意识模糊的接了电话，让它放在楼下，话说直到最后我都没见到pizza）。

虽然和mg立志一定要吃到早餐，然而由于睡前实力忘了闹钟，结果睡到了中午12点⁵（mg表示中途起来叫我，我翻面继续睡，然后他也继续睡了……）。为了弥补遗憾，我们一行人去了东北菜馆，点了一桌子菜，结果菜上来才发现是8个人的量，只好打包带走……

本来还打算试试电车，结果由于时间紧，又只好叫了Uber，就这样离开了长春还真是充满了遗憾呢……不过我还是先补完作业再说吧。

后记：主席又打算和妹子出去玩我就不写在正文里了。

长春当时的气温在7,8度左右 ↩
结果好像都猜错了%%% ↩
正解是数位dp，统计2个数lcp中1的个数 ↩
结果我们一个亿Ag，弦歌打铁（主席：我以后拒绝去这种5题不保铜的赛区）。 ↩
本来计划好了去长春电影制片厂 ↩

nike0good

有所作为是人生的最高境界

Monthly Archives: 10 月 2016

BZOJ水题大乱斗2

CCPC长春游记

Day1：

Day2：

Day3：

Day4：

2016 年 10 月
一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31