D - Secret Santa

有 \(n\) 个人，第 \(i\) 个人想给第 \(a_i\) 个人送礼物.

每个人都要恰好收到 1 份礼物 ，每个人不能给自己送东西.

令第 \(i\) 个人最终把礼物送给了 \(b_i\) .

求一种安排人送礼物的方法使得 \(b_i=a_i\) 的数量最多.

\(1\leq t\leq 10^5,\ 1\leq n\leq 2\cdot 10^5,\ \sum n\leq 2\cdot 10^5,\ 1\leq a_i\leq n,\ a_i\not=i\)

首先，对于每个人建两个点 \(i_0,i_1\) ，分别表示送礼物和收礼物.

对于 \(a_i\) ，从 \(i_0\) 向 \({a_i}_1\) 连边.

可以发现，这个图很简单，右侧的一个点会连着多个左侧的点，左侧的点只会连着一个右侧的点 .

考虑将右侧的点每个选择一个左侧的点相连，因此可以最大化 \(b_i=a_i\) 的个数 .

唯一不合法的情况是 \(b_i=i\) .

如果剩下一个及以上左侧&右侧节点，那么必定可以通过某种排列使得 \(b_i\not=i\) .

那么，唯一不合法的情况就是只剩下左侧&右侧节点，其中左侧和右侧都为 \(i\) .

考虑什么时候会出现这种情况.

发现，只有当右侧有连边的节点个数为 \(n-1\) 时才有可能出现，并且其中必定有一个节点度数为 \(2\) 而且度数为 \(2\) 的右侧节点与 \(i\) 有连边.

此时，可以将 \(i\) 连向 \(a_i\) ，剩下另一个节点，其他度数为 \(1\) 的节点均满足. 最后将剩下的点连向 \(i\) .

那么，唯一可能不合法的情况都可以被处理.

对于剩下一个以上的点，找到左侧和右侧都出现的点，如果有两个以上，则可以顺移一位；否则，就只有一个相同的点，带入到所有的点中，顺移一位 . 此时，所有的点都可合法.

题解中给了一种图论的方法，自己暂时还没有想出来.

时间复杂度 ：\(O(n)\)

空间复杂度 ：\(O(n)\)

第一次提交 : Accept

code

#include<bits/stdc++.h>
using namespace std;
int t;
int n,a[200010],b[200010];
bool vis[200010],ok[200010];
vector<int>g[200010];
void solve(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]--;
		g[a[i]].push_back(i);
	}
	int sum=0;
	for(int i=0;i<n;i++)if((int)g[i].size()>0)sum++;
	if(sum==n-1){
		int id;
		for(int i=0;i<n;i++)if((int)g[i].size()==0)id=i;
		b[id]=a[id];
		vis[a[id]]=ok[id]=true;
		for(int i=0;i<n;i++)if(i!=id){
			if(!vis[a[i]]){
				b[i]=a[i];
				ok[i]=vis[a[i]]=true;
			}
		}
		for(int i=0;i<n;i++)if(!ok[i]){
			for(int j=0;j<n;j++)if(!vis[j]){
				b[i]=j;
			}
		}
	}
	else{
		for(int i=0;i<n;i++){
			for(int j=0;j<(int)g[i].size();j++){
				int x=g[i][j];
				b[x]=i;
				ok[x]=true;
				vis[i]=true;
				break;
			}
		}
		vector<int>v;
		for(int i=0;i<n;i++){
			if(ok[i]&&vis[i])continue;
			if(ok[i]==false&&vis[i]==false)v.push_back(i);
		}
		if((int)v.size()!=1){
			for(int i=0;i<(int)v.size();i++){
				b[v[i]]=v[(i+1)%(int)v.size()];
				ok[v[i]]=vis[v[(i+1)%(int)v.size()]]=true;
			}
			vector<int>v1,v2;
			for(int i=0;i<n;i++){
				if(ok[i]==false)v1.push_back(i);
				if(vis[i]==false)v2.push_back(i);
			}
			for(int i=0;i<(int)v1.size();i++)b[v1[i]]=v2[i];
		}
		else{
			vector<int>v1,v2;
			v1.push_back(v[0]);
			v2.push_back(v[0]);
			for(int i=0;i<n;i++){
				if(ok[i]==false&&vis[i]==false)continue;
				if(ok[i]==false)v1.push_back(i);
				if(vis[i]==false)v2.push_back(i);
			}
			for(int i=0;i<(int)v1.size();i++)b[v1[i]]=v2[(i+1)%(int)v2.size()];
		}
	}
	int ans=0;
	for(int i=0;i<n;i++)if(b[i]==a[i])ans++;
	cout<<ans<<endl;
	for(int i=0;i<n;i++)cout<<b[i]+1<<" ";cout<<endl;
	for(int i=0;i<n;i++)ok[i]=vis[i]=false;
	for(int i=0;i<n;i++)g[i].clear();
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

