Codeforces 1147 Forethought Future Cup - Final Round (Onsite Finalists Only) 简要题解 - 题解

# A. Hide and Seek

看了好久没看懂题 /kk

后来意识到应该是只能移动到代币初始所在单元格的两旁的单元格，而不是当前所在单元格的两旁。

然后这题就简单很多了。

观察样例解释，发现只要起点或者终点有一个不一样就算不同方案。

换句话说，我们只考虑移动一步的情况，即向左，向右或者不动。

不难证明，这样所有的起点终点情况都会被考虑到。

考虑枚举每一个单元格，判断当前单元格能否作为：

起点以及终点。
起点在左边时的终点。
起点在右边时的终点。

如何判断呢？

我们记录一下每个点被询问到的最小时间和最晚时间。

如果代币在当前点一直不动，那么只有询问中没有出现当前点时合法，即： $mn_i > mx_i$
如果 $mn_i > mx_{i - 1}$ ，那么 $i$ 可以作为起点为 $i - 1$ 时的终点。
同理，如果 $mn_i > mx_{i + 1}$ ，那么 $i$ 可以作为起点为 $i + 1$ 时的终点。

然后记录一下答案即可。

$Code$

#include <bits/stdc++.h>
#define pb push_back
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
int n, k, ans;
int a[N], mx[N], mn[N];

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), k = read();
    memset(mx, -1, sizeof(mx));
    memset(mn, 0x3f, sizeof(mn));
    for(int i = 1; i <= k; ++i){
        a[i] = read();
        mx[a[i]] = max(mx[a[i]], i), mn[a[i]] = min(mn[a[i]], i);
    }
    for(int i = 1; i <= n; ++i){
        if(i > 1 && mn[i] > mx[i - 1]) ans++;
        if(i < n && mn[i] > mx[i + 1]) ans++;
        if(mn[i] > mx[i]) ans++;
    }
    write(ans), puts("");
    return 0;
}

# B. Chladni Figure

一个比较显然的结论：

如果旋转 $x$ 个点可以和原图形重合，那么旋转 $k \times x$ 个点也可以和原图形重合。

显然旋转一圈（即旋转 $n$ 个点）可以使得图形和原图形重合，因此我们只需要枚举 $n$ 的约数并旋转即可。

判断是否重合只需要判断每条线段旋转之后的位置是否有线段即可。

线段的位置开个 $\text{pair}$ 记录一下就行。

$Code$

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define po(x, d) ((x + d - 1) % n + 1)

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
typedef pair<int, int> P;
int n, m;
set <P> S;

inline void solve(int d){
    int flag = 1;
    for(auto x : S){
        P p = P(po(x.fi, d), po(x.se, d));
        if(p.fi > p.se) swap(p.fi, p.se);
        if(!S.count(p)) {flag = 0; break;}
    }
    if(flag) puts("Yes"), exit(0);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= m; ++i){
        int a = read(), b = read();
        if(a > b) swap(a, b);
        S.insert(P(a, b));
    }
    for(int i = 2; i * i <= n; ++i)
        if(n % i == 0) solve(i), solve(n / i);
    solve(1);
    return puts("No"), 0;
}

# C. Thanos Nim

博弈题。

先上结论：

$n$ 堆石子中最小值出现次数小于等于 $\frac n2$ 时，先手胜；反之，先手败。

证明：

如果开始时最小值出现次数小于等于 $\frac n2$ ，那么先手可以选择其他 $\frac n2$ 堆不是最小值的石堆，从中取出若干石头使得它们变成最小值。

然后最小值出现次数大于 $\frac n2$ ，并且轮到后手。

后手最多只能选择 $\frac n2$ 堆石堆，使得它们成为最小值，然后就又轮到先手。

再考虑一下什么情况下游戏结束。

最小值为 0，且 0 的个数大于 $\frac n2$ 。

再根据上面所说的过程，后手操作完最多产生 $\frac n2$ 个 0，然后先手再操作即可获得胜利。

如果开始时最小值出现次数大于 $\frac n2$ ，那么先手选择的石堆中必定包括最小石堆，导致最小值减小，从而最小值出现次数必然小于等于 $\frac n2$ ，然后后手必胜。

所以结论成立。

$Code$

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 55;
int n, mn = 60, cnt;
int a[N];

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read();
    for(int i = 1; i <= n; ++i) mn = min(mn, a[i] = read());
    for(int i = 1; i <= n; ++i)
        if(a[i] == mn) cnt++;
    puts(cnt <= n / 2 ? "Alice" : "Bob");
    return 0;
}

# D. Palindrome XOR

