题解 - [Luogu P5042] [UOJ 100] [集训队互测 2015] 丢失的题面（ydc 的题面）

发表于 更新于 分类于 ， 本文字数： 821 阅读时长 ≈ 3 分钟

题目链接

原始题面

曾经，有一个题面摆在 ydc 的面前没有珍惜，直到失去时才后悔莫及，

如果上天再给他一次机会，ydc 一定会牢牢的记住这个题面

没办法，已经失去了，所以这道题只能让你帮 ydc 做了

已知的信息只有，这道题是传统题，采用全文比较的方式，时间限制 \(1\texttt{s}\), 空间限制 \(256\texttt{MB}\)

ydc 还给你提供了这道题的所有数据

数据下载: https://pan.baidu.com/s/1kT8Al0r 密码: cb5y

不方便用百度网盘的可以在这边下载 lost.zip

—— Tifa

该题在比赛时显示的成绩就是最终成绩

来源

中国国家集训队互测 2015 - By 于纪平

题意简述

看数据猜程序

解题思路

首先根据输入数据风格分为 4 类

  1. 1-3 组：输入 1 个数，让你构造一个序列
  2. 4-6 组：输入一个数组，输出一个和输入数组构造方式差不多的数组
  3. 7-9 组：输入一个图，还有若干次查询
  4. 第 10 组：送分的

首先说下第 10 组，直接输出输出文件那一堆就行

接下来是第 1 类

  1. 第 1 组：不难发现是 Thue-Morse 序列，OEIS: A010060
  2. 第 2 组：不难发现是用类似 Fibonacci 数列构造方式构造的
  3. 第 3 组：三进制版的 POJ 1780, 输出数据即为恰好包含全部 12 位三进制数的字典序最小的序列，做法为以 n-1 位三进制数为结点建图然后从 00000000000 出发找 Euler 回路，不难发现构造出来的序列长度正好为 \(3^{12}+12-1=531452\)

然后是第 2 类

  1. 第 4 组：不难发现是组合数的数列，关键在于求模数，观察第 4 行即可得到为 104857601, 后面两组数据均以此为模数
  2. 第 5 组：就是把第 4 组的输入输出反过来
  3. 第 6 组：按前两组构造方式猜测与组合数有关，这里猜测和二项式展开有关

或者这样 (注意到 \(104857601 = 25\times 2^{22}+1\))

  1. 第 4 组：给出一个多项式，对其平方
  2. 第 5 组：给出一个多项式，对其开方
  3. 第 6 组：给出一个多项式，对其开立方

但是写 NTT 显然没有写组合数简单，所以这个看看就好

最后是第 3 类

  1. 第 7 组：观察输出数据发现，输出只有 0 和 0x7f7f7f7f, 猜测是判断两点是否连通，故直接并查集即可
  2. 第 8 组：观察输出数据发现，输出均和边权差不多，而且输入的是树，这里猜测为输出两点路径中的最大边权，直接倍增一下即可
  3. 第 9 组：观察输出数据发现其特点综合了以上两种情况，猜测为求两点路径中边权最大值的最小值，用 Kruskal 找最小生成森林之后倍增即可 (就是把前两种情况都复制过来改改就行)

代码参考

Show code

