2022 ICPC第一场网络赛几句话题解

2022 ICPC第一场网络赛解题报告

rank31

A. 01 Sequence

一个结论题，对于一段连续的$k$个$1$，$k$为偶数下可以消灭掉$\lfloor \frac{k}{2} \rfloor$个$0$，$k$为奇数下可以消灭$\lfloor \frac{k}{2}\rfloor+2$个$0$。如果无法消灭完所有$0$，输出剩下的$0$的个数除以$3$。

然后只要用前缀和处理区间信息就好了。很多人写线段树属于是魔怔了，不带修改为啥要线段树（

B. Power Station

还没补

C. Delete The Tree

输出叶子个数

D. Find the Number

找到区间$[l, r]$中的$x$，使得$x$在二进制下$1$的个数和后缀$0$的个数相等。

两种做法：

1. 预处理出所有满足条件的$x$，之后在询问区间中查找。
2. 首先枚举$1$的个数，就可以确定一段，之后从高位到低位枚举哪一位于$r$不同，然后填$1$并判断。有一些小细节

E. Tower Defence

还没补

F. Bacteria

挺裸的积性筛板子

首先考虑$f(p)$等于以$p$为结尾的数列个数，那么最终的答案就是$ans = \sum_{1}^{n}f(i)$。
考虑$f(p)$的组合含义：将$p$进行质因数分解后填入$k$个位置的方案。那么很显然$f(p \times q) (\ \gcd(p, q)=1)$可以分为$p, q$进行放置质因数，并且方案独立。很显然是个积性函数。

最后只要预处理出$f(pri^c)$的值（插板法），用Min_25板子套上去就能过。

G. Read the Documentation

暴力dp冲了就过。

H. Step Debugging

用栈进行模拟计数，签到题。

I. Permutation

给出一个排列，求循环位移后所有的排列的康托展开之和。

首先对原排列进行考虑，$a_i$产生的贡献为$count(j>i,a_j < a_i) \times (n-i)!$。再对所有的排列进行考虑：若$a_i > a_j(i < j)$，这一对数$(i, j)$产生的贡献为$\sum_{l=j-i}^{n-1}l!$，发现跟他们的距离有关系。如果$a_i < a_j (i < j)$ 那么距离就应该是$n - (j - i)$。

最后我们只需要统计出所有的$cnt[d] == count( (a_i > a_j) \&\& j-i == d )$

$ans = \sum_{d=1}^{n-1}cnt[d] \times \sum_{l=d}^{n-1}l!$

然后令$b[i]$表示数字$i$出现的位置，目标求出所有$cnt[d] = (j < i) \&\& b[j] - b[i]==d$。暴力求$O(N^2)$显然是不行的。
考虑分治：分为两个区间，递归求解区间内贡献，再考虑算出两个区间之间的答案。然后发现两个区间之间的贡献可以用$O(NlogN)$的多项式来解出（N是原排列长度），但进行$N$次多项式复杂度反而更劣了。然而分治到小区间时我们可以直接用$O(len^2)$的暴力计算，当区间长度满足$len^2 < NlogN$时就直接暴力算，否则继续分治。

最后的复杂度为$O(N \sqrt{NlogN})$
考场上没有想到先转化成$b$再进行分治，但是直觉确实是往多项式和分治这边想的，有点可惜。

J. Gachapon

队友写的，没看题

K. Pyramad

也是队友写的，但是知道一点思路。

最朴素的做法是$O(N^3)$的$DP$，因为状态比较多无法通过。但是一个关键信息是$x_i \leq5000$。假如前$71$轮只管加$w$，接下来$71$轮只管加能力值就可以超过$5000$，那么后面的$n - 142$轮一定是全赢。可以利用这个信息来对状态数量进行限制：

令$f[i][j][k]$表示前$i$轮，输了$j$轮，$w=k$时的最大能力值，那么显然第二维$j \leq 142$，第三维$k$也有一定限制（我也不清楚具体是多少，尽量搞大，能过就行），然后冲个$DP$。

L. LCS-like Problem

队友秒了