技术教程 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus) 题解 正文

2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus) 题解

2022-10-08,,,

题目列表

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的位上是1

                f[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$ 个两两相同的组合的总共情况是

\[\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 ll

const 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;

}

I. Binary Supersonic Utahraptors

题意：略

Solution

答案恒定不变，签到题

Code 
int n,m,k;

void solve() {

    int cnt_y=0,cnt_r=0;

    cin>>n>>m>>k;

    for(int i=1,x;i<=n;++i){

        cin>>x;

        cnt_y+=(x==0);

    }

    for(int i=1,x;i<=m;++i){

        cin>>x;

        cnt_r+=(x>0);

    }

    cout<

J. Burnished Security Updates

题意：略

Solution

考虑二分图染色（签到题）

Code 


const int maxn = 3e5 + 100, mod = 1e9 + 7;

int n, m, cnt, sz, col[maxn], ok = 1;

vector e[maxn];

void dfs(int u, int fa, int co) {

    col[u] = co;

    if (co == 1) cnt++;

    sz++;

    for (int v: e[u]) {

        if (v == fa) continue;

        if (col[v] == col[u]) {

            ok = 0;

            return;

        }

        if (!col[v]) dfs(v, u, -co);

    }

}

int main() {

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {

        int u, v;

        cin >> u >> v;

        e[u].push_back(v);

        e[v].push_back(u);

    }

    int ans = 0;

    for (int i = 1; i <= n; i++) {

        if (!col[i]) {

            cnt = sz = 0;

            dfs(i, 0, 1);

            if (!ok) {

                cout << -1;

                return 0;

            }

            ans += min(sz - cnt, cnt);

        }

    }

    cout << ans;

}

M. Brilliant Sequence of Umbrellas

构造一个长度至少为 $\left \lceil \frac{2}{3}\sqrt{n} \right \rceil $ 的递增数组，使得两两做 $gcd$ 也是递增的。

Solution

由于 $gcd$ 的数组也是递增的，那么要让数组尽可能的长，就要让 $gcd$ 增长的尽可能慢。

通过打表前面几个数

\[1 \ 2 \ 6 \ 15 \ 35 \ 56 \ 72 \ 99 \\
gcd数组:2 \ 3 \ 5 \ 7 \ 8 \ 9 \ 11
\]

可以发现 \(gcd\) 数组要添加的数，应当是与最后一个和倒数第二个都互质的数，然后原数组就是 \(gcd\) 数组相乘回去

Code 


typedef long long ll;

const int mod = 998244353;

const int N = 1e5 + 10;

vector a{1, 2, 6}, g{1, 2, 3};

void solve() {

    ll n;

    cin >> n;

    ll k = ceil(2 * sqrt(n) * 1.0 / 3);

    int cnt = 0;

    for (int i = 0; i < a.size(); ++i) {

        if (a[i] <= n) cnt++;

        if (cnt >= k) break;

    }

    if (cnt >= k) {

        cout << k << '\n';

        for (int i = 0; i < k; ++i) {

            cout << a[i] << " \n"[i == k - 1];

        }

    } else {

        cout << "-1\n";

    }

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr), cout.tie(nullptr);

    int t = 1;

    for (int i = 4; i <= 1e6; ++i) {

        if (__gcd(g.back(), i) == 1 $&&$ __gcd(g[g.size() - 2], i) == 1) {

            if (g.back() * i <= 1e12) a.push_back(g.back() * i), g.push_back(i);

            else break;

        }

    }

    while (t--) {

        solve();

    }

    return 0;

}

N. Best Solution Unknown

$n$个数，总共进行$n-1$次操作。每次操作选两个相邻的数，删去较小值，若两数相等，则任意删除其一，留下的数增大$1$。 问最后有可能剩下的数有哪些，按升序输出下标。
每次随机取比赛，求会有哪些人可能赢

Solution

队友：线段树+分治
因为本题中删除一个数后会改变相邻关系，所以某一段区间的最大值可以把该区间剩余的数删完的。那么把当前区间的最大值挑出来加入答案后，会分成左右两个小区间，其各自的区间最大值也是有可能留到最后的，因此可以用分治加线段树维护区间最值来做这题。

\([1，2，5，3，2]\) ，对于这组数来说，最终留下的数一定是5，因为在取出最大值5后，分成了 \([1, 2]\) 和$ [3, 2]$ 两个区间，但是我们发现两个区间的最大值2和3只能成长到3和4，也就是\([3，5，4]\)， 所以无法留到最后。从这里我们可以发现，对于每个分出来的区间，都会有一个区间下限，如果该区间的最大值在成长之后达不到这个下限，那么这个区间就是无法产生“胜者”的。

接下来考虑如何获得每个区间的下限。我们用三元组\({L, R, V}\)来表示\([L, R]\)这段区间的下限值为\(V\)，假设该区间最大值的下标为\(M\)，那对于左区间的下限\(V_1\)来说，不仅要“打败"\(a_M\), 还要在删完右区间后达到\(V\), 只有这样才能继续往大的区间吃。

即\(V_1 = Max(a_M,V+M-R-1)\)。

Code 


int n, a[maxn], maxx[maxn * 4];

vector ans;

void build(int id, int l, int r) {

    if (l == r) {

        maxx[id] = l;

    } else {

        build(ls, l, mid);

        build(rs, mid + 1, r);

        if (a[maxx[ls]] > a[maxx[rs]])

            maxx[id] = maxx[ls];

        else

            maxx[id] = maxx[rs];

    }

}

int query(int id, int l, int r, int ql, int qr) {

    if (ql <= l && qr >= r) return maxx[id];

    if (qr <= mid)

        return query(ls, l, mid, ql, qr);

    else if (ql > mid)

        return query(rs, mid + 1, r, ql, qr);

    else {

        int res1 = query(ls, l, mid, ql, mid);

        int res2 = query(rs, mid + 1, r, mid + 1, qr);

        if(a[res1] > a[res2]) return res1;

        else return res2;

    }

}

void solve(int l, int r, int maxx) {

    int pos = query(1, 1, n, l, r);

    if(a[pos] + r - l < maxx) return;

    ans.push_back(pos);

    if(l <= pos - 1) solve(l, pos - 1, max(a[pos], maxx + pos - 1 - r));

    if(pos + 1 <= r) solve(pos + 1, r, max(a[pos], maxx + l - pos - 1));

}

int main() {

    ios;

    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    build(1, 1, n);

    solve(1, n, 0);

    cout << ans.size() << endl;

    sort(ans.begin(), ans.end());

    for (int i : ans) cout << i << " ";

}

2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus) 题解的相关教程结束。

《2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus) 题解.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!