Visits: 1002

AtCoder Grand Contest 022

Diverse Word

分类讨论一下即可。

int main() {
    string s;
    cin >> s;
    if ((int)s.size() == 26) {
        string t = s;
        if (next_permutation(t.begin(), t.end())) {
            int i = 0;
            while (s[i] == t[i]) ++i;
            while ((int)t.size() > i + 1) t.pop_back();
            cout << t << endl;
        } else print(-1);
    } else {
        map<char, bool> v;
        for (char c : s) v[c] = 1;
        for (char i = 'a'; i <= 'z'; i++)
            if (!v[i]) {
                cout << s + i << endl;
                break;
            }
    }
    return 0;
}

GCD Sequence

如果 $n=3$，题目已经给出一组构造。

否则，注意到 $\le 30000$ 且是 $2$ 的倍数或 $3$ 的倍数的数恰好有 $20000$ 个，我们只使用这些数。

先选择 $2,3,4,9$，然后将其它数按 $\bmod 6$ 分类，在保证和为 $6$ 的倍数的情况下选剩下的数就能满足条件。

int main() {
    int n;
    rd(n);
    if (n == 3) return prints("2 5 63"), 0;
    vi ans = {2, 3, 4, 9};
    set<int> s[6];
    for (int i = 6; i <= 30000; i++)
        if (!(i % 2) || !(i % 3)) s[i%6].insert(i);
    s[3].erase(9);
    n -= 4;
    while (n > 1 && s[2].size() && s[4].size())
        n -= 2,
        ans.pb(*s[2].begin()), s[2].erase(s[2].begin()),
        ans.pb(*s[4].begin()), s[4].erase(s[4].begin());
    while (n > 1 && s[3].size() > 1u)
        n -= 2,
        ans.pb(*s[3].begin()), s[3].erase(s[3].begin()),
        ans.pb(*s[3].begin()), s[3].erase(s[3].begin());
    while (n && s[0].size())
        n--,
        ans.pb(*s[0].begin()), s[0].erase(s[0].begin());
    for (int x : ans) print(x, ' ');
    return 0;
}

Remainder Game

本质上就是一张 $51$ 个点的有向图，问所有 $a_i$ 能否到达 $b_i$。

由于代价是 $2^i$，因此直接贪心即可，时间复杂度 $\mathcal O(n^4)$。

const int N = 51;
int n, a[N], b[N];
bool v[N];
ll ans;

bool dfs(int x, int t, ll o) {
    if (x == t) return 1;
    if (v[x]) return 0;
    v[x] = 1;
    for (int i = 1; i < N; i++)
        if ((o >> i & 1) && dfs(x % i, t, o)) return 1;
    return 0;
}

inline bool pd(ll o) {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < N; j++) v[j] = 0;
        if (!dfs(a[i], b[i], o)) return 0;
    }
    return 1;
}

int main() {
    rd(n), rda(a, n), rda(b, n);
    for (int i = 1; i < N; i++) ans |= 1ll << i;
    if (!pd(ans)) return print(-1), 0;
    for (int i = N - 1; i; i--)
        if (pd(ans ^ 1ll << i)) ans ^= 1ll << i;
    print(ans);
    return 0;
}

Shopping

题意

• 数轴上按顺序有 $n+2$ 个点，第 $0$ 个点在 $0$ 处，第 $i(\in [1,n])$ 个点在 $x_i$ 处，第 $n+1$ 个点在 $L$ 处。
• 有一辆每秒行驶一个单位的车，一开始在 $0$ 处，然后不断在 $0,L$ 之间往返。
• 你一开始也在 $0$ 处，你可以随时上下车。
• 你需要在每个点下车一次，而且必须在第 $i$ 个点停留 $t_i$ 秒后才能再次上车。
• 最后你要回到 $0$ 处，求最短耗时。
• $n \le 3 \times 10^5$。

题解

首先答案一定是 $2L$ 的整数倍。

其次可以先把 $\lfloor \frac{t_i}{2L} \rfloor$ 加入答案，然后把 $t_i$ 模上 $2L$，显然答案不变，同时保证 $t_i < 2L$。

考虑答案的一个上界，顺次走到 $x_1,x_2,\cdots,x_n$，走到每个点停留 $2L$ 然后走到下一个点，这样答案是 $n+1$。

考虑如何更优，设 $l_i$ 表示从左边到 $i$，车在下次从右边经过 $i$ 时是否停留够了 $t_i$，即 $l_i = [2(L-x_i) \ge t_i]$；类似定义 $r_i = [2x_i \ge t_i]$。

对于 $l_i = r_i = 0$ 的点，我们完全无法优化，可以直接忽略掉。

对于 $t_i = 0$ 的点，可以将答案 $-1$，然后直接忽略掉。

对于点 $n$，如果 $l_n = 1$，可以将答案 $-1$，否则无法优化，无论是否 $-1$ 都可以直接忽略掉。

对于 $[1,n)$ 的点，如果存在 $i,j$ 满足 $i < j$ 且 $r_i = l_j = 1$，那么我们可以再经过 $i$ 时先不停留，到 $j$ 时在一轮中先完成 $j$ 后完成 $i$，可以将答案 $-1$。

于是就相当于再减掉一个最大匹配数。

又发现如果 $(l,r) = (1,0)$ 的点一定在 $(l,r) = (0,1)$ 的点的左边（根据定义式可以推出来），因此这两类点不可能匹配上。

因此我们就是要用 $(l,r) = (1,1)$ 的点先尽量和上述两类点匹配，然后剩余的两两匹配就是最大匹配了。

时间复杂度 $\mathcal O(n)$。

