2022 HDU Multi-University Training Contest 8

1001. Theramore

给一个 \(01\) 序列,每次可以对称翻转一个奇数长度的区间,问任意次操作能得到的最小字典序序列。

核心点是翻转不会交换奇偶位上的数字,所以只用长度为 \(3\) 的操作,对奇偶分别排序即可。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 100007

char s[N];

int even[2], odd[2];

inline void work() {
odd[0] = odd[1] = even[0] = even[1] = 0;
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
if (i & 1) ++odd[s[i] - '0'];
else ++even[s[i] - '0'];
}
for (int i = 1; i <= n; ++i) {
if (i & 1) {
if (odd[0]) {putchar('0'); --odd[0];}
else putchar('1');
} else {
if (even[0]) {putchar('0'); --even[0];}
else putchar('1');
}
}
puts("");
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

1005. Ironforge

给一条链,每个点上有一个数字,每条边上有一个质数,多次询问是否能从 \(x\)\(y\)

每次经过一个点就可以得到这个点的全部质数,经过一条边必须要有边上的质数才能通过。

复杂度分析题,主要目的是利用相邻的点的信息,求出每个点出发的可达区间 \([l_i,r_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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 200007

bool vis[N];

int prm[N], mnd[N], tot;

int a[N], b[N], l[N], r[N], lst[N], L[N], R[N];

inline bool inseg(int x, int pos) {
return pos >= l[x] && pos <= r[x];
}

inline void work() {
int n = rd(), m = rd();
for (int i = 1; i <= n; ++i) l[i] = r[i] = i, a[i] = rd();
for (int i = 1; i < N; ++i) lst[i] = 0;
for (int i = 1; i < n; ++i) {
int w = a[i];
while(w > 1) {lst[mnd[w]] = i; w = w / prm[mnd[w]];}
b[i] = mnd[rd()]; L[i] = lst[b[i]];
}
for (int i = 1; i < N; ++i) lst[i] = n + 1;
for (int i = n - 1; i; --i) {
int w = a[i + 1];
while (w > 1) {lst[mnd[w]] = i + 1; w = w / prm[mnd[w]];}
R[i] = lst[b[i]];
}
for (int i = n - 1; i; --i)
while (r[i] < n && inseg(i, L[r[i]])) r[i] = r[r[i] + 1];
for (int i = 2; i <= n; ++i) {
if (!inseg(i, R[l[i] - 1])) continue;
if (r[i - 1] >= i) {l[i] = l[i - 1]; r[i] = r[i - 1]; continue;}
l[i] = l[i - 1];
bool fl = 1;
while (fl) {
fl = 0;
if (l[i] > 1 && inseg(i, R[l[i] - 1])) {
if (r[l[i] - 1] >= i) {
r[i] = r[l[i] - 1];
l[i] = l[l[i] - 1]; break;
}
l[i] = l[l[i] - 1];
fl = 1;
}
if (r[i] < n && inseg(i, L[r[i]])) {
r[i] = r[r[i] + 1]; fl = 1;
}
}
}
for (; m; --m) {
int x = rd(), y = rd();
puts(y >= l[x] && y <= r[x] ? "Yes" : "No");
}
}

int main() {
for (int i = 2; i < N; ++i) {
if (!vis[i]) {prm[tot] = i; mnd[i] = tot++;}
for (int j = 0, w; j < tot; ++j) {
if (1ll * i * prm[j] >= N) break;
mnd[w = i * prm[j]] = j;
vis[w] = 1;
if (j == mnd[i]) break;
}
}
for (int t = rd(); t; --t) work();
return 0;
}

1007. Darnassus

给一个排列,建完全图 \(i\)\(j\) 之间边权为 \(|i-j|\times |p_i-p_j|\) ,求最小生成树。

注意到如果相邻连边边权都不会超过 \(n\) ,所以只需要保留 \(n\) 以内的边。

因此乘积两部分都按根号枚举即可,用桶排序保存所有的边,总复杂度 \(\mathcal O(n\sqrt n\alpha(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 namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 50007

int f[N], p[N], q[N];

vector<pii> e[N];

inline int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}

inline int Abs(int x) {return x < 0 ? -x : x;}

inline void work() {
int n = rd();
for (int i = 1; i <= n; ++i) {
f[i] = i; p[i] = rd(); q[p[i]] = i;
e[i].clear();
}
int lim = sqrt(n) + 1;
for (int i = 1; i <= n; ++i) {
for (int j = max(1, i - lim), w; j < i; ++j) {
if ((w = (i - j) * Abs(p[j] - p[i])) > n) continue;
e[w].pb(mp(i, j));
}
for (int j, w, pj = max(1, p[i] - lim); pj < p[i]; ++pj) {
j = q[pj];
if (Abs(q[pj] - i) <= lim) continue;
if ((w = (p[i] - pj) * Abs(j - i)) > n) continue;
e[w].pb(mp(i, j));
}
}
ll ans = 0;
int cnt = n - 1;
for (int i = 1; i <= n; ++i) {
for (auto cur : e[i]) {
int u = cur.fr, v = cur.sc;
if (find(u) != find(v)) {
--cnt;
f[find(u)] = find(v);
ans += i;
}
if (!cnt) break;
}
if (!cnt) break;
}
printf("%lld\n", ans);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

1008. Orgrimmar

给一棵树,求最大解离集的大小(诱导子图里每个点度不超过 \(1\)

设状态 dp[u][0/1/2] 表示 \(u\) 节点:没选 / 选了,但儿子都没选 / 选了,并且选了一个儿子。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 500007

vector<int> e[N];

int f[N][3];

// f[u][0] : not choose u
// f[u][1] : choose u, not choose u's son
// f[u][2] : choose u, choose u's son

void dfs(int u, int fa) {
int dlt = 0;
f[u][0] = 0;
f[u][1] = 1;
f[u][2] = 1;
for (auto v : e[u])
if (v != fa) {
dfs(v, u);
f[u][0] += max({f[v][0], f[v][1], f[v][2]});
f[u][1] += f[v][0];
dlt = max(dlt, f[v][1] - f[v][0]);
}
f[u][2] = f[u][1] + dlt;
}

inline void work() {
int n = rd();
for (int i = 1; i <= n; ++i) e[i].clear();
for (int i = 1; i < n; ++i) {
int u = rd(), v = rd();
e[u].pb(v); e[v].pb(u);
}
dfs(1, 1);
printf("%d\n", max({f[1][0], f[1][1], f[1][2]}));
}

int main() {
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
for (int t = rd(); t; --t) work();
exit(0);
}

1010. Vale of Eternal

给一个点集,每秒每个点向上下左右距离 \(1\) 的位置复制一个点,问第 \(t\) 秒所有点的凸包面积大小。

柴老师推的式子,前 \(t\) 秒的增量为 \(2t^2+t\sum \max(|\Delta x|,|\Delta y|)\)

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define per(i, x, y) for (int i = (x); i >= (y); --i)

inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

typedef long long T;
#define let const auto
#define lett const T
#define letp const P // P for point
#define lets const S // S for segment
#define letl const L // L for line
#define letc const C // C for convex

#define z(x) (abs((x)) <= eps) // is zero

const T eps = 1e-8;
constexpr double PI=3.1415926535897932384;
struct P {
T x, y;
P (T x = 0, T y = 0) : x(x), y(y) {}
P operator + (letp &p) const {return {x + p.x, y + p.y};}
P operator - (letp &p) const {return {x - p.x, y - p.y};}
P operator * (lett &d) const {return {x * d, y * d};}
P operator / (lett &d) const {return {x / d, y / d};}
P operator - () const {return {-x, -y};}

T operator | (letp &p) const {return x * p.x + y * p.y;} // dot
T operator ^ (letp &p) const {return x * p.y - y * p.x;} // cross

// P rot(double ang) const { // counterclockwise rotation (ang) angle
// double cosa = cos(ang), sina = sin(ang);
// return {x * cosa - y * sina, x * sina + y * cosa};
// }

bool operator == (letp &p) const {return z(x - p.x) && z(y - p.y);}
bool operator != (letp &p) const {return ! operator == (p);}
bool operator < (letp &p) const {return z(x - p.x) ? y < p.y : x < p.x;}
bool operator > (letp &p) const {return !(*this < p || *this == p);}

// left(counterclockwise) = 1 | on = 0 | right(clockwise) = -1
int ori(letp &p) const {T t = (*this) ^ p; return (t > eps) - (t < -eps);}
T norm() const {return x * x + y * y;}

} zero;

double abs(letp &p) {return sqrt(p.norm());}
P normalize(letp &p) {return p / abs(p);}
P perp(letp &p) {return {-p.y, p.x};} // turn pi / 2 left
P perpr(letp &p) {return {p.y, -p.x};} // turn pi / 2 right

bool orth(letp &p, letp &q) {return (p | q) == 0;}
bool para(letp &p, letp &q) {return (p ^ q) == 0;}

struct Polygon {
vector<P> p; // counterclockwise
Polygon(const vector<P> p = {}) : p(p) {}
size_t nxt(const size_t i) const {return i == p.size() - 1 ? 0 : i + 1;}
size_t pre(const size_t i) const {return i == 0 ? p.size() - 1 : i - 1;}
T double_area() const {
T sum = 0;
for (size_t i = 0; i < p.size(); ++i) sum += (p[i] ^ p[nxt(i)]);
return sum;
}
};

struct C : Polygon {
C (const vector<P> &p = {}) : Polygon(p) {}
};

C convexHull(vector<P> p) {
vector<P> st;
sort(p.begin(), p.end());
const auto check = [](const vector<P> &st, letp &u) {
const auto back1 = st.back(), back2 = *prev(st.end(), 2);
return (back1 - back2).ori(u - back2) <= 0;
};
for (letp &u : p) {
while (st.size() > 1 && check(st, u)) st.pop_back();
st.push_back(u);
}
size_t k=st.size();
p.pop_back(); reverse(p.begin(),p.end());
for (letp &u : p) {
while (st.size() > k && check(st, u)) st.pop_back();
st.push_back(u);
}
st.pop_back();
return {st};
}

C c;

vector<P> p;

inline void work() {
p.clear();
int n = rd(), q = rd(); p.resize(n);
for (int i = 0; i < n; ++i) {p[i].x = rd(); p[i].y = rd();}
c = convexHull(p);
ll s = c.double_area();
ll dlt = 0;
for (size_t i = 0; i < c.p.size(); ++i) {
P cur = c.p[c.nxt(i)] - c.p[i];
dlt += max(abs(cur.x), abs(cur.y));
}
for (int i = 1; i <= q; ++i) {
ll t = rd();
ll ans = s + 4 * t * t + 2 * t * dlt;
printf("%lld", ans / 2);
puts((ans & 1) ? ".5" : ".0");
}
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!