Almost Sorted

注意到 d≤5d\leq 5 ，考虑装态压缩。

由于 第 i 个数 只与[i−d,i+d][i-d,i+d] 有关，所以只用记录 2^11^ 个状态，剩下的一定不会改变。

すぬけ君の地下鉄旅行

考虑如何优化建图。

首先，对于颜色相同的连通块可以建立一个虚点，让 (i,col)(i,col),即 i 的 col 颜色 连向虚点，可以保证点数的数量级为 n+m。

建图时可能要 建立多个虚点，用并查集维护。

rep(k,1,1000000)
{
    vector<int> use; mp=CT;
    for(auto [i,j]:same[k])
    {
        fa[find(i)]=find(j);
        use.emplace_back(i),use.emplace_back(j);
    } sort(use.begin(),use.end()),use.erase(unique(use.begin(),use.end()),use.end());
    for(int i:use) if(i==find(i)) mp[i]=++idx;
    for(auto [i,j]:same[k])
    {
        g[mp[find(i)]].emplace_back((pair<int,int>){i,1});
        g[i].emplace_back((pair<int,int>){mp[find(i)],1});
        g[mp[find(j)]].emplace_back((pair<int,int>){j,1});
        g[j].emplace_back((pair<int,int>){mp[find(j)],1});
    }
    for(int i:use) fa[i]=i;
}

Finding a MEX

如果想到了分块，这题就做完了。

把 度数≥n度数\geq \sqrt n 的点用树状数组维护，剩下的直接遍历查找中位数。

时间复杂度为 qnlognq \sqrt n log_n，但可以过 (  5×108  )(\; 5 \times {10}^{8} \; )。

Binomial coefficients

首先有 C6030  =  118264581564861424≥1015C_{60}^{30} \; = \; 118264581564861424 \geq 10^{15}。

所以答案里的 minmin{ k,n-k } ≤30\leq 30。

枚举 k,n−kk,n-k , 此时的答案具有单调性。

二分即可。

Showstopper

这题是二分。

我们先把 偶数看作0，奇数看作1。

首先，我们要找的这个数并不能二分。因为它大概长这样：

                              ……010……\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \dots\dots 010 \dots \dots

但如果我们做一个前缀和，就变成了这样：

                          ……0000111111……\;\;\;\;\;\;\;\;\;\;\;\;\; \dots\dots 0000111111 \dots \dots

此时就具备了单调性。

二分 checkcheck 当前 ≤x\leq x 的数量奇偶性即可。

最后

提交地址：

https://vjudge.net.cn/contest/615804

密码：

lhf's-goot-problem