2020-2021:teams:alchemist:pku_campus_2019

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:alchemist:pku_campus_2019 [2020/05/08 10:17]
maxdumbledore [A.Ball]
+++ 2020-2021:teams:alchemist:pku_campus_2019 [2020/05/08 10:54] (当前版本)
maxdumbledore
@@ 行 103: / 行 103: @@
 ===== G.Go and Oreo =====
 ===== H.Homomorphism =====
-===== I.Chamber of Braziers =====
 ===== J.Matrix of Determinants =====
 ===== K.Winner Winner, Chicken Dinner! =====
@@ 行 110: / 行 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.1588904270.txt.gz · 最后更改: 2020/05/08 10:17 由 maxdumbledore