E - Minimax

字符串的前缀数组的第 \(i\) 个代表从第 \(i\) 位开始，可以和 \(s\) 的前缀匹配的最长长度.

给出字符串 \(s\) .

求重构字符串 \(s\) 使得 \(s\) 前缀数组的最大值最小，要求输出字典序最小的一组解.

\(1\leq t\leq 10^5\)

\(1\leq |s|\leq 10^5,\ \sum|s|\leq 10^5\)

首先考虑如何构造使得前缀数组的最大值最小，分情况考虑.

令字符 \(c\) 的出现次数为 \(cnt(c)\) .

• \(s\) 中所有字符相同. 此时无法改变，直接输出.

• \(s\) 中存在两个即以上不同字符.

  • 存在一种字符 \(c\) ，\(cnt(c)=1\)

    字符串首位 \(c\) ，剩余位置字符随便. 最大值为 \(0\) .

  • 对于任意字符 \(c\) , \(cnt(c)>1\) 或者 \(cnt(c)=0\)

    输出其中任意字符 \(c\) ，剩余位置皆放到字符串的尾部，剩余位置随便. 最大值为 \(1\).

现在发现，前缀数组的最小值最大为 \(1\) .

接下来就是要求字典序最小，本体的难度也在于此，情况也更多了.

• \(s\) 中所有的字符相同. 直接输出

• \(s\) 中存在两个及以上不同字符.

  • 存在一种字符 \(c\) , \(cnt(c)=1\)

    找到字典序的字符 \(c\) ，\(cnt(c)=1\) ，放在字符串首位，剩余位置从小到大排序填入.

  • 对于任意字符 \(c\) , \(cnt(c)>1\) 或 \(cnt(c)=0\)

    这个可以分出不少情况. 首先考虑字符串首位填入的字符要字典序尽可能小，那么，就枚举字典序最小的 \(x\) 填入首尾. 接着，我以为必须要在第二位填入和 \(x\) 不同的字符 \(y\) . 其实是不一定的，认真阅读样例，发现如果开头两位为 \(xx\) ，在某些条件下是满足前缀数组的最大值为 \(1\) ，并且 \(xx\) 的字典序要由于 \(xy\) . 分析出现 \(xx\) 需要满足什么条件，首先，对于剩余位置来说，不可能出现连续的两个 \(xx\)，对于剩下的 \(cnt(x)-2\) 个 \(x\) , 考虑交错填，那么，至少需要 \(cnt(x)-2\) 个与 \(x\) 的不同的字符才能满足条件，否则，无法满足. 此时可以分出第一类.

    • \(cnt(x)-2\leq n-cnt(x)\)

      第 \(1\) 位和第 \(2\) 位为 \(x\) ，剩余的 \(x\) 依次填入第 \(4\) 位，第 \(6\) 位，第 \(8\) 位，\(\cdots\)

      剩下的位置按照字典序的大小依次填入

    • \(cnt(x)-2>n-cnt(x)\)

      第二位不能为 \(x\) ，那么考虑第二位为字典序第二小的字符 \(y\)，大概想一下，那么最优的答案为 \(xyxx\cdots xz\cdots\)，在 \(y\) 之后放入 \(x\)，保证字典序最大，但是在最后一个 \(x\) 之后不能放入 \(y\) ，因为要保证字典序最大，此时放入字典序第三大的字符 \(z\) . 那么，就需要 \(cnt(c)>1\) 的字符 \(3\) 种，接下来，就可以又分出两种情况.

      • 出现的字符串种类大于 \(2\) .

        按照 \(xyxx\cdots xz\cdots\) 填，剩余的位置字典序从大到小填.

      • 出现的字符串种类等于 \(2\) .

        按照 \(xyy\cdots yx\cdots x\) 填.

时间复杂度 : \(O(n)\)

空间复杂度 : \(O(n)\)

第一次提交 : Run time error on test 2

