NOIP 2018 集训 Day 4

动态规划

动态规划基础

动态规划问题的特征

1. 子问题重复
2. 最优子结构，无后效性（可以通过扩充状态满足这个特征）

$\text{LIS}$

关于导弹拦截的介绍在这篇笔记里已经有了。

神级技巧！注意lower_bound(begin,end,x)和upper_bound(begin,end,x)返回的都是迭代器！这么好的东西，我们怎么能不利用？

可以用*lower_bound(begin,end,x)=x将数组中第一个大于等于$x$的数直接更改为$x$。

$\text{LCS}$

此处$\text{LCS}$指的是最长公共子序列(Longest Common Subsequence)。

如果是两个字符串的$\text{LCS}$，那么只能通过暴力的$\text{O}(n^{2})\text{ dp}$解决。

如果是两个排列的$\text{LCS}$，可以转化为$\text{LIS}$从而在$\text{O}(n\log n)$的复杂度内解决。

考虑第二个序列中的每个数$b_{i}$，建立一个新序列$c$，$c_{i} = \text{pos} (b_{i})=\text{lower}\_\text{bound}( a , a+n , b_{i} ) - a$，
则序列$c$的一个上升子序列$c_{i_1},c_{i_2},\cdots ,c_{i_m}$就代表$a_{c_{i_1}}$对应$b_{i_1}$等，是一种公共子序列的对应。那么$\text{LIS}$就代表着$\text{LCS}$。

如果对序列的限制改成：每个字符的出现次数为$\text{O}(1)$，又怎么解呢？方法是：把一个字符拆成若干个字符来解！

对于某一个字符，如果它在第一个序列中出现多次，就把它拆分为多次出现位置的倒序。如序列$a=(1,2,3,1,3,2,4)$，序列$b=(2,1,1,2,3,1,2)$，则可以把序列$b$拆为$c=(6,2,\text{ }4,1,\text{ }4,1,\text{ }6,2,\text{ }5,3,\text{ }4,1,\text{ }6,2)$，如$2$在$a$中出现的位置为$2,6$，就拆成$6,2$。这样做的好处是，如果有$c$中的一个上升子序列，那么它同样对应着一个公共子序列；倒序保证$b$中的同一个位置的数字不会对应$a$中的多个数字，“上升”（而非“不降”）保证$a$中的同一个位置的数字不会对应$b$中的多个数字。

公共子序列

我也不记得怎么解了？

树形$\text{dp}$

聪聪可可

对于每一条路径，在它的起点和终点的$\text{LCA}$处统计数量。

定义$f[i][j](i\in [1,n],j\in \{0,1,2\})$表示以$i$为根的子树中，到$i$的距离$\text{dis}$同余于$j$的点的个数。在$\text{dfs}$到某一个点时，初始化$f[x][0]=1,f[x][1]=f[x][2]=0$。每搜完一个子节点，就给答案累加上$f[\text{ch}][0]\times f[x][0]+f[\text{ch}][1]\times f[x][2]+f[\text{ch}][2]\times f[x][1]$，再把$f[\text{ch}]$的结果累加到$f[x]$上（加的顺序要注意，防止重复计数）。

Tree

点分治。具体做法考虑中。

Black Nodes in Subgraphs

中文题面见这里。

到Vjudge提交

首先考虑预处理一些信息。

先证明一个性质：对于每一个$s$，如果可行的最小$b$为$b_1$，可行的最大$b$为$b_2$，那么对于任意$k\in \mathbb{N},k\in [b_1,b_2]$，$(s,k)$都是可行的。

证明方法：若$b_1=b_2$，显然成立。

否则从最大解中删除一个黑点，在周围寻找一个白点，如果寻找不到，就寻找一个黑点。重复上述过程，不可能一直找不到白点，因为一棵树是连通的，又有$b_1<b_2$，因此只要向最小解方向靠拢，就可以找到白点。找到白点后用白点替换删除了的黑点，解的大小即减小$1$。由于解可以不断地减小直到达到最小答案，因此证明完毕。

证明了这个结论，我们也就只需求出，对于每一个$s$，可行的$b$的最大值和最小值分别是多少。而最大值和最小值是对称的，即最大值是黑点最多，最小值是白点最多。因此我们只需要考虑最大值的做法即可。

定义$r[i]$为$i$个点的连通块中黑点的最大数目，定义$f[i][j]$为在以$i$为根的子树中，包含$i$的共有$j$个点的连通块中黑点的最大数目。$r[j]=\max(f[x][j])$。

