A. 虎

算法1：我们发现非关键边与黑色边去掉以后,答案就是将所有度数为奇数的点作为路径的端点,所以记去掉非关键边与黑色边以后度数为奇数的点的个数为s,而一条路径有2个端点,所以答案就是$\frac{s}{2}$。

注意映射

#include<iostream>

#include<cstdio>

#include<cstring>

#define MAXN 1000005

using namespace std;

int n,ans=0,du[MAXN],id[MAXN],tot=0;

signed main(){

	scanf("%d",&n);

	for(int i=2,x,y,z;i<=n;i++){

		scanf("%d%d%d",&x,&y,&z);

		if(z==0){

			if(id[i]) id[x]=id[i];

			else if(id[x]) id[i]=id[x];

			else id[x]=id[i]=++tot;

		}

		if(y==0){

			if(!id[i]) id[i]=++tot;

			if(!id[x]) id[x]=++tot;

			du[id[i]]++,du[id[x]]++;

		}

	}

	for(int i=2;i<=tot;i++){

		if(du[i]&1) ans++;

	}

	printf("%d\n",(ans+1)/2);

	return 0;

}

算法2：不妨设0号点为根,那么将i到j的路径取反等价于将0到i和0到j的路径取反,因此只要求出最少需要将多少条到根的路径取反,然后除以二上取整就是答案。用f[i]表示i的子树中所有边(包括 i 连向父亲的边)满足条件时的最少取反路径数,只要先对i的所有儿子的f值求和,然后判断i连向父亲的边是否满足条件,如果不满足再+1即可。

B：阴阳

放个代码就跑

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define MAXN 1005

using namespace std;

const int mod=1e9+7;

int n,m,ans=0,sum_b[MAXN][MAXN],sum_w[MAXN][MAXN];

char ch[MAXN],app_b=0,app_w=0;

int work1(){

	int f[MAXN][MAXN]={0},res=0;

	f[0][0]=1;

	for(int i=1;i<=n;++i){

        for(int j=0;j<=m;++j){

            if(sum_w[i][j]) break;

            if(sum_b[i][m]-sum_b[i][j]) continue;

            for(int k=0;k<=j;++k)

                f[i][j]=(f[i][j]+f[i-1][k])%mod;

			if(i==n) (res+=f[n][j])%=mod;

        }

	}

    return res%mod;

}

int work2(){

	int f[MAXN][MAXN]={0},res=0;

    f[0][0]=1;

    for(int i=1;i<=n;++i){

        for(int j=0;j<=m;++j){

            if(sum_b[i][j]) break;

            if(sum_w[i][m]!=sum_w[i][j]) continue;

            for(int k=0;k<=j;++k)

                f[i][j]=(f[i][j]+f[i-1][k])%mod;

			if(i==n) (res+=f[n][j])%=mod;

        }

	}

    return res%mod;

}

int work3(){

	int f[MAXN][MAXN]={0},res=0;

    f[0][m]=1;

    for(int i=1;i<=n;++i){

        for(int j=0;j<=m;++j){

            if(sum_w[i][j]) break;

            if(sum_b[i][m]-sum_b[i][j]) continue;

            for(int k=j;k<=m;++k)

                f[i][j]=(f[i][j]+f[i-1][k])%mod;

			if(i==n) (res+=f[n][j])%=mod;

        }

	}

    return res%mod;

}

int work4(){

	int f[MAXN][MAXN]={0},res=0;

    f[0][m]=1;

    for(int i=1;i<=n;++i){

        for(int j=0;j<=m;++j){

            if(sum_b[i][j]) break;

            if(sum_w[i][m]-sum_w[i][j]) continue;

            for(int k=j;k<=m;++k)

                f[i][j]=(f[i][j]+f[i-1][k])%mod;

			if(i==n) (res+=f[n][j])%=mod;

        }

	}

	return res%mod;

}

int work5(){

	int res=0;

	for(int i=0;i<=n;++i){

        bool flag=0;

        for(int j=1;j<=i;++j)

            if(sum_w[j][m]){

				flag=1;break;

			}

        if(flag) break;

        for(int j=i+1;j<=n;++j)

            if(sum_b[j][m]){

				flag=1;break;

			}

        if(flag) continue;

        res++;

    }

	return res%mod;

}

int work6(){

	int res=0;

	for(int i=0;i<=n;++i){

        bool flag=0;

        for(int j=1;j<=i;++j)

            if(sum_b[j][m]){

				flag=1;break;

			}

        if(flag) break;

        for(int j=i+1;j<=n;++j)

            if(sum_w[j][m]){

				flag=1;break;

			}

        if(flag) continue;

        res++;

    }

	return res%mod;

}

int work7(){

	int res=0;

	for(int i=0;i<=m;++i){

        bool flag=0;

        for(int j=1;j<=n;++j){

            if(sum_w[j][i]){

                flag=1;

                break;

            }

			if(sum_b[j][m]!=sum_b[j][i]){

				flag=1;

				break;

			}

		}

        if(flag) continue;

        res++;

    }

	return res%mod;

}

int work8(){

	int res=0;

	for(int i=0;i<=m;++i){

        bool flag=0;

        for(int j=1;j<=n;++j){

            if(sum_b[j][i]){

                flag=1;

                break;

            }

			if(sum_w[j][m]!=sum_w[j][i]){

                flag=1;

                break;

            }

		}

        if(flag) continue;

        res++;

    }

	return res%mod;

}

signed main(){

	//freopen("test.in","r",stdin);

	//freopen("b1.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++){

		scanf("%s",ch+1);

		for(int j=1;j<=m;j++){

			sum_b[i][j]=sum_b[i][j-1];sum_w[i][j]=sum_w[i][j-1];

			if(ch[j]=='B') sum_b[i][j]++,app_b=1;

			if(ch[j]=='W') sum_w[i][j]++,app_w=1;

		}

	}

	if(!app_b) ans++;

	if(!app_w) ans++;

	(ans+=work1())%=mod;

	(ans+=work2())%=mod;

	(ans+=work3())%=mod;

	(ans+=work4())%=mod;

	(ans-=work5())%=mod;

	(ans-=work6())%=mod;

	(ans-=work7())%=mod;

	(ans-=work8())%=mod;

	ans%=mod;

	printf("%d\n",ans);

	return 0;

}

巴特西

HZOI20190821模拟28题解

A. 虎

最新文章

热门文章