• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

codeforces453CLittlePonyandSummerSunCelebration

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

这道题很有意思,虽然网上题解很多了,但是我还是想存档一下我的理解。

题意可以这样转换:初始所有点有 \(01\) 状态,每经过一次状态就翻转,求一条路径使得最后状态全 \(1\)

以某个状态 \(1\) 的点开始,搜出它的dfs序。dfs序的长度必定是 \(2n-1\)(因为dfs树有 \(n-1\) 条边,每条边遍历两次)。我们把这个dfs序列存在数组 \(res[0..2n-2]\) 中。当遍历到 \(res[i]\) 时,如果 \(res[i-1]\) 的状态是 \(1\),并且以后不会再遍历到 \(res[i-1]\),那么我们可以在原序列(\(...->res[i-1]->res[i]->...\))的基础上再加上 \(->res[i-1]->res[i]->\)(新序列 \(...->res[i-1]->res[i]->\)res[i-1]->res[i]\(->...\))。最后如果 \(res[2n-2]\) 状态是 \(1\),从序列中删除即可。

基于这种构造方法,最后序列的长度范围在 \([2n-1, 4n-1]\)。(比dfs序列最多多 \(2n\) 个)

以下代码有两种实现方式,一种是先把dfs序搜出来再做,一种是dfs过程中直接求出最终序列。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(x) (int)x.size()
#define de(x) cout<< #x<<" = "<<x<<endl
#define dd(x) cout<< #x<<" = "<<x<<" "
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N=101010;
int n,m;
int a[N];
vi res, ans;
vi g[N];
bool vis[N], la[N<<1];

void dfs(int u,int fa) {
	res.pb(u);
	vis[u]=1;
	rep(i,0,sz(g[u])) {
		int v=g[u][i];
		if(v==fa||vis[v]) continue;
		dfs(v, u);
		res.pb(u);
	}
}

inline void upd(int u) {
	ans.pb(u);
	a[u]^=1;
}

inline void print() {
	rep(i,1,n+1) if(a[i]) {
		puts("-1");
		return ;
	}
	printf("%d\n",sz(ans));
	rep(i,0,sz(ans)) printf("%d%c",ans[i]," \n"[i==sz(ans)-1]);
}

int main() {
	while(~scanf("%d%d",&n,&m)) {
		///init
		rep(i,0,n+1) g[i].clear();
		res.clear();
		ans.clear();
		memset(la,0,sizeof(la));
		///read
		rep(i,0,m) {
			int u,v;scanf("%d%d",&u,&v);
			g[u].pb(v);
			g[v].pb(u);
		}
		rep(i,1,n+1) scanf("%d",a+i);
		///solve
		memset(vis,0,sizeof(vis));
		rep(i,1,n+1) if(a[i]) {
			dfs(i, i);
			break;
		}
		memset(vis,0,sizeof(vis));
		for(int i=sz(res)-1;~i;--i) if(!vis[res[i]]) {
			vis[res[i]]=1;
			la[i]=1;
		}
		rep(i,0,sz(res)) {
			int u=res[i];
			upd(u);
			if(i&&a[res[i-1]]&&la[i-1]) {
				upd(res[i-1]);
				upd(u);
			}
		}
		if(sz(ans)&&a[ans[sz(ans)-1]]) a[ans[sz(ans)-1]]=0, ans.pop_back();
		print();
	}
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(x) (int)x.size()
#define de(x) cout<< #x<<" = "<<x<<endl
#define dd(x) cout<< #x<<" = "<<x<<" "
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N=101010;
int n,m;
int a[N];
vi ans;
vi g[N];
bool vis[N], la[N<<1];

inline void upd(int u) {
	ans.pb(u);
	a[u]^=1;
}

void dfs(int u,int fa) {
	upd(u);
	vis[u]=1;
	rep(i,0,sz(g[u])) {
		int v=g[u][i];
		if(v==fa||vis[v]) continue;
		dfs(v, u);
		upd(u);
		if(a[v]) {
			upd(v);
			upd(u);
		}
	}
}

inline void print() {
	rep(i,1,n+1) if(a[i]) {
		puts("-1");
		return ;
	}
	printf("%d\n",sz(ans));
	rep(i,0,sz(ans)) printf("%d%c",ans[i]," \n"[i==sz(ans)-1]);
}

int main() {
	while(~scanf("%d%d",&n,&m)) {
		///init
		rep(i,0,n+1) g[i].clear();
		ans.clear();
		memset(la,0,sizeof(la));
		memset(vis,0,sizeof(vis));
		///read
		rep(i,0,m) {
			int u,v;scanf("%d%d",&u,&v);
			g[u].pb(v);
			g[v].pb(u);
		}
		rep(i,1,n+1) scanf("%d",a+i);
		///solve
		rep(i,1,n+1) if(a[i]) {
			dfs(i, i);
			break;
		}
		if(sz(ans)&&a[ans[sz(ans)-1]]) a[ans[sz(ans)-1]]=0, ans.pop_back();
		print();
	}
	return 0;
}

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap