有可能是最后的一篇题解了……

GDOI保佑……

50/50

4326: NOIP2015 运输计划

二分答案，然后将长度大于答案的边提取来，看其交集中有没有长度够长的边可以减掉（这步可以直接树上前缀和修改），$O(nlogn)$

4325: NOIP2015 斗地主

模拟+搜索题，状压也是可以的

3677: [Apio2014]连珠线

十分恶心的树DP……

3205: [Apio2013]机器人

类似斯坦纳树的思路，设 $F(l,r,x,y)$ 表示编号为 $l-r$ 的机器人到了 $(x,y)$ 的最少操作次数，然后就DP+最短路

最短路是单位最短路，所以弄两个单调队列，前者放置已经知道距离的点，后者放遍历过的点，每次拿两个队列的最小值去扩展就行

3206: [Apio2013]道路费用

一开始先求出 $k$ 条边优先级最高的MST，再把 $k$ 条边去掉，缩联通块成点，把原图中没在MST中出现且跨联通块的边取出，然后再枚举 $k$ 条边的修建情况，做 $2^k$ 次MST，每次做完dfs一遍，预处理出原图中将结点分为两个集合时中间边的最小费用，这样就能得到 $k$ 条边的最优费用

4071: [Apio2015]巴邻旁之桥

△这题AC了然而在UOJ被Hack了所以我不打算写题解QwQ

4069: [Apio2015]巴厘岛的雕塑

按位考虑，前四个子任务做 $O(n^3)$ 的DP就可以了，第五个就做个 $O(n^2)$ 的DP

4070: [Apio2015]雅加达的摩天楼

最短路，然而对于移动能力小的doge会有很多重边，所以移动能力小于某个阀值的我们把边先建出来，移动能力大的直接建边

3671: [Noi2014]随机数生成器

按照题目描述建图，然后每次找最小的数并将它左下和右上的全部数删去，这步可以 $O(n^2)$

由于空间限制，两个数组要充分利用，且常数要优化得好……

4542: [Hnoi2016]大数

给一数字串，每次询问 $S$ 的一个子串中有多少子串是素数 $P$ 的倍数

首先预处理出 $F(i)$ 表示把 $S[i+1..n]$ 换成0之后数字串的值（模 $P$)

然后我们就可以莫队啦

（对于 $P=2,5$ 的要特殊处理）

4198: [Noi2015]荷马史诗

裸哈夫曼树

4199: [Noi2015]品酒大会

逆序插入SAM中，建出来的FailTree就是后缀树，然后就容易了

4197: [Noi2015]寿司晚宴

首先我们先将可能在质因数分解中出现两次的数记录下来（才8个）

二进制压一下，然后枚举数判断取不取，$O(500*2^8)$

对于分解后有相同大质数的我们一并解决

4500: 矩阵

看有没有四个约束构成矩形且对角相加不相等

（然而直接dfs就可以了

4546: codechef XRQRS

按二进制建持久化Trie

4547: Hdu5171 小奇的集合

先分类讨论，对于越加越大的就弄个矩阵快速幂

3530: [Sdoi2014]数数

AC自动机+数位DP

4200: [Noi2015]小园丁与老司机

首先弄个DP（顺便记录转移路径（路径居然还有多条简直SXBK

然后再求个有下界的最小可行流

3994: [SDOI2015]约数个数和

求 $\sum \sum d(ij)$，其中 $d(x)$ 是 $x$ 的约数个数

有个结论：$d(nm)=\sum_{i|n} \sum_{j|m} [gcd(i,j)=1]$（因为能一一对应）

然后式子就变成 $$\begin{align} \sum \sum d(ij) & =\sum \sum \sum_{a|i} \sum_{b|j} [gcd(a,b)=1] \\ & =\sum_a \sum_b \lfloor \frac na \rfloor \lfloor \frac mb \rfloor [gcd(a,b)=1] \\ & = \sum_a \sum_b \lfloor \frac na \rfloor \lfloor \frac mb \rfloor \sum_{d|gcd(a,b)} \mu(d) \\ & =\sum_d \mu(d) F(\lfloor \frac nd \rfloor)F(\lfloor \frac md \rfloor) \end{align}$$

其中 $F(n)=\sum \lfloor \frac ni \rfloor=\sum G(i)$，后者是约数个数

3990: [SDOI2015]排序

首先操作序列怎么改顺序都可以，然后就dfs咯

4552: [Tjoi2016&Heoi2016]排序

妈呀BC原题（见BC#76E题）

4551: [Tjoi2016&Heoi2016]树

离线后逆序连边，然后就可以并查集咯

4554: [Tjoi2016&Heoi2016]游戏

求出横竖联通的块然后二分匹配

4553: [Tjoi2016&Heoi2016]序列

求出每个数修改后的最小值和最大值，得到DP转移方程，然后就求三维偏序（CDQ时一半按最大值排序一半按原值排序）

2809: [Apio2012]dispatching

可并堆我选择斜堆

2303: [Apio2011]方格染色

首先这相当于每一行等于上面那行经过一次xor变换得到的结果，xor变换是指所有奇数列取反或偶数列取反

