仓库源文站点原文


title: Codeforces Round 940 (Div. 2) and CodeCraft-23 date: 2024-04-27 21:39:12 updated: 2024-04-27 21:39:12 categories:


A. Stickogon

大致题意

有 $n$ 根木棍,问最多可以构成多少个等边的多边形,要求每一条边只能用一根木棍

思路

构建成三角形就行,统计一下,每种边的数量整除 $3$ 即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            ++mp[tmp];
        }

        int ans = 0;
        for (auto &[a, b]: mp) ans += b / 3;
        cout << ans << endl;
    }
}

B. A BIT of a Construction

大致题意

给出一个整数 $k$,要求构造一个数组,其长度为给出的 $n$,每一项都不是负数,且满足 $\sum^n_{i=1} a_i = k$

问如何使得整个数组的 $a_1 | a_2 | \dots | a_n$ 的数中,比特位为 $1$ 数量最多

思路

由于求和为 $k$,且每一项都不是负数,那么必然可以得到所有值都比 $k$ 小,最大起码也是等于

而题目要求比特位为 $1$ 尽可能多,而尽可能多的值必然是 $2^x - 1$,所以找最大的 $x$ 使得 $2^x \leq k$,然后剩下的数值不重要了,补充满 $k$ 即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, k;
        cin >> n >> k;
        if (n == 1) {
            cout << k << endl;
            continue;
        }
        int a = 0;
        for (int i = 31; i >= 0; --i) {
            if (k >= (1 << i) - 1) {
                a = (1 << i) - 1;
                break;
            }
        }
        cout << a << ' ' << k - a;
        for (int i = 2; i < n; ++i) cout << ' ' << 0;
        cout << endl;
    }
}

C. How Does the Rook Move?

大致题意

有一个棋盘,现在黑白两方轮着下,其中玩家使用白棋,电脑使用黑棋

电脑下棋的位置固定是根据用户下的位置的相反位置,例如玩家这一步下了 $(i, j)$,那么电脑则会下 $(j, i)$。 如果 $i = j$,那么就跳过电脑的回合

现在下的每一个棋都是城堡(类似中国象棋中的车),需要保证任何一步下的位置都必定不会被出现相互吃的情况,且目前已经有几个位置已经下好了,问剩下的还有几种可能下法

思路

容易猜出这是一个递推的题,类似斐波那契数列。当然可以仔细来看

首先,已经下了几步这件事是无意义的,因为去掉已经下的那些行/列,就会回到一个普通的没有下的棋盘, 说白了就是个干扰项,只需要把给出的棋盘大小减去已经下过的位置的行数,就可以得到新的棋盘行数

同样的,不仅是已经下的位置,你现在下的位置也是如此,一旦下好了+电脑下好,再把下好的那几行/列删掉,就是一个新的空棋盘,所以这是一个递推

接下来是如何得到递推公式了,因为下哪一行都一样,删掉之后就是空白的,且根据要求,每一行必定有一个城堡,且求算的总数并不关系下的顺序,只看最后的样子, 那么我们可以只考虑第一行(因为第一行必定有一个城堡,可能是白的也可能是黑的)

如果第一行,我下了最左上角的位置,那么就会得到一个 $n - 1$ 的棋盘($i = j$,机器人没有地方下)

如果第一行,我下了不是第一个位置,那么机器人必定会下对角线位置,即得到一个 $n - 2$ 的棋盘。因为这样的位置有 $n - 1$ 个, 且第一行可能是黑的也可能是白的,所以递推公式就是

$a_n = a_{n-1} + 2 \times (n - 1) \times a_{n - 2}$

AC code

#define int long long

void solve() {
    vector<int> ans(3e5 + 10);
    ans[0] = 1;
    ans[1] = 1;
    constexpr int mod = 1e9 + 7;
    for (int i = 2; i < ans.size(); ++i) {
        ans[i] = (ans[i - 1] + (ans[i - 2] * (i - 1) * 2) % mod) % mod;
    }

    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, k;
        cin >> n >> k;
        set<int> st;
        for (int i = 0; i < k; ++i) {
            int u, v;
            cin >> u >> v;
            st.insert(u);
            st.insert(v);
        }
        cout << ans[n - st.size()] << endl;
    }
}

D. A BIT of an Inequality

大致题意

给出一个数组,要求找到一个元祖 $(x, y, z)$,满足 $0 \leq x \leq y \leq z \leq n, f(x, y) \oplus f(y, z) > f(x, z)$

其中 $f(l, r) = a_l \oplus a_{l+1} \oplus a_{l+2} \oplus \dots \oplus a_{r}$

问有多少个不同的元组

思路

很容易得到,$f(x, z) \oplus a_y = f(x, y) \oplus f(y, z)$,就是再异或上一边 $a_y$ 能让值变大

那么必然,原来 $a_y$ 中,最大的为 $1$ 那个比特位,$f(x, z)$ 为 $0$,毕竟如果是 $1$ 的话,肯定就变小了

接下来从这个角度分析,由于 $x \leq y \leq z$,所以 $f(x, z)$ 中一定已经异或过一次 $a_y$ 了, 而已知一个比特位 $a_y$ 是 $1$ 但是 $f(x, z)$ 是 $0$,那么必然在 $[x, z]$ 中,这个比特位为 $1$ 的,出现了偶数次,且至少 $2$ 次

所以只需要对于每一个可能的 $y$,找这个 $y$ 最大的为 $1$ 的那个比特位,为 $1$ 的次数恰好为偶数,且包含 $y$ 的区间数量即可。我采用了双向的奇偶标记

例如第三个例子,可以得到如下的表格

index origin 2^2 forward back 2^1 forward back 2^0 forward back
0 7 1 odd even 1 odd even 1 odd even
1 3 0 odd odd 1 even odd 1 even odd
2 7 1 even odd 1 odd even 1 odd even
3 2 0 even even 1 even odd 0 odd odd
4 1 0 even even 0 even even 1 even odd

这个表格的制作方式:

然后统计某个位置,左边的 back 下不同类型的数量和右边的 forward 不同的类型数量,再做乘法即可

AC code

#define int long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto &i: data) cin >> i;
        vector<bool> flag[32][2];
        int cntR[32][2] = {}, cntL[32][2] = {}, ans = 0;
        bool cf[43] = {};
        for (auto &i: flag) i[0].resize(n);
        for (auto &i: flag) i[1].resize(n);
        for (int v = 0; v < n; ++v) {
            for (int i = 0; i < 32; ++i) {
                if (data[v] & (1ll << i)) cf[i] = !cf[i];
                flag[i][0][v] = cf[i];
                ++cntR[i][cf[i]];
            }
        }
        for (int v = n - 1; v >= 0; --v) {
            for (int i = 0; i < 32; ++i) {
                if (data[v] & (1ll << i)) cf[i] = !cf[i];
                flag[i][1][v] = cf[i];
            }
        }
        for (int v = 0; v < n; ++v) {
            for (int i = 0; i < 32; ++i) ++cntL[i][flag[i][1][v]];
            for (int i = 31; i >= 0; --i) if (data[v] & (1ll << i)) {
                ans += cntL[i][0] * cntR[i][0] + cntL[i][1] * cntR[i][1];
                break;
            }
            for (int i = 0; i < 32; ++i) --cntR[i][flag[i][0][v]];
        }
        cout << ans << endl;
    }
}