首页 > > 程序设计 > C/C++ >

BZOJ [NOI2009]变换序列

2018-06-17 21:02:53来源：未知阅读 ()

1562: [NOI2009]变换序列

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 2139 Solved: 1079
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

5
1 1 2 2 1

Sample Output

1 2 4 0 3

HINT

30%的数据中N≤50；
60%的数据中N≤500；
100%的数据中N≤10000。

Source

[Submit][Status][Discuss]

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=10000+5;
 4 
 5 bool vis[maxn];
 6 int a,n;
 7 int whi[maxn],p[maxn][2];
 8 int w[maxn];
 9 
10 bool dfs(int x)
11 {
12     if(x==-1)
13         return false;
14     for(int i=0;i<2;i++)
15     {
16         if(!vis[p[x][i]])
17         {
18             vis[p[x][i]]=true;
19             if(whi[p[x][i]]==-1||dfs(whi[p[x][i]]))
20             {
21                 w[x]=p[x][i];
22                 whi[p[x][i]]=x;
23                 return true;
24             }
25         }
26     }
27     return false;
28 }
29 
30 int main()
31 {
32     scanf("%d",&n);
33     for(int i=0;i<n;i++)
34     {
35         scanf("%d",&a);
36         p[i][0]=min((a+i)%n,(n-a+i)%n);
37         p[i][1]=max((a+i)%n,(n-a+i)%n);
38     }
39     memset(whi,-1,sizeof whi);
40     for(int i=n-1;i>=0;i--)
41     {
42         memset(vis,false,sizeof vis);
43         if(!dfs(i))
44         {
45             printf("No Answer\n");
46             return 0;
47         }
48     }
49     for(int i=0;i<n;i++)
50     {
51         if(i==n-1)
52             printf("%d\n",w[i]);//这个鬼畜输出害我半天格式错误，最后一个输出不能有空格！ 
53         else
54             printf("%d ",w[i]);
55     }
56     return 0;
57 }