写在前面
比赛地址：https://codeforces.com/contest/1867。
简略题解。
还好没掉分。
A
令原数列中第 \(k\) 大对应 \(k\) 即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 4e4 + 10;
//=============================================================
int n, num, b[kN];
struct Data {
int a, pos;
} a[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool cmp(Data fir_, Data sec_) {
return fir_.a > sec_.a;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 1;i <= n; ++ i) a[i] = (Data) {read(), i};
std::sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++ i) b[a[i].pos] = i;
for (int i = 1; i <= n; ++ i) printf("%d ", b[i]);
printf("\n");
}
return 0;
}
B
考虑给定串前后的对应部分原来是否相同，若不同则需要且仅需要在这两个位置中改一个，若相同则可以都不改或者都改。特别地，若 \(n\) 为奇数则中间位置改不改都行。
于是分别记录两种位置的数量 \(c_0, c_1\)，显然 \(t_{c_0 + 2\times k} (0\le k\le c_1)=1\)。若原串位置为奇数则额外有 \(t_{c_0 + 2\times k + 1} = 1\)。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, flag1, cnt0, cnt1;
char s[kN];
bool ans[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(); scanf("%s", s + 1);
flag1 = n % 2, cnt0 = cnt1 = 0;
for (int i = 1, j = n; i < j; ++ i, -- j) {
if (s[i] == s[j]) ++ cnt0;
else ++ cnt1;
}
for (int i = 0; i <= n; ++ i) ans[i] = 0;
if (flag1) {
for (int i = cnt1, j = 0; j <= cnt0; i += 2, ++ j) ans[i] = ans[i + 1] = 1;
} else {
for (int i = cnt1, j = 0; j <= cnt0; i += 2, ++ j) ans[i] = 1;
}
for (int i = 0; i <= n; ++ i) printf("%d", ans[i] ? 1 : 0);
printf("\n");
}
return 0;
}
/*
101 011
1001 0 0011
2
2
1 0 0
1
*/
C
傻逼交互、、、看到交互就先跑了亏死。
CF 的交互很亲民，望周知。
第一次加 \(\operatorname{mex}\)，之后删什么加什么。
正确性显然。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
const int kN = 1e5 + 10;
//=============================================================
int n, mex, a[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
mex = 0;
for (int i = 1; i <= n; ++ i) {
a[i] = read();
if (a[i] == mex) ++ mex;
}
for (int cnt = 1, del; ; ++ cnt) {
if (cnt % 2 == 1) {
if (cnt == 1) {
printf("%d\n", mex);
fflush(stdout);
++ mex;
for (int i = mex; i <= n; ++ i) if (a[i] == mex) ++ mex;
} else {
printf("%d\n", del);
fflush(stdout);
}
} else {
del = read();
if (del == -1) break;
if (del == -2) return 0;
}
}
}
return 0;
}
D
套路。
先特判 \(k=1\)，此时当且仅当 \(b_i=i\) 有解；若 \(k\not= 1\)，则当 \(b_i=i\) 时肯定无解。
手玩一下可以发现，若对于位置 \(\{p_1, p_2, \dots, p_k\}\) 满足 \(b_{p_1} = p_2, b_{p_2} = p_3, \dots, b_{p_k} = p_1\)，那么进行一次 \(l = \{p_1, p_2, \dots, p_k\}\) 的操作即可将这些位置全部修改成目标。
发现上面的情况类似于构成了一个大小为 \(k\) 的环，转换为图论模型，从节点 \(i\) 向 \(a_i\) 连边，则没有零出度的点，构成了一片基环内向森林。
显然，若其中的所有基环内向树都是大小为 \(k\) 的环构成时皆大欢喜，分别对环中的节点代表的位置进行一次操作即可；否则若所有基环内向树中仅有大小为 \(k\) 的环时，可以考虑按照拓扑序先对链上的节点代表的位置进行操作，最后再对环中的节点代表的位置进行一次操作即可。通过上面的操作方案可以推出若出现大小不为 \(k\) 的环时无解。
于是仅需 Tarjan 检查原图中的所有环大小是否为 \(k\) 即可。总时间复杂度 \(O(n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n, m, k, a[kN];
int edgenum, head[kN], v[kN << 1], ne[kN << 1];
int dfnnum, belnum, dfn[kN], low[kN], bel[kN], sz[kN];
std::stack <int> st;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Tarjan(int u_) {
low[u_] = dfn[u_] = ++ dfnnum;
st.push(u_);
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (!dfn[v_]) {
Tarjan(v_);
low[u_] = std::min(low[u_], low[v_]);
} else if (!bel[v_]) {
low[u_] = std::min(low[u_], dfn[v_]);
}
}
if (low[u_] == dfn[u_]) {
++ belnum;
for (int now = 0; now != u_; st.pop()) {
now = st.top();
bel[now] = belnum;
++ sz[belnum];
}
}
}
void Init() {
n = read(), k = read();
edgenum = dfnnum = belnum = 0;
while (!st.empty()) st.pop();
for (int i = 1; i <= n; ++ i) {
head[i] = dfn[i] = low[i] = bel[i] = sz[i] = 0;
}
for (int i = 1; i <= n; ++ i) a[i] = read(), Add(i, a[i]);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
int flag = 1;
if (k == 1) {
for (int i = 1; i <= n; ++ i) if (a[i] != i) flag = 0;
printf("%s\n", flag ? "YES" : "NO");
continue;
} else {
for (int i = 1; i <= n; ++ i) if (a[i] == i) flag = 0;
if (!flag) {
printf("NO\n");
continue;
}
}
for (int i = 1; i <= n; ++ i) if (!dfn[i]) Tarjan(i);
for (int i = 1; i <= belnum; ++ i) {
if (sz[i] > 1 && sz[i] != k) {
flag = 0;
break;
}
}
printf("%s\n", flag ? "YES" : "NO");
}
return 0;
}
E1/E2
傻逼交互、、、
写完 D 就下班了亏死，要是把 E 写了就飞升了。
钦定了 \(n,k\) 均为偶数，且 \(k\le n\le k^2\)，且有 \(k^2\le 2500\)，显然进行不多于 \(k\) 次操作就可以覆盖整个数列。
若 \(k\mid n\) 皆大欢喜，进行 \(\frac{n}{k}\) 次操作恰好覆盖整个数列即可，否则考虑如何构造出最后的长度为 \(n \bmod k\) 的不完整段的异或和。
首先想到必须对 \([n - k + 1, n]\) 进行一次操作来得到这段的异或和，然后考虑通过异或去除重复部分的贡献。由于有进行一次操作后被操作的序列翻转的性质，一个显然的想法是在对 \([n - k + 1, n]\) 进行操作前先对它之前的某一段进行操作，在获得了一部分信息的同时，将重复部分翻转到 \([n - k + 1, n]\) 中，再对它进行操作来获得全部的信息。
设 \(s = k\times \left\lfloor\frac{n}{k}\right\rfloor + 1\)，即最后不完整段的第一个位置，钦定了 \(n, k\) 为偶数，手玩一下可以发现先对 \(\left[\left\lfloor\frac{n+s}{2}\right\rfloor - k + 1, \left\lfloor\frac{n+s}{2}\right\rfloor\right]\) 进行一次操作，再对 \([n - k + 1, n]\) 进行一次操作，两次操作的结果的异或即为最后不完整段的异或和。
上述过程仅需 \(k+2\le 52\) 次操作，稳过。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
int n, k;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
int Query(int x_) {
printf("? %d\n", x_);
fflush(stdout);
return read();
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), k = read();
int i = 1, ans = 0;
for (i = 1; i + k - 1 <= n; i += k) {
ans ^= Query(i);
}
if (i <= n) {
ans ^= Query((i + n) / 2 - k + 1);
ans ^= Query(n - k + 1);
}
printf("! %d\n", ans);
fflush(stdout);
}
return 0;
}
F
咕
写在最后
- 如果有轮换的性质可以考虑套路地建立图论模型。
- CF 的交互题很亲密，望周知。