和漂亮大姐姐的 ACM 日常 | ucup 题解报告

AtomAlpaca · 2025-03-18 14:45:28 · 个人记录

队友是漂亮姐姐 qixi，两人队。

现已因理念不合解散。

自己过的题目会放代码。

The 3rd Universal Cup. Stage 24: Poland

难度 ★★★，成绩 7/12(ABGHIJK)

A. Acronym

直接暴力枚举每个单词即可。

B. Baggage

不妨令 f_{x \in \{0.1.2\}, u, v} 为拿着 x 个行李从 u 到 v 的最少时间，其中 x = 0, 1 的时候直接跑最短路，x = 2 时可以每次拿一个行李跑两次，于是要额外对 2f_{1, u, v} + f_{0, v, u} 取 \min。

注意要在跑最短路时候取，因为如果你跑完最短路再取会影响其他一些路径在取形式如 f_{2, u, k} + f_{2, k, v} 时的答案，但是这里没有重新考虑。

G. Game MPO

发现 n 很小，扔掉脑子暴力跑即可。

#include <bits/stdc++.h>
#include <cstdio>

typedef long long ll;
const int MAX = 1e3 + 5;

const int dx[15] = {0, -1, 0, 1, -1, 1, -1, 0, 1};
const int dy[15] = {0, -1, -1, -1, 0, 0, 1, 1, 1};
char s[MAX][MAX];
ll n, ans, _ans;

bool f(char c) { return c == 'M' or c == 'O' or c == 'P'; }
bool g(char c) { return c == 'm' or c == 'o' or c == 'p'; }
int P(int x, int y)
{
    int res = 0;
    for (int i = 1; i <= 8; ++i) { res += s[x + dx[i]][y + dy[i]] == 'M'; }
    return res;
}

int M(int x, int y)
{
    int res = 0;
    for (int i = 1; i <= 8; ++i) { res += s[x + dx[i]][y + dy[i]] == 'P'; }
    return res;
}

int O(int x, int y)
{
    int res = 0;
    for (int i = 1; i <= 8; ++i) { res += s[x + dx[i]][y + dy[i]] == 'O'; }
    return res;
}

bool check(int x, int y)
{
    if (s[x][y] == 'p') { return P(x, y); }
    if (s[x][y] == 'm') { return M(x, y); }
    if (s[x][y] == 'o') { return O(x, y); }
    return false;
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) { scanf("%s", s[i] + 1); }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (f(s[i][j])) { ++ans; }
            if (s[i][j] == 'P') { _ans += P(i, j); }
            if (s[i][j] == 'M') { _ans += M(i, j); }
            if (s[i][j] == 'O') { _ans += O(i, j); }
        }
    }
    ans += _ans / 2;
    printf("%lld ", ans);
    while (true)
    {
        bool flag = false;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (check(i, j))
                {
                    if (s[i][j] == 'o') { s[i][j] = 'O'; ans += 1 + O(i, j); }
                    if (s[i][j] == 'p') { s[i][j] = 'P'; ans += 1 + P(i, j); }
                    if (s[i][j] == 'm') { s[i][j] = 'M'; ans += 1 + M(i, j); }
                    flag = true;
                    goto pos;
                }
            }
        }
        pos:
        if (!flag) { break; }
    }
    printf("%lld\n", ans);
    for (int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j) { printf("%c", s[i][j]); }
        printf("\n");
    }
}

H

考虑要挑战的一列高度 a，分数的期望是 p_{a_1} a_1 + p_{a_1}p_{a_2}(a_2−a_1)+p_{a_1}p_{a_2}p_{a_3}(a_3−a_2)+ \cdots，

考虑从后往前 dp，f_x = \max_{y > x} (f_y + y - x) p_y，凸优化一下可以做到 O(n \log n)

I. Imbalanced Teams

最优解一定是一个队取最大的 k 个一个队取最小 k 个。

