B.
离线线段树分治维护按秩合并的并查集裸题。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 const int MAXN = 100000 + 10;
6 const int MAXV = 9;
7
8 typedef pair<int, int> pii;
9
10 struct Edge {
11 int u, v;
12 int w;
13 int st, ed;
14 Edge(int u=0, int v=0, int w=0, int st=0, int ed=0)
15 : u(u), v(v), w(w), st(st), ed(ed) {}
16 } e[MAXN];
17 int ec;
18
19 pii q[MAXN];
20 int qc;
21 map<pii, int> id;
22 int ans[MAXN];
23
24 int par[MAXN];
25 int sz[MAXN];
26 int st[MAXN], top;
27 int find(int x) { return x == par[x] ? x : find(par[x]); }
28 void merge(int u, int v) {
29 u = find(u), v = find(v);
30 if (u != v) {
31 if (sz[u] < sz[v])
32 swap(u, v);
33 par[v] = u;
34 sz[u] += sz[v];
35 st[++top] = v;
36 }
37 }
38 void del(int u) {
39 sz[par[u]] -= sz[u];
40 par[u] = u;
41 }
42
43 struct SegmentTree {
44 vector<int> edges[MAXN << 2];
45 bool solved[MAXN << 2];
46 void insert(int ql, int qr, int v, int l=1, int r=qc, int o=1) {
47 if (ql > qr)
48 return;
49 if (ql == l && qr == r) {
50 edges[o].push_back(v);
51 //cerr << ql << ' ' << qr << ' ' << v << ' ' << l << ' ' << r << endl;
52 return;
53 }
54 int mid = (l + r) >> 1;
55 if (qr <= mid)
56 insert(ql, qr, v, l, mid, o << 1);
57 else if (mid < ql)
58 insert(ql, qr, v, mid + 1, r, o << 1 | 1);
59 else {
60 insert(ql, mid, v, l, mid, o << 1);
61 insert(mid + 1, qr, v, mid + 1, r, o << 1 | 1);
62 }
63 }
64 void solve(int v, int l=1, int r=qc, int o=1) {
65 if (solved[o])
66 return;
67 int temp = top;
68 for (auto id : edges[o])
69 merge(e[id].u, e[id].v);
70 if (l == r) {
71 if (ans[l] == -1 && find(q[l].first) == find(q[r].second)) {
72 ans[l] = v;
73 solved[o] = true;
74 }
75 } else {
76 int mid = (l + r) >> 1;
77 solve(v, l, mid, o << 1);
78 solve(v, mid + 1, r, o << 1 | 1);
79 solved[o] = solved[o << 1] & solved[o << 1 | 1];
80 }
81
82 while (temp != top) {
83 del(st[top--]);
84 }
85 }
86
87 } segt;
88
89 int main() {
90 ios::sync_with_stdio(false);
91 int n, t;
92 cin >> n >> t;
93 for (int i = 1; i <= t; ++i) {
94 int opt, u, v;
95 int w;
96 cin >> opt;
97 cin >> u >> v;
98 if (u > v)
99 swap(u, v);
100 if (opt == 0) {
101 cin >> w;
102 e[++ec] = Edge(u, v, w, qc + 1, -1);
103 id[pii(u, v)] = ec;
104 } else if (opt == 1) {
105 e[id[pii(u, v)]].ed = qc;
106 } else if (opt == 2) {
107 q[++qc] = pii(u, v);
108 }
109 }
110 for (int i = 1; i <= ec; ++i) {
111 if (e[i].ed == -1)
112 e[i].ed = qc;
113 }
114
115 for (int i = 0; i < n; ++i) {
116 par[i] = i;
117 sz[i] = 1;
118 }
119
120 memset(ans, -1, sizeof(ans));
121 //cerr << "NMSL\n";
122 for (int danger = 0; danger <= MAXV; ++danger) {
123 for (int i = 1; i <= ec; ++i) {
124 if (e[i].w == danger) {
125 segt.insert(e[i].st, e[i].ed, i);
126 }
127 }
128 segt.solve(danger);
129 //cerr << "WDNMD\n";
130 }
131 for (int i = 1; i <= qc; ++i) {
132 cout << ans[i] << endl;
133 }
134 }
View Code
C.
签到题。注意记忆化搜索。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 const int MAXB = 40 + 10;
6 int n;
7 int64_t x;
8 char s[MAXB];
9 int ans = MAXB;
10 map<int64_t, int> mp;
11 void dfs(int64_t cur, int step) {
12 if (cur == (1ll << n) - 1) {
13 ans = min(ans, step);
14 return;
15 }
16 if (1 << step >= n) {
17 return;
18 }
19 if (step >= ans)
20 return;
21 if (mp[cur] && mp[cur] <= step) {
22 return;
23 }
24 mp[cur] = step;
25 for (int i = 1; i < n; ++i) {
26 int64_t now = cur | (cur >> i);
27 if (now != cur) {
28 dfs(now, step + 1);
29 }
30 }
31 }
32
33 int main() {
34 ios::sync_with_stdio(false);
35 cin >> s;
36 n = strlen(s);
37 for (int i = 0; s[i]; ++i) {
38 x = x * 2 + s[i] - '0';
39 }
40 if (s[0] == '0') {
41 cout << "-1\n";
42 return 0;
43 }
44 dfs(x, 0);
45 cout << ans << endl;
46 }
View Code