CCPC 网络预选赛 2024 个人题解

Dashboard - The 2024 CCPC Online Contest - Codeforces

L

签到题，$O(nm)$ 遍历一遍即可。

const int N = 1e3 + 10;
char s[N][N];
int n,m;

signed main() {
    cin >> n >> m;
    for (int i = 1;i <= n;++i) {
        for (int j = 1;j <= m;++j) {
            cin >> s[i][j];
        }
    }
    int ans = 0;
    for (int i = 1;i < n;++i) {
        for (int j = 1;j < m;++j) {
            if (s[i][j] == 'c' && s[i][j+1] == 'c' && s[i+1][j] == 'p' && s[i+1][j+1] == 'c') {
                ++ans;
            }
        }
    }
    cout << ans;
    return 0;
}

K

考虑分类讨论一下；

• 对于奇数的情况，先手显然可以通过一直取 1 的情况先手必胜。所以答案为 Alice

• 对于偶数的情况，我们不妨考虑一下 $k$ 会带来的影响。

  一个比较直观的想法是，我们能不能通过巧妙的转化把偶数的情况转变为奇数的情况？发现是可以的，我们考虑 $lowbit(n)$，如果 $k \geq lowbit(n)$ 的话，那么显然对于先手而言，我们可以通过不断取 $lowbit(n)$ 让整个局面等价于奇数的局面。这是因为，后手不论取任何数面对的都是一个取偶数次，即先手必败的局面。所以获胜的条件显然就是 $k \geq lowbit(n)$

代码太简单没有难度不放了。

B

我们考虑怎样的序列是价值比较小的？

通过拆式子，我们不妨变为统计以下两个东西的最小值：
$$
\max {a_{p_l},a_{p_l+1}\dots a_{p_r}},\max {-a_{p_l},-a_{p_l+1}\dots -a_{p_r}},
$$
接下来考虑贡献，先考虑 $\max {a_{p_l},a_{p_l+1}\dots a_{p_r}}$ 另一个同理。我们考虑一个 $a_i$ 能产生贡献的区间是 $[l_i,r_i]$，其中 $l_i$ 代表第一个满足 $a_{l_i} > a_i$ 的位置， $r_i$ 同理。那么我们可以写出一个 $a_i$ 的贡献，即 $ans_i = a_i\times (i - l_i + 1)\times (r_i - i + 1)$。

此时贪心考虑，对于最大值而言，放在 $1/n$ 显然是最小化 $ (i - l_i + 1)\times (r_i - i + 1)$ 的，同样对于次大值而言，我们考虑放在 $2/n-1$ 显然是更加优秀的。所以我们可以得出一个结论：如果我们想要价值最小，把序列从小到大/从大到小排序即可。

接下来我们考虑方案数，观察到这个东西等价于你有 $k$ 类小球，每个小球有 $c_i$ 个，求小球整体按顺序排序，内部不一样的排列方案数。这个答案就是 $2\times \prod c_i!$，注意因为你从大到小和从小到大都可以，所以有个 2 的系数。然后如果全都相同就是 $n!$ 的。

总时间复杂度 $O(n\log n)$

const int N = 1e3 + 10;
ll a[N],n,ans1,ans2 = 1,jc[N];
int buc[N*N];

signed main() {
    read(n);
    jc[0] = 1;
    for (int i = 1;i <= n;++i) jc[i] = jc[i-1] * i % mod;
    for (int i = 1;i <= n;++i) read(a[i]),buc[a[i]]++;
    sort(a+1,a+1+n);
    for (int i = 1;i <= n;++i) {
        ans1 += a[i] * i;
    }
    reverse(a+1,a+1+n);
    for (int i = 1;i <= n;++i) {
        ans1 -= a[i] * i;
    }
    bool flag = 0;
    for (int i = 1;i <= 1000000;++i) {
        if (buc[i] == n) flag = 1;
        if (buc[i]) ans2 = (ans2 * jc[buc[i]]) % mod;
    }
    if (!flag) ans2 = 2 * ans2 % mod;
    printf("%lld %lld\n",ans1,ans2);
    return 0; 
}

D

这个题考虑，因为有 $S_i = S_{i-1} + a_i + S_{i-1}$ 这个特别对称的性质，不妨考虑区间 DP。

考虑区间 DP，$f_{i,l,r}$ 代表 $S_i$ 里 $[T_l,T_r]$ 出现的次数。

转移方程非常好写，考虑边界就可以：
$$
f_{i,l,r} = 2 * f_{i-1,l,r} + \sum\limits_{k = l}^{r-1}f_{i-1,l,k} \times f_{i-1,k+1,r} \
f_{i,l,r} =\sum\limits_{k = l}^{r-1}f_{i-1,l,k-1} \times f_{i-1,k+1,r} [a_i = t_k]\
$$
时间复杂度 $O(n^4)$

