Contestant'. Rank 847. Rating +31(+81 -50).又一次成为痛苦号（
A. Musical Puzzle
题意
给定一个字符串，输出所有相邻两个字符组成的不同字符串的个数。
思路
如题，用 \(map\) 即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7;
void solve(){
int n;
cin >> n;
string s;
cin >> s;
map<string, int> cnt;
for(int i=0;i<n - 1;i++){
cnt[to_string(s[i]) + s[i + 1]] ++;
}
cout << cnt.size() << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}题目看半天才看懂，淦
B. Restore the Weather
题意
给定 \(n\) 天的实际温度和预估温度，其中，实际温度按天升序给出，预估温度打乱顺序后给出。
给定整数 \(k\)，满足每一天的实际温度和预估温度的差的绝对值不超过 \(k\)，输出任意一种满足条件的预估温度的排列。
其中，满足一定有解。
思路
\(k\) 是没有用的。
为何呢？因为满足一定有解，我们升序排序后，依次配对即可，这样就可以让每天的差值最小。
注意配对的时候下标变化。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7;
void solve(){
int n, k;
cin >> n >> k;
vector<pii> a(n);
vector<int> b(n);
for(int i=0;i<n;i++){
cin >> a[i].fs;
a[i].sc = i;
}
for(int i=0;i<n;i++) cin >> b[i];
sort(all(a)), sort(all(b));
vector<int> w(n);
for(int i=0;i<n;i++) w[a[i].sc] = i;
for(int i=0;i<n;i++){
cout << b[w[i]] << ' ';
}
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}注意下标的变换，不要绕晕（
C. Vlad Building Beautiful Array
题意
给定一个序列 \(a\)，定义序列 \(b\) 中 \(b_i\) 为 \(a_i\) 和 \(a_i - a_j\) 中任选其一，其中 \(j \in [1, n]\) 可任意选择。
输出能否构造一个奇偶性相同的正整数序列 \(b\)。
思路
首先，既然要满足所有元素都是正整数，那么我们升序排序一下。
那么，对于 \(a_i - a_j\)，\(j \in [1, i - 1]\)。
考虑用 \(a_1\) 作为 \(b_1\)，那么如果 \(a_1\) 是奇数，我们一定可以将剩余不是奇数的 \(a_i\) 变为奇数。
如果 \(a_1\) 是偶数，那么其他元素都不可以是奇数，因为我们没办法改变 \(a_1\) 的奇偶性，而奇数减偶数还是奇数。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7;
void solve(){
int n;
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(all(a));
for(int i=1;i<n;i++){
if(a[i] % 2 != a[0] % 2 && (a[i] - a[0]) % 2 != a[0] % 2){
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}搓题解的时候才发现下标居然打错了，还没被fst(((
D. Flipper
题意
给定一个序列 \(a\)，定义操作为选定一个区间 \([l, r]\)，其中 \(1 \leq l \leq r \leq n\)，将整个区间翻转，并将剩余两侧的元素换个位置。
输出操作后最大字典序的序列。
思路
首先，不难发现的是，第一个元素在操作后一定不会在第一个位置，除非只有一个元素。
考虑到字典序的贪心性：如果某一位的两个元素能判定大小，后面的元素都不用考虑。
那么，我们就希望尽可能将最大的元素放在第一位。
由上分析，我们从第二个元素开始，找出最大的元素，并从这个元素开始，将之后的元素全都放到答案的开头。
如上，比对 \(2\ 3\ 1 \ 5\ 4\)，\(5\ 4\) 将会放在答案的开头。
其次，区间内一定有一个元素，那么最大的元素的前一个元素一定会在区间中，比如说上述例子的 \(1\) 一定包含在区间中。
接下来我们来考虑左端点的选择：
我们从最大的元素前面的第 \(2\) 个元素开始向前遍历，不难发现我们会按照这个倒序的顺序继续将元素放入答案中，而剩余的元素是按原顺序从序列的开头开始放入的。
因此，我们只需比较当前遍历到的元素是否大于序列中的第一个元素，如果小于，因为我们需要把大的元素放入答案，所以区间就不会覆盖这个元素，我们也就确定了所需的区间。
形象地说，如果剩余的序列是 \(4, 5, 1, 9, 8\)，因为 \(8 > 4, 9 > 4, 1 < 4\)，所以我们选择 \(9, 8\) 作为区间翻转，\(4, 5, 1\) 按顺序放入，得到 \(8, 9, 4, 5, 1\)。
由上，我们会发现第二个样例过不去。
为何呢？因为区间右端点可以是 \(n\)，那么可以等效于将区间内的元素翻转并将前面剩余的拼到后面。
那么，如果最大值在最后一个元素，显然我们会出现两个选择：
区间右端点为 \(n\)；
区间右端点为 \(n - 1\)
也就是说，第二个样例对应的选择是第一个，此时就出现了 \(3 < 4\) 的比较，从而得到了答案。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<int> a(n);
int mx = 1;
for(int i=0;i<n;i++) {
cin >> a[i];
if(i > 0 && a[i] > a[mx]) mx = i;
}
for(int i=mx;i<n;i++) cout << a[i] << ' ';
int dist = mx - 1 - (mx == n - 1 ? 0 : 1);
for(;dist>=0;dist--){
if(a[dist] < a[0]) break;
}
dist = max(dist, 0ll);
for(int i=mx-1;i>dist;i--) cout << a[i] << ' ';
for(int i=0;i<=dist;i++) cout << a[i] << ' ';
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}WA on 1.
E. Round Dance
题意
给定 \(n\) 个人，每个人的左右分别有一个邻居（可以是同一个邻居）。每个人只记得自己的一个邻居，并只能和自己的邻居一起跳舞。
令两个跳舞的人之间连一条边，那么如果出现了环，就视为一个 "Round Dance"。
输出 "Round Dance" 的最小和最大个数。
思路
我们将每个人记得的那个邻居之间连一个无向边，构成一个不完全联通的无向图，那么我们可以得到几个连通块。
对照题给条件，既然一个人只能有两个邻居，那么很明显，连通块要么是一整个环，要么是只含有 由两个元素组成的环 的基环树。
如果连通块为一整个环，那么显然这个环中每个人的邻居都是唯一确定的，肯定只能单独作为一个 "Round Dance"。
如果为一个基环树，那么我们一定可以找到一个只确定了一个邻居的人，并把多出的边和他连起来；我们也可以和其他的基环树相连，构成一条链。
因此，最小值就是整环的个数 \(+1\) 并与最大值取最小值，最大值就是连通块的个数。
为了方便遍历，在计算最小值的时候，不妨建一个有向图。
p.s. 这题可以用并查集完成。
时间复杂度：\(O(m)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<set<int>> e1(n + 1, set<int>()), e2(n + 1, set<int>());
for(int i=1;i<=n;i++){
int cur;
cin >> cur;
e1[i].emplace(cur);
e2[i].emplace(cur);
e2[cur].emplace(i);
}
int mn = 0, mx = 0;
vector<bool> st1(n + 1);
auto dfs1 = [&](auto self, int start, int x, int p, int step) -> bool{
bool res = false;
for(auto t : e1[x]){
if(t == p) continue;
if(st1[t]){
if(t == start && step > 2) res = true;
continue;
}
st1[t] = true;
if(self(self, start, t, x, step + 1)) res = true;
}
return res;
};
for(int i=1;i<=n;i++){
if(st1[i]) continue;
st1[i] = true;
if(dfs1(dfs1, i, i, -1, 1)) mn ++;
}
vector<bool> st2(n + 1);
auto dfs2 = [&](auto self, int x, int p) -> void{
for(auto t : e2[x]){
if(t == p || st2[t]) continue;
st2[t] = true;
self(self, t, x);
}
};
for(int i=1;i<=n;i++){
if(st2[i]) continue;
st2[i] = true;
dfs2(dfs2, i, -1);
mx ++;
}
cout << mn + (mn == mx ? 0 : 1) << ' ' << mx << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}好久没有出图论题了（
E. Ira and Flamenco
题意
给定一个多重集，以及一个整数 \(m\)，输出从多重集中取出 \(m\) 个不同的元素且任意两个元素的差的绝对值都小于 \(m\) 的方案数。
思路
首先，要满足差值的绝对值小于 \(m\)，我们就需要满足最大值和最小值的差小于 \(m\)。
因此，我们不妨遍历最左边的元素，并以这个元素确定当前能取的元素的范围，然后用组合数求解即可。
当然，这里需要取不同的元素，我们可以用下面的结论：
从一个含 \(n\) 个不同元素的多重集中取 \(m\) 个不同元素的组合数，可以看作从 \(n\) 个不同元素中取 \(m\) 个元素的组合数，再乘以每个元素出现的次数的乘积，即：\(\binom{n}{m} \times \prod_{i=1}^{n}a_i\) 。
对于范围的确定，我们既可以用滑动窗口，也可以用二分。
组合数需要 \(O(1)\) 计算，因而需要预处理。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
int fact[N], fact_inv[N];
int qp(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
int inv(int n) {
return qp(n, mod - 2);
}
int C(int n, int m){
return (fact[n] * fact_inv[n - m] % mod) * fact_inv[m] % mod;
}
void init(){
fact[0] = fact_inv[0] = 1;
for(int i=1;i<=2e5;i++){
fact[i] = fact[i - 1] * i % mod;
fact_inv[i] = inv(fact[i]);
}
}
void solve(){
int n, m;
cin >> n >> m;
vector<int> a(n + 1, inf);
map<int, int> cnt;
for(int i=0;i<n;i++) cin >> a[i], cnt[a[i]] ++;
sort(all(a));
a.resize(n = unique(all(a)) - a.begin());
vector<int> prod(n);
prod[0] = cnt[a[0]];
for(int i=1;i<n;i++) prod[i] = prod[i - 1] * cnt[a[i]] % mod;
int ans = 0;
for(int i=0;i<n;i++){
int k = lower_bound(all(a), a[i] + m) - a.begin() - 1;
if(k - i < m - 1) continue;
ans = (ans + cnt[a[i]] * C(k - i, m - 1) % mod * prod[k] % mod * inv(prod[i]) % mod) % mod;
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while(t --) solve();
}这个结论有点抽象
G. Ksyusha and Chinchilla
题意
给定一棵树，将其切割为若干个 三个元素组成的链（如下图），输出切割方案，如果无法切割输出 \(-1\)。
思路
首先，既然要让切割尽可能方便，我们肯定会去切割掉连接点尽可能少的边。
因此，我们不妨从叶节点开始向上遍历，找到含有三个元素的父节点，并砍掉父节点上面的边。
这个过程可以用树型 \(dp\) 实现。
具体来说，我们从任意一个顶点开始 \(dfs\)，在 \(dp\) 的过程中，传递需要从哪条边到达这个点。
那么，如果出现值为 \(3\) 的情况，我们就把传递过来的这条边砍掉，并把这个点的 \(dp\) 值改为 \(0\)。
因而，只要出现值大于 \(3\) 的情况，我们就割不了了。
当然，我们可以一开始预判一下点数是否是 \(3\) 的倍数，不然肯定有多出来的点。
时间复杂度：\(O(n + m)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<vector<pii>> e(n + 1);
for(int i=1;i<n;i++){
int u, v;
cin >> u >> v;
e[u].pb(v, i), e[v].pb(u, i);
}
if(n % 3 != 0){
cout << -1 << '\n';
return;
}
vector<bool> st(n + 1);
vector<int > dp(n + 1);
bool f = true;
set<int> ans;
auto dfs = [&](auto self, int x, int p, int r) -> void{
dp[x] = 1;
for(auto [t, id] : e[x]){
if(t == p || st[t]) continue;
st[t] = true;
self(self, t, x, id);
dp[x] += dp[t];
}
if(dp[x] > 3) f = false;
else if(dp[x] == 3 && r != -1){
ans.emplace(r);
dp[x] = 0;
}
};
st[1] = true;
dfs(dfs, 1, -1, -1);
if(!f){
cout << -1 << '\n';
return;
}
cout << ans.size() << '\n';
for(auto x : ans) cout << x << ' ';
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}这题怎么比上一题简单多了（