A.Musical Puzzle
题意：
用最少的长度为2的字符串按一定规则拼出s。规则是：前一个字符串的尾与后一个字符串的首相同。
分析：
统计s中长度为2的不同字符串数量。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
unordered_map<string, bool> mp;
int n;
cin >> n;
string s;
cin >> s;
int cnt = 0;
for (int i = 0; i < n - 1; i ++)
{
string s2 = s.substr(i, 2);
if (!mp[s2])
{
cnt ++;
mp[s2] = true;
}
}
cout << cnt << endl;
}
return 0;
}
B. Restore the Weather
题意：
给定数组a[n]和b[n]，重排b后，令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。
分析：
将a和b分别按从小到大的顺序匹配便是最优的，一定能满足|ai−bi|≤k成立。只需注意要恢复原来的顺序输出。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
struct Node
{
int id, v, v2;
}a[N];
int b[N];
bool cmp(Node A, Node B)
{
return A.v < B.v;
}
bool cmp2(Node A, Node B)
{
return A.id < B.id;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i ++)
{
a[i].id = i;
cin >> a[i].v;
}
for (int i = 0; i < n; i ++)
cin >> b[i];
sort(b, b + n);
sort(a, a + n, cmp);
for (int i = 0; i < n; i ++)
a[i].v2 = b[i];
sort(a, a + n, cmp2);
for (int i = 0; i < n; i ++)
cout << a[i].v2 << " ";
cout << endl;
}
return 0;
}
C. Vlad Building Beautiful Array
题意:
给定一个a序列，你要构造一个b序列：所有元素均为正数，且要么全是偶数要么全是奇数
构造的方式：令bi = ai - aj (1≤j≤n)
分析:
2只有减奇数才能改变奇偶性。值得注意的是，根据题目要求我们无法将一个奇数序列变成偶数序列，因此只有以下三种情况：
①原本全是奇数
②原本全是偶数
③有奇有偶：这时只能将偶序列变成奇序列。我们将每一个偶数与最小的奇数消减，只要最后的结果全为正数则有解，否则无解。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
int a[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
bool check = false;
for (int i = 0; i < n; i ++)
cin >> a[i];
int cnt1 = 0, min_odd = 0x3f3f3f3f;
for (int i = 0; i < n; i ++)
{
if (a[i] & 1)
{
cnt1 ++;
min_odd = min(min_odd, a[i]);
}
}
if (cnt1 == 0 || cnt1 == n)
{
check = true;
}
if (!check)
{
bool flag = true;
for (int i = 0; i < n; i ++)
{
if (a[i] % 2 == 0 && a[i] <= min_odd)
{
flag = false;
break;
}
}
check = flag;
}
if (check)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
D. Flipper
题意:
分析：
在解空间中，以n/n-1开头的排列字典序比其他可行解大，因此最优解在以n/n-1开头的解空间里。
所以本题右端点是固定的，若元素n不在开头，则r在元素n所在的位置，若n在开头，则r在元素n - 1所在的位置。
固定了r后我们再去枚举左端点l，在所有可行解中取字典序最大的那个排列即可。
代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int n;
vector<int> get(int l, int r)
{
vector<int> res(n);
int m = 0;
for (int i = r + 1; i < n; i ++)
res[m ++] = a[i];
for (int i = r; i >= l; i --)
res[m ++] = a[i];
for (int i = 0; i < l; i ++)
res[m ++] = a[i];
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
cin >> n;
a.resize(n, 0);
vector<int> res(n, 0);
for (int i = 0; i < n; i ++)
cin >> a[i];
int r;
for (int i = 0; i < n; i ++)
{
if (a[i] == n)
{
r = i;
break;
}
}
if (r == 0)
{
for (int i = 0; i < n; i ++)
{
if (a[i] == n - 1)
{
r = i;
break;
}
}
}
if (r != n - 1)
r --;
for (int i = 0; i <= r; i ++)
{
auto tmp = get(i, r);
if (tmp > res)
res = tmp;
}
for (int i = 0; i < n; i ++)
cout << res[i] << " ";
cout << endl;
}
return 0;
}
E. Round Dance
题意:
给定一个序列a[n]，这个序列描述的是，编号为i(1<=i<=n)的节点与编号为a[i]的节点之间有一条无向边，问能构造出的联通块最少是多少和能构造出的连通块最多是多少？
分析:
最多的连通块数便是不加任何操作，当前图的连通块数。
要构造出最少的连通块，我们可以将那些不存在环的连通块合并在一起拉成一条链。
因此我们可以统计出当前图中，连通块的数量m1，存在环的连通块的数量m2，则最少的连通块的数量为m2 + 1，最多的连通块的数量为m1
统计连通块的数量有很多方法，这里用的是dfs。建图时要处理重边，map处理二元元素比较麻烦，可以采用将两个int变量哈希成一个long long值的方式来处理：value = ((LL)a << 32) + (LL)b
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 5, M = 4e6 + 5;
int h[N], e[M], ne[M], idx;
bool st[N];
int m1, m2;
bool flag;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int fa)
{
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j != fa)
{
if (st[j])
{
flag = true;
}
else
dfs(j, u);
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++)
h[i] = -1;
idx = m1 = m2 = 0;
unordered_map<LL, bool> mp;
for (int i = 1; i <= n; i ++)
{
st[i] = false;
int j;
cin >> j;
LL H = ((LL)i << 32) + (LL)j, H2 = ((LL)j << 32) + (LL)i;
if (!mp[H] && !mp[H2])
{
add(i, j), add(j, i);
mp[H] = mp[H2] = true;
}
}
for (int i = 1; i <= n; i ++)
{
if (!st[i])
{
flag = false;
dfs(i, -1);
if (flag)
m2 ++;
m1 ++;
}
}
if (m2 < m1)
cout << m2 + 1 << " " << m1 << endl;
else
cout << m1 << " " << m1 << endl;
}
return 0;
}
F. Ira and Flamenco
题意：
给定一个a序列，求优美子序列总数对1e9 + 7取模的结果。优美子序列应满足：
子序列的大小为m
子序列中的元素各不相同
子序列中任意两个元素差的绝对值严格小于m
分析：
我们不妨先从小到大将其排个序，记录每个元素的个数并去重。子序列abcd出现的次数即子序列中每个元素出现次数的累乘。由于每个元素各不相同，因此任意两个元素至少相差1，所以我们选择的方案在排序去重后实际上时连续的。因此我们可以维护一个前缀积，在新序列里枚举长度为m的连续序列，只要最大值与最小值差的绝对值小于m则统计。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
vector<LL> f(n + 1);
unordered_map<int, int> mp;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
mp[a[i]] ++;
}
sort(a.begin() + 1, a.begin() + n + 1);
a.erase(unique(a.begin() + 1, a.end()), a.end());
f[0] = 1;
for (int i = 1; i < a.size(); i ++)
f[i] = f[i - 1] * mp[a[i]] % mod;
LL res = 0;
for (int i = m; i < a.size(); i ++)
{
if (a[i] - a[i - m + 1] < m)
{
res = (res + f[i] * qmi(f[i - m], mod - 2) % mod) % mod;
}
}
cout << res << endl;
}
return 0;
}
G. Ksyusha and Chinchilla
题意：
给定一个含有n个顶点的树，求一个合法的删边方案保证删完这些边后为若干个长度为3的链。输出合法的删边方案或告诉这是不可能的。
分析：
我们可以自下向上去维护子树的节点总数，合法的情况只有：
倘若当前子树节点总数为3，则将其与父节点的边砍掉并记录。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, M = 4e5 + 5;
int h[N], e[M], ne[M], idx;
int k;
LL res[N];
bool check;
bool cut[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u, int fa)
{
int cnt = 1;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (j != fa)
{
cnt += dfs(j, u);
if (cut[j])
res[k ++] = ((LL)u << 32) + (LL)j;
}
}
if (cnt > 3)
{
check = true;
return 0;
}
else if (cnt == 3 && u != 1)
{
cut[u] = true;
return 0;
}
return cnt;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
memset(h, -1, sizeof h);
memset(cut, false, sizeof cut);
idx = k = 0;
check = false;
unordered_map<LL, int> mp;
for (int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
LL H1 = ((LL)a << 32) + (LL)b, H2 = ((LL)b << 32) + (LL)a;
mp[H1] = mp[H2] = i;
add(a, b), add(b, a);
}
int remain = dfs(1, -1);
if (check || remain != 3)
cout << -1 << endl;
else
{
cout << k << endl;
if (k == 0)
cout << " " << endl;
else
{
for (int i = 0; i < k; i ++)
{
cout << mp[res[i]] << " ";
}
cout << endl;
}
}
}
return 0;
}