ll f[N][N][N],n,m;
char s[N],t[N];

signed main() {
    scanf("%s\n%s\n",s+1,t+1);
    n = strlen(s+1),m = strlen(t+1);
    for (int i = 1;i <= n;++i) {
        for (int l = 1;l <= m;++l) {
            for (int len = 1;l + len - 1 <= m;++len) {
                int r = l + len - 1;
                f[i][l][r] = f[i-1][l][r] * 2 % mod;
                for (int k = l;k < r;++k)
                f[i][l][r] = (f[i][l][r] + f[i-1][l][k] * f[i-1][k+1][r]) % mod;
            }
        }
        for (int j = 1;j <= m;++j) {
            if (s[i] == t[j]) {
                f[i][j][j]++;f[i][j][j] %= mod;
                for (int l = 1;l <= j-1;++l) {
                    for (int len = 2;l + len - 1 <= m;++len) {
                        int r = l + len - 1;
                        f[i][l][r] = (f[i][l][r] + f[i-1][l][j-1] * f[i-1][j+1][r]) % mod;
                    }
                    f[i][l][j] = (f[i][l][j] + f[i-1][l][j-1]) % mod;
                }
                for (int r = j + 1;r <= m;++r) {
                    f[i][j][r] = (f[i][j][r] + f[i-1][j+1][r]) % mod;
                }
            }
        }
    }
    printf("%lld\n",f[n][1][m]);
    return 0;
}

G

义眼顶真鉴定为网络流，考虑如何建图？

我们不妨考虑一个经典的二分图建法：左部有 $n$ 个点代表 $n$ 个人，$m$ 个点代表 $m$ 个菜品，然后考虑如何建图判定合法解？

对于每个人（除了 1 号）而言，我们考虑一个能用于支付菜品的钱数上界 $R_i$。显然 $R_i = \min {V_1+\sum\limits_{x_i = 1|y_i = 1} w_i,a_1} - V_i$ ，如果 $R_i < 0$ 那么就无解，从汇点向每个人连边。接下来考虑对于每一道菜品而言 $x_i,y_i$ 向第 $i$ 道菜品连一条容量无限大的边，第 $i$ 道菜品连一条向汇点容量为 $w_i$ 的边。跑最大流判定流量是否等于 $\sum w_i$ 即可。

这个做法的正确性是基于，对上界进行的巧妙限制，因此一定不会出现第 1 条边没跑满但是其他边跑满了的情况。

struct edge {
    ll c,f;
}e[N];

