ABC286

Find_Yourself · 2023-01-22 15:43:39 · 个人记录

[ABC286C] Rotate and Palindrome

容易发现两种操作互不干扰，所以考虑枚举换位操作个数，再计算出相应的替换操作个数，最后取最小值即可。

复杂度 O(n^2)。

[ABC286D] Money in Hand

没啥难的，背包。

[ABC286E] Souvenir

Floyed 简单题。

算最短路的同时顺带着更新一下最大价值即可。

复杂度 O(n^3)。

[ABC286F] Guess The Number 2

第一次做 AT 的交互题，蛮有意思的。

可以想到构造一个序列，使得这个序列上的每一个点都都是从左到右循环移动，大概就是这个样子：2,3,4,5......x-2,x-1,1。

然后根据一个这样的系列可以得出 n 模 x 的余数。

诶？这不就是中国剩余定理吗？

我们考虑将若干个长为质数的序列拼在一起，使得他们的乘积大于 10^9，和小于等于 110。

然后发现好像构造不出来（于是我就寄了......）

赛后想到只要互质就行，不用都是质数，这样就可以构造出来了，即：

乘积为 1338557220，和为 108。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m = 108, x[11] = {0, 4, 9, 5, 7, 11, 13, 17, 19, 23}, y[11];
ll a[200], b[200], t[11];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << m << endl;
    fflush(stdout);
    int cur = 1;
    ll fac = 1;
    for (int i = 1; i <= 9; ++i) {
        fac = fac * x[i];
        for (int j = cur; j <= cur + x[i] - 2; ++j) {
            a[j] = j + 1;
        }
        a[cur + x[i] - 1] = cur;
        cur += x[i];
    }
    for (int i = 1; i <= 108; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
    for (int i = 1; i <= 9; ++i) t[i] = fac / x[i];
    fflush(stdout);
    for (int i = 1; i <= 108; ++i) cin >> b[i];
    cur = 1;
    for (int i = 1; i <= 9; ++i) {
        y[i] = (b[cur] - cur) % x[i];
        cur += x[i];
    }
    ll ans = 0;
    for (int i = 1; i <= 9; ++i) {
        for (ll j = t[i]; j <= LLONG_MAX - 5; j += t[i]) {
            if (j % x[i] == 1) {
                ans = (ans + j * y[i] % fac) % fac;
                break;
            }
        }
    }
    cout << ans << endl;
    fflush(stdout);
    return 0;
}

[ABC286G] Unique Walk

看起来挺难，实际上很水。

考虑一张图上所有的边都是特殊边，那么是需要判断一下度数为奇的点的个数是否小于等于 2 即可。

所以对于一张一般图，我们可以用并查集把没有限制的边所连接的点合并，因为这些点之间可以随便走。

之后再在新图上统计度数就行了。

复杂度 O(n \log n)。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, u[N], v[N], vis[N], d[N], fa[N];
int ff(int x) {return fa[x] == x?x:fa[x] = ff(fa[x]);}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) cin >> u[i] >> v[i];
    int x; cin >> x;
    for (int i = 1; i <= x; ++i) {
        int t; cin >> t;
        vis[t] = 1;
    }
    for (int i = 1; i <= m; ++i) {
        if (vis[i]) continue;
        fa[ff(u[i])] = ff(v[i]);
    }
    for (int i = 1; i <= m; ++i) {
        if (vis[i]) {
            ++d[ff(u[i])]; ++d[ff(v[i])];
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (ff(i) == i) {
            if (d[i] % 2) ++cnt;
        }
    }
    if (cnt <= 2) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}