对树进行$\text{dfs}$，对于某一棵子树的根节点$x$，先初始化$f[x][1]=\text{color[x]},\text{size}(x)=1$。接着对子节点$i$进行搜索dfs(i,x)，得到f[i][j]的所有结果（$1\le j\le \text{size}(i)$）。

为什么连通块强制包含$i$呢？因为有了根节点，才能保证是连通的呀。

接着做一遍背包：

1
2
3
4
5
6

for (int i=1;i<=size[x];i++) //在加入这棵子树前的图中选i个点，一定选根
    for (int j=0;j<=size[child];j++) //在子树中选j个点
        tempmax[i+j]=max(tempmax[i+j],f[x][i]+f[child][j]); //背包
size[x]+=size[child]; //将子树大小累加
for (int i=1;i<=size[x];i++)
    f[x][i]=tempmax[i]; //将tempmax数组中的数据转移回f数组

上述代码中使用tempmax数组的目的是在记录答案的同时不改变f数组中的数据。

遍历完$x$的所有子节点后，我们把$f[x][j]$的答案更新到$r[j]$中。

最小值同理，再做一遍即可。

背包

Median Sum

这是$\text{ta}$出的测试题，不算太难。

使用大神器$\text{bitset}$。开一个比总和大的$\text{bitset}$，初始化$\text{bs}[0]=1$，对于每一个数，将$\text{bs}\mid =\text{bs}<<a[i]$，意为从前可行的每一个和，加上$a[i]$也是可行的。计算结果时从$\frac{\text{sum}}{2}$开始往上找即可。

简单困难题

$\text{bzoj}$权限题，kule。

继续动用大神器。由于是异或，因此同一个和出现两次和没有出现是一样的，出现奇数次相当于出现$1$次。因此只需保存每一个和出现次数$\mod{2}$的值。初始化和处理过程和上题相同，最后计算答案时扫描$\text{bitset}$，把为$1$的索引的值异或起来即得答案。

No Need

题意：对于集合$A$中的某一个数$x$，若$\exists B \subset A, x \not \in B,\sum_{y\in B}y<k$，且$\sum_{y\in B\cup \left \{ x \right \}}\ge k$，则称$x$是必要的。求集合中不必要的数的个数。

注意到$\varnothing \subset A$，而对于$x\ge k$，令$B=\varnothing$，则$\sum_{y\in B}y=0<k, \sum_{y\in B\cup \left \{ x \right \}}=x\ge k$，知$x$是必要的。因此，不必要的数必小于$k$。

我们还可以证明单调性：若$a\le b$，且$a$是必要的，那么$b$也是必要的。

证明是，由于$a$是必要的，知存在满足上述条件的集合$B$。
若$b\not \in B$，则$\sum_{y\in B\cup \left \{ b \right \}}\ge \sum_{y\in B\cup \left \{ a \right \}} \ge k$。
若$b \in B$，则将$B$中的$b$换成$a$得到集合$C$，由$a\le b$知$\sum_{y\in C}y\le \sum_{y\in B}y<k$，知$C$满足题设条件。而$\sum_{y\in C\cup \left \{ b \right \}}= \sum_{y\in B\cup \left \{ a \right \}} \ge k$，证毕。

有了上下界和单调性，我们就可以进行二分了。注意，下面这段代码的真实时间复杂度是$\text{O}(n^2 \log n)$，因为$\text{bitset}$的移位操作在复杂度上是$\text{O}(n)$的，只是常数很小而已。

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
32
33
34
35
36
37
38
39
40
41
42

#include <cstdio>
#include <algorithm>
#include <bitset>
#define MAXN 5005
#define MAXBS 5005
using namespace std;
bitset<MAXBS> bs;
int a[MAXN];
int main(void){
    int n,k;
    int ll,rr;
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;i++){
        scanf("%d",a+i);
    }
    sort(a,a+n);
    n=lower_bound(a,a+n,k)-a;
    //(ll,rr] 
    ll=-1,rr=n;
    while (rr-ll>1){
        int mid=(ll+rr+1)>>1;
        int necessary=0;
        bs.reset(); // bs=0
        bs.set(0); // bs[0]=1;
        for (int i=0;i<n;i++)
            if (i!=mid)
                bs|=(bs<<a[i]);
        bs>>=(k-a[mid]);
        for (int i=0;i<a[mid];i++){
            if (bs.test(i)){
                necessary=1;
                break;
            }
        }
        if (necessary)
            rr=mid;
        else
            ll=mid;
    }
    printf("%d\n",ll+1);
    return 0;
}

