CF1833 A-E

A题

题目链接：https://codeforces.com/problemset/problem/1833/A

基本思路：for循环遍历字符串s，依次截取字符串s的子串str，并保存到集合中，最后输出集合内元素的数目即可

AC代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
typedef long long ll;
typedef long double db;
void solve()
{set<string>st;int n;cin >> n;string s;cin >> s;for (int i = 0; i < n - 1; i++){string str = s.substr(i, 2);st.insert(str);}cout << st.size() << endl;
}
int main()
{int t;cin >> t;while (t--){solve();}return 0;
}

 B题

题目链接：https://codeforces.com/problemset/problem/1833/B

 基本思路：可以使用结构体与快速排序来解题。第一，用结构体p来存储数组a和其对应的原始位置id，并为数组b预留出变量c这个位置。第二，先对结构体进行排序，若a的值相同则id小的排在前面。第三，对数组b进行排序。第四，讲排序后的数组b的值依次赋值给结构体中的变量c。最后，将结构体根据id恢复其原来的排序，最后使用for循环遍历，依次输出c即可。

AC代码：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double db;
ll b[100005];
struct nodes
{ll a;int id;ll c;
}p[100005];
bool cmp(nodes x, nodes y)
{if (x.a == y.a)return x.id < y.id;return x.a < y.a;
}
bool kmp(nodes x, nodes y)
{return x.id < y.id;
}
void solve()
{int n, k;cin >> n >> k;for (int i = 1; i <= n; i++){cin >> p[i].a;p[i].id = i;}for (int i = 1; i <= n; i++){cin >> b[i];}sort(p + 1, p + 1 + n, cmp);sort(b + 1, b + 1 + n);for (int i = 1; i <= n; i++)p[i].c = b[i];sort(p + 1, p + 1 + n, kmp);for (int i = 1; i <= n; i++)cout << p[i].c << " ";cout << endl;
}
int main()
{int t;cin >> t;while (t--){solve();}return 0;
}

C题

题目链接：https://codeforces.com/problemset/problem/1833/C

基本思路：因为奇数与奇数相减为偶数，偶属于偶数相减为偶数，奇数与偶数相减只能为奇数。所以，想要数组a变成全是偶数或者全是奇数的序列（序列有奇有偶），奇数的最小值必须比偶数的最小值小，整个序列才可以变为全奇数的序列（不可能变成全偶数）。

AC代码：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double db;
int a[200005];
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];int ou = 0, ji = 0, minou = 1e9, minji = 1e9;for (int i = 1; i <= n; i++){if (a[i] & 1){ji++;minji = min(minji, a[i]);}else{ou++;minou = min(minou, a[i]);}}if (ji > 0 && ou > 0 && minou < minji){cout << "NO" << endl;}else{cout << "YES" << endl;}
}
int main()
{int t;cin >> t;while (t--){solve();}return 0;
}

D题

题目链接：https://codeforces.com/problemset/problem/1833/D

基本思路：因为要获得操作之后字典序最大的排列，所以，我们要想方设法地将p[2]到p[n]之间最大的数maxx放到最前面。我们不妨设置low和high两个左右指针。当p[n]==maxx时，high指向p[n],

当的时候，high指向maxx的前一个元素。再设置一个指针op指向p[1]，因为在将low到high之间的元素转换之后，low左边的元素会转移到后方。因此，为了使操作完成之后的排列尽可能地大，我们可以先将low指向high，如果p[low-1]>p[op],则将low指针左移，这样便可保证操作之后的排列的字典序最大。

AC代码：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double db;
int p[2005];
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++)cin >> p[i];int maxx = n;if (p[1] == maxx){maxx--;}if (p[n] == maxx){int op = 1, low = n, r = n;while (p[low - 1] > p[op])low--;for (int i = r; i >= low; i--)cout << p[i] << " ";for (int i = 1; i < low; i++)cout << p[i] << " ";cout << endl;return;}int r = 1;for(int i=1;i<=n;i++)if (p[i] == maxx){r = i - 1;break;}int op = 1, low = r;while (p[low - 1] > p[op])low--;for (int i = r + 1; i <= n; i++)cout << p[i] << " ";for (int i = r; i >= low; i--)cout << p[i] << " ";for (int i = 1; i < low; i++)cout << p[i] << " ";cout << endl;
}
int main()
{int t;cin >> t;while (t--){solve();}return 0;
}

E题

题目链接：https://codeforces.com/problemset/problem/1833/E

基本思路：可以使用并查集来求解。用并查集将其分为多少个组，最大值便是多少。因为每两个度为1的点可以合成一块，所以用变量ans来统计一下度为1的点，最后计算得到最小值的数量：

AC代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int, int>pii;
map<pii, bool>mp;
int f[200005], a[200005], du[200005];
int find(int x)//并查集认爹函数+路径压缩
{if (x != f[x])f[x] = find(f[x]);return f[x];
}
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}mp.clear();for (int i = 1; i <= n; i++){f[i] = i;du[i] = 0;}for (int i = 1; i <= n; i++){if (mp[{i, a[i]}] == false && mp[{a[i], i}] == false){du[a[i]]++;du[i]++;f[find(i)] = find(a[i]);mp[{i, a[i]}] = true;mp[{a[i], i}] = true;}}int maxx = 0, ans = 0;for (int i = 1; i <= n; i++){if (find(i) == i)maxx++;if (du[i] == 1)ans++;}int minn = min(maxx, maxx - ans / 2 + 1);cout << minn << " " << maxx << endl;
}
int main()
{int t;cin >> t;while (t--){solve();}return 0;
}