2020-2021:teams:alchemist:pku_campus_2019
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:pku_campus_2019 [2020/05/07 17:19] mountvoom [C.Parade] |
2020-2021:teams:alchemist:pku_campus_2019 [2020/05/08 10:54] (当前版本) maxdumbledore |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| ===== xsy ===== | ===== xsy ===== | ||
| - | F题让输出id输出了序号像个憨批。 | + | F题让输出id输出了序号，C题加绝对值给自己加晕了导致白给WA。 |
| + | |||
| + | C题最开始的时候考虑到了改$y$但是咋就没想到改$x$，弄了一个假的贪心乱WA。 | ||
| + | |||
| + | 像个憨批。 | ||
| ====== 题解 ====== | ====== 题解 ====== | ||
| ===== A.Ball ===== | ===== A.Ball ===== | ||
| + | 容易想到将给出的两个箱子当做一条边相连，于是形成了一个图。我们的目标是为每条边选择一侧点，并且点不会被重复选择。发现如果是一条$l$个点的链，那么就有$l$种选择，如果是一个基环树，那么就有$2$种选择，如果是其他形状，那么是不可能的，因为点数比边数还要少了，对应不起来。另外注意要额外判断单个点向自己连边的情况，这种虽然是环，但是种类是$1$。实现的时候善用并查集即可，维护点数和边数和是否含有单点环三个信息，没必要找环因为和环长无关。 | ||
| + | |||
| + | （并查集开始居然忘了路径压缩，打自己） | ||
| + | |||
| + | |||
| ===== B.Seal ===== | ===== B.Seal ===== | ||
| ===== C.Parade ===== | ===== C.Parade ===== | ||
| 行 94: | 行 103: | ||
| ===== G.Go and Oreo ===== | ===== G.Go and Oreo ===== | ||
| ===== H.Homomorphism ===== | ===== H.Homomorphism ===== | ||
| - | ===== I.Chamber of Braziers ===== | ||
| ===== J.Matrix of Determinants ===== | ===== J.Matrix of Determinants ===== | ||
| ===== K.Winner Winner, Chicken Dinner! ===== | ===== K.Winner Winner, Chicken Dinner! ===== | ||
| 行 101: | 行 109: | ||
| ====== 补题 ====== | ====== 补题 ====== | ||
| + | ===== I. Chamber of Braziers ===== | ||
| + | |||
| + | 很好的一道题，在比赛时居然死想没想出来TAT | ||
| + | |||
| + | 考虑最终答案$[l,r]$里面，必然有一个1和一个最大值$t=r-l+1$。我们分t在1左边和右边两种情况讨论，第一种是第二种的对称。如果$t$在1右边的话，那么可以先找到1，然后枚举右端点$r$，顺便求这一段最大值$mx$。那么对于这个r，可能的$l$就已经唯一确定了——$r-mx+1$。剩下的工作实际上就是判断[l,r]之间，是否满足排序之后为1 2 3 4 5... | ||
| + | |||
| + | 这个可以用对权值数组求字符串哈希来做。 | ||
| + | |||
| + | 但这里有个更方便有趣的方法，随机化+前缀异或。详见代码。如果我们需要比较的串的长度是一致，并且不考虑字符顺序的时候，可以使用这个技巧。 | ||
| + | |||
| + | <code cpp> | ||
| + | #include <bits/stdc++.h> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | const int maxn = 1000005; | ||
| + | |||
| + | int n, h[maxn], r[maxn], a[maxn], xo[maxn], ans; | ||
| + | char s[maxn]; | ||
| + | |||
| + | void solve() { | ||
| + | for (int i = 1; i <= n; i++) | ||
| + | if (a[i] == 1) { | ||
| + | int j, mx; | ||
| + | ans = max(ans, 1); | ||
| + | for (j = i + 1, mx = 1; j <= n && a[j] != 1; j++) { | ||
| + | mx = max(mx, a[j]); | ||
| + | if (j - mx >= 0 && (xo[j] ^ xo[j - mx]) == r[mx]) | ||
| + | ans = max(ans, mx); | ||
| + | } | ||
| + | i = j - 1; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | int Tt; | ||
| + | scanf("%d", &Tt); | ||
| + | srand(time(0)); | ||
| + | for (int i = 1; i < maxn; i++) | ||
| + | h[i] = RAND_MAX > maxn ? rand() : rand() * rand(), r[i] = r[i - 1] ^ h[i]; | ||
| + | while (Tt--) { | ||
| + | scanf("%d", &n); | ||
| + | for (int i = 1; i <= n; i++) { | ||
| + | scanf("%d", &a[i]); | ||
| + | xo[i] = xo[i - 1] ^ h[a[i]]; | ||
| + | } | ||
| + | ans = 0; | ||
| + | solve(); | ||
| + | reverse(a + 1, a + n + 1); | ||
| + | for (int i = 1; i <= n; i++) | ||
| + | xo[i] = xo[i - 1] ^ h[a[i]]; | ||
| + | solve(); | ||
| + | printf("%d\n", ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
2020-2021/teams/alchemist/pku_campus_2019.1588843184.txt.gz · 最后更改: 2020/05/07 17:19 由 mountvoom
