csps模拟85表达式密码，电压机制，括号密码题解

题面：https://www.cnblogs.com/Juve/articles/11733280.html

表达式密码：

是个水题。。。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN=1e5+;

 int len,fh=;

 char s[MAXN];

 signed main(){

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

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

     scanf("%s",s+);

     len=strlen(s+);

     s[len+]='?';

     if(s[]=='-') fh=;

     else fh=;

     for(int i=;i<=len;){

         while(i<=len&&s[i]<''||s[i]>'') ++i;

         if(fh==){

             putchar('-');

             putchar(s[i]);

             ++i;

             if(s[i]=='-') fh=;

             else fh=;

         }else{

             while(i<=len&&s[i]==''){

                 putchar('+');

                 putchar('');

                 ++i;

             }

             if(s[i]=='-') fh=;

             else if(s[i]=='+') fh=;

             else if(s[i]!='?'){

                 if(i!=) putchar('+');

                 while(i<=len&&s[i]>=''&&s[i]<=''){

                     putchar(s[i]);

                     ++i;

                 }

                 if(s[i]=='-') fh=;

                 else fh=;

             }

         }

     }

     puts("");

     return ;

 }

电压机制：

题目翻译：在一张无向图上，有多少边满足：在所有的奇环上但是不再任何一个偶环上

题目给了基环树的数据，启发我们想到正解

如过那个环是偶环，那么答案就是环外的，如果是奇环，答案就是环内的

考虑如何拓展到一般情况

我们dfs时会建出一个搜索树，我们把新树建出来，同时记录每一条边是否为树边

然后扫每一个不是树边的边，如果把它加进新图，就会形成环，因为是在树上，lca，两点间dis很好求，所以我们知道加入这条边会形成奇环还是偶环

暴力排除每一条边显然不可能，我们考虑差分

把每一条边放到点，统计每一个点被多少个奇环或偶环经过，打差分，最后dfs一遍就统计出了一个点在几个奇环，几个偶环中了

然后就统计出答案了，注意根节点不要统计，因为把边放到点，没有边被放到了根节点

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define re register

using namespace std;

const int MAXN=1e5+5;

int n,m,ans=0,f[MAXN],g[MAXN],tot=0;

int to[MAXN<<1],nxt[MAXN<<1],id[MAXN<<1],pre[MAXN],cnt=0;

struct node{

	int u,v;

	bool flag;//shifoushishubian

}e[MAXN<<1];

inline void add(re int u,re int v){

	++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;

}

int fa[MAXN];

inline int find(re int x){

	return fa[x]=(fa[x]==x?x:find(fa[x]));

}

int deep[MAXN],siz[MAXN],son[MAXN];

inline void dfs(re int x){

	siz[x]=1;

	for(re int i=pre[x];i;i=nxt[i]){

		re int y=to[i];

		if(y==fa[x]) continue;

		fa[y]=x;deep[y]=deep[x]+1;

		dfs(y);

		siz[x]+=siz[y];

		if(siz[son[x]]<siz[y]) son[x]=y;

	}

}

int top[MAXN];

inline void DFS(re int x,re int topf){

	top[x]=topf;

	if(son[x]) DFS(son[x],topf);

	for(re int i=pre[x];i;i=nxt[i]){

		re int y=to[i];

		if(y==fa[x]||y==son[x]) continue;

		DFS(y,y);

	}

}

inline int LCA(re int x,re int y){

	while(top[x]!=top[y]){

		if(deep[top[x]]<deep[top[y]]) swap(x,y);

		x=fa[x];

	}

	if(deep[x]>deep[y]) swap(x,y);

	return x;

}

bool vis[MAXN];

void dfs1(int x,int rt){

	vis[x]=1;

	for(int i=pre[x];i;i=nxt[i]){

		int y=to[i];

		if(y==fa[x]) continue;

		dfs1(y,rt);

		g[x]+=g[y],f[x]+=f[y];

	}

	if(f[x]==tot&&g[x]==0&&x!=rt) ++ans;

}

signed main(){

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

	for(re int i=1;i<=n;++i) fa[i]=i;

	for(re int i=1,u,v;i<=m;++i){

		scanf("%d%d",&u,&v);

		e[i]=(node){u,v,0};

	}

	re int num=0;

	for(re int i=1;i<=m;++i){

		re int x=find(e[i].u),y=find(e[i].v);

		if(x!=y){

			fa[x]=y;

			add(e[i].u,e[i].v),add(e[i].v,e[i].u);

			e[i].flag=1;

			++num;

			if(num==n-1) break;

		}

	}

	memset(fa,0,sizeof(fa));

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

		if(deep[i]) continue;

		deep[i]=1;

		dfs(i),DFS(i,i);

	}

	for(re int i=1;i<=m;++i){

		if(e[i].flag) continue;

		re int x=e[i].u,y=e[i].v;

		re int lca=LCA(x,y);

		re int dis=deep[x]+deep[y]-deep[lca]*2;

		if(dis&1){//ouhuan

			++g[x],++g[y],g[lca]-=2;

		}else{

			++tot;

			++f[x],++f[y],f[lca]-=2;

		}

	}

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

		if(vis[i]) continue;

		dfs1(i,i);

	}

	if(tot==1) ++ans;

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

	return 0;

}

括号密码：不会

巴特西

csps模拟85表达式密码，电压机制，括号密码题解

最新文章

热门文章