XXI Open Cup, Grand Prix of Belarus 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest 题解 _生活百科

题目列表

C. Brave Seekers of Unicorns
D. Bank Security Unification
G. Biological Software Utilities
I. Binary Supersonic Utahraptors
J. Burnished Security Updates
M. Brilliant Sequence of Umbrellas
N. Best Solution Unknown

C. Brave Seekers of Unicorns题目给出了一个$unicorn$序列的定义，暂且叫它完美序列，完美序列满足如下条件：

非空递增且序列元素的值域为 $[1,n]$
没有三个连续的元素异或和 $=0$

给定一个整数n，对完美序列计数（需要求出完美序列个数），答案需要对 $998244353$ 取模

Solution设 $dp_i$ 表示以$i$ 结尾的数组的方案数即
\[dp[i]= \sum\limits_{j=1}^{i-1} (dp[j]-dp[i \bigoplus j]) (i?j<j)\]求出等于 $i\oplus j$ 的数去掉同时维护前缀和，对于二进制下的 $i$ ,如果第 $x$ 位为 $1$，那么$ [2x,2{x+1}-1]$之间的数都是(除了最高位的$1$除外)，解释来说，因为要考虑$i⊕j⊕k=0 $的情况，根据异或的性质$i,j,k$三个数的每一个二进制数位上最多只有两个$1$，那就枚举$i$的除最高位的二进制位为$1$ 的数位 $x$，固定 $j$ 的第$x$位是也是$1$,此时$k$ 的第 $x $位为必然为$0$，那么第$x$ 位往后都可以随便乱取,不会有影响,也就是$k$的范围是$[2^x,2^{x+1}-1]$

Code

ll dp[N],f[N],n;void solve() {cin >> n;for (int i = 1; i <= n; ++i) {f[i] = dp[i - 1] + 1;int num = i, bit = 0;while (num) {if ((num & 1) && num != 1) {//此时i的位上是1f[i] = (f[i] - dp[min(ksm(2, bit + 1) - 1, (ll) i)] + dp[min(ksm(2, bit) - 1, (ll) i)] + mod) % mod;}num >>= 1;bit++;}dp[i] = (dp[i - 1] + f[i]) % mod;}cout << dp[n] << endl;}

D. Bank Security Unification题意：有 $n$个路由器，第 $i$ 个路由器的的频度是 $f_i$, 你选择任意个路由器打开，假设打开$k$了个路由器 $i_1 , i_2 , … , i_ k$,，则此时的网络安全系数的值是 $∑ _{i=1}^{k-1}a_i\oplus a_{i+1}$,输出网络安全系数的最大值是多少，反之就是说从一个长度为 $n$ 序列 $a$ 中取出一个子序列，使得相邻两个元素的按位与值的和最大。求出这个最大的和

Solution首先我们希望按位与和最大，就是在希望我们选取的相邻两个元素的二进制位尽可能相同，显然$dp[i][j]$表示当前在$i$位置，打开$j$ 个路由器的最大按位与值（安全系数），但是此时暴力转移的$dp$是$O(n^2)$ 的，而且$n=1e6$显然也开不了二维的$dp$数组，那么可以选择优化，让$dp_i$表示当前最后一位为 $i$ 的子序列答案最大是多少，如果考虑当前的一位，显然是与之二进制相同的位是贡献最大的，所以记录 $lst[i][0/1] $表示二进制第 $i$ 位上一个是$ 0/1$ 最近的位置在哪里，每次只从对应的$lst$ 转移而来,然后每次取更新$lst$的值

Code

ll n;ll f[N],dp[N],bit[66][2];void solve() {cin >> n;ll mx_bit = 0;for (int i = 1; i <= n; ++i) {cin >> f[i];mx_bit = max(mx_bit, f[i]);}mx_bit = ceil(log2(mx_bit)) + 1;// dbg(mx_bit);for (int i = 1; i <= n; ++i) {//贪心取最近的相同的二进制位if (i > 1) {for (int j = 0; j<=mx_bit; ++j) {int tmp = ((f[i] & (1ll << j)) > 0);int pos = bit[j][tmp];//最近的每位二进制&相同的位置dp[i] = max(dp[i], dp[pos] + (f[pos] & f[i]));}}// dbg(dp[i]);for (int j = 0; j <= mx_bit; ++j) {//更新bit[j][((f[i] & (1ll << j)) > 0)] = i;}}ll ans = 0;for (int i = 1; i <= n; ++i) {ans = max(ans, dp[i]);}cout << ans << endl; }

G. Biological Software Utilities给出一种好树的定义，删除掉一些边后能变成两两匹配的树是好树。现在给出节点的个数，求好树有多少种

Solution考虑到树的形状没有定，且也不知道删除哪一些点，但是发现最后的情况一定是两两匹配的，那么倒过来想就是把很多两两匹配完的点，通过连一些边变成一些树。首先把 $2n$ 个点分成 $n$ 个两两相同的组合的总共情况是