2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite-蒲公英云

L. Station of Fate

求组合数，考虑先分配再排列

#include <bits/stdc++.h>
#define int long long
using i64 = long long;
constexpr int N = 1e6 + 10;
constexpr int M = 1e6 + 10;
constexpr int P = 2600;
constexpr i64 Inf = 1e18;
constexpr int mod = 998244353;
constexpr double eps = 1e-6;
int n, k;
int Fac[N], inv[N];
int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
void F_init() {
    Fac[0] = 1;
    for (int i = 1; i < N; i ++) {
        Fac[i] = (Fac[i - 1] * i) % mod;
    }
    inv[N - 1] = qpow(Fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i --) {
        inv[i] = (inv[i + 1] * (i + 1)) % mod;
    }
}
int C(int n, int m) {
    return Fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void solve() {
    std::cin >> n >> k;
    std::cout << C(n - 1, k - 1) * Fac[n] % mod << "\n";
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    F_init();
    while (t--) {
        solve();
    }
    return 0;
}

E. Elevator

思路

首先第一个难点是怎么把应用场景变得具象化，你会发现题面写的有点抽象

其实可以考虑一排电梯，速度从快到慢排列，那么在某一时刻，高度是递减的

那么操作实际就是阻碍一个电梯，然后其他所有电梯往上移动一格

等效于所有电梯不动，一个电梯往下移动一格

然后问题就是

对于第 i 个电梯，让它变成高度最大的，编号最小的操作次数最少是多少

我们发现对于相邻的询问，我们可以考虑变化量(DS思想)

第 i 个比第 i - 1 个多了哪部分呢

容易发现我们只需要对比自己高度大的操作，把所有左边高度比自己高的削成和自己一样高，然后再加上左边有多少编号比自己小的

这两部分的贡献，第一部分可以直接算，第二部分用 BIT 维护即可

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-x))
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, MOD = 998244353;
struct node {
    int x, id;
    const bool operator< (const node &b) const { return x < b.x || (x == b.x && id < b.id); }
}a[N];
int ans[N], sum[N];
namespace Fenwick{
    int a[N], len;
    void add(int x, int v) {
        for(; x <= len; x += lowbit(x)) a[x] += v;
    }
    int query(int x, int ans = 0) {
        for(; x >= 1; x -= lowbit(x)) ans += a[x];
        return ans;
    }
}
inline void solve() {
    int n, m; cin >> n >> m;
    Fenwick::len = n;
    for(int i = 1; i <= n; i++) cin >> a[i].x, a[i].id = i;
    sort(a + 1, a + 1 + n); 
    for(int i = 2; i <= n; i++) {
        sum[a[i].id] = sum[a[i - 1].id] + (i - 1) * (a[i].x - a[i - 1].x);
    }
    for(int i = 1; i <= n; i++) {
        sum[a[i].id] += Fenwick::query(a[i].id);
        Fenwick::add(a[i].id, 1);
    }
    for(int i = 1; i <= n; i++) {
        if(sum[i] > m - 2) cout << -1 << endl;
        else cout << sum[i] << endl;
    }
}
signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

H. GameX

思路

首先结论就是A操作的数一定是未出现过的最小奇数，B操作的数一定是未出现的最小偶数

然后就直接模拟即可

#include<bits/stdc++.h> 
#define int long long
#define rep(i,a,n) for(int i=a; i<=n ;i++)
#define pb push_back
using namespace std;
const int mxn = 2e5+7, mxm = 1e6;
int a[mxn];
void work(){
    int n, k;
    cin >> n >> k;
    int tk=k;
    map<int,int> vis;
    rep(i,1,n) cin >> a[i], vis[a[i]]++;
    sort(a+1,a+n+1);
    //rep(i,1,n) cout << a[i] <<" \n"[i==n];
    int A=0, B=0, bi=0;
    while(1){
        if(!k) break;
        if(vis[bi]) {bi+=2; continue;}
        vis[bi]=1;
        bi+=2;
        k--;
    }
    int ai=1;
    while(1){
        if(!tk) break;
        if(vis[ai]) {ai+=2;continue;}
        vis[ai]=1;
        ai+=2;
        tk--;
    }
    int ansi = -1;
    int i=0;
    while(1){
        if(vis[i]) {i++;continue;}
        ansi=i;
        break;
        i++;
    }
   // cout << ansi <<'\n';
    if(ansi%2==0) cout <<"Alice"<<'\n';
    else cout <<"Bob"<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T=1;
    cin >> T;
    while(T--){
        work();
    }
    return 0;
}

I. Infection

#include <bits/stdc++.h>
#define int long long
constexpr int N = 2e3 + 10;
constexpr int mod = 1e9 + 7;
std::vector<int> adj[N];
int n;
int sum = 0;
int a[N];
int sz[N], Fa[N];
int p[N], inv[N];
int ans[N];
int f[N][N], g[N][N];
int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
void dfs(int u, int fa) {
    sz[u] = 1;
    Fa[u] = fa;
    static int tmp1[N], tmp2[N];
    f[u][1] = p[u];
    g[u][1] = a[u] * qpow(sum, mod - 2) % mod;
    f[u][0] = ((1 - p[u]) % mod + mod) % mod;
    g[u][0] = ((1 - p[u]) % mod + mod) % mod;
    for (auto v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        for (int k = 0; k <= sz[u] + sz[v]; k ++) tmp1[k] = tmp2[k] = 0;
        for (int k = 1; k <= sz[u]; k ++) {
            for (int l = 0; l <= sz[v]; l ++) {
                tmp1[k + l] += f[u][k] * f[v][l] % mod;
                tmp2[k + l] += g[u][k] * f[v][l] % mod;
                if (l) tmp2[k + l] += f[u][k] * g[v][l] % mod;
                tmp1[k + l] %= mod;
                tmp2[k + l] %= mod;
            }
        }
        for (int k = 1; k <= sz[u] + sz[v]; k ++) {
            f[u][k] = tmp1[k];
            g[u][k] = tmp2[k];
        }
        sz[u] += sz[v];
    }
}
void solve() {
    std::cin >> n;
    for (int i = 1; i <= n - 1; i ++) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i ++) {
        int b, c;
        std::cin >> a[i] >> b >> c;
        sum += a[i];
        sum %= mod;
        p[i] = b * qpow(c, mod - 2) % mod;
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (j == 1) ans[i] += g[j][i];
            else ans[i] += g[j][i] * (1 - p[Fa[j]] + mod) % mod;
            ans[i] %= mod;
        }
    }
    for (int i = 1; i <= n; i ++) {
        std::cout << ans[i] % mod << "\n";
    }
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    while(t --) {
        solve();
    }
    return 0;
}