B
题目大意：给你 $n$ 个集合 $S_1, S_2, \ldots, S_n$，其中每个集合里的元素是 $1$ 到 $m$ 之间的整数。需要选择一些集合（可以一个都不选，也可以全选），使得从 $1$ 到 $m$ 的每个整数至少在一个被选中的集合中出现。请判断是否有至少三种不同的方式选择集合，使上述条件成立。
数据范围：$1 \le t \le 10^4$，$2 \leq n \leq 5 \cdot 10^4$，$1 \le m \leq 10^5$，$1\le l_i \le m$，$1\le S_{i,1} < S_{i,2} < \cdots < S_{i, l_i} \le m$，$\sum n \le 5 \cdot 10^4$，$\sum m \le 10^5$，$\sum L \le 2 \cdot 10^5$。
思路：
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
| void solve() {
int n, m;
cin >> n >> m;
vi l(n);
vvi ma;
rep(i, 0, n - 1) {
cin >> l[i];
vi tem(l[i]);
rep(j, 0, l[i] - 1) cin >> tem[j];
ma.push_back(tem);
}
vi tem(m + 1);
int ans = 0;
rep(i, 0, n - 1) {
for (int& p : ma[i]) tem[p]++;
}
bool pd = true;
rep(i, 1, m) {
if (tem[i] == 0) {
cout << "NO" << endl;
return;
}
}
rep(i, 0, n - 1) {
bool flag = true;
for (int& p : ma[i]) {
if (tem[p] == 1) {
flag = false;
break;
}
}
if (flag) ans++;
}
if (ans >= 2)
cout << "YES" << endl;
else
cout << "NO" << endl;
return;
}
|
C
题目大意：给定一个整数 $n$ 和一个长度为 $n$ 的二进制字符串 $s$。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2\cdot 10^5$，$\sum n \le 2\cdot 10^5$。
思路：
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
| void solve() {
int n;
cin >> n;
string s;
cin >> s;
vi p(n);
vi tem;
rep(i, 0, n - 1) {
if (s[i] == '0') {
if (i == 0) {
if (s[1] == '1') {
cout << "NO" << endl;
return;
}
} else if (i == n - 1) {
if (s[n - 2] == '1') {
cout << "NO" << endl;
return;
}
} else {
if (s[i - 1] == '1' && s[i + 1] == '1') {
cout << "NO" << endl;
return;
}
}
}
}
cout << "YES" << endl;
rep(i, 0, n - 1) {
int j = i;
while (s[j] == s[i] && j <= n - 1) j++;
int idx = j - 1;
if (s[i] == '0') {
int len = j - i;
rep(j, 0, len - 1) p[i + j] = i + len - j;
} else {
rep(j, i, idx) p[j] = j + 1;
}
i = idx;
}
rep(i, 0, n - 1) cout << p[i] << ' ';
cout << endl;
return;
}
|
D1
题目大意：这是本题的简单版本。不同之处在于本版本中，$l=0$，并且 $r<2 \cdot 10^5$。只有在你解决了所有版本之后，你才能 hack 别人。给定两个整数 $l$ 和 $r$（$l\le r$）。令 $n = r - l + 1$。我们将创建两个数组 $a$ 和 $b$，都由 $n$ 个整数构成。初始时，$a$ 和 $b$ 都等于 $[l, l+1, \ldots, r]$。
数据范围：$1 \le t \le 10^4$，$0 = l \leq r < 2 \cdot 10^5$，$\sum n \le 2 \cdot 10^5$。
思路：
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
| void solve() {
int l, r;
cin >> l >> r;
vi a(r + 1);
vi b(r + 1);
int ans = 0;
int tem = popcount((unsigned)r);
cout << 1LL * r * (r + 1) << endl;
if ((1 << tem) == r + 1) {
rep(i, 0, r) { cout << (r ^ i) << ' '; }
cout << endl;
return;
}
tem = r;
while (tem >= 0) {
int tem2 = 1;
while (tem2 <= tem) tem2 <<= 1;
tem2--;
int len = tem2 - tem;
rep(i, len, tem) a[i] = tem2 - i;
tem = len - 1;
}
rep(i, 0, r) cout << a[i] << ' ';
cout << endl;
return;
}
|
D2
题目大意：这是该问题的 Hard 版本。不同之处在于本版本中，$0 \leq l \leq r < 2^{30}$。只有在你解决了所有版本的本题后，才可以进行 Hack。给定两个整数 $l$ 和 $r$（$l \leq r$）。设 $n = r - l + 1$。我们将创建两个长度为 $n$ 的数组 $a$ 和 $b$。一开始，$a$ 和 $b$ 均为 $[l, l+1, \ldots, r]$。
数据范围：$1 \leq t \leq 10^4$，$0 \leq l \leq r < 2^{30}$，$\sum n \le 2 \cdot 10^5$。
思路：
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
| void solve() {
ll l, r;
cin >> l >> r;
ll n = r - l + 1;
vl a(n);
ll ans = 0;
auto dfs = [&](this auto&& dfs, ll tl, ll tr) -> void {
if (tl > tr) return;
if (tl == tr) {
a[tl - l] = tl;
return;
}
ll tem = tl ^ tr;
int k = 63 - __builtin_clzll((ull)tem);
ll tem2 = (1LL << k);
ll tem3 = (tl >> (k + 1)) << (k + 1);
ll tem4 = tem3 + tem2 - 1;
ll tem5 = tem3 + (tem2 << 1) - 1;
ll cnt1 = tem4 - tl + 1;
ll cnt2 = tr - tem4;
if (cnt1 <= cnt2) {
for (ll i = tl; i <= tem4; i++) {
ll te = tem3 + tem5 - i;
a[i - l] = te;
a[te - l] = i;
}
dfs(tem3 + tem5 - tl + 1, tr);
} else {
for (ll i = tem4 + 1; i <= tr; i++) {
ll te = tem3 + tem5 - i;
a[te - l] = i;
a[i - l] = te;
}
dfs(tl, tem3 + tem5 - tr - 1);
}
};
dfs(l, r);
rep(i, 0, n - 1) { ans += 1LL * ((l + 1LL * i) | a[i]); }
cout << ans << endl;
rep(i, 0, n - 1) cout << a[i] << ' ';
cout << endl;
return;
}
|
