牛客周赛 Round 112 题解，C++ version

A ICPC Regionals

用 $if$ 判断一下即可， $\lceil\frac{a}{b}\rceil=(a+b-1)/b$ （整数意义下）。

void solve() {
    int n, k;
    cin >> n >> k;
    if (k <= (n + 9) / 10) cout << "Gold Medal" << "\n";
    else if (k <= 3 * (n + 9) / 10) cout << "Silver Medal" << "\n";
    else if (k <= 6 * (n + 9) / 10) cout << "Bronze Medal" << "\n";
    else cout << "Da Tie" << "\n";
}

B Card Game

要么取点数最大的那张，要么把所有牌丢掉取 $k$ 。

void solve() {
    int n, mx = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        mx = max(mx, x);
    }
    cout << max(mx, n) << "\n";
}

C Palindrome Coloring

分别取出所有 $0$ 和所有 $1$ 即可处理所有情况，特判一下回文即可。

void solve() {
    string s;
    cin >> s;
    char tar = s[0];
    bool f = true;
    for (int i = 0; i <= s.size() / 2; ++i) {
        if (s[i] != s[s.size() - i - 1]) {
            f = false;
            break;
        }
    }
    if (f) cout << 1 << "\n";
    else cout << 2 << "\n";
}

D Digital Pairing

从最大到最小逐一贪心，如果不影响先前位的情况下，这一位为 $1$ 的数量大于等于 $n$ ，这一位就可以置 $1$ 。

void solve() {
    int n;
    cin >> n;
    vector<int> a(2 * n + 1);
    for (int i = 1; i <= 2 * n; ++i) cin >> a[i];
    int ans = 0;
    for (int mask = 31; mask >= 0; --mask) {
        int cnt = 0, cand = ans | (1 << mask);
        for (int i = 1; i <= 2 * n; ++i) {
            if ((cand & a[i]) == cand) cnt++;
        }
        if (cnt >= n) ans = cand;
    }
    cout << ans << "\n";
}

一个更容易理解的写法

void solve() {
    int n;
    cin >> n;
    vector<int> a(2 * n + 1);
    for (int i = 1; i <= 2 * n; ++i) cin >> a[i];
 
    int ans = 0;
    for (int mask = 31; mask >= 0; --mask) {
        vector<int> b = a;
        a.clear();
        ll cand = ans | (1 << mask);
        for (auto v : b) {
            if ((cand & v) == cand) a.pb(v);
        }
        if (a.size() >= n) ans = cand;
        else a = b;
    }
    cout << ans << "\n";
}

E Beautiful Sequence

一道正难则反的题目。显然答案为 $\text{非空序列数} - gcd\text{在内的序列数}$ ，我们只需要枚举 $gcd$ ，它和它的所有倍数即可构成所有非美丽序列。

void solve() {
    int n;
    cin >> n;
    vector<int> cnt(maxn + 10);
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        cnt[x]++;
    }
 
    Z ans = power(Z(2), n) - 1;
    for (int i = 1; i <= maxn; ++i) {
        int len = 0, st;
        if (cnt[i]) {
            len += cnt[i];
            st = cnt[i];
            for (int j = i + i; j <= maxn; j += i) {
                len += cnt[j];
            }
            for (int j = 1; j <= st; ++j) {
                ans -= power(Z(2), len - j);
            }
        }
    }
    cout << ans << "\n";
}

当然也可以正做。

对于每个 $d$ ，记 $F[d]$ 为“由数组中所有能被 $d$ 整除的元素构成的、且 $gcd$ 恰好为 $d$ 的非空子序列数”。

我们可以用常见的“枚举倍数，从大到小消去”的方法得到所有的 $F[d]$ 。

G[d] = 2^{m[d]}-1,F[d] = G[d] - \sum\limits_{k\geq2}F[d\cdot k]

其中 $m[d]$ 是数组中能被 $d$ 整除的元素个数， $G[d]$ 是这些元素的所有非空子序列数。

但我们真正需要的是不包含值为 $d$ 的那些子序列（即子序列中不出现 $d$ ），设为 $F'[d]$ ，在所有只选取“能被 $d$ 整除”的子序列中，恰好包含至少一个等于 $d$ 的子序列数为

S[d] = (2^{cnt[d]}-1)\cdot 2^{m[d]-cnt[d]} = 2^{m[d]}-2^{m[d]-cnt[d]}

其中 $cnt[d]$ 是数组中等于 $d$ 的数字个数；因为选至少一个等于 $d$ 的数字方案有 $2^{m[d]}-1$ 中，其他位置任意选或不选，因此

F'[d] = F[d] - S[d]

最终答案就是对所有 $d$ （ $1\leq d\leq n$ ），将 $F'[d]$ 累加并对 $998244353$ 取模。

