跳转至

2020 CCPC Wannafly Winter Camp Day2

B

题意

给定 \(m_1,m_2,\cdots,m_n\) 和 \(k\)，求下列方程的解： $$ \bigoplus _{i=1} ^n x_i = k,0 \le x_i\le m_i $$

(\(1 \le n \le 50\)，\(0 \le m_i,k < 2^{31}\))

题解

考虑统计第 \(i\) 位往上所有数都贴上界，第 \(i\) 位存在至少一个数不贴上界的方案数：

首先所有数第 \(i\) 位往上都确定了，那么这些位置都必须要和 \(k\) 相同，如果从某一位开始不同，那么更低位的答案均为 \(0\)。

因为所有数第 \(i\) 位往上都贴上界，每一位都是确定的，因此只需要考虑第 \(i\) 及更低位可能的方案。如果存在一个数这一位脱离了上界，即上界为 \(1\) 但是它选择了 \(0\)，那么它低位就可以随便选择，因此只要第 \(i\) 位的 \(1\) 的奇偶性和 \(k\) 相同，那么除了这个数以外的其它数都可以随便选择，且最后可以唯一地确定这个数。

设 \(x_j\) 为考虑前 \(j\) 个数且异或起来第 \(i\) 位为 \(0\) 的方案数， \(y_j\) 为考虑前 \(j\) 个数且异或起来第 \(i\) 位为 \(1\) 的方案数。此时没有任何限制，因此转移方程很好写：

\[ \begin{aligned} x_j=2^ix_{j-1}+(m_{j} \bmod 2^i+1)y_{j-1}[m_j \operatorname{and}2^i=2^i] \newline y_j=2^iy_{j-1}+(m_{j} \bmod 2^i+1)x_{j-1}[m_j \operatorname{and}2^i=2^i] \end{aligned} \]

其中初始状态为 \(x_0=1,y_0=0\)。

最终如果 \(k\) 的这一位是 \(0\)，那么答案为 \(\dfrac{x_n}{2^{i}}\)，因为我们随便钦定一个这一位选 \(0\) 的数，其它数选完后它有且只有唯一的一个选择，因此要除掉它可以随意选的方案数；如果 \(k\) 的这一位是 \(1\)，那么答案为 \(\dfrac{y_n - \prod \limits _{j=1}^n (m_{j} \bmod 2^i+1)[m_j \operatorname{and}2^i=2^i]}{2^{i}}\)，减掉的部分是因为如果所有数都贴上界那么我们会在之后计入答案，所以要将其减去。

综上，我们只需要从高到低对每一位进行一次计数即可，如果遇到某一位全取 \(1\) 和 \(k\) 不同，计算完这一位直接跳出即可。需要注意的是如果所有数全取上界也是一种可行方案，最后需要判断一下这一种。设我们需要考虑的位数为 \(w\)，则时间复杂度为 \(O(nw)\)。（所以 \(n\) 可以开到 \(10^5\)）

D

题意

给定字符串 \(s\)，对于它的每个前缀 \(S\)，求 \(\{\operatorname{LCP}(i,j)|1 \le i < j \le \operatorname{len}(S)\}\) 的 \(\operatorname{mex}\) 值。其中 \(\operatorname{LCP}(i,j)\) 表示字符串第 \(i\) 个后缀和第 \(j\) 个后缀的最长公共前缀长度。(\(1 \le |s| \le 10^6\))

题解

考虑一个结论，设 \(A= \{\operatorname{LCP}(i,j)|1 \le i < j \le \operatorname{len}(S)\}\)，如果 \(x \in A\)，则 \(1,2,\cdots,x-1 \in A\)。

证明也很简单，假设 \(\operatorname{LCP}(i,j)=x\)，则有 \(\operatorname{LCP}(i+1,j+1)=x-1\)。但是这不能保证 \(0 \in A\)，因为当 \(x=1\) 时 \(\max(i-1,j-1)\) 可能大于 \(\operatorname{len}(S)\)。不过 \(0 \in A\) 等价于字符串中不是全部由同一个字符组成，这也是很好判断的。