令 b_x 是 x 总共在 a 中出现次数，f_x 是第一队选中次数，g_x 是第二队选中次数，那么考虑被选中的每个数 x，这个数的方案就是 {b_x\choose f_x + g_x}{f_x + g_x\choose f_x}，答案把全部的乘起来即可。

注意两队完全一样的时候要除以二。

#include <bits/stdc++.h>
#include <cstdio>

typedef long long ll;

const int MAX = 20005;
const int MAXX = 1e6 + 5;
const int MOD = 1e9 + 7;

ll n, k, ans, a[MAX], b[MAXX], c[MAXX], d[MAXX], dif;
ll f[MAXX], g[MAXX];

ll qp(ll a, ll x)
{
    ll res = 1;
    while (x) { if (x & 1) { res = res * a % MOD; } x >>= 1; a = a * a % MOD; }
    return res;
}

ll inv(ll x) { return qp(x, MOD - 2); }

ll C(ll x, ll y) { return f[x] * g[y] % MOD * g[x - y] % MOD; }

void init(ll x)
{
    g[0] = f[0] = 1;
    for (int i = 1; i <= x; ++i) { f[i] = f[i - 1] * i % MOD; } g[x] = qp(f[x], MOD - 2);
    for (int i = x - 1; i >= 1; --i) { g[i] = g[i + 1] * (i + 1) % MOD; }
}

int main()
{
    scanf("%lld%lld", &n, &k); ans = 1;
    init(MAXX - 5);
    for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); ++b[a[i]]; }
    std::sort(a + 1, a + n + 1);
    for (int i = 1; i <= k; ++i)
    {
        ++c[a[i]]; ++d[a[n - i + 1]];
        dif += a[n - i + 1] - a[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        if (c[a[i]] or d[a[i]])
        {
            ans = ans * C(b[a[i]], c[a[i]] + d[a[i]]) % MOD;
            ans = ans * C(c[a[i]] + d[a[i]], c[a[i]]) % MOD;
            c[a[i]] = d[a[i]] = 0;
        }
    }
    if (a[1] == a[n]) { ans = ans * inv(2ll) % MOD; }
    printf("%lld %lld", dif, ans);
}

J. Just Zeros

发现 h 很小，我们可以枚举每一行选不选，设这个状态是 S，设第 i 列的状态是 s_i，那么每列的代价是 f(i, S) = \min(\operatorname{popcount}(S \oplus s_i), h - \operatorname{popcount}(S \oplus s_i) + 1)。答案就是 \operatorname{popcount}(S) + \sum_i{f(i, S)}

然后我们来考虑修改。对于修改单点和列都是简单的，我们枚举 S，对每个 S 造成的影响都是 O(1) 的，暴力改即可。

对于行我们不把他的影响考虑到列上而是行的状态上，维护一个标记 tag 表示行修改的状态，这时想对每列都异或 S 所需的状态变成了 S \oplus tag，于是把求答案改成 \operatorname{popcount}(S \oplus tag) + \sum_i{f(i, S)} 即可。

复杂度 O(2^h(q + w))

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <cstdio>

typedef int ll;
const int MAX = 15;
const int MAXX = 1e5 + 5;
const int INF = 0x3f3f3f3f;

using std::cin;

ll h, w, x, y, q, mn, tag;
bool a[MAX][MAXX];
ll ans[1 << 8], s[MAXX];
char c, _s[MAXX];

