ICPC 2024 ShenYang

The 3rd Universal Cup. Stage 19: Shenyang

J

模拟即可。

查看代码

#include <cstdio>
int t[8];
char s[8][4];
int main ()
{
    for (int i = 0; i < 8; ++i)
        scanf("%s%d", s[i], &t[i]);
    int w[2] = { -1, -1 };
    for (int i = 0; i < 8; ++i)
    {
        int &v = w[i >> 2];
        if (!~v || t[i] > t[v]) v = i;
    }
    bool f = t[w[1]] > t[w[0]];
    printf("%s beats %s", s[w[f]], s[w[f ^ 1]]);
    return 0;
}

B

考虑对于任意一个填写的数 $k$ ，在某一行或列所能产生的最多互不相同的数的个数为 $\frac{n m}{(n m, k)}$ 。若 $k$ 是在某一行，那么有 $\frac{n m}{(n m, k)} \geq m$ ，即 $(n m, k) \leq n$ 。那么对于一个 $n$ 的倍数，他的 $n$ 的基础上不应该有更多的 $m$ 的因数。那么构成 $n m$ 的行列的数应该分别是 $n, m$ 的若干倍，且不能有更多的对方的因数。这样的话，某一行应该有 $0, n, 2 n, \dots, (m - 1) n$ 共 $m$ 个数，某一列同理，那么有 $g c d (n, m)$ 个相同的数，那么一定有 $g c d (n, m) = 1$ 才有解。

考虑如何构造方案。不妨令某一行填写了 $k$ , 如上所述，满足 $(n m, k) \leq n$ ，考虑是否存在 $(n m, k) = n$ 的方案，即 $(k, m) = 1$ 。且所有行的 $k$ 在模 $n$ 意义下不同，想到一个方案 $a_{i} = i m + 1, b_{i} = i n + 1$ ，恰好满足条件。

一个坑点，当 $n$ 或者 $m$ 为 $1$ 的时候，会造成构造的数等于 $n m$ ，不合法，还是应该取模避免这种情况。

查看代码

#include <cstdio>
int n, m;
int gcd (int a, int b) { return a ? gcd(b % a, a) : b; }
int main ()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        if (gcd(n, m) > 1)
            { puts("No"); continue; }
        puts("Yes");
        int M = n * m;
        for (int i = 0; i < n; ++i)
            printf("%d ", (i * m + 1) % M);
        puts("");
        for (int i = 0; i < m; ++i)
            printf("%d ", (i * n + 1) % M);
        puts("");
    }
    return 0;
}

D

先不考虑修改，考虑交换的要求。不妨交换 A 序列，那么交换后一定是以 B 序列为参照更有序的。即可以合为一个序列，两者均对其修改，使得交换后的序列逆序对减少。注意到一次交换逆序对的奇偶性发生改变，最后逆序对数为 $0$ ，依此可以判断谁胜利。

再考虑修改，考虑修改对逆序对数的奇偶性的改变。注意到每一次修改都可以理解为 $r - l$ 次交换，那么左移 $k$ 次，即改变了 $k (r - l)$ 次奇偶性，与 A 或者 B 序列无关。

查看代码

#include <cstdio>
const int N = 5e5 + 10;
const char C[2] = { 'B', 'A' };
int n, tr[N];
void add (int x)
{
    for (; x; x -= x & -x)
        tr[x] ^= 1;
}
bool query (int x)
{
    bool r = false;
    for (; x <= n; x += x & -x)
        r ^= tr[x];
    return r;
}
bool read ()
{
    bool r = false;
    for (int i = 1, a; i <= n; ++i)
    {
        scanf("%d", &a);
        r ^= query(a);
        add(a);
    }
    for (int i = 1; i <= n; ++i)
        tr[i] = false;
    return r;
}
int main ()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        bool t = read() ^ read();
        putchar(C[t]);
        for (int i = 1, l, r, k; i < n; ++i)
        {
            char c = getchar();
            while (c != 'A' && c != 'B') c = getchar();
            scanf("%d%d%d", &l, &r, &k);
            putchar(C[t ^= k & r - l & 1]);
        }
        puts("");
    }
    return 0;
}

E

状压最短路。考虑最多有 $2^{4} = 16$ 个局面，那么可能经过 $2^{1} 6$ 个情况，同时维护当前的局面，做最短路即可。

查看代码

#include <cstdio>
#include <queue>
const int N = 16, M = 1 << N, K = 9, inf = 1e8;
const int to[K] { 1, 2, 4, 8, 3, 12, 5, 10, 15 };
bool vis[N][M];
int A[4], d[N][M], cst[K], f[M];
struct Node
{
    int t, s, d;
    Node (int _t, int _s, int _d) : t(_t), s(_s), d(_d) { }
    bool operator < (const Node &_) const
        { return d > _.d; }
};
int main ()
{
    int T; scanf("%d", &T);
    for (int i = 0; i < 4; ++i)
        scanf("%d", &A[i]);
    for (int i = 0; i < 4; ++i) cst[i] = A[0];
    for (int i = 4; i < 6; ++i) cst[i] = A[1];
    for (int i = 6; i < 8; ++i) cst[i] = A[2];
    cst[8] = A[3];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            d[i][j] = inf;
    d[N - 1][0] = 0;
    std::priority_queue <Node> q;
    q.push(Node(N - 1, 0, 0));
    while (!q.empty())
    {
        int t = q.top().t, s = q.top().s; q.pop();
        if (vis[t][s]) continue;
        vis[t][s] = true;
        for (int k = 0; k < 9; ++k)
        {
            int _t = t ^ to[k], _s = s | 1 << _t;
            if (d[_t][_s] > d[t][s] + cst[k])
                q.push(Node(_t, _s, d[_t][_s] = d[t][s] + cst[k]));
        }
    }
    for (int i = 0; i < M; ++i)
    {
        f[i] = inf;
        for (int j = 0; j < N; ++j)
            f[i] = std::min(f[i], d[j][i]);
    }
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            if (!(j >> i & 1))
                f[j] = std::min(f[j], f[j ^ 1 << i]);
    for (int m; T; --T)
    {
        scanf("%d", &m);
        int s = 0;
        while (m--)
        {
            int t = 0;
            for (int i = 0, c; i < 4; ++i)
                scanf("%1d", &c), t |= c << i;
            s |= 1 << t;
        }
        printf("%d\n", f[s]);
    }
    return 0;
}

