CSUST - 2021 组队选拔赛

A Find Subsequence

（WA了一晚上，回来把树状数组重写了一下就过了？？？）

树状数组 + DP

令dp[i]表示前$i$个元素中，以a[i]结尾的只出现一次的子序列的数目。

1. a[i]在之前未出现过：

   $$dp[i]=1+\sum_{k=1}^{i-1}dp[k]$$

2. a[i]在之前出现过，考虑上一次出现的位置。显然当前位置使得上一次出现的位置之前的贡献变成$0$，同时处在区间$[last[a_i], i-1]$的贡献不改变。

   $$dp[i]=\sum_{k=last[a_i]}^{i-1}dp[k]$$ dp[last[a[i]]]将变成0。

B operation

• ((a & b) + (a | b)) >> 1等价于(a + b) >> 1
• 最后一次合并可以等价为，将数组从中划分成两半，分别操作完后再合并

由于可能的答案很少，考虑枚举分割点记忆化搜索。

C 翻墙之旅

10.2组队训练有一样的题：Gym 103306A Alice Birthday

SoSDP

令所有点构成的点集为$sn$，考虑一个包含点1的点集$s$，令f[s]表示使得$s$中只有一个连通分量的（点集内部的）删边方案数，cnt[s]表示点集$s$内的边数。在$s$中，点1一定能到达连通分量内的所有点，且此时外部的所有的边都可以选择删或者不删，那么该状态对$s$内的所有点的贡献即为$2^{cnt[sn-s]}\times f[s]$。

cnt[s]的计算不再赘述，关键讲f[s]：

$s$内所有边的存在形式有$2^{cnt[s]}$种，减去有多个连通分量的情况即为只有一个连通分量的数目， $$2^{cnt[s]}-\sum_{s_0 \subset s} f[s_0]\times 2^{cnt[s-s_0]}$$ 使用SoSDP（子集DP）计算，为了避免重复计算，可以限定$s_0$中包含$s$的lowbit，或者其它的某点。

1
2
3

for (int s = 0; s < bit[n]; s++)
  for (int s0 = (s - 1) & s; s0; s0 = (s0 - 1) & s)
    if (s0 & (s & -s)) ...

D SumMin

如果你了解Floyd枚举的各个变量的含义，这就是个裸题。

1
2
3

for (int k = 1; k <= n; k++) // 中间点集合
  for (int i = 1; i <= n; i++) // 起点
    for (int j = 1; j <= n; j++) // 终点

删点顺序逆过来便是枚举中间点集合的顺序。

E Number Game

BFS

由于$k\leq 1e6$，模$k$的余数有限，考虑计算余数$r$对应的最小值，那么0对应的即为答案。由于使用的为BFS最先出现的一定更小，所以对于已经出现的余数我们不再考虑。

答案记录：由于每一个余数只出现一次，且只由一种余数转移而来，我们使用last[], digit[]分别记录当前数的前一个余数和当前选择的数字。

F Number Game2

容斥

注意一下包含相同元素的排列数，$P_n / 2^{cnt}$。

$$Ans=|S_{全部情况}|-|S_{至少有一种相邻}|+|S_{至少有两种相邻}|-\dots$$

G 小郑的疑惑

这种看似离散（但是实际数据的大小不大）的一般都是转换为贡献解决。本题贡献为元素出现的个数，直接开个数组cnt[n]记录。

令times[m]表示相乘组成$m$的方案数（a[i] * a[j] = m），注意重复计算的问题。

注意到，ans[k]的值为其因子的贡献（times）之和，这里考虑$O(n\log n)$枚举累加即可。

H 签到题

字典树

从最高一层递归处理，如果当前位置的子孙中有0和1两种选择（即表示当前层可以选两种，那么总有办法使得最大值在当前位置异或为1），那么该位上结果必须加上（即加上1 << i），然后取走两边的最小值；如果只有一种子孙，显然可以直接避开不加当前位置的值。

I 一道题

单调栈 + 前缀和 + 二分

由于|运算的性质: $$a_l | a_{l+1} | \dots a_{r-1} | a_r \geq \max{a_l, a_{l+1}, \dots a_{r-1}, a_r}$$

所以，当且仅当区间中存在某个数与最大值的按位或大于最大值，区间合法。

一种很朴素的想法是：枚举最大值，找到其所在的区间端点，再找到左右最近的使得区间合法的位置，之后加入贡献。

下面一步步解决这些问题：

1. 区间端点：单调栈维护第一个大于当前值的位置。
2. 左右最近的使之合法的位置：记录每一个比特位的前缀和，枚举最大值的位0的比特位，使用二分去查找。

如果区间内最大值出现多次，我们考虑一种不会重复计算的方式：

令左右端点为（不在区间内，出界时为正无穷大）l,r。要求a[l] > a[i], a[r] >= a[i]，这样层层包含的结构使得每对相同最大值值都只计算了一次。

J City Union

（小声bb，赛中忘了线性基怎么写了，带的板子里又没有线性基真的想死，还好思路记得最后给过了，希望不是因为数据水）

• 查询集合元素是否可以异或得到某个数：线性基
• 维护集合：并查集

那么思路明确，并查集维护线性基即可。

1
2
3

2 1
9 13
1 2 0