2025 CCPC 广东省赛 & 江苏省赛

The 2025 Guangdong Provincial Collegiate Programming Contest

A 矩阵游戏

题目大意

• 给定一个 $n \times m$ 的 01 矩阵，以及整数 $A, B$ ，你每次可以将
• 行／一列的所有元素取反
• 问 $\sum_{i=1}^n \sum_{j=1}^m(A \times i+B \times j)\left[a_{i, j}=1\right]$ 的最大值。
• $n \leq 10^6, m \leq 10,|A|,|B| \leq 10^6, a_{i, j} \in{0,1}$

题解

• 先 $\mathcal{O}\left(2^m\right)$ 枚举每一列是否翻转，再 $\mathcal{O}\left(2^m\right)$ 枚举所有行状态。
• 对于一个行状态 $s$ ，令 $W=\sum_{j=1}^m j\left[s_j=1\right]$ ，那么对于第 $i$ 行，如果第 $i$ 行等于 $s$ ：
• 不翻转这行，贡献为 $S_1=A \cdot i \cdot c n t_1+B \cdot W$ ；
• 翻转这行，贡献为 $S_2=A \cdot i \cdot\left(m-c n t_1\right)+B \cdot\left(\frac{m(m+1)}{2}-W\right)$ 。其中 $c n t_1= popcount(\mathrm{s})$
• 那么如果第 $i$ 行要翻转，则需满足 $S_2>S_1$ ，即 $A \cdot i \cdot\left(m-2 c n t_1\right)>B\left(2 W-\frac{m(m+1)}{2}\right)$ 。
• 不难发现对于一个固定的行状态，除了 $i$ 之外的所有项都固定了。
• 这意味着我们的行翻转策略肯定是：存在一个分界点 $k$ ，当 $i \leq k$ 时，翻转第 $i$ 行；当 $i>k$ 时，不翻转第 $i$ 行。或者当 $i \leq k$ 时，不翻转第 $i$ 行；当 $i>k$ 时，翻转第 $i$ 行。
• 对每个行状态，可以采取二分的方式求出这个分界点。
• 确定分界点后，分界点前后两段贡献可以预处理前缀和快速计算。

时间复杂度 $\mathcal{O}\left(2^{2 m} \log n\right)$ 。

#include <bits/stdc++.h>
using i64 = long long;
using ull = unsigned long long;
using i128 = __int128;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
template <class T1, class T2> ostream &operator<<(ostream &os, const std::pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << '\n'; }
using pii = pair<int, int>;
const int inf = 1e18;

