CSP-S 备战所有题题解(week 2)

· · 个人记录

Day 1

P1373 小 a 和 uim 之大逃离

话说相同不应该都死吗？

看到 n,m,k 都小的一匹，考虑全部枚举了。

定义状态：

dp_{i,j,d,p}

表示这一步走到了 i,j，差值为 d，最后一步是由 p 走的。

方程过于板子了：

dp[i][j][d][0]=dp[i][j][d][0]+dp[i-1][j][(d-a[i][j]+k)%k][1];
dp[i][j][d][0]=dp[i][j][d][0]+dp[i][j-1][(d-a[i][j]+k)%k][1];
dp[i][j][d][1]=dp[i][j][d][1]+dp[i-1][j][(d+a[i][j])%k][0];
dp[i][j][d][1]=dp[i][j][d][1]+dp[i][j-1][(d+a[i][j])%k][0];

——k 记得加 1。

CF31E Funny Game

由于太像C的TJ了，所以我讲详细一点（以证明我不是C的）。

首先这是道博弈论对吧（要是这都看不出来就。。）

考虑一下，当先手拿和不拿 i+1 号石头的情况。

如果不拿，等于正在处理 i 号石头，因为如果 i+1 都不拿，i+k(k>1) 都不会拿。则有 dp_i=dp_{i+1}

如果拿，那么这一步获得的 s 为 \sum\limits_{j=1}^{i+1} a_j，而后手获得 dp_{i+1}，相当于获得的差值为 \sum a_j-dp_{i+1}。

所以 dp_i=\max dp_{i+1},\sum a_j-dp_{i+1}。

由于 dp_n 无意义，从 dp_{n-1}=a_n 开始即可。

答案：dp_{1}。

CF1006F Xor-Paths

双向广搜，一眼就会。

由于向下走 n 步，向右走 m 步，每次可以选走向下和向右，总的时间复杂度高达 O(2^{n+m})，直接挂掉！

考虑一下双向搜索，从顶点和终点往对角线的方向搜即可。

Day 2 考试

T1

简述题意：(i,j)\to (i+1,j) 有一条 a_i+b_j 的边；(i,j)\to (i,j+1) 有一条 c_i+d_j 的边。a_i,b_i,c_i,d_i 单调不降。问图的最小生成树。

因为单调不降，所以答案只会从左边和上面两条边转移过来。答案等于 \sum \min a_i+b_j,c_i+d_j。

定义 A_i=c_i-a_i,B_i=d_i-b_i，这一坨答案为 a_i+b_j+\min\{0,A_i+B_j\}，把 a_i+b_j 提出了，对 \min\{0,A_i+B_j\} 排序即可。

T2

简述题意：求两个字符串的编辑距离，如果大于 50，输出 -1。

编辑距离的 DP 公式原因，在此处不再赘述。定义 dp_{i,j} 表示 a 的前 i 个字符和 b 的前 j 个字符的编辑距离。

dp_{i,j}=\begin{cases}\max i,j&\min i,j=0\\\min\{dp_{i,j-1},dp_{i-1,j},dp_{i-1,j-1}\}+1& a_i\ne b_j\\dp_{i-1,j-1}&a_i=b_j\end{cases}

对于距离超过 50 的字符串，进行 dp 是没有意义的。所以用 f_{i,c} 记录 dp_{i,j+c-50} 即可。

T4

我自己的题解

Day 3

P2279 [HNOI2003] 消防局的设立

贪心题。

如果一个点没有收到消防站的覆盖，那么就在它的祖先处设立一个消防站。从深度最低的往最高的扫即可。

为什么这是最优的？在父亲节点处不是还能照顾到自己的兄弟吗？注意：这个点是目前深度最低的无法覆盖的点，如果祖父盖不到，说明这个点深度一定不是最低的。

每建立一个消防局，扫描两层即可。看起来这是 O(n^ 3) 的，实际上每条边最多被扫到 n 次，时间复杂度不超过 O(n^2)。

