传送门

这一题从看题到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;
}