牛客国庆集训派对Day1 Solution
分类:
IT文章
•
2025-01-09 08:38:08
A Tobaku Mokushiroku Kaiji
水。
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int a[3], b[3];
5
6 void Run()
7 {
8 while (scanf("%d", a) != EOF)
9 {
10 for (int i = 1; i < 3; ++i) scanf("%d", a + i);
11 for (int i = 0; i < 3; ++i) scanf("%d", b + i);
12 printf("%d
", min(a[0], b[1]) + min(a[1], b[2]) + min(a[2], b[0]));
13 }
14 }
15
16 int main()
17 {
18 #ifdef LOCAL
19 freopen("Test.in", "r", stdin);
20 #endif
21
22 Run();
23 return 0;
24 }
View Code
B Attack on Titan
留坑。
C Utawarerumono
思路：好像暴力就能过。
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 using ll = long long;
4
5 ll a, b, c, p1, p2, q1, q2;
6
7 int main()
8 {
9 while (scanf("%lld%lld%lld", &a, &b, &c) != EOF)
10 {
11 scanf("%lld%lld", &p1, &p2);
12 scanf("%lld%lld", &q1, &q2);
13 ll res = 0x3f3f3f3f3f3f3f3f;
14 for (ll x = -100000; x <= 100000; ++x)
15 {
16 if ((c - a * x) % b) continue;
17 ll y = (c - a * x) / b;
18 res = min(res, p2 * x * x + p1 * x + q2 * y * y + q1 * y);
19 }
20 if (res == 0x3f3f3f3f3f3f3f3f)
21 {
22 puts("Kuon");
23 continue;
24 }
25 printf("%lld
", res);
26 }
27 return 0;
28 }
View Code
思路：将边按权值从小到大排序，一条一条往里加，每加入一条边要合并两个联通块，用并查集维护，然后开n棵trie树维护异或最大，简单路径上的异或和可以理解为两个点到根节点的前缀异或再异或，合并的时候启发式合并，查询的时候一定要经过那条边，那就是用一个联通块里的元素查找在另一个联通块对应的trie树里面查找，启发式查找
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 100010
5
6 struct Edge
7 {
8 int u, v, nx, w;
9 Edge() {}
10 Edge(int u, int v, int nx, int w) : u(u), v(v), nx(nx), w(w) {}
11 Edge(int u, int v, int w) : u(u), v(v), w(w) {}
12 bool operator < (const Edge &r) const
13 {
14 return w < r.w;
15 }
16 }edge[N << 1], G[N];
17
18 int n;
19 int head[N], pos;
20 int prefix[N], fa[N], sz[N];
21 vector <int> v[N];
22
23 void addedge(int u, int v, int w)
24 {
25 edge[++pos] = Edge(u, v, head[u], w); head[u] = pos;
26 }
27
28 void DFS(int u, int fa)
29 {
30 for (int it = head[u]; ~it; it = edge[it].nx)
31 {
32 int v = edge[it].v;
33 if (v == fa) continue;
34 prefix[v] = prefix[u] ^ edge[it].w;
35 DFS(v, u);
36 }
37 }
38
39 struct TRIE
40 {
41 int cnt;
42 int T[N];
43 struct node
44 {
45 int son[2];
46 node()
47 {
48 memset(son, 0, sizeof son);
49 }
50 }a[N * 400];
51
52 void Init()
53 {
54 cnt = n + 1;
55 }
56
57 void Insert(int root, int x)
58 {
59 bitset <20> b; b = x;
60 for (int i = 19; i >= 0; --i)
61 {
62 if (!a[root].son[b[i]])
63 a[root].son[b[i]] = ++cnt;
64 root = a[root].son[b[i]];
65 }
66 }
67
68 int query(int root, int x)
69 {
70 bitset <20> b; b = x;
71 int res = 0;
72 for (int i = 19; i >= 0; --i)
73 {
74 int id = b[i] ^ 1;
75 bool flag = true;
76 if (!a[root].son[id])
77 {
78 flag = false;
79 id ^= 1;
80 }
81 if (flag) res += 1 << i;
82 root = a[root].son[id];
83 }
84 return res;
85 }
86 }trie;
87
88 int find(int x)
89 {
90 if (x != fa[x])
91 fa[x] = find(fa[x]);
92 return fa[x];
93 }
94
95 void Init()
96 {
97 memset(head, -1, sizeof head); pos = 0;
98 prefix[1] = 0;
99 trie.Init();
100 }
101
102 void Run()
103 {
104 while (scanf("%d", &n) != EOF)
105 {
106 Init();
107 for (int i = 1, u, v, w; i < n; ++i)
108 {
109 scanf("%d%d%d", &u, &v, &w);
110 addedge(u, v, w);
111 addedge(v, u, w);
112 G[i] = Edge(u, v, w);
113 }
114 DFS(1, 1);
115 for (int i = 1; i <= n; ++i)
116 {
117 fa[i] = i;
118 sz[i] = 1;
119 trie.T[i] = i;
120 trie.Insert(trie.T[i], prefix[i]);
121 v[i].push_back(prefix[i]);
122 }
123 sort(G + 1, G + n);
124 for (int i = 1; i < n; ++i)
125 {
126 int x = G[i].u, y = G[i].v;
127 int fx = find(x), fy = find(y);
128 if (sz[fx] > sz[fy]) swap(x, y), swap(fx, fy);
129 int res = 0;
130 for (auto it : v[fx])
131 {
132 res = max(res, trie.query(trie.T[fy], it));
133 }
134 for (auto it : v[fx])
135 {
136 trie.Insert(trie.T[fy], it);
137 v[fy].push_back(it);
138 }
139 printf("%d%c", res, "
"[i == n - 1]);
140 fa[fx] = fy;
141 sz[fy] += sz[fx];
142 }
143 }
144 }
145
146 int main()
147 {
148 #ifdef LOCAL
149 freopen("Test.in", "r", stdin);
150 #endif
151
152 Run();
153 return 0;
154 }