注意将 a 的父亲设为它自己，这样所有点的祖先不超过 1。

for(int i=2;i<=n;i++)
{
  cin>>a[i].fa;
  a[i].gf=a[a[i].fa].fa;
  a[i].dep=a[a[i].fa].dep+1;
  a[i].i=i;
  G[i].push_back(a[i].fa);
  G[a[i].fa].push_back(i);
}
sort(a+1,a+n+1); // 按深度排序
for(int i=1;i<=n;i++) dy[a[i].i]=i;
for(int i=1;i<=n;i++)
{
  if(x1[i]||x2[i]) continue;
  x1[dy[a[i].gf]]=1;ans++;
  dfs(a[i].gf,2);
}

CF893E Counting Arrays

一道很好的计数题喵。

先考虑正负数的问题。因为 1\le x\le 10^6，所以这些数字乘起来一定是一个正数，所以我们先乱填前 y-1 个数的正负，最后一个在改回来就可以了。所以正负数的可能方案数为 2^{y-1}。

这个题一看就要质因数分解。定义：

x=\prod_{i=1}^kp_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}

其中 p_1,p_2,\cdots p_k 是两两不等的质数。

对于每一个指数 e_i，它们会被分到这 y 个数上去。由于这是一个序列，所以这 y 个数本质不同。但是这 e_i 个 p_i 本质相同，并且可空。这时就变成了大型记录片之《小球进盒子·第三集》。

球 盒子 可空？ 方案数
相同 不同 可 \dbinom {n+m-1}{m-1}

——by sLMxf

所以对于每一个指数 e_i，它的方案数为 \dbinom{y+e_i-1}{y-1}。

所以最终的答案为：

2^{y-1}\prod_{i=1}^k \dbinom{y+e_i-1}{y-1}

分解质因数是 O(\sqrt x)，快速幂是 O(\log y) 的，组合数预处理 O(\max y)，单次查询 O(1)。

故总的时间复杂度为 O(\max y+q\sqrt x)。

Day 4

CF360B Levko and Array

我自己的题解

P9751 旅游巴士

最短路。

首先这题的 二分套分层图 BFS 一眼就可以看出来对吧。

然而交上去荣获 100\color{red}\texttt{WA}。为什么？因为要建一张反图。

Buy Low Sell High

本题和 CF1974G 很像。

事实证明，像到是一点也不像，但都是反悔贪心。

考虑一种贪心：每次只要能够赚取利益，就从 q 中拿一个最小的出来，否则把这个东西放进 q。

然而会有这样一种 hack：

3
1 2 114514

显然这个时候拿一个 114514-1=114513 是最优解，但程序会输出 1。为什么？因为 2 把 1 抵掉了。

考虑这样一件事：每一次用从之前拿过的最优解，把最大的替换掉。先考虑拿新的，在考虑拿旧的。

典型反悔贪心。时间复杂度是优先队列的 O(n\log n)。代码如下：

for(int i=1;i<=n;i++)
{
  cin>>m;
  if(!q.empty()&&q.top()<m)
  {
    ans+=m-q.top();
    q.pop();
    q.push(m); // 再放一个旧的进去
  }
  q.push(m);
}

附：大型纪录片之《小球进盒子·全篇》

球 (n) 盒 (m) 可空？ 答案
相同 相同 可 \text{partition}(n+m,m)
相同 相同 否 \text{partition}(n,m)
相同 不同 可 \dbinom {n+m-1}{m-1}
相同 不同 否 \dbinom{n-1}{m-1}
不同 相同 可 \sum\limits^n_{i=1}S(n,i)=\sum\limits^n_{i=1}{n\brace{i}}
不同 相同 否 S(n,m)={{n}\brace{m}}
不同 不同 可 m^n
不同 不同 否 m!S(n,m)=m!{{n}\brace{m}}