void solve() {
    int n;
    cin >> n;
    vector<int> cnt(maxn + 10);
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        cnt[x]++;
    }
 
    vector<int> m(n + 1, 0);
    for (int d = 1; d <= n; ++d) {
        for (int j = d; j <= n; j += d) m[d] += cnt[j];
    }
 
    vector<Z> p2(n + 1, 1);
    for (int i = 1; i <= n; ++i) p2[i] = p2[i - 1] + p2[i - 1];
 
    vector<Z> G(n + 1, 0);
    for (int d = 1; d <= n; ++d) {
        if (m[d] == 0) G[d] = 0;
        else G[d] = p2[m[d]] - 1;
    }
 
    vector<Z> f(n + 1, 0);
    for (int d = n; d >= 1; --d) {
        Z val = G[d];
        for (int dk = d * 2; dk <= n; dk += d) {
            val -= f[dk];
        }
        f[d] = val;
    }
 
    vector<Z> S(n + 1, 0);
    for (int d = 1; d <= n; ++d) {
        if (m[d] == 0) {
            S[d] = 0;
            continue;
        }
        S[d] = p2[m[d]] - p2[m[d] - cnt[d]];
    }
 
    Z ans = 0;
    for (int d = 1; d <= n; ++d) {
        Z fp = f[d] - S[d];
        ans += fp;
    }
    cout << ans << "\n";
}

F Bracket Counting

如果记 ‘(' 为 $+1$ ，‘)' 为 $-1$ ，如果一个括号序列是合法的，那么对于每一位，都有前缀和 $pre[i] \geq 0$ 。

记这个括号序列等价表示的最小值为 $mn[i]$ ，那么如果

pre[\text{当前的选择情况}]+mn[\text{当前括号序列}]\geq 0

那么

dp[\text{选了这个括号序列的选择情况}] += dp[\text{当前的选择情况}]

最终答案即为 $dp[\text{选择所有序列}]$ ，注意需要特判不合法的情况。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int mn = 0;
        for (auto v : s) {
            if (v == '(') a[i]++;
            else a[i]--;
            mn = min(mn, a[i]);
        }
        b[i] = mn;
    }
    int m = 1 << n;
    vector<int> pre(m);
    for (int i = 1; i < m; ++i) {
        int prev = __builtin_ctz(i);
        pre[i] = pre[i ^ (1 << prev)] + a[prev];
    }
 
 
    if (pre[m - 1] != 0) {
        cout << 0 << "\n";
        return;
    }
 
    vector<Z> dp(m);
    dp[0] = 1;
    for (int i = 0; i < m; ++i) {
        if (dp[i] == 0) continue;
        int S = pre[i];
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) continue;
            if (S + b[j] >= 0) {
                int nxt = i | (1 << j);
                dp[nxt] += dp[i];
            }
        }
    }
    cout << dp[m - 1] << "\n";
}

头文件

//Another
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    init();

    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}

自动取模

template<class T>
constexpr T power(T a, ll b) {
	T res = 1;
	while (b) {
		if (b & 1) res *= a;
		b >>= 1;
		a *= a;
	}
	return res;
}

template<int P>
struct MInt {
	int x;
	constexpr MInt(): x() {}
	constexpr MInt(ll x) : x{norm(x % getMod())} {}
	static int Mod;
	constexpr static int getMod() {
		if (P > 0) {
			return P;
		} else {
			return Mod;
		}
	}
	constexpr static void setMod(int Mod_) {
		Mod = Mod_;
	}
	constexpr int norm(int x) const {
		if (x < 0) {
			x += getMod();
		}
		if (x >= getMod()) {
			x -= getMod();
		}
		return x;
	}
	constexpr int val() const {
		return x;
	}
	explicit constexpr operator int() const {
		return x;
	}
	constexpr MInt operator-() const {
		MInt res;
		res.x = norm(getMod() - x);
		return res;
	}
	constexpr MInt inv() const {
		assert(x != 0);
		return power(*this, getMod() - 2);
	}
	constexpr MInt &operator*=(MInt rhs) & {
		x = 1LL * x * rhs.x % getMod();
		return *this;
	}
	constexpr MInt &operator+=(MInt rhs) & {
		x = norm(x + rhs.x);
		return *this;
	}
	constexpr MInt &operator-=(MInt rhs) & {
		x = norm(x - rhs.x);
		return *this;
	}
	constexpr MInt &operator/=(MInt rhs) & {
		return *this *= rhs.inv();
	}
	friend constexpr MInt operator*(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res *= rhs;
		return res;
	}
	friend constexpr MInt operator+(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res += rhs;
		return res;
	}
	friend constexpr MInt operator-(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res -= rhs;
		return res;
	}
	friend constexpr MInt operator/(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res /= rhs;
		return res;
	}
	friend constexpr istream &operator>>(istream &is, MInt &a) {
		ll v;
		is >> v;
		a = MInt(v);
		return is;
	}
	friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
		return os << a.val();
	}
	friend constexpr bool operator==(MInt lhs, MInt rhs) {
		return lhs.val() == rhs.val();
	}
	friend constexpr bool operator!=(MInt lhs, MInt rhs) {
		return lhs.val() != rhs.val();
	}
};

template<>
int MInt<0>::Mod = 998244353;

using Z = MInt<MOD>;

题解 | 牛客周赛 Round 112 题解