掉大分，但是这场也挺edu的。
C1
题目大意：给定 $n$ ，求一个长度为 $n$ 的排列 $p$ ，使得对于每个 $i(2 \leq i \leq n-1)$ 都存在一个 $j(i \leq j \leq n),p_i=p_j \bigoplus i$ 。
数据范围： $3 \leq n \leq 2 \cdot 10^5$
思路：第一反应，猜测这个影响所有数的的数是 $1$ 或者 $n$ ，然后打表发现是行的，直接冲。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void solve() {
int n;
cin >> n;
vector<int> a(n);
a[n - 1] = 1;
map<int, int> ma;
for (int i = 2; i <= n - 1; i++) ma[1 ^ i]++;
int idx = 1;
for (int i = 2; i <= n; i++) {
if (!ma.count(i)) {
idx = i;
break;
}
}
a[0] = idx;
for (int i = 1; i < n - 1; i++) {
a[i] = 1 ^ (i + 1);
}
for (int p : a) cout << p << ' ';
cout << endl;
return;
}
|
C2
题目大意：跟上题一样，但是 $1 \leq i \leq n-1$ ，如果不行就输出-1。
数据范围： $3 \leq n \leq 2 \cdot 10^5$
思路：赛时没有开出来，肯定跟上题有关系，但不知道是什么关系。
首先，打表发现 $n=2^x$ 的时候是不行的，为什么？
若 $n=2^x$ 位于 $0 \sim n-2$ 的位置，则必然存在它后面有一个数能成立，而由原来的公式是不可行的。
那么，当 $n$ 在 $n-1$ 的位置呢？此时考虑 $n-2$ 位置的数，必然是 $n \bigoplus (n-1) = p_{n-2}$ ，这显然也不对。
然后，再看可行的构造，由 $C1$ 题打表后发现可以交换 $a_1$ 跟 $a_{lowbit(n)}$ 位置的数，为什么？（一个启示：位运算题lowbit是很重要的）
由于有 $p_1 =n,p_{lowbit(n)}=p_k \bigoplus lowbit(n),$ 而 $p_{lowbit(n)}=lowbit(n) \bigoplus 1=lowbit(n)+1$ 因此往前交换后会发现， $p_1=lowbit(n)+1= lowbit(n) \bigoplus 1,p_{lowbit(n)}=n = (n \bigoplus lowbit(n)) \bigoplus lowbit(n)$ ，前者自然没啥问题，后者由于 $n-lowbit(n)=(n-lowbit(n)+1) \bigoplus 1$ ，因此也在它后面。
这时候会问，如果 $n$ 是奇数呢？奇数情况完全不需要交换，用C1构造的数列就能成立。
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
|
void solve() {
int n;
cin >> n;
int tem = popcount((unsigned)n);
if (tem == 1) {
cout << -1 << endl;
return;
}
vector<int> a(n + 1);
map<int, int> ma;
a[n] = 1;
ma[1]++;
for (int i = 2; i <= n - 1; i++) {
a[i] = (i ^ 1);
ma[i ^ 1]++;
}
for (int i = 1; i <= n; i++) {
if (!ma.count(i)) {
a[1] = i;
break;
}
}
swap(a[1], a[lowbit(n)]);
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
cout << endl;
return;
}
|
D1
题目大意：给定一个字符串 $s$ ，在D1中它只是0-1字符串， $s[i]=0$ 代表在数组 $0 \sim n-1$ 的排列中不会出现子数组的MEX值为 $i$ ，反之则出现子数组的MEX值为 $i$ ，又给定一个数 $c$ ，求这样子数组不被 $c$ 整除的最小值，并模 $10^9+7$ ，若不存在则输出-1。
数据范围： $3 \leq n \leq 2 \cdot 10^5,1 \leq c \leq 10^9$
思路：组合数学题，而且这题的 $c$ 用处不大，因此原题中能构造的排列数是定值。
首先，如果字符串的首位和末位是0，那么肯定是不行的，因此输出-1。
随后考虑插空法，这是一个很常见的方法，也就是从MEX的角度考虑逐步拓展，从 $2 \sim n-1$ ，此时存在连续子数组能够表示 $0 \sim i-1$ 了，如果不能表示MEX为 $i$ 的话，就把 $i$ 插进这个子数组中，反之插到它的两侧。
于是，这样计数即可，需要注意的是 $c$ 可以每次直接除一下公因数，判断最后是否为1。
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
|
const int MOD = 1e9 + 7;
void solve() {
int n, c;
cin >> n >> c;
string s;
cin >> s;
if (s[0] == '0' || s[n - 1] == '0') {
cout << -1 << endl;
return;
}
ll res = 1;
map<int, int> ma;
for (int i = 1; i <= n - 1; i++) {
if (s[i] == '1') {
res = res * 2;
res %= MOD;
c /= __gcd(c, 2);
} else {
res = res * i;
res %= MOD;
c /= __gcd(c, i);
}
}
cout << (c == 1 ? -1 : res) << endl;
return;
}
|
D2
题目大意：跟上题一样，但是字符串中存在?，表示不知道取0还是取1。
数据范围：跟上题一样。
思路：其实很简单，首先先把所有不是?的对应元素乘出来（最后一格跟第一格由于有默认元素了，也能算），然后考虑对应?的元素，考虑贪心。
首先，如果用1是偶数的话，那么肯定不如取2，再考虑奇数，此时从高位倒着遍历到低位，如果此时剩下的 $c$ 没有奇数因子，那么肯定此时能给的2都给高位，如果有奇数因子，那么可以全部取 $2$ 。
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
|
constexpr int MOD = 1e9 + 7;
void solve() {
int n, c;
cin >> n >> c;
string s;
cin >> s;
if (s[0] == '0' || s[n - 1] == '0') {
cout << -1 << endl;
return;
}
ll ans = 2;
c /= __gcd(c, 2);
vi res;
rep(i, 1, n - 2) {
if (s[i] == '0') {
ans = ans * i % MOD;
c /= __gcd(c, i);
} else if (s[i] == '1') {
ans = ans * 2 % MOD;
c /= __gcd(c, 2);
} else
res.push_back(i);
}
frep(i, sz(res) - 1, 0) {
if (res[i] % 2 == 0) {
ans = ans * 2 % MOD;
c /= __gcd(c, 2);
}
}
frep(i, sz(res) - 1, 0) {
if (res[i] == 1 || res[i] % 2 == 0) continue;
if (c <= 2) {
ans = ans * res[i] % MOD;
c /= __gcd(c, res[i]);
} else {
ans = ans * 2 % MOD;
c /= __gcd(c, 2);
}
}
cout << ((c == 1) ? -1 : ans) << endl;
return;
}
|
这里给出一道类题：CF1699C
。
