CF1672F2 Checker for Array Shuffling 题解

题目链接

点击打开链接

题目解法

我怎么 F1 都不会做/ll

F1：
由原始值向最终值连边
如果是排列的话，操作次数显然为 \(n-\)环数
拓展到非排列的情况，即相同数之间的下标可以选择顺序，要求分出来的环数最大
直接考虑上面的这东西，让我进入了死胡同。。
先给出一个结论：最大环数的最小值是 出现次数最大值 \(mx\)
证明一下：因为每个环不能包含相同数，所以至少需要 \(mx\) 个环；如果多出一个环，必然由环不经过 \(mx\) 对应的数，这是不优的
构造考虑：把每个位置是从前往后第几个当前数 作为层数，每一层都从小往大连成一个环即可，具体细节见代码：

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=200010;
int a[N],cnt[N];
vector<int> po[N];
void work(){
    int n;read(n);
    F(i,1,n) cnt[i]=0,po[i].clear();
    F(i,1,n) read(a[i]),po[++cnt[a[i]]].pb(i);
    F(i,1,n){
        sort(po[i].begin(),po[i].end(),[&](int x,int y){ return a[x]<a[y];});
        F(j,0,SZ(po[i])-1) swap(a[po[i][j]],a[po[i][j+1]]); 
    }
    F(i,1,n) printf("%d ",a[i]);puts("");
}
int main(){
    int T;read(T);
    while(T--) work();
    return 0;
}

F2：
把出现次数最多的数删掉，然后建图，如果存在环，则 \(wa\)，否则 \(ac\)
因为根据 F1，每个环中一定会包含出现次数最多的数，所以如果有环不包含它的话，那么一定 \(wa\)
时间复杂度 \(O(n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=200010;
int a[N],cnt[N];
vector<int> po[N];
void work(){
    int n;read(n);
    F(i,1,n) cnt[i]=0,po[i].clear();
    F(i,1,n) read(a[i]),po[++cnt[a[i]]].pb(i);
    F(i,1,n){
        sort(po[i].begin(),po[i].end(),[&](int x,int y){ return a[x]<a[y];});
        F(j,0,SZ(po[i])-1) swap(a[po[i][j]],a[po[i][j+1]]); 
    }
    F(i,1,n) printf("%d ",a[i]);puts("");
}
int main(){
    int T;read(T);
    while(T--) work();
    return 0;
}