当然，除了二分，我们还有$\text{O}(n^2)$的更优的解法。

二分法为什么慢呢？因为对于每一个$\text{mid}$，我们都要计算一遍除了$a_{\text{mid}}$以外的元素的组合能达到的数值。下面的方法可以避免重复计算。

我们还需要一个结论。设$s=\sum_{i=1}^{k}a_{i}$，如果$\exists B \subset A, \left\{ a_{1},a_{2},\cdots,a_{k} \right \} \cap B =\varnothing, \sum_{y\in B}y<k$，且$s+\sum_{y\in B}\ge k$，那么$a_{k}$是必要的。

证明：假设$a_k$不是必要的，那么根据单调性，$a_1,a_2,\cdots,a_k$都不是必要的。

根据题目条件，将$a_1,a_2,\cdots,a_k$按顺序加入到$B$中，则必存在$1\le j\le k$，使加入$a_1,a_2,\cdots,a_{k-1}$时，和小于$k$；加入$a_j$时，和大于等于$k$。因此$a_j$是必要的，与上述假设矛盾。

故假设不成立，$a_{k}$是必要的。

于是，我们可以根据$a_{k+1},a_{k+2},\cdots,a_{n}$的组合能达到的范围来确定$a_k$的必要性，这样就避免了$\text{bitset}$的重复计算，时间复杂度降到$\text{O}(n^2)$。

数位$\text{dp}$

Counting Digits / 梦中的统计 / 数字计数

先计算$1\le m <n$的整数中出现数字$x$出现的次数。

依次考虑每一位，考虑个位时令$t=1$，考虑十位时令$t=10$，考虑百位时令$t=100$……

那么在$T=10t$的一个完整周期内，这一位上数字$x$共出现了$t$次。

考虑不完整的那一个周期，如果这一位上的数$\lfloor\frac{n}{t}\rfloor \% 10 > x$，那么出现了完整的$t$次；如果$\lfloor\frac{n}{t}\rfloor \% 10 = x$，那么出现了$n \% t$次；如果$\lfloor\frac{n}{t}\rfloor \% 10 < x$，那么没有出现。

对于Counting Digits，暴力对每个数求解即可。优化是如果一个$x$不是解，且函数值为$y$，那么只比$x$大一点的数也不会是解，因此$x$可以增加一个大一点的数。

另外，Counting Digits可以到这里提交。

对于梦中的统计，求出端点相减即可。

“数字计数”是只有一组数据的版本。双倍经验

状态压缩

Sphere Packing

相当于求哈密顿路。状压。

状态转移的必备技巧（又名$\text{FMT}$,Fans MeeTing Fast Mobius Transform）

已知数组$a[0...2^k-1]$。设$b[i]=\sum_{j\& i=j}a[j]$（可以认为是$A$的所有子集的权值之和）。请在$\text{O}(k2^{k})$的时间内求出$b$数组的值。

暴力法：对每一个$i\in [0...2^k-1]$，枚举$j\in [0...2^k-1]$，如果满足条件，则求和。$\text{O}(4^k)$。

子集枚举法：对每一个集合$A$，枚举$A$的所有子集，进行求和。

如何枚举子集？

1
2
3
4
5
6

int i; //枚举A(表示为i)的子集
for (int j=i;;j=(j-1)&i){
    //进行操作
    if (!j)
        break;
}

时间复杂度$\text{O}(3^{k})$。

正解：进行递推。

1
2
3
4
5
6
7
8

int len=1<<k;
for (int i=0;i<k;i++){
    int tpow=1<<i;
    for (int j=0;j<len;j++){
        if (j&tpow)
            f[j]+=f[j^tpow];
    }
}

如何理解上面这段代码呢？

请看拙作第二题

补充：请注意$\text{FMT}$的应用范围！参考洛谷$11$月月赛 咕咕咕。

Upd: 这个东西又叫做 SoS (Sum over Subsets) dp。

Or Plus Max

转化：$i\mid j\le k$这个条件很难利用，我们可以求一个数组$f[k]=\max(A_i+A_j)\ \ (i\mid j=k)$，求$f[k]$的前缀最大值$g[k]=\max(f[i])\ \ (i\le k)$，则$g[k]$即为答案数组。

这么计算同样有难度。我们再进行一次转化：令$h[k]=\max(A_i+A_j)(i\subseteq k,j\subseteq j,i\neq j)$，则我们直接用$\text{FMT}$求出$k$的子集中$A$的最大值和次大值即可。

期望$\text{dp}$

分手是住院祝愿

