闲言

比赛链接:传送门

没有代码,放心食用。

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 签到题

字典树

从最高一层递归处理,如果当前位置的子孙中有01两种选择(即表示当前层可以选两种,那么总有办法使得最大值在当前位置异或为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,赛中忘了线性基怎么写了,带的板子里又没有线性基真的想死,还好思路记得最后给过了,希望不是因为数据水

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

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


Tip

建议改下J题面

在$u_i$可以到达的所有城市中,是否存在某些城市的异或和为$x_i$

似乎是要求非空集合的异或和,此时普通的线性基无法正确判断x=0的情况,例如:

1
2
3
2 1
9 13
1 2 0

应该是No,但是由于线性基在判能否可以异或得到是实际是在看$x$为1的比特位,处理不了0这种特殊数据,我那份通过的代码会输出Yes

  • 如果需要处理,则需要修改查询函数。

(因为有学弟在问,下面是回复,应该挺好理解的)

只要查看线性基中向量的数目是否等于已有的集合的数量即可判断是否能够异或得到0。线性基可以异或得到既有集合中的所有数,当线性基中向量的数目小于集合元素的数目,说明可以替换插入的数从而得到其它的线性基。换句话说,异或得到某个数的方式不唯一,那么就可以使之异或得到0。