Good Bye 2022

A.Koxia and Whiteboards

**题目大意: ** 给定一个长度为$n$的序列，接下来进行$m$次操作，问操作之后序列值最大是多少

解题思路: 数量级很小考虑暴力即可，每次把$a$序列中最小的元素换下来

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
const int maxn = 1e6 + 10;
int n,m,a[maxn],b[maxn];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		multiset<int> st;
		for(int i = 1;i <= n;++i) cin >> a[i],st.insert(a[i]);
		for(int i = 1;i <= m;++i) cin >> b[i];
		for(int i = 1;i <= m;++i)
		{
			st.erase(st.begin());
			st.insert(b[i]);
		}
		int sum = 0;
		for(auto to:st) sum += to;
		cout << sum << "\n";
	}
	return 0;
	
}

B. Koxia and Permutation

题目大意: 构造一个长度为$n$的序列，进行$n - k + 1$次划分，第$i$次划分获得的是从$i$开始$k$个数字的最大值和最小值相加，一个排列$p$的代价是划分中的值的最大值，问这个最大值最小的序列是什么样的

解题思路: 因为最后要让我们的最大值最小，考虑值的构成是一个区域内的最大值加上最小值，如果一段区域里面都是连续的大数是肯定不行的，因此我们可以从$1-n$的数字头尾顺序取即可

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
const int maxn = 1e6 + 10;
int n,m,a[maxn],b[maxn];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		vector<int> ans;
		for(int i = 1,j = n;i < j;++i,--j)
		{
			ans.push_back(j);
			ans.push_back(i);
			// cout << "??? " << i << " " << j << "\n";
		}
		if(n & 1) ans.push_back((n + 1) / 2);
		for(auto to:ans)
		{
			cout << to << " ";
		}
		cout << "\n";
	}
	return 0;
	
}

C. Koxia and Number Theory

题目大意: 给定一个长度为$n$的序列,问是否存在一个$x$使得每一对$gcd(a_i+ x ,a_j + x) = 1$

解题思路: 不懂数学，感觉可以看严格鸽的

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
const int maxn = 1e6 + 10;
int n,m,a[maxn],b[maxn];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		set<int> st;
		for(int i = 1;i <= n;++i) cin >> a[i],st.insert(a[i]);
		if(st.size() != n)
		{
			cout << "No\n";
			continue;
		}
		int f = 1;
		for(int p = 2;p <= n;++p)
		{
			map<int,int> mp;
			for(int i = 1;i <= n;++i) mp[a[i] % p]++;
			int mi = n + n;
			int ha = 0;
			for(auto to:mp)
			{
				if(to.second >= 2) ha++;
			}
			if(ha >= p) f = 0;
		}
		if(f) cout << "Yes\n";
		else cout << "No\n";

	}
	return 0;
	
}

D. Koxia and Game

题目大意: 有三个长度为$n$的序列$a,b,c$

$Alice$和$Bob$玩游戏，一共进行$n$个回合，游戏规则如下：

• 选定$a_i,b_i,c_i$
• $Alice$从这三个数字选择一个数字删掉
• $Bob$从这三个数字选择一个数字

我们让$Bob$每回合选择的数字是$d_i$,如果序列$d$是一个排列那么$Alice$获胜否则$Bob$获胜

现在给定$a,b$两个数组，问有多少个$c$数组可以使得$Bob$获胜，结果对$998244353$取模

解题思路: 首先我们先考虑$Alice$会选择什么数字删掉，假设对于第$i$次操作来说，$a_i = b_i$,那么我们可以选择任意的$c_i$并且最终把$c_i$删掉，这样子$Bob$一定取到的是$a_i$这个数字表示的值(因为$a_i = b_i$)

然后我们考虑如果$a_i \neq b_i$那么我们选择的$c_i$就非常重要，因为$c_i$决定着我们可以选择$a_i$或者$b_i$中的哪个数字，只需要让$c_i = a_i \ or \ c_i = b_i$即可

那么选择某一个位置的思路就很清晰了，我们只需要考虑构造大于等于两个相同的并且把其中一个不需要的值删掉即可

接下来我们再考虑位置之间带来的因素

假设我们没有$a_i = b_i$的情况，那么我们现在的问题可以转换为给定两个序列分别是$a,b$，每个位置上面取一个看是否可以构成一个排序

对于这一个问题来说，因为每一个位置做一个选择，同时也相同与每一个位置的两个数字相互制衡，那么我们可以用图论的语言来表达，在他们之间建一条边

我们可以发现只有基环树的形式是可以的，而基环树的形式实际上就是点数等于边数

那么我们最终只需要使用并查集取维护每个环中存在点数和边数即可

那么最后再思考答案贡献，对于一个基环树来说，如果这个树里面没有自环，那么贡献就是$2$，因为考虑每条边有两个选择，如果里面有自环的话，贡献就是$n$

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
const int maxn = 1e6 + 10;
const int mod = 998244353;
int n,m,a[maxn],b[maxn];
int f[maxn],szv[maxn],sze[maxn],loop[maxn];
void init()
{
	for(int i = 1;i <= n;++i)
	{
		f[i] = i;
		szv[i] = 1;
		sze[i] = 0;
		loop[i] = 0;
	}
}
int getf(int x)
{
	return x == f[x] ? x : f[x] = getf(f[x]);
}
void merge(int x,int y)
{
	int fx = getf(x);
	int fy = getf(y);
	if(fx != fy)
	{
		f[fy] = fx;
		sze[fx] += sze[fy];
		szv[fx] += szv[fy];
		loop[fx] += loop[fy];
	}
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		init();
		for(int i = 1;i <= n;++i) cin >> a[i];
		for(int i = 1;i <= n;++i) cin >> b[i];
		for(int i = 1;i <= n;++i)
		{
			merge(a[i],b[i]);
			sze[getf(a[i])]++;
			if(a[i] == b[i]) loop[getf(a[i])]++;
		}
		int ans = 1;
		for(int i = 1;i <= n;++i)
		{
			if(i == getf(i))
			{
				if(sze[i] != szv[i]) ans = 0;

                else ans = ans * 2 % mod;
			}
		}
		cout << ans << "\n";
	}
	return 0;
	
}