XCPC Notes

Appearance

发布时间：2023-09-19

模型 ​

此类问题大多与拓扑序有关，可以拆成三种集合，环，环上带若干条链(基环树)，单条链(只有点数n>边数m存在)

例题 ​

F. Selling a Menagerie ​

题意：
c[i]表示i的价值，当i在a[i]前面出现时，i的贡献价值为2*c[i]，否则为c[i],求一个顺序使总价值最大，所有a[i],i<=n
思路：
i向a[i]连边,先做个拓扑序,剩下还有数说明有环，在环内找出最小的c[i],当前i在该环排最后即可(题目中集合可分为三种：1.单个环，2.单条边，3.一个环和若干条指向它的边（环指向边不可能存在）)

cpp
void solve(){
	int n;
	cin>>n;
	vector<int> a(n+1),c(n+1),deg(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		deg[a[i]]++;
	}
	for(int i=1;i<=n;i++)cin>>c[i];
	vector<int> ans;
	vector<bool> vis(n+1);
	auto dfs=[&](auto self,int u)->void{
		if(--deg[a[u]]==0&&!vis[a[u]]){
			vis[a[u]]=1;
			ans.pb(a[u]);
			self(self,a[u]);
		}
	};
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		if(deg[i]==0){
			vis[i]=1;
			ans.pb(i);
			dfs(dfs,i);
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		vector<int> b,C;
		for(int j=i;!vis[j];j=a[j]){
			b.pb(j);
			C.pb(c[j]);
			vis[j]=1;
		}
		int p=min_element(all(C))-C.begin();
		for(int j=0;j<b.size();j++){
			ans.pb(b[(j+1+p)%b.size()]);
		}
	}
	for(auto it:ans)cout<<it<<" ";
	cout<<"\n";
}

D. Cyclic Operations ​

题意：
给定数组n初始化为0，另外一个数组a(每个数都小于等于n)，和整数k；可以进行无数次下列操作：

  • 做一个数组长度为k， [b1,b2,b3,...,bk][b_1,b_2,b_3,...,b_k], abi=ab(i+1)mod(n+1)a_{b{i}}=a_{b_{(i+1)mod(n+1)}}

可以使数组等于数组a
思路： 连边 i→aii \to a_i,对于每个集合中的环的个数必须等于k，否则输出NO，连在环上的链可以通过环(在环内再进行一次循环)，消除影响；当k=1时单独考虑，此时不能存在边，必须每个元素自环

cpp
void solve(){
	int n,m;
	cin>>n>>m;
	vector<int> a(n+1),deg(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		deg[a[i]]++;
	}
	if(m==1){
		for(int i=1;i<=n;i++){
			if(a[i]!=i){
				cout<<"NO\n";
				return;
			}
		}
		cout<<"YES\n";
		return;
	}
	vector<bool> vis(n+1);
	auto dfs=[&](auto self,int x)->void{
		if(--deg[a[x]]==0&&!vis[a[x]]){
			vis[a[x]]=1;
			self(self,a[x]);
		}
	};
	for(int i=1;i<=n;i++){
		if(deg[i]==0&&!vis[i]){
			vis[i]=1;
			dfs(dfs,i);
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		int cnt=1;
		vis[i]=1;
		for(int j=a[i];!vis[j];j=a[j]){
			vis[j]=1;
			cnt++;
		}
		if(cnt!=m){
			cout<<"NO\n";
			return;
		}
	}
	cout<<"YES\n";
}

置换环 ​

  • i−>a[i]i->a[i]连边
  • 每个环变为正序的操作数为siz环−1每个环变为正序的操作数为siz_环-1
  • 总操作数为n−cnt环总操作数为n-cnt_环
  • 在置换环中，总有一种方法，用一次调换两个元素，使得一个元素自环，其他成环在置换环中，总有一种方法，用一次调换两个元素，使得一个元素自环，其他成环

CF1768D Lucky Permutation ​

求只有一个逆序对的最小操作数 若相邻两数在一个环中，操作数减1，否则加1

map<int,bool> mp;
int cnr;
bool flag;
void dfs(int u){
	if(vis[u])return;
	vis[u]=1;
	mp[u]=1;
	int v=a[u];
	if(mp[u-1]||mp[u+1])flag=1;
	dfs(v);
}
signed main(){
	cin>>t;
	while(t--){
		memset(vis,0,sizeof(vis));
		cur=0,flag=0;
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				cur++;
				mp.clear();
				dfs(i);		
			}
		}
		if(flag)cout<<n-cur-1<<"\n";
		else cout<<n-cur+1<<"\n";
	}
}

CF1677C ​