因此，我们只需要考虑一个前缀由同一个字符组成，以及任意两个后缀 \(\operatorname{LCP}\) 的最大值。注意到后者其实等价于最长的至少出现两次的子串，可以使用 SAM 逐步插入字符得到对应前缀的答案。插入一个字符后，新增的最长的至少出现两次的子串，其实就是当前整个字符串所有后缀中，出现次数大于 \(1\) 且最长的那个，对应的长度就是新增节点在 parent 树上父亲的 \(\text{len}\)。因此只需要每次插入维护这个最大值，以及判断是否有相同的字符，就可以得到对应集合的 \(\operatorname{mex}\)。

F

题意

给出一颗 \(n\) 个节点带边权的树，初始所有点权均为 \(0\)，树的根节点为 \(1\)，有 \(q\) 次下列两种操作：

  • 给 \(x\) 点增加 \(y\) 的权值。
  • 将根节点换为 \(x\)。

每次操作后，设根为 \(x\)，需要输出下列值： $$ \sum_{i\text{ is son of }x} w_{x,i}f_i $$ 其中 \(w_{x,i}\) 是 \(x\) 和 \(i\) 之间边的权值，\(f_i\) 是以 \(i\) 为根的子树中所有点的权值之和。

(\(1 \le n,q, \le 10^6\))

题解

考虑直接 dfn 序维护点权和，这样每次查询和根节点的度数有关，很容易被卡爆。可以使用树链剖分，每次 dfn 序只考虑重儿子的子树部分和子树外部分这两部分，轻儿子部分对应的权值每次修改时维护，查询时 \(O(1)\) 获取。注意到一个点跳到祖先最多有 \(O(\log n)\) 条轻边，因此可以通过预处理出重链的顶端，直接暴力向上跳进行修改。此外还需要使用树状数组维护上述的 dfn 区间和，总时间复杂度为 \(O(n \log n)\)。

H

题意

给定 \(n\)，求最大的 \(m\) ，使得存在一个长度为 \(n\) 的值域为 \([1,m]\) 的序列 \(a_1,a_2,\cdots,a_n\)，满足对任意 \(1 \le x < y \le m\)，都存在 \(1 \le i < n\) 满足 \((a_i=x \land a_{i+1}=y) \lor (a_i=y \land a_{i+1}=x)\)。如果 \(n \le 2 \times 10^6\)，你需要构造出一个这样的序列。(\(1 \le n \le 10^{18}\))

题解

题目等价于给定一个 \(m\) 个点的完全无向图，增加尽量少的边（允许重边）使得图存在一条欧拉路径或欧拉回路，对应的序列长度即为新图的边数 \(+1\)。

如果 \(m\) 是奇数，则原图所有点度数都是偶数，是连通欧拉图，不需要增加新的边，对应序列长度为 \(\dfrac{m(m-1)}{2}+1\)。

如果 \(m\) 是偶数，则原图所有点度数都是奇数，需要将 \(m-2\) 个点的度数都变为偶数才能存在欧拉路径，对应序列长度为 \(\dfrac{m(m-1)+m-2}{2}+1\)。

可以发现随着 \(m\) 增加对应序列长度也是递增的，因此可以进行二分，二分后再跑欧拉回路或欧拉路径，多余的长度随便放数字即可。注意欧拉路径起点一定选择度数为奇数的。

使用 cur 数组优化删除边，即可用 Hierholzer 算法在 \(O(n+m)\) 的时间内找到欧拉回路或欧拉路径。

I

题意

给定一个 \(n \times m\) 的方格图，每个格子需要放非负的硬币，有 \(k\) 个如下约束：

  • \((x,y)\) 和 \((X,Y)\) 位置的硬币之和不能少于 \(z\)，保证 \((x,y)\) 和 \((X,Y)\) 相邻。

求所有位置硬币数之和的最小值。(\(1 \le n \times m \le 1500\)，\(0 \le k \le n \times m\))

题解

方格图是二分图，将每个限制条件改为在对应两个点连接对应权值的边，可以证明这个二分图的最大权匹配就是所有硬币之和的最小值：

