NOI2009变换序列
Description
Input
Output
Sample Input
5
1 1 2 2 1
1 1 2 2 1
Sample Output
1 2 4 0 3
HINT
30%的数据中N≤50；
60%的数据中N≤500；
100%的数据中N≤10000。
题解
byvoid大神：https://www.byvoid.com/blog/noi-2009-transform/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int d[10005],lk[10005],ans[10005]; bool vis[10005]; vector<int>e[10005]; int dis(int x,int y) { return min(abs(x-y),n-abs(x-y)); } bool find(int x) { for(int i=0;i<e[x].size();i++) if(!vis[e[x][i]]) { vis[e[x][i]]=1; if(lk[e[x][i]]==0||find(lk[e[x][i]])) { lk[e[x][i]]=x; return 1; } } return 0; } int main() { n=read(); for(int i=0;i<n;i++)d[i]=read(); for(int i=0;i<n;i++) { int x=i+d[i],y=i-d[i]+n; x%=n;y%=n; if(dis(x,i)!=d[i])x=-1; if(dis(y,i)!=d[i])y=-1; if(x>y)swap(x,y); if(x!=-1)e[i].push_back(x); if(y!=-1)e[i].push_back(y); } for(int i=n-1;i>=0;i--) { memset(vis,0,sizeof(vis)); if(!find(i)) { puts("No Answer"); return 0; } } for(int i=0;i<n;i++)ans[lk[i]]=i; for(int i=0;i<n-1;i++)printf("%d ",ans[i]); printf("%d\n",ans[n-1]); return 0; } |
Subscribe
计数器 9787360
OI 课件=>
OI 课件=>