The Red Button
The Red Button
问题
问题描述
Piegirl终于发现了红色按钮，你现在还剩最后一个机会去改变这个结局。这个按钮下面的电路由n个从0到n-1编号节点组成。为了关闭这个按钮，这n个节点必须以特定的序列拆解。节点0必须首先拆解，在拆解了节点i后，下一个被拆解的节点必须是(2·i) mod n或(2·i)+1 mod n。最后一个被拆解的节点必须是节点0。节点0必须被拆解两次，其他节点必须刚好被拆解一次。你的任务是找到一个符合要求的顺序并输出它。如果没有任何一个顺序满足条件，输出-1。
输入格式
包含一个整数n(2<=n<=105)
输出格式
输出一个可以拆解所有节点的顺序。如果不可能输出-1。如果有多个可能的顺序，输出任意一个。
样例输入
数据1
2
数据2
3
数据3
4
数据4
16
2
数据2
3
数据3
4
数据4
16
样例输出
数据1
0 1 0
数据2
-1
数据3
0 1 3 2 0
数据4
0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0
0 1 0
数据2
-1
数据3
0 1 3 2 0
数据4
0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0
数据规模和约定
对于15%的数据2<=n<=10
对于30%的数据2<=n<=20
对于100%的数据2<=n<=105
对于30%的数据2<=n<=20
对于100%的数据2<=n<=105
解法
一开始的思路是DFS，每个节点最多有两个方向，可以就走，不能就回溯找另一个方向，这样数量大之后就会TLE，自测120多就出不来结果
TLE代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int n; int len; int dist[maxn]; bool vis[maxn]; bool dfs(int k,int d) { if(d==n-1&&(k*2==n||k*2+1==n)) { dist[d]=k; dist[n]=0; return true; } dist[d]=k; // cout<<d<<" :"<<k<<endl; int ne=(k*2)%n; if(vis[ne]==false) { vis[ne]=true; if(dfs(ne,d+1)) return true; vis[ne]=false; } int nex=(k*2+1)%n; if(vis[nex]==false) { vis[nex]=true; if(dfs(nex,d+1)) return true; vis[nex]=false; } return false; } int main() { int i,j; cin>>n; vis[0]=true; if(n&1) cout<<"-1"<<endl; else { if(dfs(0,0)) { for(i=0;i<=n;i++) { if(i!=0) cout<<" "; cout<<dist[i]; } } } return 0; }
正确解法：
只需标记所有节点一遍即可，第一个走头无路的点就是终点，第二个走投无路的点是倒数第二个终点。。。。
因此，只需标记完所有节点一次，就可得出结果的倒叙。反序后再加上0，就为最终答案。对于偶数直接输出-1
正确代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int n; vector<int> dist; bool vis[maxn]; void dfs(int k) { vis[k]=true; if(!vis[(k*2)%n]) dfs((k*2)%n); if(!vis[(k*2+1)%n]) dfs((k*2+1)%n); dist.push_back(k); } int main() { int i,j; cin>>n; vis[0]=true; if(n&1) cout<<"-1"<<endl; else { dfs(0); reverse(dist.begin(),dist.end()); dist.push_back(0); for(i=0;i<dist.size();i++) cout<<dist[i]<<" "; cout<<endl; } return 0; }