代码

const int N = 3e5 + 7;
int n, L, x[N], t[N];
ll ans;
bool l[N], r[N], v[N];
vi p;

int main() {
    rd(n, L), rda(x, n), rda(t, n), ans = n + 1;
    for (int i = 1; i <= n; i++) {
        ans += t[i] / (2 * L), t[i] %= 2 * L;
        l[i] = 2 * (L - x[i]) >= t[i], r[i] = 2 * x[i] >= t[i];
        if (!t[i]) --ans, v[i] = 1;
        else if (!l[i] && !r[i]) v[i] = 1;
        else if (i == n && l[i]) --ans;
    }
    for (int i = 1; i < n; i++)
        if (!v[i]) {
            if (l[i] && r[i]) p.pb(i);
            else if (l[i] && !r[i] && p.size())
                --ans, v[i] = 1, v[p.back()] = 1, p.pop_back();
        }
    p.clear();
    for (int i = n - 1; i; i--)
        if (!v[i]) {
            if (l[i] && r[i]) p.pb(i);
            else if (!l[i] && r[i] && p.size())
                --ans, v[i] = 1, v[p.back()] = 1, p.pop_back();
        }
    ans -= p.size() / 2;
    print(ans * 2 * L);
    return 0;
}

Median Replace

题意

• 给定一个长度为 $n$ 的 $0/1$ 串 $s$，保证 $n$ 为奇数，其中有些位置上的字符不确定。
• 请你求出有多少个 $s$ 满足执行下列操作 $\frac {n-1}2$ 次后能使 $s$ 为 1：
  • 选择 $s$ 的三个连续的字符，将它们替换为这三个数的中位数。
• $n \le 3 \times 10^5$，答案对 $10^9+7$ 取模。

题解

考虑如何判断一个 $0/1$ 串是否合法。

维护一个栈，这个栈从栈底到栈顶由一段连续的 $1$ 和一段连续的 $0$ 组成。

对于一个新加字符 $c$：

• 若 $c=0$：由于三个 $0$ 抵消为一个 $0$ 严格不劣，因此若原来栈顶有两个 $0$ 则抵消为一个，否则加一个 $0$。
• 若 $c=1$：如果栈顶是 $0$，可以直接将这个 $0$ 与新加的 $1$ 抵消（因为无论和另外哪个数取中位数，答案都是另外那个数）；如果栈顶为 $1$，若已经有两个 $1$ 了，那么这个串一定合法，因此直接忽略掉这个 $1$ 就可以了，否则加一个 $1$。

根据这个过程可以知道栈 $0/1$ 的个数只有 $0 \sim 2$ 这三种，总共只有 $9$ 种情况。

考虑根据这个判定方法进行 DP，时间复杂度 $\mathcal O(n)$。

代码

const int N = 3e5 + 7;
int n;
char s[N];
modint f[N][3][3], ans;

int main() {
    rds(s, n), f[0][0][0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                if (!!f[i][j][k]) {
                    if (s[i+1] != '0') {
                        if (k) f[i+1][j][k-1] += f[i][j][k];
                        else f[i+1][min(j+1,2)][k] += f[i][j][k];
                    }
                    if (s[i+1] != '1') {
                        if (k == 2) f[i+1][j][1] += f[i][j][k];
                        else f[i+1][j][k+1] += f[i][j][k];
                    }
                }
    for (int i = 0; i < 3; i++)
        for (int j = 0; j <= i; j++)
            ans += f[n][i][j];
    print(ans);
    return 0;
}

Checkers

题意

• 令 $x = 10^{100}$。
• 数轴上有 $n$ 个点，第 $i$ 个点的坐标为 $x^i$。
• 你会进行下列操作 $n-1$ 次，最终只剩下一个点：
  • 选择两个点 $a,b$，将 $a$ 移动到关于 $b$ 的对称点。
  • 移除 $b$。
• 求可能的最终点的坐标的数量。
• $n \le 50$，答案对 $10^9+7$ 取模。

题解

由于 $x$ 很大，只用考虑每个数的贡献，贡献不同的方案对应的坐标也不同，显然每个数的贡献形如 $\pm 2^k$。

对于每次操作选择的 $a,b$，将 $b$ 的父亲设为 $a$，这样会得到一颗有根树，点 $i$ 贡献中的 $k$ 就是它的深度（根的深度为 $0$）。

考虑正负号，设点 $i$ 有 $c$ 个儿子，则会有 $\lfloor \frac c2 \rfloor$ 个儿子和 $i$ 异号，剩下的同号。

考虑 DP，设 $f_{i,j}$ 表示已经有 $i$ 个点，其中有 $j$ 个奇数个儿子的点的方案数，枚举这一层的点数 $k$，那么不考虑这一层的点的儿子的影响，有 $\frac {k-j}{2}$ 个点和父亲不同，再枚举实际有 $x$ 个点和父亲不同，则意味着有 $|\frac {k-j}2 – x|$ 个点有奇数个儿子。

时间复杂度 $\mathcal O(n^4)$。

代码

const int N = 57;
int n;
modint f[N][N];

int main() {
    rd(n), init(n), f[1][0] = f[1][1] = n;
    for (int i = 1; i < n; i++)
        for (int j = 0; j <= i; j++)
            for (int k = max(j, 1); k <= n - i; k++) {
                if ((k - j) & 1) continue;
                int y = (k - j) / 2;
                for (int x = 0; x <= k; x++)
                    f[i+k][abs(y-x)] += f[i][j] * binom(n - i, k) * binom(k, x);
            }
    print(f[n][0]);
    return 0;
}