[ABC286C] Rotate and Palindrome
容易发现两种操作互不干扰，所以考虑枚举换位操作个数，再计算出相应的替换操作个数，最后取最小值即可。
复杂度 \(O(n^2)\)。
没啥难的，背包。
Floyed 简单题。
算最短路的同时顺带着更新一下最大价值即可。
复杂度 \(O(n^3)\)。
第一次做 AT 的交互题，蛮有意思的。
可以想到构造一个序列，使得这个序列上的每一个点都都是从左到右循环移动，大概就是这个样子：\(2,3,4,5......x-2,x-1,1\)。
然后根据一个这样的系列可以得出 \(n\) 模 \(x\) 的余数。
诶？这不就是中国剩余定理吗？
我们考虑将若干个长为质数的序列拼在一起，使得他们的乘积大于 \(10^9\)，和小于等于 \(110\)。
然后发现好像构造不出来（于是我就寄了......）
赛后想到只要互质就行，不用都是质数，这样就可以构造出来了，即：
\[4, 9, 5, 7, 11, 13, 17, 19, 23
\]
乘积为 \(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;
}
看起来挺难，实际上很水。
考虑一张图上所有的边都是特殊边，那么是需要判断一下度数为奇的点的个数是否小于等于 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;
}