题意：
给定一个序列a,b,需要构造一个数组nums,每次赋值若a[i]==b[i]==x，则需满足nums[a[i]]==nums[b[i]],最大化∑i=nN∣nums(i+1)%n−numsi∣\sum_{i=n}^N |nums_{(i+1)\%n}-nums_{i}|
思路：

  • 容易想到ai→bia_i \to b_i 连边，形成若干个环
  • 对于每个环的赋值,贪心的话肯定是一大一小放,但是这有个问题如果是奇数环,则最后填的数是不会影响整个环的贡献的,如果继续贪心选，那么当前这个数在下一个环中可能会有更大贡献，这就导致答案不对(比如当前最后一个奇数位置选了6 ，然后下一个环选5 2;但是如果当前不选6，则下一个环的贡献为6 2明显更优),因此对于每个奇数环，都减1让它变成偶数环，直接模拟即可
  • 进一步发现，定义山峰为a[i-1]<=a[i]>=a[i+1],山谷为a[i-1]>=a[i]<=a[i+1],其他为山坡,设当前位置数字为x，有以下贡献
    • 2⋅x,山峰∣ai−ai−1∣+∣ai+1−ai∣=2∗ai−()2 \cdot x ,山峰 |a_i-a_{i-1}|+|a_{i+1}-a_i|=2*a_i-()
    • −2⋅x,山谷∣ai−ai−1∣+∣ai+1−ai∣=()−2∗ai-2 \cdot x,山谷|a_i-a_{i-1}|+|a_{i+1}-a_i|=()-2*a_i
    • 0山坡∣ai−ai−1∣+∣ai+1−ai∣=()符号相反所以抵消0 山坡|a_i-a_{i-1}|+|a_{i+1}-a_i|=()符号相反所以抵消 因此只需计算山峰(山坡大小),设大小为a，则由等差数列公式可推出答案为2a(n−a)2a(n-a)

P6193 [USACO07FEB] Cow Sorting G ​

题意：
给定长度为n的数组，交换X和Y的代价为X+Y，问变为正序的最小花费
思路：

  • 看到排序升序，最小交换花费(次数),想到置换环
  • 题目所给的序列并不是permulation,因此使用置换环就需要离散化
  • 对于每个环，因为每次操作都可以让一个元素自环(还原到排序后的位置),因此可以顺着环的最小数字走，则除了最小数字其他数字只贡献一次，而最小数字贡献次数为交换次数
  • 但这并不一定最优，当环中最小数很大时，先将环的最小数与整个序列的最小数换一下，将环中元素排好后再换回来
  • 因此取上面两种情况的min值
cpp
struct node{
    int val;
    int pos;
    bool operator<(const node&tmp)const{
        return val<tmp.val;
    }
};
struct M{
    int val,x;
};
void solve(){
    int n;
    cin>>n;
    vector<int> adj(n+1),vis(n+1);
    vector<node> e(n+1);
    vector<M> a(n+1); 
    for(int i=1;i<=n;i++){
        cin>>e[i].val;
        e[i].pos=i;
    }
    sort(e.begin()+1,e.end());
    for(int i=1;i<=n;i++){
        a[e[i].pos].val=i;
        a[e[i].pos].x=e[i].val;
    }
    for(int i=1;i<=n;i++){
        adj[i]=a[i].val;
    }
    //for(int i=1;i<=n;i++)cout<<adj[i]<<" \n"[i==n];
    int cnt=0,ans=0;
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        int x=i;
        int d1=1e15,sum=0;
        int c=0;    
        while(!vis[x]){
            vis[x]=1;
            c++;
            sum+=a[x].x;
            //cout<<sum<<"\n";
            d1=min(d1,a[x].x);
            x=adj[x];
            //cout<<x<<" ";
        }
        if(c==1)continue;
        //cout<<sum<<" "<<d1<<"\n";
        sum-=d1;
        c--;
        int res1=sum+c*d1;
        int res2=1e15;
        if(d1!=e[1].val)res2=(d1+e[1].val)*2+sum+c*e[1].val;
        ans+=min(res1,res2);
    }
    cout<<ans<<"\n";
}

CF1690F Shifting String ​

给定一个字符串s和序列，每次操作，当前位置i的字符会换成a[i]位置的字符,求最小操作数使其还原
思路：

  • 很明显也是一个置换环的题型
  • 对于单个环来讲
    • 如果环内元素都不相同，那么此时最小操作数就是环数
    • 如果环内元素有相同的，那么就不一定了，因为n=200所以可以暴力 O(n2)O(n^2) 判断
  • 总操作数就是所有环的操作数的最小公倍数
  • 总复杂度:O(n3logn)O(n^3logn)
cpp
void solve(){
    int n;
    string s;
    cin>>n>>s;
    s=" "+s;
    vector<int> adj(n+1),a(n+1);
    vector<bool> vis(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        adj[i]=a[i];
    }
    ll ans=1;
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        int x=i;
        ll cnt=0;
        string tmp="";
        while(!vis[x]){
            vis[x]=1;
            tmp+=s[x];
            cnt++;
            x=adj[x];
        }
        ll res=0;
        for(int len=1;len<=cnt;len++){
            string c="";
            for(int j=len,k=1;k<=cnt;k++,j++)c+=tmp[j%cnt];
            if(c==tmp){
                res=len;
                break;
            }
        }
        ans=ans*res/__gcd(ans,res);
    }
    cout<<ans<<"\n";
}

Wenwei Lin · 2022 — 2025