题目中有个很奇怪的性质：

$s$ 的首个字符为 1。

又因为 $a < b$ ，可得 $b$ 的第一位为 1， $a$ 的第一位为 0。

因此我们 $b$ 的最高位已经确定了， $a$ 的最高位还没有确定，考虑先枚举 $a$ 的最高位是第几位。

然后 $a$ 和 $b$ 的最高位是第几位都确定了，其他位如何处理呢？

考虑转化为图论模型。

现在的问题是：有 $2n$ 个点分为两组，每组 $n$ 个点，每个点都有一个点权为 $0$ 或 $1$ ，有一些点的点权已经确定，有的点权还没确定。有一些限制条件形如 $u$ 和 $v$ 权值必须相同，或必须不同，求合法的不同点权方案数。

建一张有 $2n + 2$ 个点的图，其中有两个点 $0, 1$ ，点权分别为 $0, 1$ ，如果有 $u, v$ 两个点权值相同，那么 $u, v$ 之间连权值为 $0$ 的边，反之连权值为 $1$ 的边。

具体来说：

$0$ 先向 $1$ 连权值为 $1$ 的边，表示 $0, 1$ 点权不同。
根据 $s_i$ $s_{i}$ 连边：
- 若 $s_i = 1$ ，表示 $a_i, b_i$ 点权不同， $a_i, b_i$ 之间连权值为 $1$ 的边。
- 若 $s_i = 0$ 同理，令 $a_i, b_i$ 之间连权值为 $0$ 的边。
- 若 $s_i = ?$ ，那么不连边。
若 $u$ 点权固定，那么向它的点权连权值为 $0$ 的边。
对于回文要求： $b_i$ 向 $b_{n - i + 1}$ 连权值为 $0$ 的边，表示 $b_i$ 和 $b_{n - i + 1}$ 权值相同， $a$ 同理。

建好图之后，我们可以把边权为 $0$ 的边缩起来，这一步用并查集实现，然后就只剩下了边权为 $1$ 的边。

对于每个联通块，显然都必须是二分图，否则不合法，判二分图直接黑白染色即可。

最后的贡献就是 $2^{cnt - 1}$ ， $cnt$ 为合法联通块个数，减 $1$ 是因为 $0, 1$ 那两个点所在联通块的权值已经固定了，没有贡献。

$Code$

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2010;
const int mod = 998244353;
int n, tot;
char s[N];
int a[N], b[N];
int id[N], id_a[N], id_b[N];
int fa[N], siz[N], col[N];
vector <int> g[N];

