ZJT's Blog

Keep your determination.

集训队作业之AGC002-D

2017-10-7 20:112017-10-7 20:11
集训队作业AtCoder整体二分并查集可持久化

传送门

裸的整体二分+可持久化并查集。

直到现在才彻底搞清楚可持久化并查集的时间戳到底是怎么打的。。。我好菜啊。。。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 100010
using namespace std;

int n,m,numq;
int e[MAXN][2];
int f[MAXN],rk[MAXN],tf[MAXN];
vector< pair<int,int> > size[MAXN];
int ans[MAXN];

struct Query{
    int x1,x2,k,id;
}q[MAXN],q0[MAXN];

int getf(int x,int t){
    while(x!=f[x] && tf[x]<=t) x=f[x];
    return x;
}

int getsize(int x,int t){
    int l=0,r=size[x].size()-1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(size[x][mid].first<=t) l=mid;
        else r=mid-1;
    }
    return size[x][l].second;
}

void build(){
    for(int i=1;i<=n;i++){
        f[i]=i;
        size[i].push_back(make_pair(0,1));
    }
    for(int i=1;i<=m;i++){
        int x=getf(e[i][0],m),y=getf(e[i][1],m);
        if(x==y) continue;
        if(rk[x]<rk[y]) x^=y^=x^=y;
        f[y]=x;
        tf[y]=i;
        if(rk[x]==rk[y]) rk[x]++;
        size[x].push_back(make_pair(i,size[x][size[x].size()-1].second+size[y][size[y].size()-1].second));
    }
}

