POI 2010 题解汇总

OI 题解汇总

---

---

【bzoj2079】Guilds - DFS

题意

给定一张图。
给每个点进行染色：染成黑色，或染成白色。
问能否有一种方案，使得任意一个点，满足存在一个相邻的点与它不同色。

$1\leq n\leq 200000$
$1\leq m\leq 500000$

分析

我们把原图拆分成若干个连通图，原图有解，当且仅当每个连通图有解。
对于一个连通图，设它的节点数为$n$。
①当$n=1$时，必定无解；
②当$n>1$时，有种很棒的想法：由于每个连通图可以对应若干个分层，设每个点在$dist[i]$层，则有

$$dist[u]=\max(dist[pre])+1$$
我们随便选择一个点$s$，$dist[s]=0$，然后求出分层图。
对于$dist[i]$为奇数的，染成黑色。
对于$dist[i]$为偶数的，染成白色。
根据分层图的定义，所以上述染色方案一定是一组解。

代码

#include <cstdio>
#include <cctype>
#define F(i,a,b) for (int i=(a);i<=(b);i++)
int rd(void);
const int N=262144;
int n,m;
int f[N],s[N];
int Find(int x) {
    if (f[x]==x) return x;
    return f[x]=Find(f[x]);
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd(),m=rd();
    F(i,1,n) {
        f[i]=i;
        s[i]=1;
    }
    F(i,1,m) {
        int x=rd(),y=rd();
        int fx=Find(x);
        int fy=Find(y);
        if (fx!=fy) {
            f[fx]=fy;
            s[fy]+=s[fx];
        }
    }
    F(i,1,n)
        if (Find(i)==i&&s[i]==1) {
            printf("NIE\n");
            return 0;
        }
    printf("TAK\n");
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2080】Railways - 数形结合+构建最小生成森林

题意

给定一个序列$A$，问$A$是否有双栈排序的方法。
若无，则输出NIE。
若有，则输出字典序最小的序列。

分析

VFK的题解写的很详细：https://pan.baidu.com/share/link?shareid=360807&uk=235772034
业界良心！

学了两个波兰语。
NIE是NO的意思。。
TAK是YES的意思。。

我们通过观察，可以得到这样一个结论：
任何时候，两个栈中的元素都是单调递减的。
证明很简单，假如元素单调递增了，由于先要弹出上面的，再弹出下面的，所以就一定不能从小到大了。

发现想象能力非常重要呢。
就是自己闭上眼睛，在脑海里画图的能力。
嗯，我确乎地看到了一幅清晰的图像。

我们可以把这个双栈排序操作看成$n$次操作，每次插入一个元素$a_i$，然后把两个栈中的一些元素弹出。

考虑$a_i$最早可能在哪里弹出。
我们粗略地估计：至少要把所有比$a_i$小的元素弹出后，它才能弹出。
所以设$L_i$表示不比$a_i$大的数的最大的坐标，即：

$$L_i=\max_{i\leq j且a_i\geq a_j}j$$
那么$a_i$最早也只可能在$L_i$步，把$a_i$插入并弹出后，弹出。

那么，假如有解，$a_i$是否一定能在$L_i$步弹出呢？
这是肯定的，VFK的证明我并没有看懂，但是自己YY出来了。
先说一下证明的大致思路：假设有一个方案$A$，但是不满足$a_i$在$L_i$步弹出。我们利用方案$A$的可行性，构造出满足条件的方案$A^*$。
其中，$A^*$的每个元素的压入并弹出的栈与$A$相同，只是弹出的时间不同。
我既然可以早一点弹出，那为什么不早一点弹出呢？
所以，我们得到结论：序列$A$有双栈排序方案，当且仅当序列$A$的第$i$个元素在第$L_i$步弹出。

我们考虑两个元素$i,j$，$i<j\leq L_i$，则$i$一定不能在$L_i$步前弹出，若$a_i<a_j$，则一定不能把$i,j$压入同一个栈。
我们把$(i,j)$进行连边。

现在的问题变成：对于一张图，我们对点进行2染色，问是否有一种方案，使得任一相邻两个点的颜色不一样。
即是否能把原图变成二分图。

波兰人在这里还扯了一下。
k栈排序问题相当于问k染色有没有解。

暴力的做法是直接DFS。
但是注意到边数$E=O(n^2)$，直接做会TLE。
所以考虑优化。

我们考虑构建一个原图的生成森林，对生成森林进行2染色。
那么，考虑生成森林与原图的关系，很简单：若生成森林的2染色方案用在原图无解，则原图一定无解。
总之，我们得到了这样一个流程：
【STEP 1】构建生成森林
【STEP 2】把生成森林进行2染色
【STEP 3】判定染色方案在原图有没有解

对于【STEP 2】，直接进行DFS实现，$O(n)$。

void Modified_DFS(int u) {
    col[u]=tot;
    erase(u);
    while (1) {
        get nx = find_edge(u)
        if (nx==NULL)
            break;
        else Modified_DFS(v);
    }
}

对于【STEP 3】，直接模拟双栈排序进行判定，$O(n)$。

关键的问题是【STEP 1】。

【STEP 1】
边分为两种类型，一种是后向边，一种是前向边。什么意思？
对于一条边$(u,v)$，我们在访问$u$的时候要找到$v$，在访问$v$的时候要找到$u$。
后向边：以坐标为基底，维护一棵线段树。对于点$u$，找$[u,L_u]$内的$a$值最小的点及其坐标。erase的时候就删除线段树的单点。
前向边：$[u,L_u]$这个区间，对应线段树的某些点。我们把线段树的每个点建一个链表，表示这个区间可以取到的$u$。我们把线段树的这些点的链表，都加上点$u$。
我们查找一个点的时候，找从线段树的根到这个点的每个链表。为了节省时间复杂度，我们只找a值最大的那个点，所以在插入的时候按照从大到小的顺序插入。
删除一个点的时候，我们只需要处理出这个点对应那些链上的节点即可。

还差一个问题。
怎么保证字典序最小？
字典序最小要在有解的前提下。
所以我们每次尽量从编号小的点开始染色就好了。

---

【bzoj2081】Beads - 调和级数+Hash

题意

给定一个长度为$n$的序列$A$。
求$k$，最大化$ans$，其中$ans$为：把序列连续的$k$个切成一段，所有段中段的不同个数。
$1\leq n\leq 200000$

分析

这么简单的题竟然没想到QAQ。

首先连续的$k$个切成一段。
枚举$k$，这是个经典的调和级数的复杂度啦。

对于一个$k$，如何求不同的段的个数？
直接考虑字符串Hash的方法。
把所有的字符Hash值用一个Hash存起来。

关于Hash的实现，我获得了一个新的姿势：用vector<LL>写Hash。
这样写会简单很多。
但是不好调试+速度超慢是不是。。

代码

#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define LL unsigned long long
int rd(void);
const int N=262144;
const int L=1000009;
int n;
int a[N];
int m;
LL pwr[N];
LL h[N],rh[N];
int mx;
int len,lis[N];
int tot;
vector<LL> mp[L];
LL Get(int l,int r) {
    return h[r]-h[l-1]*pwr[r-l+1];
}
LL GetR(int l,int r) {
    return rh[l]-rh[r+1]*pwr[r-l+1];
}
int Find(LL w) {
    int key=w%L;
    for (vector<LL>::iterator it=mp[key].begin();it!=mp[key].end();it++)
        if (*it==w)
            return 1;
    return 0;
}
void Ins(LL w) {
    int key=w%L;
    mp[key].push_back(w);
}
void Erase(LL w) {
    int key=w%L;
    mp[key].clear();
}
void Update(int k) {
    int siz=0;
    for (int i=0;i+k<=n;i+=k) {
        int l=i+1;
        int r=i+k;
        LL w=Get(l,r);
        LL rw=GetR(l,r);
        int tag=Find(w);
        int tagR=Find(rw);
        if (!tag&&!tagR)
            siz++;
        if (!tag)
            Ins(w);
        if (!tagR)
            Ins(rw);
    }
    for (int i=0;i+k<=n;i+=k) {
        int l=i+1;
        int r=i+k;
        LL w=Get(l,r);
        LL rw=GetR(l,r);
        Erase(w);
        Erase(rw);
    }
    if (siz>=mx) {
        if (siz>mx) {
            mx=siz;
            F(i,1,len)
                lis[i]=0;
            len=0;
        }
        lis[++len]=k;
    }
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd();
    F(i,1,n)
        a[i]=rd();
    m=n+1;
    pwr[0]=1;
    F(i,1,n)
        pwr[i]=pwr[i-1]*m;
    F(i,1,n)
        h[i]=h[i-1]*m+a[i];
    D(i,n,1)
        rh[i]=rh[i+1]*m+a[i];
    F(k,1,n)
        Update(k);
    printf("%d %d\n",mx,len);
    F(i,1,len) {
        printf("%d",lis[i]);
        if (i<len)
            printf(" ");
        else printf("\n");
    }
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2082】Divine Divisor - 数论

链接

http://blog.csdn.net/Kanosword/article/details/52717273

---

【bzoj2083】Intelligence test - vector+二分 or 离线+链表

题意

给定长度为$n$的最初的序列$A$。
$m$个询问，给定长度为$nk$的序列$B$，问$B$是否是由$A$删去某些字符得到的。
$1\leq n,m,a_i\leq 1000000$

分析1：vector+二分

我们考虑逐个判定$B$能否由$A$得到。
那么，考虑一位位判定，看能否在$A$找到，肯定尽量往前找。
考虑把每种数值列一条链表，每次在链表上二分合适的位置。

代码1：vector+二分

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
int rd(void);
const int N=1048576;
int m;
int a[N];
vector<int> list_A[N];
int n;
int nk,b[N];
int Run(void) {
    int pre=0;
    F(i,1,nk) {
        int kd=b[i];
        vector<int>::iterator it=upper_bound(list_A[kd].begin(),list_A[kd].end(),pre);
        if (it==list_A[kd].end())
            return 0;
        pre=*it;
    }
    return 1;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    m=rd();
    F(i,1,m)
        a[i]=rd();
    F(i,1,m)
        list_A[a[i]].push_back(i);
    n=rd();
    F(c,1,n) {
        nk=rd();
        F(i,1,nk)
            b[i]=rd();
        int tag=Run();
        if (tag)
            printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

分析2：离线+链表

网上基本上没有人用这种做法。
除了popoqqq的题解和少量题解。
理论上这种做法更优秀啊。。

注意这道题是多组询问。
可以离线处理，利用遍历时的连续性来加快求解。

把要查找的串的每个链头给分类。
遍历原串，每次一个类的链头全都往后移一步。

复杂度与读入同阶。
然而跑得更慢QAQ。

代码2：离线+链表

#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
int rd(void);
const int N=1048576;
int m;
int a[N];
int n;
int nk[N];
vector<int> g[N];
vector<int>::iterator git[N];
vector<int> top_chr[N];
vector<int> tmp;
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    m=rd();
    F(i,1,m)
        a[i]=rd();
    n=rd();
    F(c,1,n) {
        nk[c]=rd();
        g[c].resize(nk[c]+1);
        F(i,1,nk[c])
            g[c][i]=rd();
        git[c]=g[c].begin();
        git[c]++;
        top_chr[*git[c]].push_back(c);
    }
    F(i,1,m) {
        int kd=a[i];
        for (vector<int>::iterator it=top_chr[kd].begin();it!=top_chr[kd].end();it++)
            tmp.push_back(*it);
        top_chr[kd].clear();
        for (vector<int>::iterator it=tmp.begin();it!=tmp.end();it++) {
            int id=*it;
            git[id]++;
            if (git[id]!=g[id].end())
                top_chr[*git[id]].push_back(id);
        }
        tmp.clear();
    }
    F(c,1,n)
        if (git[c]==g[c].end())
            printf("TAK\n");
        else printf("NIE\n");
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2084】Antisymmetry - Manacher or 二分+Hash

题意

对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。
现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。
$n\leq 500000$

分析

据观察，发现一个结论：具有反对称性的字符串，它的长度一定是偶数的。
证明：反设它的长度为奇数，那么对于中点$c$，在反对称后终点为$rev(c)$，$c\neq rev(c)$，所以不相等，矛盾。

那么，如何刻画一个串是不是反对称串？
或者说，如何$O(n)$内判定一个反对称串？

首先，它的长度要是偶数。
其次，对于每个位置，它的对应位置的数字与其不同，一个是0，一个是1。
这两个位置的坐标加起来为奇数，一个0，一个1。
？？？

我们考虑把坐标为奇数的位置亦或1。
这样，问题就变为：求长度为偶数的回文串的个数

回文串有一个重要的指标，就是它的中点。
我们枚举不在点上的回文串的中点（因为长度为偶数），进行累加答案。
每次求以该点为中点的最长回文串的长度即可。

以每个点为中点的最长回文串，有几种求法：
①二分+Hash
②Manacher
③回文自动机

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LL long long
int rd(void);
const int N=1048576;
int n;
char s[N];
int len;
char t[N];
int ex[N];
LL ans;
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd();
    scanf("%s",s+1);
    F(i,1,n)
        if (i&1) {
            if (s[i]=='0')
                s[i]='1';
            else s[i]='0';
        }
    len=n+n+2;
    t[0]='<';
    t[1]='+';
    t[len]='>';
    F(i,1,n) {
        t[i<<1]=s[i];
        t[i<<1|1]='+';
    }
    int mxp=0;
    F(i,1,len) {
        int j=(!mxp?0:min(mxp+ex[mxp]-i,ex[mxp+mxp-i]));
        while (t[i+j]==t[i-j])
            j++;
        ex[i]=j;
        if (i+ex[i]-1>mxp+ex[mxp]-1)
            mxp=i;
    }
    F(i,1,len)
        if (t[i]=='+')
            ans+=(ex[i]>>1);
    printf("%lld\n",ans);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2085】Hamsters - KMP+倍增Floyd

题意

给定$n$个长度总和不超过$10W$的字符串。
求一个最短的母串，使$所有字符串的出现次数之和=m$。 这n个字符串保证不互相包含。
$1\leq n\leq 200,1\leq m\leq 10^9$

分析

我们求出一个字符串$s_i$后面接上另一个字符串$s_j$需要增加的长度$f[i][j]$。
直接通过KMP，在$O(n^2L)$的暴力下求解。

然后相当于这样一个模型：
给定一个有向图，从任意点出发走$m$条边的路径长度的最小值。
倍增Floyd求解。

在实现上，首先是关于$n$个长度总和为$O(L)$的字符串的存储方式及使用方式。
我的方法是存到一个大的字符串里，两个不同的字符串用+号分割开。如果要访问某个位置，我们设$\Delta_i=start[i]-1$，那么访问第$i$个位置就为$\Delta_i+i$。

然后就是关于倍增Floyd。
其实自己YY出来就好了。
一般$m\leq 10^9$或者$m\leq 10^{18}$的问题都是通过倍增来实现的。

还有就是关于快速幂的非递归实现方法。

void pwr(Data &ans,Data &bas,int m) {
    while (m>0) {
        if (m%2==1)
            ans=ans+bas;
        bas=bas+bas;
        m>>=1;
    }
}

注意写void比较好，否则返回值比较大就GG了。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LL long long
int rd(void);
const int N=256;
const int L=131072;
const int U=32;
const LL MAX=(LL)1e16;
int n,m;
char s[L];
int star[N],fin[N],len[N];
int nx[L];
int unit;
struct Data {
    LL go[N][N];
    Data(void) {
        memset(go,0,sizeof go);
    }
    friend Data operator + (Data a,Data b) {
        Data c;
        F(i,1,n) F(j,1,n) {
            c.go[i][j]=MAX;
            F(k,1,n)
                c.go[i][j]=min(c.go[i][j],a.go[i][k]+b.go[k][j]);
        }
        return c;
    }
    LL Min_path(void) {
        LL ans=MAX;
        F(i,1,n)
            F(j,1,n)
                ans=min(ans,go[i][j]);
        return ans;
    }
}bas,ans;
int Match(int c,int d) {
    int j=0;
    int dc=star[c]-1;
    int dd=star[d]-1;
    F(i,1,len[c]) {
        while (j>0&&s[dc+i]!=s[dd+(j+1)])
            j=nx[dd+j];
        if (s[dc+i]==s[dd+(j+1)])
            j++;
    }
    int ret=len[d]-j;
    return ret;
}
void pwr(Data &ans,Data &bas,int m) {
    while (m>0) {
        if (m%2==1)
            ans=ans+bas;
        bas=bas+bas;
        m>>=1;
    }
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd(),m=rd();
    F(i,1,n) {
        s[fin[i-1]+1]='+';
        star[i]=fin[i-1]+2;
        scanf("%s",s+star[i]);
        len[i]=strlen(s+star[i]);
        fin[i]=star[i]+len[i]-1;
    }
    s[fin[n]+1]='+';
    F(c,1,n) {
        int dc=star[c]-1;
        nx[dc+1]=0;
        int j=0;
        F(i,2,len[c]) {
            while (j>0&&s[dc+i]!=s[dc+(j+1)])
                j=nx[dc+j];
            if (s[dc+i]==s[dc+(j+1)])
                j++;
            nx[dc+i]=j;
        }
    }
    F(i,1,n) F(j,1,n)
        if (i==j)
            ans.go[i][j]=len[i];
        else ans.go[i][j]=MAX;
    m--;
    F(i,1,n) F(j,1,n)
        if (i==j)
            bas.go[i][j]=len[i]-nx[star[i]+len[i]-1];
        else bas.go[i][j]=Match(i,j);
    pwr(ans,bas,m);
    LL ret=ans.Min_path();
    printf("%lld\n",ret);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2086】Block - 单调栈

题意

给出$N$个正整数$a[1..N]$，再给出一个正整数$k$，现在可以进行如下操作：每次选择一个大于$k$的正整数$a[i]$，将$a[i]$减去$1$，选择$a[i-1]$或$a[i+1]$中的一个加上$1$。经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于$k$。
总共给出$M$次询问，每次询问给出的$k$不同，你需要分别回答。
$1\leq N\leq 1000000,1\leq M\leq 50,k\leq 10^9$

分析

先来一个不相关的问题：如果可以随便算数，任意次数，求最大值。
注意要流量是守恒的，所以总流量是$sum$，最长的就是${sum\over k}$。

现在要求大于$k$的才能流动。
那么，问题变成了：求最长的区间，满足平均数大于等于$k$。

我们把每个位置减去$k$，得到$a'$，问题变为：求最长的区间，满足平均数大于0。即：求最长的区间，满足和大于0。

记$s_k=\sum_{i=1}^k a_i$
所以要求：

$$maxinum~~~ans=r-l+1\\s.t.~s_r-s_{l-1}\geq 0$$

即

$$maxinum~~~ans=r-l\\s.t.~s_r-s_l\geq 0\\~~~~~~~~~~~0\leq l\leq n-1\\~~~~1\leq r\leq n$$

我们考虑枚举右端点，看左端点要满足什么条件。
对于$i<j$，若$s_i\leq s_j$，则$i$比$j$优，$j$一定不需要作为左端点。
所以从$1$到$n$进行加点，我们假如把每个点抽象成二维平面上的点$(i,s_i)$，我们得到了递减的一段折线。
这个用栈记录一下即可。

从$n$到$1$枚举右端点。
考虑过右端点做一条水平的线，取下面的最左的点更新答案。
最左的点的右边的点一定不能取了，因为已经可以取到（最左的点，右端点），若再往中间取没有任何意义。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define LL long long
int rd(void);
const int N=1048576;
int n,m;
int a[N];
int nk;
LL s[N];
int stk[N],top;
void Solve(int nk,char out) {
    F(i,1,n)
        s[i]=a[i]-nk;
    F(i,1,n)
        s[i]+=s[i-1];
    while (top>0)
        stk[top--]=0;
    F(i,0,n-1)
        if (!top||s[stk[top]]>s[i])
            stk[++top]=i;
    int ans=0;
    D(i,n,1) {
        while (top>0&&stk[top]>=i)
            stk[top--]=0;
        if (top>0&&s[i]>=s[stk[top]]) {
            while (top-1>0&&s[i]>=s[stk[top-1]])
                stk[top--]=0;
            ans=max(ans,i-stk[top]);
        }
    }
    printf("%d%c",ans,out);
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd(),m=rd();
    F(i,1,n)
        a[i]=rd();
    F(i,1,m) {
        nk=rd();
        Solve(nk,(i==m)?'\n':' ');
    }
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2087】Sheep - 单调性+极角排序+区间DP

题意

给定$n$个点$(x_i,y_i)$，这些点组成一个凸包。
给定凸包内的$k$个点$(a_i,b_i)$，保证$k$为偶数。
把凸包切成若干个三角形，求满足三角形的边上没有点且三角形内都有偶数个点的划分方案数，答案模$m$。

$4\leq n\leq 600$
$2\leq m\leq 20000$

分析

安利一份题解：http://blog.csdn.net/zqh_wz/article/details/52734092

以凸包上的第一个点为基准点，对凸包的所有点进行极角排序。

设$f[l][r]$表示把第$l$个点到第$r$个点划分成三角形的方案数。
则有：

$$f[l][r]=\sum_{i=l+1}^{r-1}(g[l][i]*g[i][r])*f[l][i]*f[i][r]$$
其中，$g[i][j]$表示能否将$i$与$j$连接一条边。
DP的复杂度为$O(n^3)$

如何判定能否连边？
有两个要求：①边上没有点 ②两边都有偶数个

对于从一个点出发，考虑它连向其他的所有点。
可以通过two pointer在$O(nk\log k)$实现连边。
具体见代码。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
int rd(void);
const int N=1024;
const int K=32768;
int n,nk,m;
struct Point {
    int x,y;
    Point(int _x=0,int _y=0) {
        x=_x,y=_y;
    }
    friend Point operator - (Point a,Point b) {
        return Point(a.x-b.x,a.y-b.y);
    }
    void Read(void) {
        x=rd(),y=rd();
    }
}x[N],p[K],org;
int g[N][N];
int f[N][N];
int dot(Point a,Point b) {
    return a.x*b.y-a.y*b.x;
}
int cmp(Point a,Point b) {
    return dot(a-org,b-org)<0;
}
int DP(int l,int r) {
    int *res=&(f[l][r]);
    if (~*res)
        return *res;
    *res=0;
    F(i,l+1,r-1) 
        if (g[l][i]&&g[r][i]){
            int tL=DP(l,i);
            int tR=DP(i,r);
            (*res+=(tL*tR)%m)%=m;
        }
    return *res;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd(),nk=rd(),m=rd();
    F(i,1,n)
        x[i].Read();
    F(i,1,nk)
        p[i].Read();
    org=x[1];
    sort(x+2,x+n+1,cmp);
    F(i,1,n) {
        org=x[i];
        sort(p+1,p+nk+1,cmp);
        int cnt=0;
        F(j,i+1,n) {
            while (cnt+1<=nk&&cmp(p[cnt+1],x[j]))
                cnt++;
            if (!(cnt&1)&&(cnt==nk||dot(p[cnt+1]-org,x[j]-org)>0))
                g[i][j]=g[j][i]=1;
        }
    }
    memset(f,-1,sizeof f);
    F(i,1,n-1)
        f[i][i+1]=1;
    int ans=DP(1,n);
    printf("%d\n",ans);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2088】Teleportation - 分层图+构造

题意

给定一张图。
求给原图加最多的边，使得从起点$1$到终点$2$的最小步数不小于6。
$2\leq n\leq 40000$

分析

首先数据是合法的。

我们考虑最终的图长什么样。
总边数-减去最初的边数即可。

注意到最小的步数是个很小的常数，肯定有一些奇技淫巧。
最小步数想到了什么。。。
SAM？
分层图！
我们从$1$开始，对图进行分层，那么层数为6。

起点在第1层。
与起点相邻的在第2层。
与起点相邻的点相邻的在第3层。
终点在第6层。
与终点相邻的在第5层。
与终点相邻的点相邻的在第4层。
还剩下一些点，我们需要考虑它怎么分配。

怎么分配要看怎么计算答案。
很明显，相同一层的可以相互连边，相邻两个不同层也可以两两连边。

设第一层的个数为a，第二层的个数为b...
以此类推，为 a b c d e f 个。
现在考虑增加$x$个。

我们可以通过数值计算比较出两种方案的优劣。
由于是数值，数值具有传递性，所以方案的比较具有传递性。
我们考虑每增加一个，应该增加到哪里就行了。算增加一个的贡献。

增加到$a$：$a+b$
增加到$b$：$a+b+c$
增加到$c$：$b+c+d$
增加到$d$：$c+d+e$
增加到$e$：$d+e+f$
增加到$f$：$e+f$

所以肯定不会增加到$a$或$f$。
即：$a=f=1$

代入：
增加到$b$：$1+b+c$
增加到$c$：$b+c+d$
增加到$d$：$c+d+e$
增加到$e$：$d+e+1$

所以只可能增加到$c$或者$d$
即比较$b$和$e$的大小即可。

代码

#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++) 
#define LL long long
int rd(void);
const int N=65536;
int n,m;
int fs,ft;
vector<int> g[N];
int vis[N];
int cnt[8];
LL ans;
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd(),m=rd();
    fs=1,ft=2;
    F(i,1,m) {
        int x=rd(),y=rd();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vis[fs]=1;
    cnt[1]=1;
    vis[ft]=5;
    cnt[5]=1;
    F(i,1,g[fs].size()) {
        vis[g[fs][i-1]]=2;
        cnt[2]++;
    }
    ans+=(LL)cnt[2]*(cnt[2]-1)>>1;
    ans+=cnt[2];
    F(i,1,g[ft].size()) {
        vis[g[ft][i-1]]=4;
        cnt[4]++;
    }
    ans+=(LL)cnt[4]*(cnt[4]-1)>>1;
    ans+=cnt[4];
    cnt[3]=n-cnt[1]-cnt[2]-cnt[4]-cnt[5];
    ans+=(LL)cnt[3]*(cnt[3]-1)>>1;
    F(i,1,g[fs].size()) {
        int v=g[fs][i-1];
        F(j,1,g[v].size())
            if (!vis[g[v][j-1]]) {
                vis[g[v][j-1]]=3;
                ans+=cnt[2];
            }
    }
    F(i,1,g[ft].size()) {
        int v=g[ft][i-1];
        F(j,1,g[v].size())
            if (!vis[g[v][j-1]]) {
                vis[g[v][j-1]]=3;
                ans+=cnt[4];
            }
    }
    F(i,1,n)
        if (!vis[i]) {
            vis[i]=3;
            ans+=max(cnt[2],cnt[4]);
        }
    ans-=m;
    printf("%lld\n",ans);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2089】Monotonicity - 贪心+dp

同【bzoj2090】

---

【bzoj2090】Monotonicity 2 - 贪心+dp

题意

给定一个长度为$n$的序列$a$，以及长度为$n$的包含$<,=,>$的字符串。
求最长的子序列，子序列的相邻项要满足大小关系。
$n,k\leq 500000$

分析

最初的想法是二维dp，但肯定不行。
这时候考虑优化的方法，可以证明

$$f[i]=\max_{a[j]~opt[f[j]]~a[i]}(f[j]+1)$$
两棵权值树状数组实现。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
int rd(void);
char rd_chr(void);
const int N=1048576;
const int A=1000000;
int n;
int a[N];
int nk;
char s[N];
int f[N];
int ans;
int tr1[N];     //< 中 找比a[i]小的 
int eq[N];      //= 中 找等于a[i]的 
int tr2[N];     //> 中 找比a[i]大的 
int lowbit(int i) {
    return i&-i;
}
void Ins1(int x,int ad) {
    for (int i=x;i<=A;i+=lowbit(i))
        if (tr1[i]<ad)
            tr1[i]=ad;
        else break;
}
int Query1(int x) {
    int mx=0;
    for (int i=x;i>0;i-=lowbit(i))
        mx=max(mx,tr1[i]);
    return mx;
}
void Ins2(int x,int ad) {
    for (int i=x;i<=A;i+=lowbit(i))
        if (tr2[i]<ad)
            tr2[i]=ad;
        else break;
}
int Query2(int x) {
    int mx=0;
    for (int i=x;i>0;i-=lowbit(i))
        mx=max(mx,tr2[i]);
    return mx;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd(),nk=rd();
    F(i,1,n)
        a[i]=rd();
    F(i,1,nk)
        s[i]=rd_chr();
    F(i,nk+1,n)
        s[i]=s[i-nk];
    F(i,1,n) {
        int tL=Query1(a[i]-1);
        int tM=eq[a[i]];
        int tR=Query2(A-(a[i]+1)+1);
        int t=max(tL,max(tM,tR));
        f[i]=t+1;
        if (s[f[i]]=='<')
            Ins1(a[i],f[i]);
        else if (s[f[i]]=='=')
            eq[a[i]]=max(eq[a[i]],f[i]);
        else Ins2(A-a[i]+1,f[i]);
    }
    ans=*max_element(f,f+n+1);
    printf("%d\n",ans);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();    
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char rd_chr(void) {
    char c=getchar();
    while (c!='<'&&c!='='&&c!='>')
        c=getchar();
    return c;
}

---

【bzoj2091】The Minima Game - dp

题意

给出$N$个正整数，A和B两个人轮流取数，A先取。每次可以取任意多个数，直到$N$个数都被取走。
每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。
在这样的情况下，最终A的得分减去B的得分为多少。

分析

把$a$按从小到大排序。
为了让自己的得分尽可能大，对手的得分尽可能小，每次必然取尾部的一段。
设$f[i]$表示还剩前$i$个没有取时，先手所能得到的最大值。

我开始的想法是：

$$f[i]=\max_{j\geq i}(a[j]-f[j+1])$$
从大到小处理$f$，然后$f[1]$为答案。
这样是错的，因为当前决策的不一定是先手。
那求出来的是什么？
有可能是后手得分的最大值，或者先手的最大值。

那怎么办？
考虑从小到大处理$f[i]$。
$f[i]$表示剩下最小的$i$个，先手处理第$i$个的最大值。
则

$$f[i]=\max_{1\leq j\leq i}(a[j]-f[j-1])$$
这样递推求出来的就是答案。

其实还有一种做法。
我们照样可以从大到小地推。
就是记$f[i][0..1]$分别表示到第$i$个，当前是先手决策还是后手决策。
奠基：

$$f[n+1][0]=\infty$$ $$f[n+1][1]=0$$
转移： $$f[i][0]=\max_{j=i+1}^{n+1}(a[i]-f[j][1])$$
$$f[i][1]=\max_{j=i+1}^{n+1}(a[i]-f[j][0])$$
答案： $$ans=f[1][0]$$

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define LL long long
int rd(void);
const int N=1048576;
int n,a[N];
LL max_val,f[N];
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd();
    F(i,1,n)
        a[i]=rd();
    sort(a+1,a+n+1);
    F(i,1,n) {
        max_val=max(max_val,a[i]-f[i-1]);
        f[i]=max_val;
    }
    printf("%lld\n",f[n]);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2092】Lamp

无题面。

---

【bzoj2093】Frog - 单调性+倍增

题意

给定$n$个点，$n$个点在一条直线上，给定河岸的距离。
对于每个点，它会跳到离它距离第$k$近的点处。
求每个点跳$m$步会跳到哪里。

$1\leq n\leq 1000000$
$1\leq m\leq {10}^{18}$

分析

离一个点$k$近的所有点集，是一个连续的区间。
直接求解必定TLE。
但是，这是个离线的问题，可以利用到一些连续性的东西。
由于$k$一定，所以区间的长度相同。
随着$i$的增大，点$i$的连续区间在单调的后移。
所以我们维护two pointer即可。

然后求出每个点可以跳到哪里了。
这是个基环树。
可以考虑把环给求出来。
也可以考虑直接倍增求解。

因为倍增好写。
所以我写了倍增。
实现10s，我9s卡过了。

代码

#include <cstdio>
#include <cctype>
#include <cmath>
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LL long long
LL rd(void);
const int N=1000001;
const int U=60;
int n,nk;
LL m;
LL a[N];
int c;
int nx[U][N];
int Go(int x,LL m) {
    F(i,0,c)
        if (m>>i&1)
            x=nx[i][x];
    return x;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd(),nk=rd(),m=rd();
    F(i,1,n)
        a[i]=rd();
    c=(int)(log(m)/log(2));
    int l=1,r=nk+1;
    F(i,1,n) {
        while (l+1<=i&&r+1<=n) {
            if (a[i]-a[l]>a[r+1]-a[i])
                l++,r++;
            else break;
        }
        if (a[i]-a[l]>=a[r]-a[i])
            nx[0][i]=l;
        else nx[0][i]=r;
    }
    F(i,1,c)
        F(j,1,n)
            nx[i][j]=nx[i-1][nx[i-1][j]];
    F(i,1,n) {
        int t=Go(i,m);
        printf("%d",t);
        if (i<n)
            printf(" ");
        else printf("\n");
    }
    return 0;
}
LL rd(void) {
    LL x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2095】Bridge - 二分答案+混合图欧拉回路

题意

给出一个$n$个点$m$条边的无向图，每个边$(u,v)$，$(v,u)$各有一个权值。
现要从点$1$出发，对每条边经过且仅经过一次。
求一种方案使经过的最大权值最小。
在bzoj上，输出这个权值即可。
$2\leq n\leq 1000,1\leq m\leq 2000$

分析

二分+混合图欧拉回路。

混合图欧拉回路的求解：

首先要判定基图连通，且每个点的度数为偶数。

然后把无向边任意定向，计算每个点入度与出度的差$d$，按照定的方向连一条容量为1的边。在后面进行网络流的时候，若这条边流满，说明这条边要反向。

若$d_i>0$，则将源点与当前点连边，反之该点与汇点连边。容量应该是多少呢？流意味着中和，中和到d值为0。我们改变一条边，差值为2，所以容量应该是${1\over 2}d_i$。

那么，混合图欧拉回路如果有解，意味着满流。

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define fore(k,u) for (int k=hd[u];k>0;k=mp[k].nx)
int rd(void);
const int N=1024;
const int M=2048;
const int E=8192;
const int INF=(0x7fffffff)>>1;
const int REV_INF=-INF;
int n,m;
struct Ed {
    int a,b,c,d;
    Ed(int _a=0,int _b=0,int _c=0,int _d=0) {
        a=_a,b=_b,c=_c,d=_d;
    }
}ed[M];
int al,ar;
int am;
int f[N];
int sd[N];
int flow_siz;
int fs,ft,siz;
struct G {
    int v,f; int nx;
    G(int _v=0,int _f=0,int _nx=0) {
        v=_v,f=_f;
        nx=_nx;
    }
}mp[E];
int tot,hd[N];
int q[N],qh,qt,lev[N];
int mx_Flow;
void Ins(int u,int v,int f) {
    int x=++tot;
    mp[x]=G(v,f,hd[u]);
    hd[u]=x;
    x=++tot;
    mp[x]=G(u,0,hd[v]);
    hd[v]=x;
}
int BFS(int fs,int ft) {
    memset(q,0,sizeof q);
    qh=qt=0;
    memset(lev,0,sizeof lev);
    q[++qt]=fs;
    lev[fs]=1;
    while (qh!=qt) {
        int x=q[++qh];
        fore(k,x)
            if (mp[k].f>0&&!lev[mp[k].v]) {
                lev[mp[k].v]=lev[x]+1;
                if (mp[k].v==ft)
                    return 1;
                q[++qt]=mp[k].v;
            }
    }
    return 0;
}
int DFS(int x,int ft,int flow) {
    if (x==ft)
        return flow;
    int sum=0;
    fore(k,x)
        if (mp[k].f>0&&lev[mp[k].v]==lev[x]+1) {
            int t=DFS(mp[k].v,ft,min(flow,mp[k].f));
            if (t>0) {
                sum+=t;
                flow-=t;
                mp[k].f-=t;
                mp[k^1].f+=t;
                if (!flow) break;
            }
            else lev[mp[k].v]=INF;
        }
    return sum;
}
int Check(int lim) {
    memset(sd,0,sizeof sd);
    flow_siz=0;
    fs=ft=siz=0;
    tot=0;
    memset(hd,0,sizeof hd);
    siz=n;
    fs=++siz;
    ft=++siz;
    tot=1;
    F(i,1,m) {
        int a=ed[i].a,b=ed[i].b,c=ed[i].c,d=ed[i].d;
        if (c<=lim&&d<=lim) {
            sd[a]++;
            sd[b]--;
            Ins(a,b,1);
        }
        else if (c<=lim) {
            sd[a]++;
            sd[b]--;
        }
        else if (d<=lim) {
            sd[b]++;
            sd[a]--;
        }
    }
    F(i,1,n)
        if (sd[i]>0) {
            Ins(fs,i,sd[i]>>1);
            flow_siz+=(sd[i]>>1);
        }
        else if (sd[i]<0)
            Ins(i,ft,(-sd[i])>>1);
    mx_Flow=0;
    while (1) {
        int tag=BFS(fs,ft);
        if (!tag)
            break;
        int del=DFS(fs,ft,INF);
        mx_Flow+=del;
    }
    return mx_Flow==flow_siz;
}
int Find(int x) {
    if (f[x]==x)
        return x;
    else return f[x]=Find(f[x]);
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    n=rd(),m=rd();
    F(i,1,m) {
        int a=rd(),b=rd(),c=rd(),d=rd();
        ed[i]=Ed(a,b,c,d);
    }
    F(i,1,n)
        f[i]=i;
    F(i,1,m) {
        int a=ed[i].a,b=ed[i].b;
        f[Find(a)]=Find(b);
    }
    F(i,2,n)
        if (Find(i)!=Find(1)) {
            printf("NIE\n");
            return 0;
        }
    F(i,1,m)
        sd[ed[i].a]++,sd[ed[i].b]++;
    F(i,1,n)
        if (sd[i]%2==1) {
            printf("NIE\n");
            return 0;
        }
    al=REV_INF;
    ar=REV_INF;
    F(i,1,m) {
        int c=ed[i].c,d=ed[i].d;
        al=max(al,min(c,d));
        ar=max(ar,max(c,d));
    }
    if (!Check(ar)) {
        printf("NIE\n");
        return 0;
    }
    while (al<ar) {
        am=(al+ar)>>1;
        int tag=Check(am);
        if (tag)
            ar=am;
        else al=am+1;
    }
    printf("%d\n",al);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---

【bzoj2096】Pilots - 单调队列

题意

长度为$n$的给定的序列$A$。
找到一个最长的子串，满足任意两个难度差不会超过他设定的最大值。
输出最长子串的长度。

$n\leq 3000000$

分析

我们考虑枚举右端点$r$。
记$l^*$为符合条件的最小左端点。
随着$r$的增大，$l^*$必然也不下降。

而且，能作为以$r$为右端点的区间的最大值以及最小值。
随着$r$的增大，是可以使用单调队列维护的。

所以我们维护两个单调队列就好了。
具体见实现。

从hzwer的博客处。
我涨姿势了。
假如单调队列不会写，可以用priority_queue实现单调队列。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
int rd(void);
const int N=3000010;
int n,nk;
int a[N];
int q1[N],h1,t1;
int q2[N],h2,t2;
int l;
int ans;
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("a.in","r",stdin);
        freopen("a.out","w",stdout);
    #endif
    nk=rd(),n=rd();
    F(i,1,n)
        a[i]=rd();
    h1=h2=1;
    l=1;
    F(r,1,n) {
        while (h1<=t1&&a[r]>=a[q1[t1]])
            q1[t1--]=0;
        q1[++t1]=r;
        while (h2<=t2&&a[r]<=a[q2[t2]])
            q2[t2--]=0;
        q2[++t2]=r;
        while (a[q1[h1]]-a[q2[h2]]>nk)
            if (q1[h1]<q2[h2]) {
                l=q1[h1]+1;
                q1[h1++]=0;
            }
            else {
                l=q2[h2]+1;
                q2[h2++]=0;
            }
        ans=max(ans,r-l+1);
    }
    printf("%d\n",ans);
    return 0;
}
int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

---