A. Equal Subsequences
全 1 接全 0，两种串的数量都是 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) cout << 1;
for (int i = 0; i < n - m; i++) cout << 0;
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
B. Make It Permutation
手玩即可发现，每行固定交换前 i 个和后 n - i 个数即可
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
struct Node {
int i, l, r;
};
void solve() {
int n;
cin >> n;
vector<Node> ans;
for (int i = 1; i <= n; i++) {
if (i > 1) ans.push_back({i, 1, i});
if (i + 1 < n) ans.push_back({i, i + 1, n});
}
cout << ans.size() << endl;
for (auto &x : ans) {
cout << x.i << " " << x.l << " " << x.r << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
C. Make It Beautiful
按位操作，对输入的每个数的每一位，如果为 1，加入答案，反之则存到一个 Multiset 中，接着对 set 中元素操作，从小到大，用 k 来组成对应的数，看能组成多少个。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
ll n, k;
cin >> n >> k;
int ans = 0;
multiset<ll> s;
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
for (int j = 0; j < 63; j++) {
if (x & (1ll << j)) {
ans++;
} else {
s.insert(1ll << j);
}
}
}
for (auto x : s) {
if (k >= x) {
ans++;
k -= x;
} else break;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
D1. Red Light, Green Light (Easy version)
官方题解的代码直接交上去 wa 了，神人
注意到数据小，可暴力。
DFS 当前位置（只考虑红绿灯的位置），已用时间，方向。
只有 5005002 个状态，足够。
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e3 + 7, mod = 1e9 + 7;
int vis[N][N][2];
int n, k;
bool flag = 0;
vector<ll> a(N), d(N);
void dfs(int x, ll t, int dir) {
if (dir == 0) {
if (x == 1 && (t - d[x]) % k == 0) {
flag = 1;
return;
}
if(x == n && (t - d[x]) % k != 0) {
flag = 1;
return;
}
if ((t - d[x]) % k == 0) {
if (vis[x][t % k][1]) return;
vis[x][t % k][1] = 1;
if (x > 1) dfs(x - 1, t + a[x] - a[x - 1], 1);
// vis[x][t % k][1] = 0;
} else {
if (vis[x][t % k][0]) return;
vis[x][t % k][0] = 1;
if (x < n) dfs(x + 1, t + a[x + 1] - a[x], 0);
// vis[x][t % k][0] = 0;
}
} else {
if(x == n && (t - d[x]) % k != 0) {
flag = 1;
return;
}
if (x == 1 && (t - d[x]) % k != 0) {
flag = 1;
return;
}
if ((t - d[x]) % k == 0) {
if (vis[x][t % k][0]) return;
vis[x][t % k][0] = 1;
if (x < n) dfs(x + 1, t + a[x + 1] - a[x], 0);
// vis[x][t % k][0] = 0;
} else {
if (vis[x][t % k][1]) return;
vis[x][t % k][1] = 1;
if (x > 1) dfs(x - 1, t + a[x] - a[x - 1], 1);
// vis[x][t % k][1] = 0;
}
}
}
void solve() {
// int n, k;
cin >> n >> k;
// vector<ll> a(n + 1), d(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
int q;
cin >> q;
while (q--) {
ll pos;
cin >> pos;
if(pos > a[n]) {
cout << "YES\n";
continue;
}
memset(vis, 0, sizeof(vis));
flag = 0;
int x = lower_bound(a.begin() + 1, a.begin() + n + 1, pos) - a.begin();
dfs(x, a[x] - pos, 0);
cout << (flag ? "YES" : "NO") << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
D2. Red Light, Green Light (Hard version)
数据大了之后，不能再暴力。
注意到，只能在红灯上转向，且某灯红灯时间对 k 取模后固定。
将遇到某灯且其红灯视为一个状态，只会在这些状态之间跳跃。
问题转化为在这些出度 <= 1 的点构成的有向图之间能否走到边界。
预处理向左向右时，与到某灯，且其红灯的时间。
向右存入前 n 个，向左存入后 n 个，避免覆盖同时方便使用。
接着对这 2 * n 个点判断，如果其有对应状态，赛入其边集合。
某点如果没有对应边，那么其可为出口，用 BFS 找出所有可出去的节点。
开 k 个桶，对应路灯位置模 k 后的状态，对应存入，并将每个桶排序。
回答查询：
先将输入位置模 k，查找桶表中是否存在，如果没有这个桶，说明直接可出去。
否则二分找到对应桶表中其右侧最近的红灯，如果没有，说明其右侧无红灯，也可出。
对找到的红灯判断其是否可出即可
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
ll n, k;
cin >> n >> k;
vector<ll> p(n + 1), d(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
vector<int> to(2 * n + 10, -1);
unordered_map<ll, int> lst;
lst.reserve(n * 2 + 10);
for (int i = 1; i <= n; i++) {
ll r = (p[i] + d[i]) % k;
if (auto it = lst.find(r); it != lst.end()) {
to[i] = it->second + n;
}
lst[r] = i;
}
lst.clear();
lst.reserve(n * 2 + 10);
for (int i = n; i > 0; i--) {
ll r = (p[i] - d[i]) % k;
if (r < 0) r += k;
if (auto it = lst.find(r); it != lst.end()) {
to[i + n] = it->second;
}
lst[r] = i;
}
vector<vector<int>> rev(2 * n + 10);
for (int i = 1; i <= 2 * n; i++) {
if (to[i] != -1) {
rev[to[i]].push_back(i);
}
}
vector<int> ans(2 * n + 10, 0);
deque<int> q;
for (int i = 1; i <= 2 * n; i++) {
if (to[i] == -1) {
ans[i] = 1;
q.push_back(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto v : rev[u]) {
if (!ans[v]) {
ans[v] = 1;
q.push_back(v);
}
}
}
unordered_map<ll, vector<pair<ll, int>>> buc;
buc.reserve(n * 2 + 10);
for (int i = 1; i <= n; i++) {
ll r = (p[i] - d[i]) % k;
if (r < 0) r += k;
buc[r].emplace_back(p[i], i);
}
for (auto &[_, vec] : buc) {
sort(vec.begin(), vec.end());
}
int qu;
cin >> qu;
while (qu--) {
ll pos;
cin >> pos;
ll r = pos % k;
auto fd = buc.find(r);
if (fd == buc.end()) {
cout << "YES" << endl;
continue;
}
const auto &v = fd->second;
auto it = lower_bound(v.begin(), v.end(), make_pair(pos, -1));
if (it == v.end()) {
cout << "YES" << endl;
continue;
}
int idx = it->second;
cout << (ans[idx] ? "YES" : "NO") << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|