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

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

表达式密码：

是个水题。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1e5+5;
 7 int len,fh=0;
 8 char s[MAXN];
 9 signed main(){
10     //freopen("expression.in","r",stdin);
11     //freopen("i.out","w",stdout);
12     scanf("%s",s+1);
13     len=strlen(s+1);
14     s[len+1]='?';
15     if(s[1]=='-') fh=2;
16     else fh=1;
17     for(int i=1;i<=len;){
18         while(i<=len&&s[i]<'0'||s[i]>'9') ++i;
19         if(fh==2){
20             putchar('-');
21             putchar(s[i]);
22             ++i;
23             if(s[i]=='-') fh=2;
24             else fh=1;
25         }else{
26             while(i<=len&&s[i]=='0'){
27                 putchar('+');
28                 putchar('0');
29                 ++i;
30             }
31             if(s[i]=='-') fh=2;
32             else if(s[i]=='+') fh=1;
33             else if(s[i]!='?'){
34                 if(i!=1) putchar('+');
35                 while(i<=len&&s[i]>='0'&&s[i]<='9'){
36                     putchar(s[i]);
37                     ++i;
38                 }
39                 if(s[i]=='-') fh=2;
40                 else fh=1;
41             }
42         }
43     }
44     puts("");
45     return 0;
46 }

View Code

电压机制：

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

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

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

考虑如何拓展到一般情况

我们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
",ans);
	return 0;
}

括号密码：不会