BZOJ 4123 [Baltic2015] Hacker 解题报告

时间：2021-03-19 19:45:41

首先，Alice 会选择一个长度为 $\lfloor\frac{n+1}{2}\rfloor$ 的区间，我们把这个长度记为 $len$。

有这么一个结论：令 $F_i$ 为覆盖 $i$ 点的所有长度为 $len$ 的区间的元素和的最小值，那么答案就是 $F_i$ 的最大值。

因为 Bob 可以控制 Alice 最后选择的是什么区间。

【扯淡 ing】大概是这样子：

BZOJ 4123 [Baltic2015] Hacker 解题报告

假设 Alice 一开始选择的是红色的点 $i$，并且蓝色的线以左所覆盖的区间和就是 $F_i$，那么对于 Bob，他就可以选择绿色的点，然后 Alice 逆时针选的话，Bob 就顺时针选 $\dots$ 总之，Bob 的选择只要关于那个对称轴与 Alice 对称就可以了。

所以我们就可以用个单调队列什么的就可以做了。

时间空间复杂度均为 $O(n)$。

 #include <cstdio>

 #define N 500000 + 5

 #define INF 1000000007

 int n, A[N], Sum[N << ], q[N << ];

 inline int getint()

 {

     char ch = '\n';

     for (; ch != '-' && (ch > '' || ch < ''); ch = getchar()) ;

     int f = ch == '-' ? - : ;

     int res = ch == '-' ?  : ch - '';

     for (ch = getchar(); ch >= '' && ch <= ''; ch = getchar())

         res = (res << ) + (res << ) + ch - '';

     return res * f;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("4123.in", "r", stdin);

         freopen("4123.out", "w", stdout);

     #endif

     n = getint();

     for (int i = ; i <= n; i ++)

         A[i] = getint();

     for (int i = ; i <= (n << ); i ++)

         Sum[i] = Sum[i - ] + A[i > n ? i - n : i];

     int len = n +  >> , Max = -INF, head = , tail = ;

     for (int i = len; i < (len << ); i ++)

     {

         for (; head <= tail && Sum[i] - Sum[i - len] <= Sum[q[tail]] - Sum[q[tail] - len]; tail --) ;

         q[++ tail] = i;

     }

     for (int i = (len << ) - ; i <= n << ; i ++)

     {

         for (; head <= tail && q[head] + len <= i; head ++) ;

         for (; head <= tail && Sum[i] - Sum[i - len] <= Sum[q[tail]] - Sum[q[tail] - len]; tail --) ;

         q[++ tail] = i;

         int t = Sum[q[head]] - Sum[q[head] - len];

         Max = Max > t ? Max : t;

     }

     printf("%d\n", Max);

     #ifndef ONLINE_JUDGE

         fclose(stdin);

         fclose(stdout);

     #endif

     return ;

 }

4123_Gromah

相关文章