ll f(ll x) { ll res = 0; while (x) { x ^= (x & -x); ++res; } return res; }

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> h >> w >> q; mn = INF;
    for (int i = 1; i <= h; ++i)
    {
        cin >> _s + 1;
        for (int j = 1; j <= w; ++j) { a[i][j] = _s[j] - '0'; s[j] += (_s[j] - '0') << (i - 1); }
    }
    for (int S = 0; S <= (1 << h) - 1; ++S)
    {
        for (int i = 1; i <= w; ++i)
        {
            ll v = f(S ^ s[i]);
            ans[S] += std::min(v, 1 + h - v);
        }
        mn = std::min(mn, ans[S] + f(S));
    }
    std::cout << mn << '\n';
    while (q--)
    {
        mn = INF;
        std::cin >> c;
        if (c == 'R')
        {
            cin >> x;
            tag ^= 1ll << (x - 1);
        }
        else if (c == 'K')
        {
            cin >> y;
            for (int S = 0; S <= (1 << h) - 1; ++S)
            {
                ll v = f(s[y] ^ S);
                ans[S] -= std::min(v, 1 + h - v);
            }
            s[y] ^= (1 << h) - 1;
            for (int S = 0; S <= (1 << h) - 1; ++S)
            {
                ll v = f(s[y] ^ S);
                ans[S] += std::min(v, 1 + h - v);
            }
        }
        else
        {
            cin >> x >> y;
            for (int S = 0; S <= (1 << h) - 1; ++S)
            {
                ll v = f(s[y] ^ S);
                ans[S] -= std::min(v, 1 + h - v);
            }
            s[y] ^= 1ll << (x - 1);
            for (int S = 0; S <= (1 << h) - 1; ++S)
            {
                ll v = f(s[y] ^ S);
                ans[S] += std::min(v, 1 + h - v);
            }
        }
        for (int S = 0; S <= (1 << h) - 1; ++S) { mn = std::min(mn, ans[S] + f(tag ^ S)); }
        std::cout << mn << '\n';
    }
}

K. Kindergarten Square

不难发现 w 是两行对应位置的差，h 简单算一下就好。判断合法主要看两个数是否减一后除以 w 相等即可。

#include <bits/stdc++.h>
#include <cstdio>

typedef long long ll;

ll a1, a2, a3, a4, T, h, w;

void solve()
{
    scanf("%lld%lld%lld%lld", &a1, &a2, &a3, &a4);
    w = a3 - a1;
    h = std::ceil(1.0 * a4 / w);
    if (a2 != a1 + 1 or a4 != a3 + 1) { printf("-1\n"); return ; }
    if (w <= 0) { printf("-1\n"); return ; }
    if ((a1 - 1) / w != (a2 - 1) / w or (a3 - 1) / w != (a4 - 1) / w) { printf("-1\n"); return ; }
    printf("%lld %lld\n", h, w);
}

int main() { scanf("%lld", &T); while (T--) { solve(); } }

The 3rd Universal Cup. Stage 32: Dhaka

神秘比赛。成绩 2 / 13。

D. Qwiksort

考虑把序列分成两半，把前一半的都换到前面后一半都换到后面，然后分别排序。

先考虑偶数的情况。我们先把两半排序，然后把前一部分的后一半，和后一部分的前一半组成的序列排序，然后两半再排序再重复上述步骤，就一定能把前一半的都换到前面后一半都换到后面。正确性可以考虑 worst case 2n, 2n-1 \cdots 2, 1。

奇数不能恰好分出一半，要把前一部分多给出一个和后一部分多一个的情况都做一下。

发现奇数的情况恰好卡到 10 次。

#include <bits/stdc++.h>
#include <cstdio>

typedef long long ll;
const int MAX = 5e6 + 5;

ll T, n, a[MAX];

void solve()
{
    scanf("%lld", &n);
    for (int i = 1; i <= 2 * n; ++i) { scanf("%lld", &a[i]); }
    if (n & 1)
    {
        printf("10\n");
        printf("%lld %lld\n%lld %lld\n", 1, n, n + 1, 2ll * n);
        printf("%lld %lld\n", n / 2 + 1, n / 2  + n);
        printf("%lld %lld\n", n / 2 + 2, n / 2  + n + 1);
        printf("%lld %lld\n%lld %lld\n", 1, n, n + 1, 2ll * n);
        printf("%lld %lld\n", n / 2 + 1, n / 2  + n);
        printf("%lld %lld\n", n / 2 + 2, n / 2  + n + 1);
        printf("%lld %lld\n%lld %lld\n", 1, n, n + 1, 2ll * n);
    }
    else {
        printf("8\n");
        printf("%lld %lld\n%lld %lld\n", 1, n, n + 1, 2ll * n);
        printf("%lld %lld\n", n / 2 + 1, n / 2  + n);
        printf("%lld %lld\n%lld %lld\n", 1, n, n + 1, 2ll * n);
        printf("%lld %lld\n", n / 2 + 1, n / 2  + n);
        printf("%lld %lld\n%lld %lld\n", 1, n, n + 1, 2ll * n);
    }
}