void solve() {
    int n = read();
    int m = read();
    int A = read();
    int B = read();

    vector<int> a(n);
    vector<vector<int>> buk(1 << m);
    for (int i = 0; i < n; i++) {
        auto &x = a[i];
        string s; cin >> s;
        for(int j = 0; j < m; j++) {
            x |= (s[j] - '0') << j;
        }
        buk[x].eb(i + 1);
    }

    auto getcw = [&](int s) -> pii {
        int cnt = __builtin_popcountll(s);
        int w = 0;
        for (int j = 1; j <= m; j++) {
            if (s >> (j - 1) & 1) w += j;
        }
        return pii(cnt, w);
    };

    vector<int> siz(1 << m);
    vector<vector<int>> sum(1 << m);
    for (int s = 0; s < (1 << m); s++) {
        siz[s] = buk[s].size();
        sum[s].assign(siz[s] + 1, 0);
        for (int i = 1; i <= siz[s]; i++) {
            sum[s][i] = sum[s][i - 1] + buk[s][i - 1];
        }
    }

    int ans = -4e18;
    for (int s1 = 0; s1 < (1 << m); s1++) {

        int res = 0;
        for (int s2 = 0; s2 < (1 << m); s2++) {

            int s = s1 ^ s2;
            int sz = siz[s2];
            if (sz == 0) continue;

            auto [cnt, w] = getcw(s);

            auto getSum = [&](int l, int r) -> int { 
                return sum[s2][r] - sum[s2][l - 1]; 
            };
            auto calc = [&](int i, int op) -> int {
                if (op == 1) {
                    return A * i * (m - cnt) + B * ((m + 1) * m / 2 - w);                
                } else {
                    return A * i * cnt + B * w;
                }
            };
            auto getType = [&](int i) -> bool { 
                return calc(i, 1) > calc(i, 0);
            };
            
            int type = getType(buk[s2][0]);
            int k = 0;
            for (int L = 0, R = sz - 1; L <= R; ) {
                int mid = L + R >> 1;
                int pos = buk[s2][mid];
                if (getType(pos) == type) k = mid, L = mid + 1;
                else R = mid - 1;
            }

            k++;

            if (type) {
                // for (int i = 0; i <= k; i++) res += calc(buk[s2][i], 1);
                // for (int i = k + 1; i < sz; i++) res += calc(buk[s2][i], 0);
                res += A * getSum(k + 1, sz) * cnt + B * w * (sz - k);
                res += A * getSum(1, k) * (m - cnt) + B * ((m + 1) * m / 2ll - w) * (k);
            } else {
                // for (int i = 0; i <= k; i++) res += calc(buk[s2][i], 0);
                // for (int i = k + 1; i < sz; i++) res += calc(buk[s2][i], 1);
                res += A * getSum(1, k) * cnt + B * w * k;
                res += A * getSum(k + 1, sz) * (m - cnt) + B * ((m + 1) * m / 2ll - w) * (sz - k);
            }
            // for (auto x : buk[s2]) res += calc(x, getType(x));
        }
        ans = max(ans, res);
    }

    cout << ans << '\n';
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

I 队伍取名

题目大意

• 一堆名字三个字的人，问有多少三人一队组队方式使得每个人名选一个不同位置的字组成的名字是队里的一个人名
• $n \leq 10^5$

题解

• 枚举一个人 $i$ 的名字作为队伍名（题目已经保证名字两两不同）。
• 考虑计算 $f_{i,s}$ 表示和 $i$ 的名字里每个字是否相同的状态恰好为二进制数 $s$ 的人名个数。
• 这个并不好直接统计，可以先统计 $g_{i,s}$ 表示和 $i$ 的名字里每个字是否相同的状态为二进制数 $s$ 的超集的人名个数，然后进行 fwt / SOSdp 或者暴力容斥都可以（因为 $s$ 的集合大小只有 2^3）计算出 $f$ 。
• $g$ 可以直接 $2^3$ 枚举每个人名字的子集统计。统计的方式可以直接用 map/unordered_map 存 vector 或者名字的哈希。
• 然后考虑如何利用 $f$ 统计答案，显然 $f_{i, 0}$ 先忽略，然后考虑两种情况：两个人与 $i$ 的相同状态是否相同，如果不相同，那么显然任何两个人选出来，因为与 $i$ 的名字相同的地方不完全一样，所以一定都是可以组成 $i$ 的名字的，暴力 $8^2$枚举，个数相乘就可以了。如果相同，那么要求就是 $popcount(s) \geq 2$ 的状态 $s$ 才行，那么这一部分的答案就是 $\binom{f_i, s}{2}$ ，然后累加起来就行。
• 根据容斥和统计的实现方式，复杂度为 $\mathcal{O}\left(2^3 n \log n\right)$ 或者 $\mathcal{O}\left(4^3 n \log n\right)$ 或者 $\mathcal{O}\left(2^3 n\right)$ 或者 $\mathcal{O}\left(4^3 n\right)$ 。

经典套路恰好和至少。

用 SOSdp 实现的。

补题的时候发现，随手敲了个 base = 19937 的自然溢出被卡了，然后随手换了个 base = 19260817 就过了。

#include <bits/stdc++.h>
using i64 = long long;
using ull = unsigned long long;
using i128 = __int128;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using namespace std;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
template <class T1, class T2> ostream &operator<<(ostream &os, const std::pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << '\n'; }
using pii = pair<int, int>;
const int inf = 1e18;

void solve() {
    const int S = 1 << 3;
    using sname = array<int, 3>; 

    int n = read();

    vector<sname> a(n);
    vector<map<ull, int>> buk(S);

    for (auto &arr : a) {
        for (auto &x : arr) {
            x = read();
        }
    }

    ull bas = 19260817;
    auto gethash = [&](auto s) -> ull {
        ull res = 0;
        for (auto x : s) res = res * bas + x;
        return res;
    };

    for (auto &arr : a) {
        for (int s = 0; s < S; s++) {
            vector<int> t;
            for (int i = 0; i < 3; i++) {
                if (s >> i & 1) {
                    t.eb(arr[i]);
                }
            }
            buk[s][gethash(t)]++;
        }
    }

    vector g(n, vector(S, 0));
    for (int i = 0; i < n; i++) {
        auto arr = a[i];
        for (int s = 0; s < S; s++) {
            vector<int> t;
            for (int i = 0; i < 3; i++) {
                if (s >> i & 1) {
                    t.eb(arr[i]);
                }
            }
            g[i][s] = buk[s][gethash(t)] - 1;
        }
    }

    // for (int i = 0; i < n; i++) {
    //     auto arr = a[i];
    //     for (int s = 0; s < S; s++) {
    //         cerr << "g[i][s]: " << i << " " << s << " " << g[i][s] << '\n';
    //     }
    // }

    auto f = g;
    for (auto &f : f) {
        for (int i = 0; i < 3; i++) {
            for (int s = 0; s < S; s++) {
                if (s >> i & 1) {
                    f[s ^ (1 << i)] -= f[s];
                }
            }
        }
    }
    

    // for (int i = 0; i < n; i++) {
    //     auto arr = a[i];
    //     for (int s = 0; s < S; s++) {
    //         cerr << "f[i][s]: " << i << " " << s << " " << f[i][s] << '\n';
    //     }
    // }

    int ans = 0;
    for (auto &f : f) {
        int res = 0;
        for (int s1 = 1; s1 < S; s1++) {
            for (int s2 = s1; s2 < S; s2++) {
                if (s1 != s2) {
                    res += f[s1] * f[s2];
                } else {
                    if (__builtin_popcountll(s1) < 2) continue;
                    int x = f[s1];
                    res += x * (x - 1) / 2;
                }
            }
        }

        ans += res;
    }

    cout << ans << '\n';
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

G 货币系统

题目大意

• 给一个货币系统，$f(x)$ 表示在尽量多换大面额纸币的情况下用多少张纸币才能凑数 $x$ 元，给定 $m$ 问满足 $f(i)=m$ 的正整数 $i$ 有多少个
• 多组询问
• $n \leq 10^5, q \leq 10^6, A_i \leq 10^6, m_i \leq 10^9$

题解

• 对于给定的数组 $\lbrace A_k \rbrace _{k=1}^n$ ，显然有 $f\left(x+A_n, n\right)=f(x, n)+1$ ，因此只需要先算出对于 $x \in\left[1, A_n\right]$ 的情况下 $f(x, n)$ 的值，对于 $x>A_n$ 情况，直接可得 $f(x, n)=f\left(x \bmod A_n, n\right)+\left\lfloor x / A_n\right\rfloor$ 。
• 设 $\lbrace B_k \rbrace _{k=1}^{\infty}$ 数组中的元素 $B_k$ 表示对于 $x \in\left[1, A_n\right]$ 的情况下满足 $f(x, n)=k$ 的 $x$ 的个数，显然这个数组的所有元素之和为 $A_n$ ，并且可以发现对于 $k>A_n$ 有 $B_k=0$ ，因此只需要求这个数组的前 $A_n$ 项。
• 由此可以发现，满足 $f(x, n)=1$ 的 $x$ 只能有 $B_1$ 个，满足 $f(x, n)=2$ 的 $x$ 有 $B_1+B_2$ 个，因为对于 $B_1$ 中的每个 $x$ ， $f\left(x+A_n, n\right)=2$ ，同理满足 $f(x, n)=3$ 的 $x$ 有 $B_1+B_2+B_3$ 个，因为对于 $B_1$ 中的每个 $x$ ， $f\left(x+2 A_n, n\right)=3$ ，而对于 $B_2$ 中的每个 $x$ ， $f\left(x+A_n, n\right)=3$ 。
• 以此类推可得，满足 $f(x, n)=m$ 的 $x$ 恰好有 $\sum_{k=1}^m B_k$ 个，因此要解出本题，只需要先算出对于 $x \in\left[1, A_n\right]$ 的情况下 $f(x, n)$ 的值，再利用这些值算出 $\lbrace B_k\rbrace_{k=1}^{A_n}$ 数组，再对其做前缀和，根据 $\lbrace B_k\rbrace_{k=1}^{\infty}$ 的性质，当询问一个小于等于 $A_n$ 的 $m$ 时答案即为 $\sum_{k=1}^m B_k$ ，而当询问一个大于 $A_n$ 的 $m$ 时答案即为 $\sum_{k=1}^m B_k=\sum_{k=1}^{A_n} B_k$ 。
• 预处理复杂度为 $\mathcal{O}\left(A_n\right)$ ，处理询问复杂度为 $\mathcal{O}(1)$ ，因此总的复杂度为 $\mathcal{O}\left(\max \left(A_n, q\right)\right)$ 。

对于那些 $x > A_n$ 的 $x$，只能由前面的加上若干个 $A_n$ 组成。

赛时的打表其实有这个规律了，但是可能太洪文了不够冷静没仔细想

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
using namespace std;
#define eb emplace_back
#define pb 
int read(int x = 0, int f = 0, char ch = getchar()) {
	while (ch < 48 or ch > 57) f = ch == 45, ch = getchar();
	while (48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
	return f ? -x : x; 
}
const int N = 1e5 + 5;
const int M = 2e6 + 5;
const int P = 998244353;

void solve() {
	int n = read();
	int q = read();
	
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) a[i] = read();
	
	int m = a[n];
	
	vector<int> dp(m + 1), cnt(m + 1);
	for (int i = 1, j = 1; i <= m; i++) {
		while (j + 1 <= n and a[j + 1] <= i) j++;
		dp[i] = dp[i - a[j]] + 1;
		cnt[dp[i]]++;
	}
	vector<int> sum(m + 1);
	for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + cnt[i];
	
	for (int i = 1; i <= q; i++) {
		int x = read();
		if (x <= a[n]) {
			cout << sum[x] << " ";	
		} else {
			cout << sum[a[n]] << " ";
		}
	}
}

signed main() {
//	for (int T = read(); T--; solve());
	solve();
	return 0;
}