这场难度较低，好几道题都挺典的，很有教育意义
C. Simple Repetition
题解：
有点构造题的感觉，首先可以发现对于任何一个数字 都可以有类似 1000100010001 这样的因子，而只有1数字重复多次后可能没有，所以特殊考虑 1 11 111，这样的数字，随便写个判质数就行了
bool isPrime(int n) {
if (n < 2) return false;
for (long long i = 2; i * i <= n; i++) {
if(n % i == 0)
return false;
}
return true;
}
void solve()
{
int x, k;
cin >> x >> k;
if(k == 1) {
cout << (isPrime(x) ? "YES" : "NO") << "\n";
} else {
if(x != 1) {
cout << "NO\n";
} else {
cout << (k == 2 ? "YES" : "NO") << "\n";
}
}
}
D. Skibidi Table
题解：
递归好题，就是代码不太好写。
首先我们可以发现，任何一个边长为 2 n 2^n 2n 的正方形都是由，四个较小的 边长为 2 n − 1 2^{n - 1} 2n−1 的小正方形来组成的
将每个小正方形视作一个 block，则一个 block 的和就是 2 n − 1 ∗ 2 n − 1 2^{n - 1} * 2^{n - 1} 2n−1∗2n−1 = = = 2 2 n − 2 2^{2n - 2} 22n−2，
又可以根据在左上，右下，左下，右上，将值分为 [ 0 , b l o c k ] , [ b l o c k + 1 , 2 ∗ b l o c k ] , [ 2 ∗ b l o c k + 1 , 3 ∗ b l o c k ] , [ 3 ∗ b l o c k + 1 , b l o c k ∗ 4 ] [0, block], [block + 1, 2 * block], [2 * block + 1, 3 * block ], [3 * block + 1, block * 4] [0,block],[block+1,2∗block],[2∗block+1,3∗block],[3∗block+1,block∗4] 四个区间，这也就能根据 d 来递归到底在哪个格子里。
如果最后 n = 1，则就在2 * 2 的一个block 中，那就看到底是四个单元格中的哪一个就行了，然后直接返回，不断向上累加答案
坐标也是同理，只是这次按照中位线进行划分。
代码如下：
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define int long long
#define debug(x) cerr << #x" = " << x << '\n';
typedef pair<int, int> PII;
const i64 N = 2e5 + 10, INF = 1e18 + 10;
i64 mod;
void solve()
{
int n, q;
cin >> n >> q;
auto dfs1 = [&](auto dfs1, int n, int x, int y) -> int {
if (n == 1) {
if (x == 1 && y == 1) return 1;
if (x == 2 && y == 2) return 2;
if (x == 2 && y == 1) return 3;
if (x == 1 && y == 2) return 4;
}
int mid = 1LL << (n - 1);
int pre = 1LL << (2 * (n - 1));
if (x <= mid && y <= mid) {
return dfs1(dfs1, n - 1, x, y);
} else if (x > mid && y > mid) {
return pre + dfs1(dfs1, n - 1, x - mid, y - mid);
} else if (x > mid && y <= mid) {
return pre * 2 + dfs1(dfs1, n - 1, x - mid, y);
} else {
return pre * 3 + dfs1(dfs1, n - 1, x, y - mid);
}
};
auto dfs2 = [&](auto dfs2, int n, int d) -> PII {
if(n == 1) {
if(d == 1) return {1, 1};
if(d == 2) return {2, 2};
if(d == 3) return {2, 1};
if(d == 4) return {1, 2};
}
int mid = 1LL << (n - 1);
int pre = 1LL << (2 * (n - 1));
PII p;
if (d <= pre) {
p = dfs2(dfs2, n - 1, d);
return {p.first, p.second};
} else if (d <= 2 * pre) {
p = dfs2(dfs2, n - 1, d - pre);
return {p.first + mid, p.second + mid};
} else if (d <= 3 * pre) {
p = dfs2(dfs2, n - 1, d - 2 * pre);
return {p.first + mid, p.second};
} else {
p = dfs2(dfs2, n - 1, d - 3 * pre);
return {p.first, p.second + mid};
}
};
while(q--) {
string s;
cin >> s;
if (s == "->") {
int x, y;
cin >> x >> y;
cout << dfs1(dfs1, n, x, y) << endl;
} else {
int d;
cin >> d;
PII p = dfs2(dfs2, n, d);
cout << p.first << ' ' << p.second << endl;
}
}
}
signed main()
{
cin.tie(nullptr) -> ios::sync_with_stdio(false);
int T = 1;
cin >> T;
while (T --) solve();
return 0;
}
E. Min Max MEX
题解：
二分贪心的好题
简单来说直接枚举答案MEX值，然后在数组中贪心，只要能达到MEX就视作一段，然后清空cnt，再从头计数
另外一点，不要用set，map，unordered_set,map 这种，容易被卡，直接用数组记录MEX值就行
void solve()
{
int n, k, Max = 0;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
auto check = [&](int mid) -> bool {
int cnt = 0, cur = 0;
vector<int> S(mid, 0);
//cout << mid << endl;
for (int i = 1; i <= n; i++) {
if (a[i] < mid && !S[a[i]]) {
S[a[i]] = 1;
cur++;
if (cur == mid) {
cnt++;
fill(S.begin(), S.end(), 0);
cur = 0;
}
}
}
return cnt >= k;
};
int l = 0, r = n;
while(l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
F. Hackers and Neural Networks
题解：
真叫我唐完了，本来以为是一道很复杂的贪心，没想到是个思维，想明白了就跟 800 分的题一样
简单来说就是选择能匹配上的数量最多的一个 b i b_i bi 作为第一个匹配的，然后每清除一个错误的单词，就匹配一个正确的，这样就能保证是最优解，赛时一直在想一下子都匹配完再统一全部清除，居然是一个一个清除，太唐了
struct B {
vector<string> ss;
int cnt = 0;
};
void solve()
{
int n, m;
cin >> n >> m;
vector<B> b(m + 1);
vector<string> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<int> st(n + 1, 0);
int res = 0;
for (int i = 1; i <= m; i++) {
vector<string> t(n + 1);
for (int j = 1; j <= n; j++) {
cin >> t[j];
if (t[j] == a[j]) b[i].cnt++, st[j] = 1;
}
b[i].ss = t;
res = max(res, b[i].cnt);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans += st[i];
}
if (ans < n) {
cout << -1 << endl;
return;
}
int num = (n - res) * 2;
cout << n + num << endl;
}
G. Shorten the Array
题解：
挺好的一道关于字典树的题。
简单来说，就是让我们找一个距离最近的一对 b i b_i bi b j b_j bj 使得他们的异或值大于等于 k。
第一个问题，如何确定最近？
这个问题其实挺典的，就是在遍历的过程中不断修改为相同值下的 更大的下标，这样在遍历的过程中查找满足条件的数的下标就一定是离目前元素最近的。
第二个问题，如何确定哪些数是满足条件的？
这里的思想跟数位DP很像，牵扯到一个从高位到低位的数字是否贴近下界的问题。
具体的，如果当前我枚举到了 b i b_i bi，我想查找一个数字异或起来大于等于 k，我就要枚举k的位数，从高到低，
- 如果 k k k 的第 j j j 位是1，那么我就得选择一个数字满足 第 j 位和 b i b_i bi 不同，这样一来，才能保证从高位到第j位满足不比 k k k 小，不然，后面不论取多少，也不会比 k k k。
- 如果第 j 位是 0，则寻找一个该位与 b i b_i bi 不同的数字后，不论后面取什么，也肯定都比k要大，所以直接加入到答案的情况中，取max，同时接着沿着异或为 0 的情况向下搜。
看代码：
class XorTrie {
static constexpr int BITS = 1e7 + 10;
public:
int n, idx;
static int tr[BITS][2];
static int val[BITS];
XorTrie() {
idx = 1;
}
~XorTrie() {
clear();
}
int newNode() {
int x = ++idx;
tr[x][0] = tr[x][1] = 0;
return x;
}
void insert(int x, int k) {
int p = 1;
for (int i = 31; ~i; i--) {
int bit = x >> i & 1;
if (!tr[p][bit]) {
tr[p][bit] = newNode();
}
p = tr[p][bit];
val[p] = k;
}
}
int query(int x, int k) {
int p = 1, res = 0;
for (int i = 31; ~i; i--) {
int bit = x >> i & 1;
if (!(k & (1 << i))) { // 如果当前k位置上为 0
res = max(res, val[tr[p][bit ^ 1]]);
p = tr[p][bit];
} else {
p = tr[p][bit ^ 1]; // 必须取不同的才能保证比k大
}
if (!p) return res;
}
return max(res, val[p]);
}
void clear() {
for (int i = 1; i <= idx; i++) {
tr[i][0] = tr[i][1] = 0;
val[i] = 0;
}
idx = 1;
}
};
int XorTrie::tr[BITS][2];
int XorTrie::val[BITS];
void solve()
{
int n, k;
cin >> n >> k;
XorTrie tr;
vector<int> a(n + 1);
int ans = INF;
for (int i = 1; i <= n; i++) {
cin >> a[i];
tr.insert(a[i], i);
int p = tr.query(a[i], k);
if (p) ans = min(ans, i - p + 1);
}
cout << (ans == INF ? -1 : ans) << endl;
}