Visits: 263

AtCoder Grand Contest 041

Table Tennis Training

如果 $a,b$ 奇偶性相同，那么一起往中间走即可。

否则，走到某一端，浪费一次步数之后再一起往中间走。

int main() {
    ll n, a, b;
    rd(n, a, b);
    if ((a ^ b) & 1) print(min((a + b - 1) >> 1, (n - a + n - b + 1) >> 1));
    else print((b - a) >> 1); 
    return 0;
}

Voting Judges

贪心，考虑清楚合法条件，需要前缀和一下。

const int N = 1e5 + 7;
int n, m, v, p, a[N];
ll s[N];

int main() {
    rd(n, m), rd(v, p), rda(a, n);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) s[i] = a[i] + s[i-1];
    for (int i = 1; i <= n; i++) {
        int c = n + 1 - (upper_bound(a + 1, a + n + 1, a[i] + m) - a);
        if (c + 1 > p) continue;
        int d = (upper_bound(a + 1, a + n + 1, a[i]) - a) - 2;
        ll o = 1ll * m * (v - 1 - c - d) - (1ll * (a[i] + m) * (n - 1 - c - d) - (s[n-c] - s[d+1]));
        if (o <= (s[n-c] - s[n-p+1]) - 1ll * (p - 1 - c) * a[i]) {
            print(n - i + 1);
            break;
        }
    }
    return 0;
}

Domino Quality

$n \le 2$ 无解，手玩出 $n=3/4/5/6/7$，用 $4/5/6/7$ 去凑出后面的数。

const string S4[4] = {"abcc", "abdd", "ccab", "ddab"};
const string S5[5] = {"abbcc", "ad..a", "bd..a", "b.eez", "oorrz"};
const string S6[6] = {"oorrzz", ".a.b.c", ".a.b.c", "d.e.f.", "d.e.f.", "oorrzz"};
const string S7[7] = {".oorrzz", "oabb...", "oa.c...", "rddc...", "r...abb", "z...a.c", "z...ddc"};

const int N = 1e3 + 7;
int n;
char s[N][N];

inline void solve(int &n, int x) {
    if (x == 4)
        for (int i = 0; i < x; i++)
            for (int j = 0; j < x; j++)
                s[n+i][n+j] = S4[i][j];
    if (x == 5)
        for (int i = 0; i < x; i++)
            for (int j = 0; j < x; j++)
                s[n+i][n+j] = S5[i][j];
    if (x == 6)
        for (int i = 0; i < x; i++)
            for (int j = 0; j < x; j++)
                s[n+i][n+j] = S6[i][j];
    if (x == 7)
        for (int i = 0; i < x; i++)
            for (int j = 0; j < x; j++)
                s[n+i][n+j] = S7[i][j];
    n += x;
}

int main() {
    rd(n);
    if (n <= 2) return print(-1), 0;
    if (n == 3) return prints("a.."), prints("a.."), prints(".bb"), 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            s[i][j] = '.';
    int m = 1;
    solve(m, n % 4 + 4);
    while (m <= n) solve(m, 4);
    for (int i = 1; i <= n; i++) prints(s[i], n);
    return 0;
}

Problem Scores

限制相当于要求前 $k+1$ 个数的和大于后 $k$ 个数的和。

注意到如果 $k > \lfloor \frac {n-1}2 \rfloor$ 会有重复的部分，把重复的部分去掉之后就变成 $k \le \lfloor \frac {n-1}2 \rfloor$ 的情况，因此我们只用考虑 $k \le \lfloor \frac {n-1}2 \rfloor$ 的情况。

又当 $k \le \lfloor \frac {n-1}2 \rfloor$ 时，若 $k$ 满足条件，则 $k-1$ 一定满足条件，因此我们只用考虑 $k = \lfloor \frac {n-1}2 \rfloor$ 的情况。

先考虑 $n$ 为偶数的情况，此时有且仅有 $a_{k+2}$ 既不在前 $k+1$ 个数中，又不在后 $k$ 个数中。

考虑枚举 $a_{k+2} = x$，先将所有数都设为 $x$，此时前 $k+1$ 个数的和比后 $k$ 个数的和大 $x$。

然后我们可以做的就是让前 $k+1$ 个数的若干个前缀同时 $-1$，后 $k$ 个数的若干个后缀同时 $+1$，使得：

• 前 $k+1$ 个数最多进行 $x-1$ 次 $-1$。
• 后 $k$ 个数最多进行 $n-x$ 次 $+1$。
• 前 $k+1$ 个数减掉的总数与后 $k$ 个数加上的总数之和 $< x$。

