A
核心思路：其实就是考察一个muliset的应用，这个和set的区别是它可以储存重复的元素。然后需要注意题目啊，必须得进行m次操作.
#include<iostream>
#include<set>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
void solve()
{
int n, m;
cin >> n >> m;
multiset<int> s;
for (int i = 0;i < n;i++)
{
int x;
cin >> x;
s.insert(x);
}
while (m--)
{
int x;
cin >> x;
s.erase(s.begin());
s.insert(x);
}
LL sum = 0;
for (auto x : s)
sum += x;
cout << sum << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
B
核心思路：这个一个最开始的思路是想先让最大值和最小值相隔k个单位，再让次大值和次小值相隔k个单位、、、、、。其实仔细一想根本没这个必要，我们只需要最大值和最小值交替安排就好了，这种情况肯定是符合的，因为随便你取一段连续的序列那个序列长度都是大于2的。
所以做构造题一定要多构造出几组数据。
#include<iostream>
#include<set>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int a[N];
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 1, j = n;i <= n;i += 2, j--)
a[i] = j;
for (int i = 2, j = 1;i <= n;i += 2, j++)
a[i] = j;
for (int i = 1;i <= n;i++)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
C
核心思路：这个题目是有一定的深度的，首先简化问题：
\(gcd(a_i+x,a_i-a_j)=1\)也就是需要这两个数互质，但是我们可以发现\(t=a_i-a_j\)是一个常数,所以我们可以对t分解质因数，于是整个问题就变成了：\(a_i+x\neq0(\mod p)\),所以就需要x%p!=(p-a%p)%p;
所以我们可以令T=(p-a%p)%p,也就是x的解。我们可以统计使用map统计T的所有可能的解，如果个数是p就说明：
\(x\neq(0,1,....,p-1)\)在%p的前提下，这显然是不可能的。所以这就是无解的情况.
#include<iostream>
#include<set>
#include<cstring>
#include<map>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
#include<random>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
LL a[N];
int primes[N], st[N];
int cnt;
void Init()
{
for (int i = 2;i <= N;i++)
{
if (!st[i])
primes[cnt++] = i;
for (int j = 0;i * primes[j] <= N;j++)
{
st[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
}
void solve()
{
int n;
cin >> n;
map<LL, set<LL>> mp;
for (int i = 1;i <= n;i++)
cin >> a[i];
int success = 1;
for(int i=1;i<=n;i++)
for (int j = i + 1;j <= n;j++)
{
if (a[i] == a[j])
{
success = 0;
}
}
if (!success)
{
cout << "NO" << endl;
return;
}
for (int i = 1;i <= n;i++)
{
set<LL> f;
for (int j = 1;j <= n;j++)
{
if (i == j)
continue;
LL t = abs(a[i] - a[j]);
for (int k = 0;k < cnt;k++)
{
int p = primes[k];
if (t % p == 0)
f.insert(p);
}
}
for (auto x : f)
mp[x].insert(((x - a[i] % x) % x));
}
for (auto p : mp)
{
if (p.first == p.second.size())
{
success = 0;
break;
}
}
cout << (success ? "YES" : "NO") << endl;
}
int main()
{
Init();
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
solve();
}
}
D
核心思路： 这题可以联想图论，虽然这个思路很难想。但是仔细一想好像也是那么回事。因为我们可以通过模拟有样例可以知道，对于\(a[i]和b[i]\),如果不相等的话我们必然可以构造出来\(c_i\)使得选中我们想要的那个数在\(a[i]和b[i]\)之间。
但是我们可以发现选出来的d数组必须还得是一个序列，所以我们就可以联想到\(a_i还与其他几个数存在联系\)，所以这种联系我们可以使用图论表示。
其实我们可以挖掘出几个性质，通过对于\(a[i]和b[i]之间建立边之后\)：
- 如果存在自环的话，那么答案需要乘上n.因为已经不管\(c_i\)什么事了，\(c_i可以随便选\)
- 一个连通块里面只有点数和边数是相等的，才有答案，并且答案需要乘上2.如果两个点之间有重复的边那必然不会相等，也就不会有解.
接下来我们可以使用并查集对这个数据结构进行维护.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const int mod = 998244353;
int fa[N], cnt_v[N], cnt_e[N], selfloop[N];
LL a[N], b[N], n;
int find(int x)
{
if (x != fa[x])
fa[x] = find(fa[x]);
return fa[x];
}
void Init(int n)
{
for (int i = 1;i <= n;i++)
{
fa[i] = i;
cnt_v[i] = 1;
cnt_e[i] = 0;
selfloop[i] = 0;
}
}
void merge(int u, int v)
{
u = find(u);
v = find(v);
cnt_v[u] += cnt_v[v];
cnt_e[u] += cnt_e[v];
selfloop[u] |= selfloop[v];//因为如果某一个有了那么这个连通块肯定也有了
fa[v] = u;
}
void solve()
{
cin >> n;
for (int i = 1;i <= n;i++)
cin >> a[i];
for (int i = 1;i <= n;i++)
cin >> b[i];
Init(n);
for (int i = 1;i <= n;i++)
{
if (find(a[i]) != find(b[i]))
merge(a[i], b[i]);
cnt_e[find(a[i])]++;//自己千万不可以忘了.
if (a[i] == b[i])
selfloop[find(a[i])] = 1;
}
map<int, int> vis;
LL ans = 1;
for (int i = 1;i <= n;i++)
{
if (vis[find(i)])
continue;
if (cnt_e[find(i)] != cnt_v[find(i)])
ans = 0;
if (selfloop[find(i)])
ans = (ans * n) % mod;
else
ans = (ans * 2) % mod;
vis[find(i)] = 1;
}
cout << ans << endl;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}