这次训练赛clone的是2019的哈尔滨ccpc区域赛，I题K题都是“猜”出来的，E题卡常数T了好几发（卡速读是没想到的），按照原榜本来可以拿银结果只有铜首了，有点可惜。A、B、L为金牌题，知识点分别为差分约束，dp，字典树/hash，看情况补一下。
E – Exchanging Gifts
题意
一个序列随意排列后和原序列不同的个数定义为这个序列的快乐值。给你一个序列，求这个序列快乐值的最大值。但是这个序列不是直接给你，因为序列长度最大可能为$10^{18}$,所以将序列拆成n段给出，其中这n段有两种表示形式，第一个输入的数字表示序列类型，若为1 则下一个数字表示序列长度，序列正常输入；若为2 则接下来输入两个a b数字表示当前的序列由编号为a 和 b 的两个序列收尾拼接而成。
题目分析
记录长度为 $n$ 的字符串中出现次数最多的字符的个数为 $max$， 若 $max <= 2 * n$，则快乐数为 $n$，否则为 $2 * (n-max)$。随便画几个例子移动一下即可，最优情况总是出现在，将整个字符串向右平移 $max$ 个距离时出现的。
剩下的问题就是如何获得这个 $max$，由于字符串非常长且输入方式的特殊，不能直接暴力。可以先将输入看成一个图，若c由a和b拼接而成，则从c向b以及c向a连边。建好图后，从最后一个节点开始dfs，记录每个节点被用到的次数，同时更新一下最终长度。由于数据量过大，dfs会TLE，改写成递推形式，另外此题要用快读，scanf也会超时…
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
vector<int> v[N];
map<int, LL> mp;
int book[N], k[N], a[N], b[N];
LL num[N];
LL dfs(int n) {
LL len = 0;
num[n] = 1;
for (int i = n; i; i--) {
if (book[i] == 2) {
num[a[i]] += num[i];
num[b[i]] += num[i];
} else {
for (auto it : v[i]) {
mp[it] += num[i];
}
len += (LL)k[i] * num[i];
}
}
return len;
}
int main() {
int t, n, x;
cin >> t;
while (t--) {
n = read();
for (int i = 1; i <= n; i++) {
book[i] = read();
v[i].clear();
num[i] = 0;
if (book[i] == 1) {
k[i] = read();
for (int j = 0; j < k[i]; j++) {
x = read();
v[i].push_back(x);
}
} else {
a[i] = read();
b[i] = read();
}
}
mp.clear();
LL len = dfs(n);
LL Max = 0;
for (auto it : mp) {
if (it.second > Max) {
Max = it.second;
}
}
LL res;
if (Max * 2 <= len)
res = len;
else
res = 2 * (len - Max);
printf("%lld\n", res);
}
return 0;
}
F – Fixing Banners
题意
输入六个字符串，让你从每个字符串中必须取且只取一个字母，使得可以组成“harbin”（没有顺序的限制）。
题目分析
由于需要找的字符只有6个，字符串也只有6个，所以直接爆搜遍历每个字符串即可。
代码
#include <bits/stdc++.h>
using namespace std;
bool book[6][26];
bool vis[26];
char str[10] = "harbin";
bool dfs(int p) {
if (p == 6) return true;
for (int i = 0; i < 6; i++) {
int id = str[i] - 'a';
if (!vis[id] && book[p][id]) {
vis[id] = true;
if (dfs(p + 1)) return true;
vis[id] = false;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
string s;
int t;
cin >> t;
while (t--) {
memset(book, false, sizeof book);
memset(vis, false, sizeof vis);
for (int i = 0; i < 6; i++) {
cin >> s;
for (auto c : s) {
book[i][c - 'a'] = true;
}
}
if (dfs(0))
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
I – Interesting Permutation
题意
对于一个序列 $a_i$ ，定义：
– For each $1≤i≤n, f_i=max(a_1,a_2,…,a_i);$
– For each $1≤i≤n, g_i=min(a_1,a_2,…,a_i);$
– For each $1≤i≤n, h_i=f_i−g_i.$
现在给出一组序列 $h$，让你找出满足序列 $h$ 的序列 $a$ 的个数。
题目分析
先处理掉无解的情况，即 $h[0] = 0$; $h$ 中存在降序；$h[i] >= n$。
然后对于$h[i] > h[i-1]$ 的情况，可能是最大值变大了，也可能是最小值变小了，故有两种可能，在原方案数的基础上乘2。对于 $h[i] = h[i-1]$ ，可选的数字是 $1-i$ 中介于最大值和最小值之间的数，在原方案数的基础上乘上可选数字的个数，可选数字的个数其实就是当 $h[i] > h[i – 1]$ 时，它们的差值 $(h[i] – h[i – 1] – 1)$ ，减1是因为要将 $h[i]$ 自身除去。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7;
typedef long long LL;
int h[N];
bool book[N];
bool check(int n) {
if (h[1] != 0) return false;
int Max = 0;
for (int i = 1; i <= n; i++) {
if (h[i] < max(Max, i - 1) || h[i] >= n) return false;
Max = max(Max, h[i]);
}
return true;
}
int main() {
int t, n, m;
cin >> t;
while (t--) {
scanf("%d", &n);
m = 0;
for (int i = 0; i <= n; i++) book[i] = false;
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i]);
}
if (check(n)) {
for (int i = 1; i <= n; i++)
if (book[h[i]] == false) {
m++;
book[h[i]] = true;
}
int res = 1;
for (int i = 1; i < m; i++) res = (LL)res * 2 % mod;
for(int i = 2;i<=n;i++){
if(h[i]==h[i-1]) {
res = (LL)res*(h[i]-i+2)%mod;
}
}
printf("%d\n", res);
} else {
puts("0");
}
}
return 0;
}
J – Justifying the Conjecture
题意
给你一个数a，输出一个素数和一个不为1的非素数，使得和为a。
题目分析
若为偶数则用 2 和 n-2表示，奇数用3 和 n-3表示，若n小于等于5则无解。
代码
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int n, t;
cin >> t;
while (t--) {
scanf("%d", &n);
if (n <= 5) {
puts("-1");
} else if (n & 1) {
printf("%d %d\n", 3, n - 3);
} else {
printf("%d %d\n", 2, n - 2);
}
}
return 0;
}
K – Keeping Rabbits
题意
$n$ 只兔子，每只兔子初始体重为 $w[i]$,每天给1根胡萝卜，兔子们打架，最终胜利的会得到胡萝卜，其体重相应的+1，求k天后，每只兔子体重的期望。其中，每只兔子的胜率为：$ \frac {w^′i}{\sum{j=1}^n w^′_j} $。
题目分析
一开始队友猜测，最终期望就用最开始的概率计算得到，试了一下A了，然后去证明，发现：
第 $i$ 只兔子第一天后的体重期望为：$ w_i+\frac {w_i}{\sum_{j=1}^n w_j} $, 将其当做第二天的体重，代入计算第二天的胜率，发现和第一天的一样，所以k天的期望可以用第一天的概率直接算。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int a[N];
int main() {
int n, t, k;
cin >> t;
while (t--) {
scanf("%d %d", &n, &k);
double sum = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
for (int i = 1; i <= n; i++) {
printf("%lf%c", a[i] + k / sum * a[i], i == n ? '\n' : ' ');
}
}
}
