首页 题解

# A. Hide and Seek

看了好久没看懂题 /kk

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

然后这题就简单很多了。

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

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

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

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

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

如何判断呢？

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

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

然后记录一下答案即可。

CodeCode

#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
一个比较显然的结论：
如果旋转 xx 个点可以和原图形重合，那么旋转 k×xk \times x 个点也可以和原图形重合。
显然旋转一圈（即旋转 nn 个点）可以使得图形和原图形重合，因此我们只需要枚举 nn 的约数并旋转即可。
判断是否重合只需要判断每条线段旋转之后的位置是否有线段即可。
线段的位置开个 pair\text{pair} 记录一下就行。
CodeCode
#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
博弈题。
先上结论：
nn 堆石子中最小值出现次数小于等于 n2\frac n2 时，先手胜；反之，先手败。
证明：
如果开始时最小值出现次数小于等于 n2\frac n2，那么先手可以选择其他 n2\frac n2 堆不是最小值的石堆，从中取出若干石头使得它们变成最小值。
然后最小值出现次数大于 n2\frac n2 ，并且轮到后手。
后手最多只能选择 n2\frac n2 堆石堆，使得它们成为最小值，然后就又轮到先手。
再考虑一下什么情况下游戏结束。
最小值为 0，且 0 的个数大于 n2\frac n2。
再根据上面所说的过程，后手操作完最多产生 n2\frac n2 个 0，然后先手再操作即可获得胜利。
如果开始时最小值出现次数大于 n2\frac n2，那么先手选择的石堆中必定包括最小石堆，导致最小值减小，从而最小值出现次数必然小于等于 n2\frac n2，然后后手必胜。
所以结论成立。
CodeCode
#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
题目中有个很奇怪的性质：
ss 的首个字符为 1。
又因为 a<ba < b，可得 bb 的第一位为 1，aa 的第一位为 0。
因此我们 bb 的最高位已经确定了，aa 的最高位还没有确定，考虑先枚举 aa 的最高位是第几位。
然后 aa 和 bb 的最高位是第几位都确定了，其他位如何处理呢？
考虑转化为图论模型。
现在的问题是：有 2n2n 个点分为两组，每组 nn 个点，每个点都有一个点权为 00 或 11，有一些点的点权已经确定，有的点权还没确定。有一些限制条件形如 uu 和 vv 权值必须相同，或必须不同，求合法的不同点权方案数。
建一张有 2n+22n + 2 个点的图，其中有两个点 0,10, 1，点权分别为 0,10, 1，如果有 u,vu, v 两个点权值相同，那么 u,vu, v 之间连权值为 00 的边，反之连权值为 11 的边。
具体来说：
  • 00 先向 11 连权值为 11 的边，表示 0,10, 1 点权不同。
  • 根据 sis_i 连边：
    • 若 si=1s_i = 1，表示 ai,bia_i, b_i 点权不同，ai,bia_i, b_i 之间连权值为 11 的边。
    • 若 si=0s_i = 0 同理，令 ai,bia_i, b_i 之间连权值为 00 的边。
    • 若 si=?s_i = ?，那么不连边。
  • 若 uu 点权固定，那么向它的点权连权值为 00 的边。
  • 对于回文要求：bib_i 向 bn−i+1b_{n - i + 1} 连权值为 00 的边，表示 bib_i 和 bn−i+1b_{n - i + 1} 权值相同，aa 同理。
建好图之后，我们可以把边权为 00 的边缩起来，这一步用并查集实现，然后就只剩下了边权为 11 的边。
对于每个联通块，显然都必须是二分图，否则不合法，判二分图直接黑白染色即可。
最后的贡献就是 2cnt−12^{cnt - 1}，cntcnt 为合法联通块个数，减 11 是因为 0,10, 1 那两个点所在联通块的权值已经固定了，没有贡献。
CodeCode
#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
观察到最多 77 次询问，那跟序列长度肯定是没什么关系了。
我们肯定尽可能的把每次询问都问满，那么比较显然地询问：
  1. [a1,a2],[a3,a4]⋯[a2k−1,a2k][a_1, a_2], [a_3, a_4]\cdots[a_{2k - 1}, a_{2k}]
  2. [a2,a3],[a4,a5]⋯[a2k,a2k+1][a_2, a_3], [a_4, a_5]\cdots[a_{2k}, a_{2k + 1}]
然后相邻的两个硬币的颜色关系就已经知道了，我们再把颜色相同的合并一下，合并之后的颜色块为 b1,b2⋯btotb_1, b_2 \cdots b_{tot}。
现在相邻两个 bb 的颜色不同。
继续来询问：
  1. [b1,b3],[b2,b4],[b5,b7],[b6,b8]⋯[b_1, b_3], [b_2, b_4], [b_5, b_7], [b_6, b_8] \cdots
  2. [b3,b5],[b4,b6],[b7,b9],[b8,b10]⋯[b_3, b_5], [b_4, b_6], [b_7, b_9], [b_8, b_{10}] \cdots
此时我们就已经可以推出所有的颜色了，具体来说，设三种颜色分别为 1,2,31, 2, 3：
  • 设 b1=1,b2=2b_1 = 1, b_2 = 2。
  • 如果 b1≠b3b_1 \neq b_3，那么 b3=6−b1−b2b_3 = 6 - b_1 - b_2，反之 b3=b1b_3 = b_1。
  • b4b_4 同理。
  • 此时我们知道了 [1∼4],[5∼8]⋯[1 \sim 4], [5 \sim 8] \cdots 这样 4 个一组之内的颜色关系。
  • 第 4 次询问后我们又把所有组连在了一起：
  • 如果 b3≠b5b_3 \neq b_5，那么 b5=6−b4−b3b_5 = 6 - b_4 - b_3，反之 b5=b3b_5 = b_3。
  • b6b_6 同理。
  • 然后我们就把 1∼41 \sim 4 和 5∼85 \sim 8 连起来了，后面的依次推过去即可。
CodeCode
#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
太过神仙，还不会。
 更新于   阅读次数  次