code

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
string s;
int cnt[30];
int ans[100010];
void solve(){
	cin>>s;
	n=(int)s.size();
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<n;i++)ans[i]=-1;
	for(int i=0;i<n;i++)cnt[s[i]-'a']++;
	bool flag;
	flag=false;
	for(int i=0;i<26;i++)if(cnt[i]==n)flag=true;
	if(flag){
		cout<<s<<endl;
		return;
	}
	flag=false;
	for(int i=0;i<26;i++)if(cnt[i]==1)flag=true;
	if(flag){
		for(int i=0;i<26;i++)if(cnt[i]==1){
			cout<<char(i+'a');
			cnt[i]--;
			break;
		}
		for(int i=0;i<26;i++){
			for(int j=0;j<cnt[i];j++)cout<<char(i+'a');
		}
		cout<<endl;
		return;
	}
	int x;
	for(int i=0;i<26;i++){
		if(cnt[i]>0){
			x=i;
			break; 
		}
	}
	if(n-cnt[x]>=cnt[x]-2){
		ans[0]=ans[1]=x;
		cnt[x]-=2;
		for(int i=3;i<n;i+=2){
			if(cnt[x]<=0)break;
			ans[i]=x;
			cnt[x]--;
		}
		for(int i=0;i<n;i++){
			if(ans[i]==-1){
				for(int j=0;j<26;j++){
					if(cnt[j]>0){
						cnt[j]--;
						ans[i]=j;
						break;
					}
				}
			}
		}
	}
	else{
		int sum=0;
		for(int i=0;i<26;i++)if(cnt[i]>0)sum++;
		if(sum==2){
			ans[0]=x;cnt[x]--;
			for(int i=n-1;i>=0;i--){
				ans[i]=x;
				cnt[x]--;
				if(cnt[x]==0)break;
			}
			for(int i=0;i<n;i++){
				if(ans[i]==-1){
					for(int j=0;j<26;j++){
						if(cnt[j]>0){
							ans[i]=j;
							cnt[j]--;
							break;
						}
					}
				}
			}
		}
		else{
			ans[0]=x;cnt[x]--;
			int y;
			for(int i=0;i<26;i++){
				if(i!=x&&cnt[i]>0){
					y=i;
					cnt[i]--;
					ans[1]=i;
					break;	
				}
			}
			int j=2;
			for(int i=2;i<n;i++,j++){
				ans[i]=x;
				cnt[x]--;
				if(cnt[x]==0)break;
			}
			j++;
			for(int i=0;i<26;i++){
				if(i!=x&&i!=y&&cnt[i]>0){
					cnt[i]--;
					ans[j]=i;
					break;
				}
			}
			for(int i=0;i<n;i++){
				if(ans[i]==-1){
					for(int j=0;j<26;j++){
						if(cnt[j]>0){
							cnt[j]--;
							ans[i]=j;
							break;
						}
					}
				}
			}
		}
	}
	for(int i=0;i<n;i++)cout<<char(ans[i]+'a');
	cout<<endl;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
/*inline? ll or int? size? min max?*/

Petr ‘ s code

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

// Actual solution is at the bottom

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
//#include "../atcoder/all"

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

using namespace std;

typedef int64_t int64;
typedef pair<int, int> ii;

class EMinimaks {
 public:
  void solveOne() {
    string s;
    cin >> s;
    vector<int> cnt(26);
    for (char c : s) {
      ++cnt[c - 'a'];
    }

    auto dump = [&] {
      for (int j = 0; j < 26; ++j) {
        for (int k = 0; k < cnt[j]; ++k) {
          cout << (char) ('a' + j);
        }
      }
      cout << "\n";
    };
    int nonzero = 0;
    int first = -1;
    int second = -1;
    int third = -1;
    for (int i = 0; i < 26; ++i) {
      if (cnt[i]) {
        ++nonzero;
        if (first < 0) first = i; else if (second < 0) second = i; else if (third < 0) third = i;
      }
      if (cnt[i] == 1) {
        cout << (char) ('a' + i);
        --cnt[i];
        dump();
        return;
      }
    }
    if (nonzero == 1) {
      dump();
      return;
    }
    if (2 * (cnt[first] - 1) <= s.size()) {
      cout << (char) ('a' + first);
      --cnt[first];
      for (int j = first + 1; j < 26; ++j) {
        for (int k = 0; k < cnt[j]; ++k) {
          if (cnt[first] > 0) {
            cout << (char) ('a' + first);
            --cnt[first];
          }
          cout << (char) ('a' + j);
        }
        cnt[j] = 0;
      }
      dump();
      return;
    } else {
      cout << (char) ('a' + first);
      --cnt[first];
      cout << (char) ('a' + second);
      --cnt[second];
      if (third >= 0) {
        for (int k = 0; k < cnt[first]; ++k) {
          cout << (char) ('a' + first);
        }
        cnt[first] = 0;
        cout << (char) ('a' + third);
        --cnt[third];
        dump();
      } else {
        for (int k = 0; k < cnt[second]; ++k) {
          cout << (char) ('a' + second);
        }
        cnt[second] = 0;
        dump();
      }
      return;
    }
  }

  void solve() {
    int nt;
    cin >> nt;
    for (int it = 0; it < nt; ++it) {
      solveOne();
    }
  }
};


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    EMinimaks solver;


    solver.solve();
    return 0;
}

tourist 出的题，de 两题怎么都是分类讨论的题，但是不仅考验思维严谨性，还有代码能力.