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過程中直接求出最終序列。

#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)) {///initrep(i,0,n+1) 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,n+1) scanf("%d",a+i);///solvememset(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)) {///initrep(i,0,n+1) 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,n+1) scanf("%d",a+i);///solverep(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; }

轉載于:https://www.cnblogs.com/wuyuanyuan/p/8675210.html

總結

以上是生活随笔為你收集整理的codeforces 453C Little Pony and Summer Sun Celebration的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。