inline int find(int x){
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

inline void Union(int x, int y){
    x = find(x), y = find(y);
    if(x == y) return;
    if(siz[x] > siz[y]) swap(x, y);
    fa[x] = y, siz[y] += siz[x];
}

inline void add(int x, int y){
    g[find(x)].pb(find(y)), g[find(y)].pb(find(x));
}

bool flag;

inline void dfs(int x, int c){
    col[x] = c;
    for(auto y : g[x]){
        if(col[y] == col[x]) return flag = 1, void();
        if(!col[y]) dfs(y, 3 - c);
    }
}

int px[N], ans;

inline void init(){
    id[0] = ++tot, id[1] = ++tot;
    for(int i = 1; i <= n; ++i)
        id_a[i] = ++tot, id_b[i] = ++tot;
    px[0] = 1;
    for(int i = 1; i <= tot; ++i) px[i] = 2ll * px[i - 1] % mod;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    scanf("%s", s + 1), n = strlen(s + 1);
    init();
    for(int st = 2; st <= n; ++st){
        for(int i = 1; i <= tot; ++i) fa[i] = i, siz[i] = 1, col[i] = 0, g[i].clear();
        Union(id_a[st], id[1]), Union(id_b[1], id[1]);
        for(int i = 1; i < st; ++i) Union(id_a[i], id[0]);
        for(int i = st; i <= n; ++i) Union(id_a[i], id_a[n - (i - st + 1) + 1]);
        for(int i = 1; i <= n; ++i){
            Union(id_b[i], id_b[n - i + 1]);
            if(s[i] == '0') Union(id_a[i], id_b[i]);
        }
        add(id[0], id[1]);
        for(int i = 1; i <= n; ++i)
            if(s[i] == '1') add(id_a[i], id_b[i]);
        int cnt = 0; flag = 0;
        for(int i = 1; i <= tot; ++i)
            if(find(i) == i && !col[i]){
                dfs(i, 1);
                if(flag) break;
                cnt++;
            }
        if(!flag) ans = (ans + px[cnt - 1]) % mod;
    }
    write(ans), puts("");
    return 0;
}

# E. Rainbow Coins

观察到最多 $7$ 次询问，那跟序列长度肯定是没什么关系了。

我们肯定尽可能的把每次询问都问满，那么比较显然地询问：

$[a_1, a_2], [a_3, a_4]\cdots[a_{2k - 1}, a_{2k}]$
$[a_2, a_3], [a_4, a_5]\cdots[a_{2k}, a_{2k + 1}]$

然后相邻的两个硬币的颜色关系就已经知道了，我们再把颜色相同的合并一下，合并之后的颜色块为 $b_1, b_2 \cdots b_{tot}$ 。

现在相邻两个 $b$ 的颜色不同。

继续来询问：

$[b_1, b_3], [b_2, b_4], [b_5, b_7], [b_6, b_8] \cdots$
$[b_3, b_5], [b_4, b_6], [b_7, b_9], [b_8, b_{10}] \cdots$

此时我们就已经可以推出所有的颜色了，具体来说，设三种颜色分别为 $1, 2, 3$ ：

设 $b_1 = 1, b_2 = 2$ 。
如果 $b_1 \neq b_3$ ，那么 $b_3 = 6 - b_1 - b_2$ ，反之 $b_3 = b_1$ 。
$b_4$ 同理。
此时我们知道了 $[1 \sim 4], [5 \sim 8] \cdots$ 这样 4 个一组之内的颜色关系。
第 4 次询问后我们又把所有组连在了一起：
如果 $b_3 \neq b_5$ ，那么 $b_5 = 6 - b_4 - b_3$ ，反之 $b_5 = b_3$ 。
$b_6$ 同理。
然后我们就把 $1 \sim 4$ 和 $5 \sim 8$ 连起来了，后面的依次推过去即可。

$Code$

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
int T, n, cnt;
int ans[N], now[N];
vector <int> A, B, C;
char s[N];
typedef pair<int, int> P;
map <P, int> col;

inline void Clear(){
    memset(ans, 0, sizeof(ans));
    A.clear(), B.clear(), cnt = 0;
    col.clear();
}

inline void ask(){
    if(A.empty()) return;
    printf("Q %d ", (int)A.size());
    for(int i = 0; i < (int)A.size(); ++i)
        printf("%d %d ", A[i], B[i]);
    puts("");
    fflush(stdout);
    scanf("%s", s);
    for(int i = 0; i < (int)A.size(); ++i)
        col[P(A[i], B[i])] = (s[i] == '1');
    A.clear(), B.clear();
}

inline void add(int st, int ed, int l){
    for(int i = st; i <= ed; i += l) A.pb(i), B.pb(i + (l >> 1));
}

inline void add_now(int st, int ed, int l){
    for(int i = st; i <= ed; i += l) A.pb(now[i]), B.pb(now[i + (l >> 1)]);
}

inline void print(vector <int> A){
    for(auto x : A) printf("%d ", x);
    puts("");
}

inline void solve(){
    scanf("%d", &n);
    add(1, n - 1, 2), ask();
    add(2, n - 1, 2), ask();
    now[++cnt] = 1;
    for(int i = 1; i < n; ++i)
        if(!col[P(i, i + 1)]) now[++cnt] = i + 1;
    add_now(1, cnt - 2, 4), add_now(2, cnt - 2, 4), ask();
    add_now(3, cnt - 2, 4), add_now(4, cnt - 2, 4), ask();
    ans[now[1]] = 1;
    if(cnt > 1) ans[now[2]] = 2;
    for(int i = 3; i <= cnt; ++i){
        if(col[P(now[i - 2], now[i])]) ans[now[i]] = ans[now[i - 2]];
        else ans[now[i]] = 6 - ans[now[i - 2]] - ans[now[i - 1]];
    }
    A.clear(), B.clear(), C.clear();
    for(int i = 1, c; i <= n; ++i){
        if(ans[i]) c = ans[i];
        if(c == 1) A.pb(i);
        if(c == 2) B.pb(i);
        if(c == 3) C.pb(i);
    }
    printf("A %d %d %d\n", (int)A.size(), (int)B.size(), (int)C.size());
    print(A), print(B), print(C);
    fflush(stdout);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    scanf("%d", &T);
    while(T--) Clear(), solve();
    return 0;
}

# F. Zigzag Game

太过神仙，还不会。

# A. Hide and Seek

# B. Chladni Figure

# C. Thanos Nim

# D. Palindrome XOR

# E. Rainbow Coins

# F. Zigzag Game

后缀数组（SA） & 后缀自动机（SAM）

2022 常中集训游记