先考虑没有限制的情况，那么方案数等于 $2^m2^{n-1}$

对于同一行有多个列有限制的话，那么也可以推出第一行这两列的关系

因此可以把限制全部推到第一行（而且还要判断合不合法

当然那些在第一行的限制就固定的了

方案数等于 $2^{未限制块数}2^{未限制行数}$

1911: [Apio2010]特别行动队

斜率优化

1179: [Apio2009]Atm

缩环跑拓扑图

1177: [Apio2009]Oil

我们可以枚举三个正方形之间的分割线（就同方向2种+不同方向4种）

1178: [Apio2009]CONVENTION会议中心

第一问可以右端点排序后贪心

第二问我们预处理出 $F[i][j]$ 表示点 $i$ 后面接 $2^j$ 个订单的最小右端点（离散化后倍增求）

然后我们可以按编号从小到大考虑，设之前确定放置的订单中在前面的为 $A$，在后面的为 $B$，若 $Ans(A.Right+1，B.Left-1)=Ans(A.Right+1，Left-1)+1+Ans(Right+1，B.Left-1)$ 则放置

$Ans$ 是指一段区间最多放多少订单，可以通过之前的预处理得到

1912: [Apio2010]patrol 巡逻

找两次最长路（第一次找完之后将路上的边全部取负）（第二次找用树DP）

4576: [Usaco2016 Open]262144

设 $F[i][j]$ 表示第 $i$ 格往右合并出一个 $j$ 时右端的位置

4563: [Haoi2016]放棋子

你把所有障碍移到对角线，就会发现这不是要求错排方案嘛

4562: [Haoi2016]食物链

搜索

4566: [Haoi2016]找相同字符

反向建广义SAM然后就可以求了（每个节点的贡献为 $(Len[x]-Len[Fail(x)])*cnt1*cnt2$

4557: [JLoi2016]侦察守卫

树DP

4567: [Scoi2016]背单词

Trie建出来，将没被标记的点删掉，然后贪心，每次先走小子树

4569: [Scoi2016]萌萌哒

离线做法：建立ST表然后将限制转成两对ST表的限制（就是用并查集来维护每一层的ST表）然后就可以一层层往下推

在线做法：建立ST表然后将限制转成两对ST表的限制然后递归合并（可以发现最多 $nlogn$ 个节点所以最多合并 $nlogn$ 次

4568: [Scoi2016]幸运数字

可以倍增+线性基，可以点分+线性基

点分的话建出重心树，每个节点维护其到祖父重心的线性基，询问就可以找到最深公共重心然后玩一波

4571: [Scoi2016]美味

对于加完才xor的情况我们就拎出权值线段树处理偏移

按位贪心，我们会发现满足条件的 $Ai$ 是在某个区间内的，这就可以线段树了嘛

1508: [NOI2003]Game

搜索

3884: 上帝与集合的正确用法

首先设 $F(p)$ 为当模数为 $p$ 时的值，设 $p=2^ka$，其中 $a$ 为奇数

$$\begin{align} 2^{2^{2^{...}}} \mod p &= 2^{2^{2^{...}}-k} \mod a \\ &= 2^{(2^{2^{...}}-k) \mod {\varphi(a)}} \mod a \\ &= 2^{2^{2^{...}} \mod {\varphi(a)}-k \mod {\varphi(a)}} \mod a \end{align}$$

也就是说 $F(p)=2^{F(\varphi(a))-k \mod {\varphi(a)}} \mod p$

1443: [JSOI2009]游戏Game

二分图匹配，假如能完全匹配则必败，否则找未盖点并随着匹配方案搜索查找可行点

4586: [Usaco2016 Open]Landscaping

算出每个地方的变化情况（该增加还是该减少）然后每次找代价最小的移动方式

update:16.5.24

从Claris那里获得了更不错的解法

这道题本质是费用流，那么退流我们怎么办呢？退流其实相当于取消决策，所以这里我们利用这一点来解决。

我们建立两个堆，往右走的用Q1，往左走的用Q2，然后假如此刻位置上是正的则在Q1中找最小代价，累加进答案并扔到Q2，负的则同理

距离代价我们可以统一减去 $(pos*Z)$，这样就可以处理距离的绝对值问题

1975: [Sdoi2010]魔法猪学院

K短路，建个堆，按“当前已走过的距离+距离终点最近距离”为关键字从小到大排序，每次取最小的一个方案扩展

4570: [Scoi2016]妖怪

右上凸包上的每个点都有可能成为最大值，求出并得到每个点成为最大值时K的范围，统计一下即可

4530: [Bjoi2014]大融合

在线：启发式合并+LCT

离线：对于最后的森林建立树链剖分，维护子树大小和最远祖先，然后倒序删边

4338: BJOI2015 糖果

求 $P^{n}_{C^{m}_{m+K-1}}$

先通过求1-m的逆元算出C，然后乘n次算出P

4550: 小奇的博弈 & 2281: [Sdoi2011]黑白棋

【错题，应该假设白棋只能往右，黑棋只能往左】

将一个“白+黑”的间距设为一堆石子，问题变成Nim-K问题

必败态为将所有堆二进制分位后每个位上1的个数是 $K+1$ 的倍数