被暴打了555，还是太菜了
1001-Theramore
题目描述
给出一段01序列，可以操作若干次，每次操作可以将一段长度为偶数的子序列翻转，求最终能得到的字典序最小的序列。
思路
贪心地将每个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
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using LL = long long;
signed main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int t;
std::cin >> t;
while (t -- ) {
std::string s;
std::cin >> s;
int odd = 0, even = 0;
for (int i = 0; i < s.size(); ++ i) {
if (s[i] == '1') {
if (i & 1) {
++ odd;
} else {
++ even;
}
}
}
std::vector< char > ans(s.size(), '0');
for (int i = s.size() - 1; i >= 0; -- i) {
if ((i & 1) && odd) {
-- odd;
ans[i] = '1';
}
if (!(i & 1) && even) {
-- even;
ans[i] = '1';
}
}
for (int i = 0; i < s.size(); ++ i) {
std::cout << (char)ans[i];
}
std::cout << '\n';
}
return 0;
}
|
1005-Ironforge
题目描述
一开始有一个长度为 $n$ 的链，每个节点有一个点权 $a_i$ ，第 $i$ 和第 $i+1(1 \leq i \leq n - 1)$ 个节点之间有一条边权为 $b_i$ 的边。
若此时你处于第 $x$ 个节点，你会得到 $a_x$ 的所有质因子，你能通过第 $i$ 条边当且仅当你拥有 $b_i$ 这个质数。
有 $q$ 次询问，每次询问给出起点 $x$ 和终点 $y$ ，问是否能从 $x$ 走到 $y$ ，每条边和每个节点可以重复走。
思路
这题求的是每个点能走的最大范围是多少。
首先从后往前遍历，若现在处于节点 $i$ 且 $i \rightarrow i+1$ 这条边能走通， 那么 $R_i = i + 1$ ，若 $i+1$ 还能向右拓展我们就继续让 $R_i=R_{i+1}$ ，一直这样，类似并查集的路径压缩。
然后从前往后遍历，若现在处于节点 $i$ ，$i-1$ 能向 $i$ 拓展且从 $i \backsim R_i$ 能走回到 $i-1$ ，就让 $R_i=R_{i-1},L_i=L_{i-1}$ ，若回不到 $i-1$ ，那么让 $L_i=i$。若 $i-1$ 不能向 $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
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
| #include<bits/stdc++.h>
using LL = long long;
template < typename T >
void read(T &x) {
x = 0;
T f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') {
f = -1;
ch = getchar();
}
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x= x * f;
}
template < typename T >
void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x < 10) {
putchar(x + '0');
} else {
write(x / 10);
putchar(x % 10 + '0');
}
}
template < typename T, typename ...Arg >
void read(T &x, Arg &...arg) {
read(x);
read(arg...);
}
template < typename T, typename ...Arg >
void write(T &x,Arg &...arg) {
write(x);
putchar(' ');
write(arg...);
}
constexpr int NUMBER_SIZE = 2e5 + 1;
int v[NUMBER_SIZE], pri[NUMBER_SIZE], tot;
std::vector< int > fac[NUMBER_SIZE];
void Pre_Work() {
for (int i = 2; i < NUMBER_SIZE; ++ i) {
if (!v[i]) {
v[i] = i;
pri[tot ++ ] = i;
}
for (int j = 0; j < tot && 1LL * pri[j] * i < NUMBER_SIZE; ++ j) {
if (pri[j] > v[i]) {
break;
}
v[pri[j] * i] = pri[j];
}
}
for (int i = 1; i < NUMBER_SIZE; ++ i) {
int x = i;
for (int j = 0; j < tot && pri[j] <= x; ++ j) {
if (x % pri[j] == 0) {
fac[i].emplace_back(pri[j]);
while (x % pri[j] == 0) {
x /= pri[j];
}
}
}
}
}
const int N = 2e5 + 1;
int n, q, a[N], b[N], L[N], R[N];
std::vector< int > pos[N];
bool find(int x, int l, int r) {
if (pos[x].empty() || pos[x].back() < l || pos[x].front() > r) {
return false;
}
return *lower_bound(begin(pos[x]), end(pos[x]), l) <= r;
}
void solve() {
read(n, q);
for (int i = 0; i < tot; ++ i) {
pos[pri[i]].clear();
}
for (int i = 1; i <= n; ++ i) {
read(a[i]);
for (const auto &x : fac[a[i]]) {
pos[x].emplace_back(i);
}
}
for (int i = 1; i < n; ++ i) {
read(b[i]);
}
for (int i = n; i >= 1; -- i) {
R[i] = i;
while (i < n && find(b[R[i]], i, R[i])) {
R[i] = R[R[i] + 1];
}
}
for (int i = 1; i <= n; ++ i) {
if (i > 1 && R[i - 1] >= i) {
if (find(b[i - 1], i, R[i])) {
L[i] = L[i - 1];
R[i] = R[i - 1];
} else {
L[i] = i;
}
} else {
L[i] = i;
bool update;
do {
update = false;
while (R[i] < n && find(b[R[i]], L[i], R[i])) {
update = true;
R[i] = R[R[i] + 1];
}
while (L[i] > 1 && find(b[L[i] - 1], L[i], R[i])) {
update = true;
L[i] = L[L[i] - 1];
}
} while (update);
}
}
while (q -- ) {
int x, y;
read(x, y);
if (L[x] <= y && R[x] >= y) {
puts("Yes");
} else {
puts("No");
}
}
}
signed main() {
Pre_Work();
int t;
read(t);
while (t -- ) {
solve();
}
return 0;
}
|
1007-Darnassus
题目描述
给你 $n$ 个点，每个点的权值为 $a_i$ ，$i$ 和 $j$ 之间的边权为 $|i-j| \times|a_i-a_j|$ ，求这 $n$ 个点的最小生成树。
思路
观察到 $mst$ 的最大边权不超过 $n-1$ ，那么 $|i-j|$ 和 $|a_i - a_j|$ 中至少有一个小于等于 $\sqrt n$ ，暴力找边即可。
代码
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
| #include<bits/stdc++.h>
using LL = long long;
const int N = 5e4 + 5;
int n, a[N], pos[N];
int head[N], from[N * 460], to[N * 460], next[N * 460], cur;
void AddEdge(int x, int u, int v) {
++ cur;
from[cur] = u;
to[cur] = v;
next[cur] = head[x];
head[x] = cur;
}
int f[N];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void solve() {
std::cin >> n;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
pos[a[i]] = i;
head[i] = 0;
f[i] = i;
}
int m = sqrt(n);
cur = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= std::min(i + m, n); ++ j) {
LL k1 = 1LL * (j - i) * abs(a[i] - a[j]);
if (k1 < n) {
AddEdge(k1, i, j);
}
LL k2 = 1LL * (j - i) * abs(pos[i] - pos[j]);
if (k2 < n) {
AddEdge(k2, pos[i], pos[j]);
}
}
}
LL ans = 0;
int edge = 0;
for (int i = 1; i < n; ++ i) {
for (int j = head[i]; j; j = next[j]) {
int u = find(from[j]), v = find(to[j]);
if (u != v) {
ans += i;
f[u] = v;
++ edge;
}
if (edge == n - 1) {
break;
}
}
if (edge == n - 1) {
break;
}
}
std::cout << ans << '\n';
}
signed main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int t;
std::cin >> t;
while (t -- ) {
solve();
}
return 0;
}
|
1008-Orgrimmar
题目描述
给出一颗树，你可以从中选出一些点集，要求这些点集中每个点至多有一条边和它相连，最大化点集大小。
思路
设 $f_{x,0}$ 为选了 x 且向下有一条连边的最大点集数， $f_{x,1}$ 为选了 x 但没有连边的最大点集数， $f_{x,2}$ 为不选 x 的最大点集数。
最后对根节点的三种方案取最大值即可
代码
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
| #include<bits/stdc++.h>
using LL = long long;
void solve() {
int n;
std::cin >> n;
std::vector< std::vector< int > > adj(n), f(n, std::vector< int >(3));
for (int i = 1; i < n; ++ i) {
int u, v;
std::cin >> u >> v;
-- u;
-- v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
std::function< void(int, int) > dfs = [&](int x, int p) {
int mx = 0, sum = 0;
f[x][0] = f[x][1] = 1;
for (const auto &y : adj[x]) {
if (y ^ p) {
dfs(y, x);
mx = std::max(mx, f[y][1] - f[y][2]);
sum += f[y][2];
f[x][2] += std::max({f[y][0], f[y][1], f[y][2]});
}
}
f[x][0] += sum + mx;
f[x][1] += sum;
};
dfs(0, -1);
std::cout << *std::max_element(begin(f[0]), end(f[0])) << '\n';
}
signed main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int size(512<<20);
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
int t;
std::cin >> t;
while (t -- ) {
solve();
}
exit(0);
}
|
