只记录写了的题
A PENTA KILL!
签到题，主要难点在于读题…
如果你玩moba类游戏，会觉得他这个题意十分别扭，听说有个省赛金牌爷这题开局错了五发
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
unordered_map<string, vector<string>> m;
for (int i = 0; i < n; ++i)
{
string u, v;
cin >> u >> v;
m[u].push_back(v);
}
for (auto &[_, s] : m)
{
for (int i = 0; i + 4 < (int)s.size(); ++i)
{
bool flag = true;
for (int j = i; j < i + 5; ++j)
{
for (int k = j + 1; k < i + 5; ++k)
{
if (s[j] == s[k])
flag = false;
}
}
if (flag)
{
cout << "PENTA KILL!" << endl;
return 0;
}
}
}
cout << "SAD:(" << endl;
return 0;
}C Jump and Treasure
大意
有个调皮的小朋友在数轴的柱子上往正方向跳，一开始在 $ 0 $ ，有 $n(1 \le n \le 10^6)$ 个柱子可以跳，分别位于 $1,2,3,\dots,n$ ，跳的距离不能超过 $p(2 \le p \le 10^6)$，每个柱子的权值为 $a_{i} (-10^9 \le a_{i} \le 10^9)$。有 $q(1 \le q \le 10^6)$ 次询问，每次询问给定一个数 $x$ ，限定跳的距离只能是 $x(1 \le x \le n)$ 的倍数，跳到 $[n+1,+\infty)$ 即视为游戏胜利。对每次询问，如果能胜利，求跳的柱子权值和最大值，否则输出 $Noob$ 。
思路
易知不用管大于p的跳跃距离。如果对剩下的每种跳跃距离枚举，找到每种距离能跳的所有柱子，符合调和级数复杂度，为 $O(nlogn)$。对每个距离找到的柱子进行动态规划，易列出转移式
$$
dp[i] = max_{i−j \le p}(dp[j]) + a[i]
$$
然后这就是单调队列的经典运用了，注意空间优化，毕竟是用 $long \; long$ 存的，输入输出也注意优化，因为已经到了百万级了。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
int a[N];
ll ans[N];
int main()
{
int n, q, p;
scanf("%d%d%d", &n, &q, &p);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
fill(ans, ans + n + 1, LLONG_MIN);
for (int i = 1; i <= p; ++i)
{
deque<int> q{0};
vector<ll> dp(n / i + 1, LLONG_MIN);
dp[0] = 0;
for (int j = i, cnt = 1; j <= n; j += i, ++cnt)
{
while ((cnt - q.front()) * i > p)
q.pop_front();
dp[cnt] = dp[q.front()] + a[j];
if (j + p > n)
ans[i] = max(ans[i], dp[cnt]);
while (q.size() && dp[cnt] >= dp[q.back()])
q.pop_back();
q.push_back(cnt);
}
}
for (int i = 1, x; i <= q; ++i)
{
scanf("%d", &x);
if (x <= p)
printf("%lld\n", ans[x]);
else
printf("Noob\n");
}
return 0;
}I Cutting Suffix
大意
给定一个字符串，将其所有后缀字符串分为两个集合，使得集合一的每个字符串与集合二的每个字符串两两之间最长公共前缀长度之和最小
思路
如果该字符串不是只有一个字符，那么总可以按后缀字符串的首字母拆成两个集合，两个集合里的字符串两两公共前缀长度均为 $0$ ，总和为 $0$ 。如果该字符串只有一个字符，那么将长度为 $1$ 的后缀字符串单独划为一个集合，其他在另一个集合，总和即为原字符串长度减 $1$
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
unordered_set<char> p(s.begin(), s.end());
if (p.size() == 1)
cout << s.size() - 1 << endl;
else
cout << 0 << endl;
return 0;
}J Balanced Tree
大意
$T(1 \le T \le 10^6)$ 组测试数据，每组给一个数 $n(0 \le n \lt 2^{64})$ ，求节点数为 $n$ 的超级平衡二叉树数量，答案模$2^{64}$ 。如果一棵树为空树，或者左子树节点数和右子树节点数之差小于等于 $1$ ，则为超级平衡二叉树。对此题特别提一下空间只给了 $64MB$ ，时限是 $1.5s$ 。
思路
很容易想到下面的递归式。
$$
f[0]=1 \\\
f[x]=
\begin{cases}
2f[\frac{x}{2}]f[\frac{x}{2}-1],\quad x 为偶数 \\\
f[\frac{x-1}{2}]^2,\quad x为奇数
\end{cases}
$$
加上哈希就成了记忆化搜索，使用C++的unsigned long long自然溢出取模，代码如下
#include <bits/stdc++.h>
using namespace std;
using R = unsigned long long;
void solve()
{
R n;
scanf("%llu", &n);
unordered_map<R, R> m;
m[0] = 1;
function<R(R)> dfs = [&](R x)
{
if (m.count(x))
return m[x];
R les = (x - 1) >> 1;
if ((x - 1) & 1)
m[x] = dfs(les) * dfs(les + 1) * 2;
else
m[x] = dfs(les) * dfs(les);
return m[x];
};
printf("%llu\n", dfs(n));
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
solve();
return 0;
}懒得算复杂度了，直接交，果然超时。如果把容器和函数移到solve外面，那么就超空间。
考虑优化，由递归式可以看出结果为2的幂，要是能直接得到幂就好解了，幂大于等于64的结果为0，其他的输出结果即可
为了得到幂，进行取对数操作
$$
设\; g[x]=\log_{2}{f[x]}，有\\\
g[0]=0\\\
g[x]=
\begin{cases}
g[\frac{x}{2}]+g[\frac{x}{2}-1]+1,\quad x 为偶数\\\
2g[\frac{x-1}{2}],\quad x为奇数
\end{cases}\\\
由上易知\;\forall n \in N,存在\; x \in N^{*},\;g[n]=a \cdot g[x]+b \cdot g[x-1]+c\\\
化为\;g[n]=
\begin{cases}
a \cdot (g[\frac{x}{2}] + g[\frac{x}{2} − 1] + 1) + b \cdot (2g[\frac{x-1-1}{2}]) + c,\quad x是偶数\\\
a \cdot (2g[\frac{x-1}{2}]) + b \cdot (g[\frac{x-1}{2}] + g[\frac{x-1}{2} − 1] + 1) + c,\quad x是奇数
\end{cases}\\\
=
\begin{cases}
a \cdot g[\frac{x}{2}] + (a+2b) \cdot g[\frac{x}{2}-1] + c + a,\quad x是偶数\\\
(2a+b) \cdot g[\frac{x-1}{2}] + b \cdot g[\frac{x-1}{2}-1] + c + b,\quad x是奇数
\end{cases}\\\
于是初始\;g[n]=1\cdot g[n] + 0 \cdot g[n-1] + 0\\\
不断除二直到\;n = 1,化为\\\
g[n] = a\cdot g[1] + b \cdot g[0] + c=c
$$
最后只需要对 $c$ 进行前文提到的判断即可得到答案
#include <bits/stdc++.h>
using namespace std;
using R = unsigned long long;
void solve()
{
R n;
scanf("%llu", &n);
R a = 1, b = 0, c = 0;
while (n > 1)
{
if (n & 1)
a <<= 1, a += b, c += b;
else
b <<= 1, b += a, c += a;
if (c >= 64)
{
printf("0\n");
return;
}
n >>= 1;
}
printf("%llu\n", 1ull << c);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
solve();
return 0;
}这里记录一个坑点，C++编译器种类实在太多了。。。你任何不规范的操作都有可能导致在不同编译器下结果不同，在此题中，之前犯的错误是忽略了编译器的警告，这样进行输出 printf("%llu\n", 0); ，在有些编译器下不一定输出0，而是一个很大的整数，除非在格式化输出前对 $0$ 进行强转，转为unsigned long long
K aaaaaaaaaaA heH heH nuN
大意
$T(1\le T \le 1000)$ 组测试数据，每组给出一个数 $n (0 \le n \le 10^9)$ ，构造一个字符串，其所有子序列中，优雅字符串的数量为 $n$。优雅字符串的定义是，前缀为 $ nunhehheh $ ，后缀为任意非零数量的 $a$ 。且你输出的所有字符串长度总和不超过 $10^6$
思路
该题有点反动态规划的感觉，通过答案来构造。一般这种数据范围这么大的，都是有指数级构造法的。很容易想到如果在 $ nunhehhe $ 后面，加上 $n$ 个 $h$ ，最后加上个 $a$ ，总能构造出所有的值。但由于输出长度限制不能这么做。
要指数级只能从 $a$ 的个数下手，容易发现 $nunhehheh\underbrace{a\dots a}_{x个}$ 这种形式符合要求的子序列有 $2^x-1$ 个，于是就可以从大到小枚举 $x$ ，$n$ 大于等于 $2^x -1$ 就减去，添加 $h$
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
string ans = "nunhehhe";
for (int i = 29; i >= 1; --i)
{
ans += 'a';
while (n >= (1 << i) - 1)
{
ans += 'h';
n -= (1 << i) - 1;
}
}
ans += 'a';
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}L Collecting Diamonds
大意
给你一个由字符 $A,B,C$ 构成的字符串，长度小于 $2 \cdot 10^5$，每个字符的下标为 $1,2,3,\dots,n$ 。如果子串有 $ABC$ ，则可以进行操作，$A$ 为奇数下标则取走该子串的$A,C$，为偶数下标则取走 $B$ ，该字符串剩下的字符顺次拼接，并重新划定下标。问最多能够进行多少次操作。
思路
首先易见，两种操作中，只有取走 $A,C$ 才可以连续操作，同时该操作不会改变后面下标的奇偶性。只有取走 $B$，才会改变。
同时，我们可以发现每个类似 $AAA\dots ABC \dots CCC$ 的子串都相对独立，即对该子串进行操作，不会影响其他这类子串的字符数量，于是每次找到 $B$ 可以左右找 $A,C$，将原字符串划分。
还有，取走 $B$ 对上述划分后的子串，最多只能进行一次。我们为了能对后面进行更灵活的操作，肯定是尽可能让前面的子串都进行一次取 $B$ 的操作
于是我们可以用一个变量暂存前面取 $B$ 操作的次数，计算每个子串最多能删除多少次 $A,C$
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
int n = s.size(), tot = 0, ans = 0;
for (int i = 0; i < n; ++i)
{
if (s[i] == 'B')
{
int l = i - 1, r = i + 1, cnt = 0;
while (l >= 0 and r < n and s[l] == 'A' and s[r] == 'C')
--l, ++r, ++cnt;
++l, --r;
if (l == r)
continue;
if (i & 1)
{
if (cnt == 1)
{
if (tot)
++tot;
ans += 1;
}
else
{
ans += min(tot, cnt - 2) + 2;
++tot;
}
}
else
{
ans += min(tot, cnt - 1) + 1;
++tot;
}
}
}
cout << ans << endl;
return 0;
}
