首页 > 代码库 > Codeforces Good Bye 2014 B. New Year Permutation
Codeforces Good Bye 2014 B. New Year Permutation
这道题我一开始的想法是：把每个需要交换的都交换了，循环n次肯定就是结果，n又比较小不会超时。但是这种想法too young，因为它无法交换需要间接交换的两个数。
所以一种正确解法是：找出能间接交换的所有i和j，把对应的A[i][j]=A[j][i]=‘1‘，之后只需扫一遍整个矩阵把要换的换了就是最终结果啦。
#include <bits/stdc++.h>using namespace std;const int N = 1010;int n , a[N] , A[N][N];string s ;int main(){ cin >> n; for( int i = 1 ; i <= n ; ++i ) cin >> a[i]; for( int i = 1 ; i <= n ; ++i ) { cin >> s ; for( int j = 0 ; j < n ; ++j ) { if( s[j] == ‘1‘ ) A[i][j+1] = 1 ; else A[i][j+1] = 0 ; } } for( int i = 1 ; i <= n ; ++i ) { for( int j = 1 ; j <= n ; ++j ) { if( A[j][i] == 0 ) continue ; for( int k = 1 ; k <= n ; ++k ) { if( A[i][k] ) A[j][k] = 1 ; } } } for( int i = 1 ; i <= n ; ++i ) { for( int j = i + 1 ; j <= n ; ++j ) { if( A[i][j] && a[i] > a[j] ) swap( a[i] , a[j] ); } } for( int i = 1 ; i <= n ; ++i ) cout << a[i] << " ";}
另外一种解法：两个数能不能交换是二元关系，这样的关系往往可以用图建模来分析，何况给的矩阵多像邻接矩阵丫。。用并查集找出联通块，一块之内元素可以随便交换次序，每一块排好之后在输出就行了。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=300+10;int n,a[maxn],cnt[maxn],group[maxn];vector<int>v[maxn];char A[maxn][maxn];int f(int i){ return i==group[i]?i:(group[i]=f(group[i]));}void merge_(int i,int j){ /*if(f(i)!=f(j)) { group[i]=j; }*/ i=f(i); j=f(j); if(i!=j) group[i]=j; /*上面错误的原因是：合并操作时i和j还是没变，所以那么 赋值就是把i合并到j所在的集合里，而i原本所在的集合并没有 和j所在的集合合并。*/}int main(){ //freopen("in2.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); group[i]=i; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cin>>A[i][j]; } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { if(A[i][j]==‘1‘) { merge_(i,j); } } } for(int i=1;i<=n;i++) { v[f(i)].push_back(a[i]); } for(int i=1;i<=n;i++) { sort(v[i].begin(),v[i].end()); } for(int i=1;i<=n;i++) { printf("%d ",v[f(i)][cnt[f(i)]++]); } //fclose(stdin); //fclose(stdout); return 0;}
Codeforces Good Bye 2014 B. New Year Permutation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。