浙江龙网

  1. 首页 > 生活百科 > >

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]\)
Codell 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$的值
Codell 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$ 个两两相同的组合的总共情况是
\[\frac{(2n)!}{n!*2^n} = \frac{\begin{pmatrix} 2n\\n\end{pmatrix} * n!}{2^n}\]然后每个组合其实可以看成是一个点，然后有一个重要的结论，\(n\) 个点的生成树个数为 \(n^{n-2}\) 个 。然后由于每个最后连的边，具体到这道题里都是四条，所以最后还要乘上 \(4^{n - 2}\)
所以最后的公式就是
\[\frac{\begin{pmatrix} 2n\\n\end{pmatrix}*n!}{2^n}*4^{n-1}*n^{n-2}\]
Code#include<bits/stdc++.h>#define debug(x) cerr << #x << " = " << x << '\n';using namespace std;typedef long long ll;#define int llconst int inf = 0x3f3f3f3f;const ll mod = 998244353;const int N = 1e6 + 10;int fac[N], inv[N];ll ksm(ll a, ll b) {ll ans = 1;while (b) {if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}ll c(ll k, ll n) {return fac[n] % mod * inv[k] % mod * inv[n - k] % mod;}void solve() {int n;cin >> n;if (n & 1) {cout << 0 << '\n';return;}if (n == 2) {cout << 1 << '\n';return;}int k = n / 2;ll ans = c(k, n) * fac[k] % mod;for (int i = 1; i <= k; ++i) {ans = ans * ksm(2, mod - 2) % mod;}for (int i = 1; i <= k - 1; ++i) {ans = ans * 4 % mod;}cout << ans * ksm(k, k - 2) % mod << '\n';}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t = 1;// cin >> t;fac[0] = inv[0] = 1;for (int i = 1; i <= 1e6; ++i) {fac[i] = fac[i - 1] * i % mod;inv[i] = ksm(fac[i], mod - 2) % mod;}while(t--) {solve();}return 0;}

推荐阅读


上一篇：Div. 2 Codeforces Round #823 A-D

下一篇：工作7年收集到的git命令