水题大集锦（整理远古时期A过的题）

49/50

1214: [HNOI2004]FTP服务器

大模拟（无SPJ）

1216: [HNOI2003]操作系统

用堆模拟即可

3212: Pku3468 A Simple Problem with Integers

线段树

2819: Nim

链剖

3083: 遥远的国度

链剖*2

3155: Preprefix sum

用线段树维护第一重前缀和

2045: 双亲数

$$\begin{align} \sum^n \sum^m [gcd(i,j)=d] &= \sum^{\frac nd} \sum^{\frac md} [gcd(i,j)=1] \\ &= \sum^{\frac nd} \sum^{\frac md} \sum_{a|gcd(i,j)} \mu(a) \\ &= \sum_a \mu(a) {\frac n{da}}{\frac m{da}} \end{align}$$

1819: [JSOI]Word Query电子字典

字符串+Hash

2038: [2009国家集训队]小Z的袜子(hose)

莫队

1259: [CQOI2007]矩形rect

状压连通性DP？打表！

3437: 小P的牧场

斜率优化

3439: Kpm的MC密码

反向加入AC自动机然后每个点维护主席树

3209: 花神的数论题

依次枚举哪一位上的1的段数和个数

3207: 花神的嘲讽计划Ⅰ

Hash一发数列然后询问就可以主席树了

1430: 小猴打架

生成树有 $n^{n-2}$ 种，然后选边的顺序为 $(n-1)!$，相乘即可

1874: [BeiJing2009 WinterCamp]取石子游戏

SG函数求出来就好了，至于方案嘛，看减完SG函数异或和满足要求不

1201: [HNOI2005]数三角形

统计，需要用到树状数组

3040: 最短路(road)

配对堆维护最短路（你可以将随机生成的边全部去掉，答案也是对的）

2829: 信用卡凸包

求出所有点然后凸包，然后加上一个圆的周长即可

3781: 小B的询问

莫队

2732: [HNOI2012]射箭

每个约数条件可以转成半平面，然后就变成半平面交了

1038: [ZJOI2008]瞭望塔

也是半平面交

3097: Hash Killer I

卡模2^64的构造方法：

对于偶数进制就直接abbbbbbbbb...和bbbbbbbbbbb...

对于奇数进制就直接建个原串然后将其复制反转后连接在后面

3098: Hash Killer II

输出一个随机字符串

4352: Tower

从大到小放，每次能放的位置是有限个的 $[A-D,A]$，然后累乘

2441: [中山市选2011]小W的问题

建两棵线段树，一棵储存 y1 有关的信息（A），一棵储存 y2 有关的信息（B）

按 x 从小到大遍历，其作为 y3 的方案数为 A[1,y-1] 减去 B[1,y]，查询完修改则将 A[1,y-1] 中包含的点全部+1，将查询到的总点数修改进 B[y,y]，当然也别忘了将点加进 A[y,y]

然后右边的部分就同样的处理

2154: Crash的数字表格

啊变形后成这样

$$Ans=\sum_{a|n} a \sum_{b|n} b^2 \mu(b) \sum^{\frac{n}{ab}} \sum^{\frac{m}{ab}} ij$$

这样其实就能双参数 $O(n)$ 完成

然后其实可以变成

$$Ans=\sum_{a|n} a \sum_{b|a} b \mu(b) \sum^{\frac{n}{ab}} \sum^{\frac{m}{ab}} ij$$

我们把前面那部分提出来，会发现

$$g(n)=\sum_{a|n} a \sum_{b|a} b \mu(b)$$

这是积性函数，所以可以线性筛然后 $O(n^0.5)$ 出解

1455: 罗马游戏

斜堆

3262: 陌上花开

CDQ，先按第一维排序，然后分治，分治回来每块都已经按照第二维排序，接着用树状数组来维护左边对右边的贡献，复杂度 $O(nlog^2n)$

2150: 部落战争

从上往下连边，然后最小路径覆盖

3065: 带插入区间K小值

数据结构模版题（详细题解看跳蚤国王Blog

2555: SubString

后缀平衡树模版题

4146: [AMPPZ2014]Divisors

每一维排序后相邻点连边，然后最短路

4143: [AMPPZ2014]The Lawyer

每一天分别考虑，然后就随便 dp

4145: [AMPPZ2014]The Prices

状压

4423: [AMPPZ2013]Bytehattan

对偶图，假如边两边是同个联通块那么边两端就断开

4276: [ONTAK2015]Bajtman i Okrągły Robin

按 v 从大到小然后匈牙利

3550: [ONTAK2010]Vacation

单纯形

4245: [ONTAK2015]OR-XOR

按位贪心考虑

3544: [ONTAK2010]Creative Accounting

前缀和然后对于每一位 $O(nlogn)$ 二分查找

2013: [Ceoi2010]A huge tower

从小到大插入，看有多少合法的位置能够插入

2386: [Ceoi2011]Team

基数排序完贪心考虑，设 $f(x)$ 表示前 x 个人的最多组数

1768: [Ceoi2009]logs

一行行扫下来，一行扫过后维护每一列往上连续多少个 1 并让其升序

2275: [Coci2010]HRPA

答案是那个数的 Fib 构成的最小的数（并不会证明）

3810: [Coci2015]Stanovi

记忆化搜索

2223: [Coci 2009]PATULJCI

主席树

4291: [PA2015]Kieszonkowe

删掉最小的奇数即可

3714: [PA2014]Kuglarz

转成 MST

3709: [PA2014]Bohater

对于回血大于扣血的怪物，当前能打的就找回血最多的（相对扣血前），然后对于其他的就找回血最多的（相对扣血后）