Preface

今天的B组题确实比A组难多了。。。

T1

Description

有一个长为\(n(n\in[1,2*10^5])\)的01串，有\(m(m\in[1,10^5])\)个限制\(a_i、b_i\)，表示限定区间\([a_i,b_i]\)中有且只有1个1。

求最多的1的数目。无解输出-1。

Solution

这题可以DP。但我们有一种更加巧妙也方便的方法——差分约束。~~（我好像是第一次打这东西）~~

一个标准的差分约束系统是有一个未知数列\(x_{1..n}\)，有若干个形如\(x_i-x_j≤k\)的限制，求\(x_n-x_0\)的最大值。它的实现是建图，跑最短路。拿限制\(x_i-x_j≤k\)举例，我们从\(j\)向\(i\)连一条长为\(k\)的边，那么最短路满足\(dis_j+k≥dis_i\)，则将\(dis\)代入\(x\)即可。

回到这题，我们可以对原串的前缀和构造差分约束系统。对于一个限制\(a、b（a≤b）\)，我们可以视为有两个限制：\(s_b-s_{a-1}≤1\)，\(s_{a-1}-s_b≤-1\)；当然它还有隐限制\(s_i-s_{i-1}≤1\)，\(s_{i-1}-s_i≤0\)。

建出了图后，我们就跑spfa。但囿于可能有负环，我们可以考虑在spfa中运行太久便确认负环存在，输出-1并退出程序。

Code

#include 
    
     #define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;const int N=21e4,M=4*N;int i,n,m,a,b,tov[M],len[M],nex[M],las[N],dis[N],h,t,d[10*M];double start;bool p[N];void read(int&x){    char c=getchar(); x=0;    for(;!isdigit(c);c=getchar());    for(;isdigit(c);c=getchar()) x=x*10+(c^48);}inline void link(int x,int y,int z) {static int tot=0; tov[++tot]=y,len[tot]=z,nex[tot]=las[x],las[x]=tot;}void spfa(){    fo(i,1,n) dis[i]=1e9;    h=0, p[d[t=1]=0]=1;    while(h
     
      dis[a]+len[i])            {                dis[b]=dis[a]+len[i];                if(!p[b])                {                    if(++t>=10*M) {puts("-1"); exit(0);}                    p[d[t]=b]=1;                    if(dis[d[h+1]]>dis[b]) swap(d[h+1],d[t]);                }            }        p[a]=0;    }}int main(){    read(n), read(m);    fo(i,1,n) link(i-1,i,1), link(i,i-1,0);    fo(i,1,m)    {        read(a), read(b);        link(a-1,b,1), link(b,a-1,-1);    }    spfa();    printf("%d",dis[n]);}

T2

Description

给定一棵\(N(N\in[1,10^5])\)个点的树，树边有黑白两种颜色。

对于一条路径，令一个非起点/终点的点为休息点。定义平衡路径为起点到休息点、休息点到终点的分路径上都满足黑边数等于白边数的路径。

求平衡路径数。

Solution

这题一眼树形DP；但仔细考虑后发现树形DP状态太大，转移太复杂。

于是考虑点分治。

我们以每个分治中心为根，计算贡献。那么有两种可能：一种是穿过根的路径；一种是一个端点在根上的路径（后者一定不能忘了考虑！！！）。

对于前者，我们可以计算根子树内每个点到根的距离（白边为-1，黑边为1）。然后我们要记录每个点到根路径上是否有合法的休息点，这个只要它们的距离一样即可。

然后我们合并两个路径，这可根据休息点的位置分类讨论。而合并的路径须满足两者到根距离互为相反数。

具体实现可以用桶。

Code

这题真心不难打，也就1K多一点。~~但我弱调了半天~~

#include 
    
     #define max(x,y) (x>y?x:y)#define fo(i,a,b) for(i=a;i<=b;i++)#define rep(x) for(int i=las[x],y;y=tov[i];i=nex[i])if(y!=fa&&!lG[y])using namespace std;typedef long long ll;const int N=51e4;int i,j,n,a,b,len[N],tov[N],nex[N],las[N],sz[N],siz[N],ms[N],dis[N],ed[N],d[N],d1[N],c[N],ck[N];bool k[N],lG[N];ll ans;int getG(int x,int fa,int n){    sz[x]=1,ms[x]=0;    rep(x)    {        int G=getG(y,x,n);        if(G) return G;        sz[x]+=sz[y];        if(ms[x]
     
      >1]];        getdis(y,x,n), siz[x]+=siz[y];    }    ed[dis[x]]--;}void solve(int G,int n){    if(n<5) return;    G=getG(G,0,n);    int fa=0;    rep(G)    {        dis[y]=2*n+len[i>>1];        getdis(y,G,n);        do        {            y=d[d[0]];            c[dis[y]]++, ck[dis[y]]+=k[y];            d1[++d1[0]]=y;            k[y]=0;        }while(--d[0]);    }    while(d1[0]) {int y=d1[d1[0]--]; c[dis[y]]=ck[dis[y]]=0;}    lG[G]=1;    rep(G) solve(y,siz[y]);}int main(){    scanf("%d",&n);    fo(i,1,n-1)    {        scanf("%d%d%d",&a,&b,&len[i]);        if(!len[i]) len[i]=-1;        tov[i*2]=b,  nex[i*2]=las[a],  las[a]=i*2;        tov[i*2+1]=a,nex[i*2+1]=las[b],las[b]=i*2+1;    }    solve(1,n);    printf("%lld",ans);}