Luogu_P5042view raw
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
namespace Subtask_1 {
void main() {
  vector<bool> vb;
  vb.reserve(1 << 22);
  vb.push_back(false);
  for (int i = 0; i < 22; ++i)
    for (auto it = vb.begin(); it != vb.begin() + (1 << i); ++it)
      vb.push_back(!*it);
  for (auto i : vb) cout << (i ? '1' : '0');
  cout << '\n';
}
}  // namespace Subtask_1
namespace Subtask_2 {
void main() {
  string a("0"), b("1"), c;
  for (int i = 1; i < 33; ++i) {
    c = a + b;
    a = b;
    b = c;
  }
  cout << a << '\n';
}
}  // namespace Subtask_2
namespace Subtask_3 {
const int n = 12;
const int m = 177147;
int node[m + 1];
stack<int> s;
void f(int v) {
  int w;
  while (node[v] < 3) {
    s.push(w = 3 * v + node[v]++);
    v = w % m;
  }
}
void main() {
  string ans;
  f(0);
  int w;
  while (!s.empty()) {
    w = s.top();
    s.pop();
    ans.push_back(w % 3 + '0');
    f(w / 3);
  }
  ans += string(n - 1, '0');
  reverse(ans.begin(), ans.end());
  cout << ans << '\n';
}
}  // namespace Subtask_3
namespace Subtask_4 {
const int p = 104857601, n = 131072, n2 = n * 2;
int inv[n2 + 1];
void main() {
  inv[1] = 1;
  for (int i = 2; i <= n2; ++i) inv[i] = (int64_t)(p - p / i) * inv[p % i] % p;
  vector<int> v;
  v.reserve(n + 1);
  v.push_back(1);
  for (int i = 1; i <= n; ++i)
    v.push_back(1ll * v.back() * (n2 - i + 1) % p * inv[i] % p);
  cout << n2 << '\n';
  for (auto i : v) cout << i << '\n';
  for (auto it = v.rbegin() + 1; it != v.rend(); ++it) cout << *it << '\n';
}
}  // namespace Subtask_4
namespace Subtask_5 {
const int p = 104857601, n = 131072, n2 = n * 2;
int inv[n2 + 1];
void main() {
  inv[1] = 1;
  for (int i = 2; i <= n2; ++i) inv[i] = (int64_t)(p - p / i) * inv[p % i] % p;
  vector<int> v;
  v.reserve(n + 1);
  v.push_back(1);
  for (int i = 1; i <= n; ++i)
    v.push_back(1ll * v.back() * (n - i + 1) % p * inv[i] % p);
  cout << n << '\n';
  for (int i = 0; i <= n; ++i) cout << (i % 2 ? p - v[i] : v[i]) << '\n';
}
}  // namespace Subtask_5
namespace Subtask_6 {
const int p = 104857601, a = 23333333, b = 33333333;
constexpr int64_t qpow(int64_t a, int64_t b) {
  int64_t res(1);
  for (; b; b >>= 1, (a *= a) %= p)
    if (b & 1) (res *= a) %= p;
  return res;
}
const int inv_a = qpow(a, p - 2);
const int n = 177147;
int inv[n + 1];
void main() {
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) inv[i] = (int64_t)(p - p / i) * inv[p % i] % p;
  int64_t res = qpow(a, n);
  cout << n << '\n' << res << '\n';
  for (int i = 1; i <= n; ++i)
    cout << (res = res * inv_a % p * b % p * (n - i + 1) % p * inv[i] % p)
         << '\n';
}
}  // namespace Subtask_6
namespace Subtask_7 {
const int n = 100000, m = 100000, q = 200000;
int dsu[n + 1];
int find(int x) { return x == dsu[x] ? dsu[x] : dsu[x] = find(dsu[x]); }
void merge(int x, int y) { dsu[find(x)] = find(y); }
void main() {
  for (int i = 1; i <= n; ++i) dsu[i] = i;
  for (int i = 0, x, y; i < m; ++i) {
    cin >> x >> y;
    merge(x, y);
  }
  for (int i = 0, x, y; i < q; ++i) {
    cin >> x >> y;
    cout << (find(x) == find(y) ? "0\n" : "2139062143\n");
  }
}
}  // namespace Subtask_7
namespace Subtask_8 {
const int n = 100000, m = 99999, q = 200000;
const int lbn = log2(n);
struct Edge {
  int w, to, next;
  Edge(int _w = 0, int _to = 0, int _next = 0): w(_w), to(_to), next(_next) {}
} e[2 * m + 1];
int head[n + 1], cnt_edge;
void addEdge(int x, int y, int w = 1) {
  e[++cnt_edge] = Edge(w, y, head[x]);
  head[x] = cnt_edge;
}
#define _for_graph(head, e, i, now) \
  for (int i = head[now], to = e[i].to; i; to = e[i = e[i].next].to)
int acstr[n + 1][lbn + 1], max_w[n + 1][lbn + 1], dep[n + 1];
void multiply(int now, int fa) {
  dep[now] = dep[acstr[now][0] = fa] + 1;
  for (int i = 0; i < lbn; ++i) {
    acstr[now][i + 1] = acstr[acstr[now][i]][i];
    max_w[now][i + 1] = max(max_w[now][i], max_w[acstr[now][i]][i]);
  }
  _for_graph(head, e, i, now) {
    if (to == fa) continue;
    max_w[to][0] = e[i].w;
    multiply(to, now);
  }
}
int get_res(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  int ans = 0;
  for (int i = lbn; ~i; --i)
    if (dep[acstr[x][i]] >= dep[y]) {
      ans = max(ans, max_w[x][i]);
      x = acstr[x][i];
    }
  if (x == y) return ans;
  for (int i = lbn; ~i; --i)
    if (acstr[x][i] != acstr[y][i]) {
      ans = max(ans, max(max_w[x][i], max_w[y][i]));
      x = acstr[x][i];
      y = acstr[y][i];
    }
  return max(ans, max(max_w[x][0], max_w[y][0]));
}
void main() {
  for (int i = 0, x, y, w; i < m; ++i) {
    cin >> x >> y >> w;
    addEdge(x, y, w);
    addEdge(y, x, w);
  }
  multiply(1, 0);
  for (int i = 0, x, y; i < q; ++i) {
    cin >> x >> y;
    cout << get_res(x, y) << '\n';
  }
}
#undef _for_graph
}  // namespace Subtask_8
namespace Subtask_9 {
const int n = 50000, m = 100000, q = 200000;
const int lbn = log2(n);
struct Edge {
  int w, to, next;
  Edge(int _w = 0, int _to = 0, int _next = 0): w(_w), to(_to), next(_next) {}
} e[2 * m + 1];
int head[n + 1], cnt_edge;
void addEdge(int x, int y, int w = 1) {
  e[++cnt_edge] = Edge(w, y, head[x]);
  head[x] = cnt_edge;
}
#define _for_graph(head, e, i, now) \
  for (int i = head[now], to = e[i].to; i; to = e[i = e[i].next].to)
int dsu[n + 1];
int find(int x) { return x == dsu[x] ? dsu[x] : dsu[x] = find(dsu[x]); }
void merge(int x, int y) { dsu[find(x)] = find(y); }
int acstr[n + 1][lbn + 1], max_w[n + 1][lbn + 1], dep[n + 1];
void multiply(int now, int fa) {
  dep[now] = dep[acstr[now][0] = fa] + 1;
  for (int i = 0; i < lbn; ++i) {
    acstr[now][i + 1] = acstr[acstr[now][i]][i];
    max_w[now][i + 1] = max(max_w[now][i], max_w[acstr[now][i]][i]);
  }
  _for_graph(head, e, i, now) {
    if (to == fa) continue;
    max_w[to][0] = e[i].w;
    multiply(to, now);
  }
}
int get_res(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  int ans = 0;
  for (int i = lbn; ~i; --i)
    if (dep[acstr[x][i]] >= dep[y]) {
      ans = max(ans, max_w[x][i]);
      x = acstr[x][i];
    }
  if (x == y) return ans;
  for (int i = lbn; ~i; --i)
    if (acstr[x][i] != acstr[y][i]) {
      ans = max(ans, max(max_w[x][i], max_w[y][i]));
      x = acstr[x][i];
      y = acstr[y][i];
    }
  return max(ans, max(max_w[x][0], max_w[y][0]));
}
struct Node {
  int x, y, w;
  bool operator<(const Node &rhs) const { return w < rhs.w; }
} data[m];
void main() {
  for (int i = 1; i <= n; ++i) dsu[i] = i;
  for (int i = 0; i < m; ++i) cin >> data[i].x >> data[i].y >> data[i].w;
  sort(data, data + m);
  for (int i = 0; i < m; ++i)
    if (find(data[i].x) != find(data[i].y)) {
      merge(data[i].x, data[i].y);
      addEdge(data[i].x, data[i].y, data[i].w);
      addEdge(data[i].y, data[i].x, data[i].w);
    }
  for (int i = 1; i <= n; ++i)
    if (!dep[i]) multiply(i, 0);
  for (int i = 0, x, y; i < q; ++i) {
    cin >> x >> y;
    if (find(x) != find(y)) {
      cout << "2139062143\n";
      continue;
    }
    cout << get_res(x, y) << '\n';
  }
}
#undef _for_graph
}  // namespace Subtask_9
namespace Subtask_10 {
void main() {
  cout << "Your program should output itself here.\n"
          "Sounds very difficult, yeah?\n"
          "Anyway, good luck!\n";
}
}  // namespace Subtask_10
#define _run_return(expressions) return (expressions), 0
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  string _;
  getline(cin, _);
  if (_.front() == 'M') _run_return(Subtask_10::main());
  if (_ == "22") _run_return(Subtask_1::main());
  if (_ == "33") _run_return(Subtask_2::main());
  if (_ == "12") _run_return(Subtask_3::main());
  if (_ == "131072") _run_return(Subtask_4::main());
  if (_ == "262144") _run_return(Subtask_5::main());
  if (_ == "531441") _run_return(Subtask_6::main());
  if (_ == "100000 100000 200000") _run_return(Subtask_7::main());
  if (_ == "100000 99999 200000") _run_return(Subtask_8::main());
  if (_ == "50000 100000 200000") _run_return(Subtask_9::main());
  return 1;
}