void solve(int l,int r,int ql,int qr){
    if(ql>qr) return;
    if(l==r){
        for(int i=ql;i<=qr;i++)
            ans[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1;
    for(int i=ql;i<=qr;i++) q0[i]=q[i];
    int now1=ql-1,now2=qr+1;
    for(int i=ql;i<=qr;i++){
        int x1=q0[i].x1,x2=q0[i].x2,k=q0[i].k;
        x1=getf(x1,mid); x2=getf(x2,mid);
        int res=getsize(x1,mid);
        if(x1!=x2) res+=getsize(x2,mid);
        if(res>=k) q[++now1]=q0[i];
        else q[--now2]=q0[i];
    }
    solve(l,mid,ql,now1);
    solve(mid+1,r,now2,qr);
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&e[i][0],&e[i][1]);
    scanf("%d",&numq);
    for(int i=1;i<=numq;i++){
        scanf("%d%d%d",&q[i].x1,&q[i].x2,&q[i].k);
        q[i].id=i;
    }
    build();
    solve(1,m,1,numq);
    for(int i=1;i<=numq;i++)
        printf("%d\n",ans[i]);
    return 0;
}

查看详细内容

集训队作业之AGC006-F

2017-10-7 16:572017-10-7 16:59
集训队作业AtCoder结论题并查集拆点

传送门

这一题从看题到AC总共花了4.5h,有大概3h都在盯着草稿纸发呆。。。还是要提高一个做题的效率。

首先显然可以把每个格子转成有向图的一条边,然后就变成了可以选$u\to v,v\to w$两条边,然后加上$w\to u$这条新边,然后问最后最多能有多少边。

考虑每条边是怎么产生的。产生一条新边需要两条已有的边,所以我们每次可以把一条边分成两条边,一直分下去,最后能得到一个已有的边组成的序列,并且这个序列的边不考虑方向时是图中的一条路径(不一定是简单路径)。考虑沿着这条路径走,每走一步可能是沿着这条边的方向走,也可能是逆着他的方向走。记正着走是1,反着走是-1,那么这个路径就能表示成1和-1组成的一个边权的序列。

考虑这个序列合法(即这些边最终能凑出一条连接路径两端的边)的条件。首先所有边权的和必须模3余1。这是因为两个-1能拼成一个1,两个1能拼成一个-1,而这些转换的过程都保证了所有边权的和在模3意义下是不变的。既然最终需要拼成一条正向的边,而一条正向边的权值是1,那所有边权的和就只能一直为1了。

上面仅仅是一个必要条件,而且确实有反例,比如$1,-1,1,...,1,-1,1$。这时我们需要一个充分必要条件。注意到反例的序列中相邻的元素都不同,那是不是只要存在两个相邻元素相同,就能直接说明序列合法呢?事实上这个结论是正确的(就是这个鬼结论我tm证了半小时)。考虑归纳,当结论对所有长度为$n-1$的序列都成立时,考虑任何一个长度为$n$且元素和模3余1的序列。

这时可以分类讨论:

  1. 如果序列中每个元素都相等,这时可以构造出一种方法,使得最后恰好剩下一个1。
  2. 如果前两个就相等了,那就找到从前往后第一个不同的元素,并把这个元素前的两个相同元素合并。合并完之后,产生出来的新值就和后面那个一样了,这时满足归纳条件,可以直接归纳到$n-1$的情况。
  3. 如果前面两个不同,就找到从前往后第一个相邻两个元素相同的位置,并把这两个元素合并,这时新的值就与前面的那个值相同了,可以归纳。

证完了这个结论之后,好像并没有什么用。。。?考虑一条不符合这个性质的路径(就是上面的那个反例),前缀和一直在1和0之间切换。那是不是只要前缀和达到过2,就能符合这个性质了呢?事实上这个也是成立的(这个很好证,我这里就不证了)。所以我们从一个点开始,维护一个边权和(初始为0),可以沿着一条边的方向走,也可以逆着一条边的方向走。前者边权和+1(模3意义下),后者-1。只要边权和到达过2,并且最终停在某个点时边权和为1,那么就能拼出一条初始点到这个点的单向边。

这时我们可以把每个点拆成5个点,编号分别是$0,1,2,0',1'$。0号点和$0'$号点代表边权和模3为0的状态,$1、1'、2$同理。0和$0'$的区别在于0的状态不曾到达过2,而$0'$曾经到达过2。这样的话,对于原图中的每条边,分别在$(0,1),(1,2),(0,2),(0',1'),(1',2),(0',2)$之间连上相应的边。只要一个点从对应的0号点出发,能到达另一个点对应的$1'$号点,那么这两个点之间就可以拼出一条有向边。注意到这个图实际上是个无向图,所以处理出所有连通块之后统计一下就行了。注意特判原图中的边的情况,按照这个走法不一定能统计到原图中的边。

感觉这个题还是挺妙的。最后拆5个点那一步一直想不到,想了半天之后突然之间就想出来了,想的过程中还得到了一堆错误结论+错误做法。AC之后看了看题解和别人的AC代码,好像跟我的完全不一样??奥妙重重.jpg

其实比较好奇别人怎么做的。。。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 1000010
#define LL long long

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m;
int g[MAXN],nume;
int p[MAXN][5],nump;
int e2[MAXN][2];
int f[MAXN],visit[MAXN];
int cnt[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
    e[nume]=edge(u,g[v]);
    g[v]=nume++;
}

int getf(int x){
    if(x==f[x]) return x;
    return f[x]=getf(f[x]);
}

void dfs(int x){
    visit[x]=1;
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            f[getf(e[i].to)]=getf(x);
            dfs(e[i].to);
        }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&m);
    for(int j=0;j<5;j++)
        for(int i=1;i<=n;i++) 
            p[i][j]=++nump;
    for(int i=1;i<=nump;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&e2[i][0],&e2[i][1]);
        int u=e2[i][0],v=e2[i][1];
        addEdge(p[u][0],p[v][1]);
        addEdge(p[u][1],p[v][2]);
        addEdge(p[u][2],p[v][0]);
        addEdge(p[u][2],p[v][4]);
        addEdge(p[u][3],p[v][2]);
        addEdge(p[u][4],p[v][3]);
    }
    for(int i=1;i<=nump;i++)
        if(!visit[i])
            dfs(i);
    for(int i=1;i<=n;i++) cnt[getf(p[i][3])]++;
    LL ans=0;
    for(int i=1;i<=n;i++)
        ans+=cnt[getf(p[i][0])];
    for(int i=1;i<=m;i++)
        if(getf(p[e2[i][0]][0])!=getf(p[e2[i][1]][3]))
            ans++;
    printf("%lld\n",ans);
    return 0;
}

查看详细内容