int main()
{
    scanf("%lld", &T); while (T--) { solve(); }
}

L. Uncle Bob and XOR Sum

一个选择方式 p 不满足条件的情况即 (\bigoplus_{i}{a_{p_i}}) \land b_j = b_j，把 b_j 乘（？）进里面就是 (\bigoplus_{i}{a_{p_i}} \land b_j) = b_j，这个方案数可以线性基求出。

同时我们还要对 b_i 做容斥，发现两个 b_i, b_j 重合的部分是 b_i \lor b_j 的答案。于是我们有一个暴力的算法：枚举每个 b_i 选不选，或起来得到 B，然后每个 a_i 与上 B 构造线性基，看下构造 B 的方案数进行容斥，最后统计答案用总方案数减一下。

复杂度是 O(32\times2^k n)，考虑优化，发现我们可以先把 a 的线性基求出，然后枚举每个 B 的时候把线性基里的数取出来构造新线性基，这样的基不难发现和原来是等价的。然后复杂度降到 O(32 ^ 2\times 2^k)，于是就能过了。

要特判 b 里有 0 的情况。

#include <bits/stdc++.h>
#include <cstdio>

typedef long long ll;

const int MAX = 1e5 + 5;
const int MAXX = 105;
const int MOD = 1e9 + 7;

ll n, T, k, ans;
ll a[MAX], b[MAXX];

ll popcnt(ll x) { ll res = 0; while (x) { x ^= x & -x; ++res; } return res; }

ll qp(ll a, ll x)
{
    ll res = 1;
    while (x) { if (x & 1) { res = res * a % MOD; } a = a * a % MOD; x >>= 1; }
    return res;
}

struct B
{
    ll siz = 0, a[35];
    B() { siz = 0; for (int i = 0; i <= 31; ++i) { a[i] = 0; } }
    void ins(ll x)
    {
        for (int i = 31; i >= 0; --i)
        {
            if (!x) { break; }
            if (!(x & (1 << i))) { continue; }
            if (!a[i]) { a[i] = x; ++siz; break; }
            x ^= a[i];
        }
    }

    bool f(ll x)
    {
        for (int i = 31; i >= 0; --i)
        {
            if (!(x & (1 << i))) { continue; }
            x ^= a[i];
        }
        if (!x) { return true; }
        else { return false; }
    }
    void clear() { siz = 0; for (int i = 0; i <= 31; ++i) { a[i] = 0; } }
} A, B;

void _solve(ll S)
{
    B.clear(); ll bb = 0;
    for (int i = 1; i <= k; ++i) { if (S & (1 << (i - 1))) { bb |= b[i]; } }
    for (int i = 31; i >= 0; --i) { if (A.a[i]) { B.ins(bb & A.a[i]); } }
    if (B.f(bb)) { ans = (ans + qp(-1, 1 + popcnt(S)) * qp(2, n - B.siz) % MOD + MOD) % MOD; }
}

void solve()
{
    scanf("%lld%lld", &n, &k); ans = 0; A.clear();
    for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); A.ins(a[i]); }
    for (int i = 1; i <= k; ++i) { scanf("%lld", &b[i]); }
    for (int i = 1; i <= k; ++i) { if (b[i] == 0) { printf("%lld\n", 0ll); return ; } }
    for (int S = 1; S <= (1 << k) - 1; ++S) { _solve(S); }
    ans = (qp(2, n) - 1 - ans + MOD + MOD) % MOD;
    printf("%lld\n", ans);
}

int main()
{
    scanf("%lld", &T); while (T--) { solve(); }
}