考虑这个图的最大权匹配，任意有匹配的两点它们的硬币之和必然不能小于该边的边权，从而所有硬币之和不能小于所有匹配边的边权，即最大权匹配。且我们可以达到这个下界，考虑 KM 算法最终合法的顶标分配方案，它们的顶标之和即为最大权匹配，且它们因为是合法顶标，也满足任意边权不超过其两点的顶标之和，从而是将顶标改为对应点的硬币数即得到一组合法解。

因此直接费用流求最大权匹配即可，注意所有左侧的点也要直接向汇点连边！因为最大权匹配不一定是最大匹配，有的点不匹配要给他流向汇点的机会。

J

题意

给出一个 2-SAT 模板，构造一组有解的数据，把下述代码中的 \(\text{CNT}\) 卡到 \(\dfrac{n^2}{2}\) 或以上。\(n\) 是输入给定的，构造数据由 \(m\) 个形如 \(x \lor y = 1\) 的方程构成，其中 \(x,y\) 可以是任意的 \(b_i\) 或 \(\neg b_i\)。方程数 \(m\) 不能超过 \(n\)。(\(1 \le n \le 3000\))

 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
43
#include<cstdio>
using namespace std;
const int N=3010;
int g[N<<1],nxt[N<<1],v[N<<1],num;
int q[N<<1],t;
bool vis[N<<1];
int CNT;
int n,m;
void add(int x,int y){
    nxt[++num]=g[x];
    v[num]=y;
    g[x]=num;
}
bool dfs(int x){
    CNT++;
    if(vis[x>n?x-n:x+n])return 0;
    if(vis[x])return 1;
    vis[q[++t]=x]=1;
    for(int i=g[x];i;i=nxt[i])if(!dfs(v[i]))return 0;
    return 1;
}
bool solve(){
    for(int i=1;i<=n;i++)if(!vis[i]&&!vis[i+n]){
        t=0;
        if(!dfs(i)){
            while(t)vis[q[t--]]=0;
            if(!dfs(i+n))return 0;
        }
    }
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        if(x<0)x=n-x;if(y<0)y=n-y;
        add(x>n?x-n:x+n,y);add(y>n?y-n:y+n,x);
    }
    solve();
    return 0;
}

题解

这份代码就是从 \(1\) 到 \(n\)，如果这个点已经赋值了，就跳过；否则先给这个点赋 \(\text{true}\)，通过 dfs 确定所有能确定的点，如果没有矛盾就让他赋为 \(\text{true}\)；如果出现矛盾，再给他赋 \(\text{false}\)，如果没有矛盾就让他赋为 \(\text{false}\)，如果还是有矛盾就输出无解。

那么我们构造下面这个序列： $$ b_1\to b_2 \to\cdots\to b_{n-1} \to b_n \to \neg b_{n} \to \neg b_{n-1} \to \cdots \to \neg b_2 \to \neg b_1 $$ 这样从 \(b_1\) 开始，遍历到 \(\neg b_{n}\) 出现矛盾，因此选择 \(\neg b_1\)；接着 \(b_2\) 也是遍历到 \(\neg b_{n}\) 出现矛盾，选择了 \(\neg b_2\)；每一个变量都是同理，总枚举量即为等差数列求和 \(\dfrac{n(n+1)}{2}\)。

最后将上述序列改为 \(\lor\) 的形式，即： $$ \begin{cases} \neg b_i \lor b_{i+1} = 1,1 \le i < n \newline \neg b_n \lor \neg b_n = 1 \end{cases} $$

K

题意

有 \(n\) 个字符串 \(s_i\)，每个字符串有一个权值 \(a_i\)，你需要选一些按顺序拼一起将其组成 \(S\)，每选一次第 \(i\) 个字符串就需要花费 \(a_i\)，最小化总权值或判断无解。(\(1 \le n,S,\sum |s_i| \le 5 \times 10^5\))

题解

直接 AC 自动机多串匹配进行 dp 看起来很暴力，但因为总串长和 \(n\) 同数量级，而 fail 树每往上跳一层长度都会减少，因此 fail 树高不会超过 \(O(\sqrt n)\)，从而总复杂度为 \(O(n \sqrt n)\)。

这辣鸡题卡常，AC自动机用结构体就会 T。

回到页面顶部