设 $f_{j,l}$ 表示前 $k+1$ 个数进行了 $j$ 次 $-1$，共减掉 $l$ 的方案数，$g_{j,l}$ 表示后 $k$ 个数进行了 $j$ 次 $+1$，共加上 $l$ 的方案数。

则答案为：
$$
\sum_{x=1}^n \sum_{p=0}^{x-1} \sum_{q=0}^{n-x} \sum_{i=0}^{x-1} \sum_{j=0}^{x-1-i} f_{p,i} g_{q,j}
$$
这玩意儿在求出 $f,g$ 之后借助前缀和可以做到 $\mathcal O(n^2)$。

由于 $f,g$ 定义类似，这里只考虑如何求 $f$。

在 $[1,k+1]$ 的范围内从大到小枚举 $i$，表示此时 $-1$ 会导致总共 $-i$，再枚举一个状态 $f_{j,l}$，转移到 $f_{j+1,l+i}$。

乍看之下复杂度为 $\mathcal O(n^3)$，但仔细观察可以发现 $l$ 只需要从 $ij$ 开始枚举即可，又 $ij < n$，因此有效的 $i,j$ 只有 $\mathcal O(n \log n)$ 种，总时间复杂度 $\mathcal O(n^2 \log n)$。

最后是当 $n$ 为奇数的情况，唯一的区别就是变成枚举 $a_{k+1}$，其它的都很类似，事实上只需要将求 $f$ 时枚举 $i$ 的范围从 $[1,k+1]$ 改成 $[1,k]$ 即可。

const int N = 5e3 + 7;
int n, k;
modint f[N][N], g[N][N], ans;

int main() {
    rd(n, P), k = (n - 1) >> 1;
    f[0][0] = g[0][0] = 1;
    for (int i = k + !(n & 1); i; i--)
        for (int j = 0; i * (j + 1) < n; j++)
            for (int l = i * j; l + i < n; l++)
                f[j+1][l+i] += f[j][l];
    for (int i = k; i; i--)
        for (int j = 0; i * (j + 1) < n; j++)
            for (int l = i * j; l + i < n; l++)
                g[j+1][l+i] += g[j][l];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            f[i][j] += (i ? f[i-1][j] : 0),
            g[i][j] += (i ? g[i-1][j] : 0) + (j ? g[i][j-1] : 0) - ((i && j) ? g[i-1][j-1] : 0);
    for (int x = 1; x <= n; x++)
        for (int i = 0; i < x; i++)
            ans += f[x-1][i] * g[n-x][x-1-i];
    print(ans);
    return 0;
}

Balancing Network

对于 $T = 1$，设 $a_{i,j}$ 表示 $j$ 是否能到达 $i$，则依次考虑每个操作 $(x,y)$，相当于将 $a_x$ 和 $a_y$ 取并，bitset 即可，时间复杂度 $\mathcal O(\frac {nm}w)$。

对于 $T = 2$，注意到 $n=3$ 时必然有解，于是怎么搞都行了。

const int N = 5e4 + 7, M = 1e5 + 7;
int n, m, t, x[M], y[M];
bitset<N> a[N];
bool v[N];
int b[N], c[N];
char s[M];

int main() {
    rd(n, m, t);
    if (t == 1) {
        for (int i = 1; i <= n; i++) a[i][i] = 1;
        for (int i = 1; i <= m; i++)
            rd(x[i], y[i]), a[x[i]] = a[y[i]] |= a[x[i]];
        for (int i = 1; i <= n; i++)
            if ((int)a[i].count() == n) {
                v[i] = 1;
                for (int i = m; i; i--)
                    if (v[x[i]]) s[i] = '^', v[y[i]] = 1;
                    else if (v[y[i]]) s[i] = 'v', v[x[i]] = 1;
                    else s[i] = '^';
                prints(s, m);
                return 0;
            }
        print(-1);
    } else {
        if (n == 2) return print(-1), 0;
        for (int i = 1; i <= n; i++) b[i] = i, c[i] = 1;
        for (int i = 1; i <= m; i++) rd(x[i], y[i]);
        for (int i = m; i; i--)
            if (b[x[i]] == b[y[i]]) s[i] = '^';
            else {
                if (c[b[x[i]]] <= 1) swap(x[i], y[i]), s[i] = '^';
                else s[i] = 'v';
                --c[b[x[i]]], b[x[i]] = b[y[i]], ++c[b[x[i]]];
            }
        prints(s, m);
    }
    return 0;
}

Histogram Rooks

咕