vector <pii> G[N];
int n,m,s,t,tot = -1,cur[N];
ll dis[N];
bool vis[N];
bool BFS() {
    //memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue <int> q;
    q.push(s);dis[s] = 0;vis[s] = 1;
    while (!q.empty()) {
        int x = q.front();q.pop();
        //printf("%d\n",x);
        for (auto ed : G[x]) {
            int y = ed.first,num = ed.second;
            if (!vis[y] && e[num].c > e[num].f) {
                vis[y] = 1;
                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }
    }
    return vis[t];
}

ll DFS(int x,ll res) {
    //printf("%d %d\n",x,res);
    if (x == t || res == 0) return res;
    ll now = 0;
    for (int& i = cur[x];i < G[x].size();++i) {
        pii ed = G[x][i];
        int y = ed.first,num = ed.second;
        if (dis[x] + 1 == dis[y]) {
            ll f = DFS(y,min(res,e[num].c - e[num].f));
            if (f > 0) {
                e[num].f += f;
                e[num ^ 1].f -= f;
                now += f;
                res -= f;
                if (!res) break;
            }
        }
    }
    return now;
}

ll maxflow() {
    int ans = 0;
    while (BFS()) {
        memset(cur,0,sizeof cur);
        ans += DFS(s,1e15);
    }
    return ans;
}

ll a[N],v[N];

void addedge(int a,int b,ll c) {
    G[a].push_back(mp(b,++tot));
    e[tot].c = c;
    G[b].push_back(mp(a,++tot));
}

signed main() {
    read(n,m);
    s = n + m + 1,t = n + m + 2;
    ll lim = 0;
    for (int i = 1;i <= n;++i) read(a[i],v[i]);
    lim = v[1];
    ll gol = 0;
    for (int i = 1;i <= m;++i) {
        ll a,b,c;
        read(a,b,c);
        if (a == 1 || b == 1) lim += c;
        addedge(a,n+i,0x3f3f3f3f);addedge(b,n+i,0x3f3f3f3f);addedge(n+i,t,c);
        gol += c;
    }
    lim = min(lim,a[1]);
    bool flag = 0;
            addedge(s,1,lim - v[1]);
    for (int i = 2;i <= n;++i) {
        if (lim <= v[i]) {
            flag = 1;
            break;
        }
            addedge(s,i,min(a[i],lim - 1) - v[i]);
    }
    if (maxflow() < gol || flag) puts("NO");
    else puts("YES");
    return 0;
}

E

对于每一层而言，第 $i$ 层最多的节点数为 $\min(26^i,n)$ 鸽巢原理易证，所以第一问答案为 $\sum\limits_{m=0}^n \min(26^i,n)$

对于第二问，我们仍然按层考虑，对于第 $i$ 层的每个节点而言，出现的概率显然相等。不妨记作 $p_i$，正难则反，考虑其不出现的概率，对于一个串的而言，不出现概率为 $1 - \frac{1}{26^i}$，那么这个东西直接乘 $n$ 次就得到答案了。

所以最后的答案就是:
$$
\sum\limits_{i=0}^m [1 - (1 - \frac{1}{26^i})^n]\times 26^i
$$

const ll mod = 998244353;
const double eps = 1e-10;
ll ffpow(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 ffpow2(ll a,ll b) {ll ans = 1;while (b) {if (b & 1) ans = ans * a;a = a * a,b >>= 1;}return ans;}
ll ans1,ans2,n,m;
signed main() {
    read(n,m);
    bool flag = 0;
    for (int i = 0;i <= m;++i) {
        if (ffpow2(26,i) >= n) flag = 1;
        if (!flag) ans1 += min(ffpow2(26,i),n);
        else ans1 += n;
    }
    ans1 %= mod;
    for (int i = 0;i <= m;++i) {
        ll p = (1 - ffpow(ffpow(26,i),mod-2) + mod) % mod;
        p = ffpow(p,n);
        ll val = (1 - p + mod) % mod * ffpow(26,i) % mod;
        ans2 =( ans2 + val) % mod;
    }
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}

J

我不会线性基！完啦！幸好队友会

考虑交换这个东西，实际上是对 $A,B$ 都做了 $\oplus a_i \oplus b_i$ 这个操作，然后我们按位考虑。对于某一位，发现如果 $A,B$ 在这位上是 1 的话，我们考虑能不能搞出一个对应的 $i$ 使得异或上 $a_i\oplus b_i$ 是更加优秀的。这个时候不妨考虑使用线性基考虑，according to my 队友，线性基可以维护的是这一位如果是 1，那么就代表肯定能凑出来一个 1。

所以就直接贪心考虑，记我们构造出的线性基第 $i$ 位为 $s_i$，那么考虑这一位上有没有东西。如果 $s_i > 0$，我们直接贪心考虑异或上会不会对答案更优秀即可。

时间复杂度 $O(n\log \omega)$

int n,a[N],b[N],s[50];

void insert(int x) {
    for (int i = 31;i >= 0;--i) {
        if (x & (1 << i)) {
            if (s[i]) x ^= s[i];
            else {
                for (int j = 0;j < i;++j) if (x & (1 << j)) x ^= s[j];
                for (int j = i+1;j <= 31;++j) if (s[j] & (1 << i)) s[j] ^= x;
                s[i] = x;
                return ;
            }
        }
    }
}



void solve() {
    read(n);
    memset(s,0,sizeof s);
    int A = 0,B = 0;
    for (int i = 1;i <= n;++i) read(a[i]),A ^= a[i];
    for (int i = 1;i <= n;++i) read(b[i]),B ^= b[i];
    for (int i = 1;i <= n;++i) {
        insert(a[i] ^ b[i]);
    }
    int ans = max(A,B);
    //for (int i = 0;i <= 31;++i) printf("%d ",s[i]);
    //puts("");
    for (int i = 31;i >= 0;--i) {
        int bita = A & (1 << i),bitb = B & (1 << i);
        if (!s[i]) continue;
        int nval = max(A^s[i],B^s[i]);
        if (nval < ans) {
            ans = nval;
            A ^= s[i];B ^= s[i];
        }
    }
    printf("%d\n",ans);
}

I

首先将 $a,b$ 从小到大排序，显然问题是等价的，便于考虑。

考虑第 $i$ 个人可选的行李范围即 $[1,r_i]$，有一个特别好的性质是 $r_i$ 是单调递增的，这个性质很显然。如果从枚举最早有人拿到自己的行李的时刻来考虑，记当前枚举的答案为 $k$，那么每个人的可选范围就变为了 $[1,R_i](R_i - a_i \geq d)$ ，显然这个 $R_i$ 仍然满足单调递增的性质。此时不妨考虑 DP：$f_{i,j}$ 代表前 $i$ 个人选 $j$ 个行李方案数，枚举 $d$ 去做这个东西就可以了。时间复杂度 $O(n^3)$