考试总结 模拟$100$

考试过程

暴力分都拿到了，T1看出了是欧拉路，而且之前也看过书上的板子，但是考场上大脑一片空白，对知识理解不够深入

T2应该多去想想一些比较显然的优化

T3暴力在OJ上T了，但是本机过40分了，可能是厌氧。没看出来为什么，以本机为准吧

 题解

T1「欧拉路」

板子题啊

大概稍总结一下：

欧拉路经的判定：

1.无向图，奇度点有2个起点和终点，其他都是偶度点。若奇度点有0个，则是欧拉回路

2.有向图，除两个特殊点：outd=ind+1的是起点，ind==outd+1的是终点，其余ind==outd，。若都想等的，是欧拉回路

求解：基于这样的性质：路径上的每个点，进去之后，一定会有一条边出来，

dfs一遍，并且用栈记录顺序并且倒序输出即可，每个点枚举所有边的最劣复杂度会是$O(n*m)$

那么用上当前弧优化，就可以避免枚举重复的边

#include<bits/stdc++.h>
#define EXIT {puts("NO");return;}
using namespace std;
inline int rd(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
}
const int maxn=1e5+5;
int T,n,m;
int ind[maxn],outd[maxn];
int n_e=1,ver[maxn<<2],nxt[maxn<<2],head[maxn];
void add(int x,int y){
	ver[++n_e]=y;
	nxt[n_e]=head[x];
	head[x]=n_e;
}
int pvis[maxn];
void pdfs(int x){
	pvis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(pvis[y])continue;
		pdfs(y);
	}
}
int vis[maxn<<2],sta[maxn<<2],top;
void euler(int x){
	for(int i=head[x];i;){
		if(vis[i]){
			head[x]=i=nxt[i];
		}
		else{
			vis[i]=1;
			if(T==1)vis[i^1]=1;
			head[x]=nxt[i];
			euler(ver[i]);
			sta[++top]=i;
			i=head[x];
		}
	}
}
inline void sol1(){
	for(int i=1;i<=m;++i){
		int x=rd(),y=rd();
		add(x,y),add(y,x);
		++ind[x],++ind[y];
	}
	int S=0,E=0;
	for(int x=1;x<=n;++x){
		if(!(ind[x]&1))continue;
		if(!S) S=x;
		else if(!E) E=x;
		else EXIT
	}
	if(!S)for(int x=1;x<=n;++x)
		if(ind[x]){S=x;break;}
	pdfs(S);
	for(int x=1;x<=n;++x)
		if(!pvis[x]&&ind[x]) EXIT
	puts("YES");
	euler(S);
	for(int i=top;i>=1;--i){
		int nw=sta[i];
		if(nw&1)nw*=-1;
		nw/=2;
		printf("%d ",nw);
	}
}
inline void sol2(){
	for(int i=1;i<=m;++i){
		int x=rd(),y=rd();
		add(x,y);++outd[x],++ind[y];
	}
	int S=0,E=0;
	for(int x=1;x<=n;++x){
		if(ind[x]==outd[x])continue;
		if(ind[x]+1==outd[x]){if(!S)S=x;else EXIT}
		else if(ind[x]==outd[x]+1){if(!E)E=x;else EXIT}
		else EXIT
	}
	
	if(!S)for(int x=1;x<=n;++x)
		if(outd[x]){S=x;break;}
	
	pdfs(S);
	for(int x=1;x<=n;++x)
		if(!pvis[x]&&ind[x]) EXIT
	euler(S);
	puts("YES");
	for(int i=top;i>=1;--i)
		printf("%d ",sta[i]-1);
}
int main(){
	freopen("merge.in","r",stdin);
	freopen("merge.out","w",stdout);
	T=rd(),n=rd(),m=rd();
	if(T==1)sol1();
	else sol2();
}

T2「贪心」「性质题」

可以发现每次的操作过后那一串的点的贡献都变为了0，且其他的点的贡献不变

所以在第二次出现要操作这个点的时候，直接输出上一次的ans

 等会我没写正解