M

按照题意建图，如果形成一个环，意味可以无限进行一个系列操作。那么现在只要经过操作后的数发生变化就能成为一个无限集合，即环的边权和不为 $0$ 。

缩点。考虑一个强连通分量，如果所有的环的边权和都是 $0$ 。那么满足存在一个势能方案，边权恰好为势能差。

每个点再考虑后继点即可。

查看代码

#include <cstdio>
#include <vector>
typedef long long L;
const int N = 5e5 + 10;
L h[N];
int n, m, q;
bool f[N], in[N], vis[N];
int tp, stk[N];
int stmp, dfn[N], low[N], cnt, id[N];
int idx, hd[N], nxt[N], edg[N], wt[N];
std::vector <int> e[N];
void add (int a, int b, int c)
{
    nxt[idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx++] = c;
}
void chkmin (int &x, int k) { if (k < x) x = k; }
bool chk (int u, L k)
{
    if (vis[u])
        return h[u] == k;
    vis[u] = true, h[u] = k;
    for (int i = hd[u], v = edg[i]; ~i; v = edg[i = nxt[i]])
        if (id[u] == id[v] && !chk(v, k + wt[i]))
            return false;
    return true;
}
void tarjan (int u)
{
    dfn[u] = low[u] = ++stmp;
    in[stk[++tp] = u] = true;
    for (int i = hd[u], v = edg[i]; ~i; v = edg[i = nxt[i]])
        if (!dfn[v])
        {
            tarjan(v);
            chkmin(low[u], low[v]);
        }
        else if (in[v])
            chkmin(low[u], dfn[v]);
    if (dfn[u] ^ low[u]) return;
    int v;
    do
    {
        in[v = stk[tp--]] = false;
        id[v] = cnt;
    }
    while (v ^ u);
    f[cnt++] = chk(u, 0) ^ 1;
}
bool dfs (int u)
{
    bool &r = f[u];
    if (vis[u]) return r;
    vis[u] = true;
    for (int v : e[u])
        r |= dfs(v);
    return r;
}
int main ()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 0; i < n; ++i) hd[i] = -1;
    for (int a, b; m; --m)
    {
        scanf("%d%d", &a, &b);
        a = (a % n + n) % n;
        add(a, ((a + b) % n + n) % n, b);
    }
    for (int i = 0; i < n; ++i)
        vis[i] = false;
    for (int i = 0; i < n; ++i)
        id[i] = -1;
    for (int i = 0; i < n; ++i)
        if (!dfn[i]) tarjan(i);
    for (int u = 0; u < n; ++u)
        for (int i = hd[u], v = edg[i]; ~i; v = edg[i = nxt[i]])
            if (id[u] ^ id[v]) e[id[u]].push_back(id[v]);
    for (int i = 0; i < n; ++i)
        vis[i] = false;
    for (int x; q; --q)
    {
        scanf("%d", &x);
        x = (x % n + n) % n;
        puts(dfs(id[x]) ? "Yes" : "No");
    }
    return 0;
}

G

不妨当作凸多边形考虑，相当于切割成了若干个梯形的面积。如果每一个 $x$ 互不相同的话，直接询问每一个 $x$ 所截取的长度求若干梯形即可。

现在考虑如果有多个 $x$ 相同 $y$ 不同的点，那么长度可能会出现问题，只需要和前后的 $x$ 取中点查询就可获得正确的长度。

遗憾的是用 $n - 2$ 次操作不能将两者统一，需要分类讨论。

注意到所有点的坐标均为整数，那么答案的两倍也为整数。过程中也用大整数分数类太过麻烦，实际上用 long double 可以满足精度要求。

查看代码

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
typedef long double D;
const int N = 1e3 + 10;
int n;
D query (D p, D q)
{
    printf("? %.0Lf %.0Lf\n", p, q);
    fflush(stdout);
    scanf("%Lf%Lf", &p, &q);
    return p / q;
}
int main ()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        std::vector <int> ws;
        for (int i = 1, x; i <= n; ++i)
        {
            scanf("%d%*d", &x);
            ws.push_back(x);
        }
        sort(ws.begin(), ws.end());
        ws.erase(std::unique(ws.begin(), ws.end()), ws.end());
        D dr = 0;
        if (ws.size() < n)
            for (int i = 1; i < ws.size(); ++i)
                dr += query(ws[i] + ws[i - 1], 2) * (ws[i] - ws[i - 1]) * 2;
        else
            for (int i = 1; i + 1 < n; ++i)
                dr += (ws[i + 1] - ws[i - 1]) * query(ws[i], 1);
        int r = llround(dr);
        if (r & 1) printf("! %d 2\n", r);
        else printf("! %d 1\n", r / 2);
        fflush(stdout);
    }
    return 0;
}

查看代码