前言
前天晚上掉到青名后昨晚马上冲回来了。虽然但是昨晚的编码体验并不好。
赛时A、B、C、D四题
A
题意
找到一个排列，满足$max(p_{i-1},p_i) \mod i = i - 1$
思路
猜猜题，根据条件形式想到构造形如
1
| n, 1, 2, …… n - 2, n - 1
|
的排列，根据样例发现当n为偶数时不能满足条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int n;
void solve() {
cin >> n;
if(n % 2 == 0) {
cout << -1 << endl;
return;
}
cout << n << " ";
for(int i = 2; i <= n; ++i) {
cout << i - 1 << " \n"[i == n];
}
return;
}
|
B
题意
对于一个给定的序列，判断重排后能否找到一个i，使得$\min([a1, a_2,\cdots,a_i]) = \gcd([a{i+1}, a_{i+2},\cdots，a_n])$
思路
通过手搓几组样例可以发现题意可以等价为判断序列中的最小值能否表示为其他若干个元素的最大公因数
为什么？
必要性：假设最后假设序列中任意两个不相等的数a < b,如果a在b左侧，那么取min时不会取到b；如果a在b右侧，显然后面若干数与a的gcd不会大于a，等式不可能成立。
充分性：记这个最小值为mina，只要序列中存在其他若干元素的gcd为mina，我们可以将这些数字放在mina右边，其他数字放在mina左边，显然等式成立。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void solve() {
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + 1 + n);
for(int i = 2; i <= n; ++i) {
if(a[i] % a[1] == 0) {
ll g = a[i];
for(int j = i; j <= n; ++j) {
if(a[j] % a[1] == 0) {
g = gcd(a[j], g);
}
}
cout << (g == a[1] ? "Yes\n" : "No\n");
return;
}
}
cout << "No\n";
}
|
C
题意
给定长度均为n的排列a、b，对于给定操作
- 选择两个索引i、j，交换a[i]和a[j],b[i]和b[j]
判断进行不超过n次操作后能否实现对于每个1~n中的i，a[i]=b[n+1-i]
思路
n次操作给的空间还挺宽裕的。观察操作形式，发现进行任意次操作后a[i]和b[i]的对应关系不会发生变化。
用数组记录每个元素在a中出现的位置，遍历1~n，
- 如果a[i] = b[i]，那么想要达到目标序列，必须满足n为奇数且a[n/2+1]!=b[n/2+1],执行操作（i，n/2+1）
- 否则，记it为元素b[i]在a数组中出现的位置，判断b[it]与a[i]是否相等，之后暴力进行修改操作并更新pos数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<vector<int>>
using namespace std;
const int MOD = 99244353;
const int N = 2e5 + 1;
int n;
int a[N];
int b[N];
int pos[N];
void solve() {
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int j = 1; j <= n; ++j) cin >> b[j];
for(int i = 1; i <= n; ++i) {
pos[a[i]] = i;
}
vector<pii> ans;
for(int i = 1; i <= n / 2; ++i) {
if(a[i] == b[i]) {
if(n * 2 == 0 || a[n / 2 + 1] == b[n / 2 + 1]) {
cout << -1 << endl;
return;
}
swap(a[i], a[n / 2 + 1]);
swap(b[i], b[n / 2 + 1]);
pos[a[i]] = i;
pos[a[n / 2 + 1]] = n / 2 + 1;
ans.emplace_back(i, n / 2 + 1);
}
int it = pos[b[i]];
if(b[it] != a[i]) {
cout << -1 << endl;
return;
}
if(it == n + 1 - i) continue;
swap(a[n + 1 - i], a[it]);
swap(b[n + 1 - i], b[it]);
pos[a[n + 1 - i]] = n + 1 - i;
pos[a[it]] = it;
ans.emplace_back(n + 1 - i, it);
}
cout << ans.size() << endl;
for(auto i : ans) {
cout << i.first << ' ' << i.second << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t; cin >> t;
while(t--) {
solve();
}
return 0;
}
|
D
题意
题意很长，大概是说给定n，m，k，构造一个长度为n的序列p，从中删去m段长度为k的连续子段后使得mex(p)最大
思路
我们需要构造一个序列在执行操作后mex最大，先考虑长度为k的一段s：
如果s中有多个某个元素，那么执行一次操作后可以将这多个元素全部删掉。
反之，如果我们希望多个元素有贡献，那么我们至少需要m+1个这个元素，且间隔至少为k
构造字串长度为len=max（k, n/(m+1)）,将0 1 2 …… len - 1反复添加到序列中，可以证明得到的序列进行操作后mex值最大。
1
2
3
4
5
6
7
8
9
| int n, m, k;
void solve() {
cin >> n >> m >> k;
int ans = max(k, n / (m + 1));
for(int i = 0; i < n; ++i) {
cout << i % ans << " \n"[i == n - 1];
}
}
|
后记
一开始B题没有输出21行的NO，wa了两发，喜提罚时。但是CD做的挺顺的。
看榜发现E难度极大，过四题+手速可以进到500名，而我由于罚时（加上本身手速不如他们）只到了2000名
（E好像又是个组合数学题，我一开始读错题写了个暴力模拟一直调不过样例后两个点）
rating又回到1630啦 qwq