首先考虑最优策略。假设当前亮着的编号最大的灯是$x$，则关掉它的最优策略是按下开关$x$把它关上，同时$x$的因数的灯的状态会改变。我们接着寻找下一个亮着的灯，继续如此操作。现在我们就能算出，如果一直按照最优策略，需要操作的次数。这样就能拿到$k=n$的$50$分了。

现在我们考虑随机情况。设状态$k$为“此时按照最优策略，还需操作$k$次”，$f[k]$表示从状态$k$转移到状态$k-1$所需操作次数的期望。

在状态$k$，如果我们按了正确的开关（即$k$个正确开关中的一个），那么状态就转移成了$k-1$；如果我们按了其余的$n-k$个错误的开关，我们就必须再按一次这个错误的开关，因此状态被转移到了$k+1$。而状态$k+1$要转移到状态$k-1$，首先必须回到状态$k$。于是得到$f[k]=\frac{k}{n}\times 1+\frac{n-k}{n}\times (1+f[k+1]+f[k])$。由此式知$f[n]=1,f[k]=\frac{(n-k)f[k+1]+n}{k}$。可以从$f[n]$开始，递推得到所有$f$的值。

因此若设最优策略的步数为$t$，则答案即为

$\sum^{t}_{i=k+1}f[i]+\sum^{k}_{i=1}1$

有分数怎么办？最后不是求得不就是$\text{ans}\times n! \text{ }\% 100003$的值嘛，因此计算过程中遇到除法就换成乘以逆元就好了。

WJMZBMR打osu! / Easy

期望有些很神奇的性质！

期望的线性性质 $\text{Ex}(k_1X+k_2Y)=k_1\text{Ex}(X)+k_2\text{Ex}(Y)$ （见维基百科 Expected value）

因此，期望可以乱加（逃）。只要是线性的，我们就方便处理。

考虑一段连续的o，第$k$个位置和第$k+1$个位置的得分满足$(k+1)^2-k^2=2k+1$是线性的，可以处理。因此我们得出，如果一个位置是o，那么这个位置的得分的期望可以由上一个位置的得分期望计算出。

设$f[i]$表示到第$i$步为止得分的期望，$g[i]$表示在第$i$步末尾连续o的个数的期望。设$u[i]=f[i]-f[i-1]$。

现在对第$i$步的状况进行讨论。

如果第$i$步是x，那么$u[i]=0,g[i]=0$。
如果第$i$步是o，那么根据上面的讨论，$u[i]=2g[i-1]+1,g[i]=g[i-1]+1$。
如果第$i$步是?，那么$u[i]=(0+2g[i-1]+1)\div 2=g[i-1]+0.5,g[i]=g[i-1]+0.5$。

于是只需要再使用$f[i]=f[i-1]+u[i]$计算即可。可以使用滚动数组节省空间。最后的答案即为$f[n]$。

按位或

这是篇好博客，如果看不懂我自己写的就看这里的吧。

暴力法

设$f[i]$表示从数$i$到$2^n-1$所需操作次数的期望，则$f[2^n-1]=0$，$f[x]=1+\sum_{i=0}^{2^{n}-1}f[x \mid i]\times p[i]$。于是最暴力的方法就有了：对于每一个$x$，枚举$i\not\subseteq x$，将$p[i]\times f[x\mid i]$进行累加后加上$1$，再除以$f[x]$项的系数$1-\sum_{i\subseteq x}p[i]$，即得$f[x]$。最后输出$f[0]$。

正解

看题解吧……

歌唱王国

利用$\text{KMP}$的$\text{next}$数组。

奇妙的解法

阿狸和桃子的游戏

如果只有点权，就很简单了。

加上边权了如何呢？

把边权平分到两个端点上，如果这条边被两个人分别选择，那么差值为$0$；否则这两半会累加成一个完整的边权。

tql

星之器

我们可以发现，无论操作方法如何，从初状态转移到末状态释放的能量是相等的。考虑物理中势能的概念，我们定义一个点$(x,y)$的单位势能为$E_{s}=\frac{x^2+y^2}{2}$，一个点的势能为$E_{p}=\text{cnt}(\text{star})E_s$，即星星数目乘以单位势能。定义一个状态的势能为所有点的势能之和。那么从初状态到末状态的能量释放数即为势能差。

Friends

答案就是$32^n$。可以使用$\text{long double}$直接输出。

这个答案可以从样例推得。因为每一种语言都是独立的，设语言种数为$n$，则答案一定是$a^{n}$。代入样例知$a=32$。

一道防AK好题

从结束标志$0,0,0$倒推。