A. Zebras

如果 0 多是不用关心的，所以我们只需要用尽可能少的 0 带走尽可能多的 1，也就是构造的子序列最长。开两个 set 记录每个 0 的位置和每个 1 的位置，每次贪心选最前面的 0 然后轮流选 1/0，如果最前面是 1 或者选了一个 1 后面没有未被选的 0 了那么就无解。

B. A Leapfrog in the Array

虽然是简单题，但 vp 时想了很久也没想出来。。

考虑对于一个位置，逆推它的移动路径。对于一个奇数的位置，我们可以立刻得到它的值；对于一个偶数位置 p，设一个数从位置 q 移动到它，那么 p 前有 \frac{p}{2} 个有值的元素，所以 p 后包括 q 就有 n-\frac{p}{2} 个元素，即 q-p=n-\frac{p}{2}。移向得 q=\frac{p}{2}+n ，如此迭代直到 p 为奇数为止。

C. Data Center Maintenance

考虑建图，对于一组有序点对 (u,v)，若有一个客户被分配的两台机器分别是 u 和 v，且 (u+1)\mod h=v，则从点 u 到点 v 连一条有向边。现在的问题就是要求一个最小闭合子图。Tarjan 缩一下点，找到最小的出度为 0 的强连通分量即为答案。

D. Curfew

先二分答案。对于一个答案 k，有一个贪心的策略是将区间 [k+1,n-k] 的房间全部分配上不小于 b 的人数。那么考虑宿管检查房间 i 前有哪些房间的人可以跑到这个房间。若 i 房间被第一个宿管检查，那么这是一个前缀；否则这是一个后缀，这不难求出。那么我们可以建立一个二分图匹配模型，左部点代表 i 号房间的最终状态，右部点代表初始状态，那么左部点到右部点间应该存在一个完美匹配，这可以用 Hall 定理判断。可以证明，只需检查每个前缀和每个后缀即可。代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=110000;
typedef long long ll;
int n, d, b, a[MAXN];
ll s[MAXN];
bool check(int k)
{
    int l=k+1, r=n-k, mid=(n+1)/2;
    for (int i=l; i<=mid; i++)
        if (s[min(i+1ll*i*d, 1ll*n)]<1ll*(i-l+1)*b) return 0;
    for (int i=mid+1; i<=r; i++)
        if (s[n]-s[max(i-1ll*(n-i+1)*d, 1ll)-1]<1ll*(r-i+1)*b) return 0;
    return 1;
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    scanf("%d%d%d", &n, &d, &b);
    for (int i=1; i<=n; i++)
        scanf("%d", &a[i]), s[i]=s[i-1]+a[i];
    int l=0, r=(n+1)/2;
    while (l<r)
    {
        int mid=(l+r)/2;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d\n", l);
    return 0;
}