免费好用的网站,王占郡,网站建设问题新闻资讯,杭州最好的工业设计公司codeforces 453C Little Pony and Summer Sun Celebration 这道题很有意思#xff0c;虽然网上题解很多了#xff0c;但是我还是想存档一下我的理解。 题意可以这样转换#xff1a;初始所有点有 \(01\) 状态#xff0c;每经过一次状态就翻转#xff0c;求一条路径使得最后…codeforces 453C Little Pony and Summer Sun Celebration 这道题很有意思虽然网上题解很多了但是我还是想存档一下我的理解。 题意可以这样转换初始所有点有 \(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过程中直接求出最终序列。 #includebits/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 xendl
#define dd(x) cout #x x
typedef long long ll;
typedef pairint, int pii;
typedef vectorint vi;const int N101010;
int n,m;
int a[N];
vi res, ans;
vi g[N];
bool vis[N], la[N1];void dfs(int u,int fa) {res.pb(u);vis[u]1;rep(i,0,sz(g[u])) {int vg[u][i];if(vfa||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,n1) if(a[i]) {puts(-1);return ;}printf(%d\n,sz(ans));rep(i,0,sz(ans)) printf(%d%c,ans[i], \n[isz(ans)-1]);
}int main() {while(~scanf(%d%d,n,m)) {///initrep(i,0,n1) g[i].clear();res.clear();ans.clear();memset(la,0,sizeof(la));///readrep(i,0,m) {int u,v;scanf(%d%d,u,v);g[u].pb(v);g[v].pb(u);}rep(i,1,n1) scanf(%d,ai);///solvememset(vis,0,sizeof(vis));rep(i,1,n1) if(a[i]) {dfs(i, i);break;}memset(vis,0,sizeof(vis));for(int isz(res)-1;~i;--i) if(!vis[res[i]]) {vis[res[i]]1;la[i]1;}rep(i,0,sz(res)) {int ures[i];upd(u);if(ia[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;
} #includebits/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 xendl
#define dd(x) cout #x x
typedef long long ll;
typedef pairint, int pii;
typedef vectorint vi;const int N101010;
int n,m;
int a[N];
vi ans;
vi g[N];
bool vis[N], la[N1];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 vg[u][i];if(vfa||vis[v]) continue;dfs(v, u);upd(u);if(a[v]) {upd(v);upd(u);}}
}inline void print() {rep(i,1,n1) if(a[i]) {puts(-1);return ;}printf(%d\n,sz(ans));rep(i,0,sz(ans)) printf(%d%c,ans[i], \n[isz(ans)-1]);
}int main() {while(~scanf(%d%d,n,m)) {///initrep(i,0,n1) g[i].clear();ans.clear();memset(la,0,sizeof(la));memset(vis,0,sizeof(vis));///readrep(i,0,m) {int u,v;scanf(%d%d,u,v);g[u].pb(v);g[v].pb(u);}rep(i,1,n1) scanf(%d,ai);///solverep(i,1,n1) 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;
} 转载于:https://www.cnblogs.com/wuyuanyuan/p/8675210.html
