Deltix Round, Autumn 2021, Div.1 + Div.2
A. Divide and Multiply
题意
给定一个长度为 \(n\)（\(1 \le n \le 15\)）的数组，\([a_1, a_2, \ldots, a_n]\)，其中 \(1 \le a_i \le 16\)。
我们可以执行操作：
- 选择 \([1, n]\) 范围内的整数 \(i\) 和 \(j\)。其中必须满足 \(2 \mid a_i\)
- 令 \(a_i = {a_i \over 2}\)。
- 令 \(a_j = 2 \times a_j\)。
我们可以执行任意多次，问执行任意多次操作之后我们能够得到的最大的数组的和是多少？
分析
转换题意
分析可知，操作本质上就是转移了一个 \(2\) 的素因子，即把 \(a_i\) 中的 \(2\) 的素因子转移到 \(a_j\) 上。
那么我们可以简化问题：一开始我们把所有 \(a_i\) 的所有素因子 \(2\) 提取出来，然后再用最优解法放回去，最后得到的就是最优解了。
比如说我们一开始有数组 \([1, 2, 3, 4, 5]\)，提取了所有的 \(2\) 有 \([1, 1, 3, 1, 5]\)，共提取了 \(3\) 个 \(2\)，求怎么放回去我们才能得到最优解。
最优解法
那么最优解法是什么呢？假设我们把 \(2\) 乘入到提取素因子 \(2\) 之后的 \(a_i\) 上，那么数组的和 \(S\) 就自增了一个 \(a_i\)。
那么贪心的，最优解法就是乘入到最大的数组元素上。
参考代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int t;scanf("%d", &t);
while(t--){
int n;scanf("%d", &n);
int cnt = 0;
// 记录提取后的最大的元素。
int maxe=0,maxi;
// 数组 A。
constexpr int LEN = 20;
static ll A[LEN];
// 读入、提取、和记录最大元素。
for(int i = 0; i < n; ++i) {
scanf("%lld", &A[i]);
while(A[i] % 2 == 0){
A[i] /= 2;
cnt++;
}
if(A[i] > maxe) {
maxe = A[i];
maxi = i;
}
}
// 把 2 乘入到最大的元素。
for(int i = 0; i < cnt; ++i) {
A[maxi] *= 2;
}
// 求解答案。
ll result = 0;
for(int i = 0; i < n; ++i) {
result += A[i];
}
printf("%lld\n", result);
}
return 0;
}B. William the Vigilant
题意
给定一个长度为 \(n\)（\(1 \le n \le 10^5\)）的字符串 \(s\)，而 \(s\) 仅仅由字符 'a'、'b'、'c' 构成。
之后我们有 \(q\)（\(1 \le q \le 10^5\)）个查询，其中每一查询分为两部分，即位置 \(p\) 和字符 \(c\)，表示将 \(s\) 中第 \(p\) 个字符替换成 \(c\)，并问替换后其对应的值（描述见下）。
其中一个字符串对应的值表述为：使得 'abc' 不是该串的 子串 的最小的有效替换次数，其中有效替换为将串中一个字符替换为 'a'、'b' 或 'c' 的一次操作。
比如，给定 \(s =\) 'abcabcabc'，那么有：
- 第一个查询是 \(p = 1\)，\(c =\)
'a'，那么 \(s =\)'abcabcabc'，其对应的值是 \(3\)（比如替换为'bbcaccabb'）。 - 第二个查询是 \(p = 1\)，\(c =\)
'b'，那么 \(s =\)'bbcabcabc'，其对应的值是 \(2\)（比如替换为'bbcbbcbbc'）。 - 第三个查询是 \(p = 2\)，\(c =\)
'c'，那么 \(s =\)'bccabcabc'，其对应的值为 \(2\)（比如替换为'bccbbcbbc'）。
如果一个串 \(a\) 是串 \(b\) 的子串，当且仅当我们可以通过删除 \(b\) 的一个前缀和一个后缀（可以为空）来待到 \(a\)。
分析
首先我们观察到题墓指明的是子串 'abc'，那么任意两个子串肯定都是不重叠的、且独立的。并且我们可以通过一个操作把 'abc' 这个子串去掉：把 'a' 替换为 'b' 即可。
那么我们一开始就可以先处理出来一共有几个子串。
然后每一次查询的时候，我们进行如下操作：
- 判断是否破坏了
'abc'子串，如果破坏了，计数减掉一。 - 判断是否构成了
'abc'子串，如果构成了，计数增加一。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, q;
scanf("%d%d", &n, &q);
constexpr int LEN = 1e5 + 16;
static char S[LEN];
scanf("%s", S);
// 记录 abc 子串的位置。
set<int> PS;
for (int i = 0; i < n; ++i) {
if (S[i] == 'a' && S[i + 1] == 'b' && S[i + 2] == 'c')
PS.insert(i);
}
for (int _ = 0; _ < q; ++_) {
// 读入查询并修改。
int pos;
char c;
scanf("%d %c", &pos, &c);
pos--;
S[pos] = c;
// 拿到最近的一个 abc 子串的位置。
auto nxt = PS.upper_bound(pos);
auto bef = (nxt == PS.begin() ? -5 : *--nxt);
// 如果修改的地方恰好再这个子串中间的话，那么就破坏掉了这个子串。
if (pos >= bef && pos <= bef + 2) {
PS.erase(bef);
}
// 构成了新的串
if (c == 'a') {
if (S[pos + 1] == 'b' && S[pos + 2] == 'c') {
PS.insert(pos);
}
} else if (c == 'b') {
if (S[pos - 1] == 'a' && S[pos + 1] == 'c') {
PS.insert(pos - 1);
}
} else {
if (S[pos - 2] == 'a' && S[pos - 1] == 'b') {
PS.insert(pos - 2);
}
}
// PS 的大小就是答案。
printf("%d\n", (int)PS.size());
}
return 0;
}C. Complex Market Analysis
题意
对于一个给定的数组 \(a\)（数组长度为 \(1 \le n \le 2 \cdot 10^5\)）和一个自然数 \(e\)（\(1 \le e \le n\)）。
我们希望求出 \((i, k)\) 的对数，其中它必须满足下面的三个条件：
- \(1 \le i, k\)。
- \(i + e \cdot k \le n\)。
- \(a_i \cdot a_{i + e} \cdot a_{i + 2e} \cdot \cdots \cdot a_{i + ke}\) 是一个素数。
分析
很明显如果两个数相乘，一般而言答案都不会是一个素数，除了一个例外，即一个素数和一相乘，其会得到一个素数。
那么一开始我们可以把数分为三类：素数、合数和一。
然后我们可以看到，只有下标在模 \(e\) 下同余的数，才可能相乘。那么我们枚举所有的余数，然后在同余下标的数里找出答案，相加即可。
比如说如果 \(a = [10, 2, 1, 3, 1, 19, 3]\)，而 \(e = 3\)，那么我们可以把它划分为三类：下标模 \(e\) 结果为 \(1\) 的 \([10, 3, 3]\)；为 \(2\) 的 \([2, 1]\)，为 \(0\) 的 \([1, 19]\)，三个对应的答案为 \(0\)、\(1\)、\(1\)，故答案为它们的和 \(2\)。
现在问题来到了如何求同余下标的数所对应的答案？从左到右扫描即可，扫描时维护好素数前有几个一，素数后有几个一即可。具体逻辑见代码即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, b, e) for (int i = b; i < e; i++)
constexpr int P_RAG = 1e6 + 16;
int PS[P_RAG << 2];
bitset<P_RAG> notP;
// 利用欧拉筛，处理出所有的素数。
void PSinit()
{
notP[0] = notP[1] = true;
for (int i = 2; i < P_RAG; i++) {
if (!notP[i])
PS[++PS[0]] = i;
for (int pi = 1; PS[pi] * i < P_RAG; pi++) {
notP[PS[pi] * i] = true;
if (i % PS[pi] == 0)
break;
}
}
}
int main()
{
PSinit();
int t;
scanf("%d", &t);
while (t--) {
// 读入 n、e。
int n, e;
scanf("%d%d", &n, &e);
// 读入数组并处理为 0、1、2，简化问题。
constexpr int LEN = 2e5 + 16;
int P[LEN]; // 0 -> 合数, 1 -> 1, 2 -> 素数
for (int i = 0; i < n; ++i) {
int tmp;
scanf("%d", &tmp);
P[i] = tmp == 1 ? 1 : notP[tmp] ? 0 : 2;
}
ll res = 0;
for(int i = 0; i < e; ++i) {
ll bfnum = 0, afnum = 0;
int state = 0; // 状态：0 -> 在素数前, 1 -> 在素数后。
for (int j = i; j < n; j += e) {
if (state == 0) { // 如果在素数前。
if (P[j] == 1) {
// 遇到了一个一，那么素数前的一变多了。
bfnum++;
} else if (P[j] == 2) {
// 如果遇到了素数，那么状态切换到“素数后”。
state = 1;
} else {
// 如果遇到合数，那么初始化即可。
bfnum = 0, afnum = 0, state = 0;
}
} else { // 如果在素数后。
if (P[j] == 1) {
// 如果遇到了一，那么素数后的一变多了。
afnum++;
} else {
// 不然的话，先搞定其对应的答案：
// 自选前面的一，有 bfnum 个情况。自选后面的一，有 afnum
// 个情况。两边都选，那么有 bfnum * afnum 个情况。
res += bfnum * afnum + bfnum + afnum;
// 如果是素数，那么原来的 afnum 变成了 bfnum。
if (P[j] == 2) {
bfnum = afnum;
j -= e;
// 如果是合数，那么 bfnum 也变成零。
} else {
bfnum = 0;
}
afnum = 0, state = 0;
}
}
}
// 扫描完了，状态是一的话，还需要清理掉剩下的答案。漏掉就不好了。
if (state == 1)
res += bfnum * afnum + bfnum + afnum;
}
printf("%lld\n", res);
}
return 0;
}D. Social Network
题意
一共有 \(n\)（\(2 \le n \le 10^3\)）个节点和 \(d\) 个条件，第 \(i\) 个条件要求 \(x_i\) 和 \(y_i\) 有联系。
如果 \(a\) 和 \(b\) 有联系，说明存在一条路径，从 \(a\) 到 \(b\)。
现在要求你输出 \(d\) 个数字。
其中第 \(i\) 个数字，应该是：要求你添加 \(i\) 个边，在满足 \(1\) 到 \(i\) 个条件下，一个节点可以拥有的最大邻居节点数。
应当注意的是，数字之间是互相独立的。这意味这，当计算第 \(i\) 个数字的时候，你应该假设没有两个节点是有了联系的。
邻居节点表示直接相连的节点。
分析
因为答案独立，那么我们就只需要考虑第 \(i\) 个答案，即添加 \(i\) 个边，且满足第 \(1\) 到第 \(i\) 个约束条件，在这种情况下，某一个节点可以拥有的最大邻居节点数。
那么根据 \(i\) 个约束条件，我们可以把节点划分成多个集合，同一个集合内的节点代表了它们两两有联系。那么假设某一个集合内有 \(n\) 个节点，那么两两之间有联系，就代表了这个集合之间的所有节点是连通的，最小的连通就是构造一个树，即添加 \(n - 1\) 个边即可。
那么我们首先先遍历一边，利用并查集构造出多个集合。如果 \(x_i\) 和 \(y_i\) 本身就在同一个集合内，那么我们就可以省下添加边的次数，记为 \(C\)。
那么最后我们构造出了集合的划分，然后我们再把前 \(C + 1\) 个最大的集合连起来构造一个大连通图（树）。
参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, b, e) for (int i = b; i < e; i++)
constexpr int LEN = 1e3 + 16;
int fa[LEN], n, sz[LEN];
// 初始化并查集
void init_fa()
{
for (int i = 1; i <= n; i++)
fa[i] = i, sz[i] = 1;
}
// 得到并查集节点所对应的根节点。
int get_fa(int n)
{
return fa[n] != n ? fa[n] = get_fa(fa[n]) : n;
}
// 合并并查集。
void merge(int u, int v)
{
if (get_fa(u) == get_fa(v))
return;
sz[get_fa(v)] += sz[get_fa(u)];
fa[get_fa(u)] = get_fa(v);
}
int main()
{
int d;
scanf("%d%d", &n, &d);
init_fa();
// GDM 表示可以灵活配置的人数。
int GDM = 1;
// 遍历所有情况。
for (int i = 0; i < d; i++) {
// 获取对应的约束并更新并查集。
int x, y;
scanf("%d%d", &x, &y);
// 如果 x 和 y 在一个并查集里，那么说明他们在之前的约束限制下已经认识了
// 。不然我们就必须介绍他们认识。
if (get_fa(x) != get_fa(y))
merge(x, y);
else
GDM++;
// X 记录所有并查集的大小。并得到最大的放入到 X[0] 中。
static int X[LEN];
int X_len = 0;
for (int i = 1; i <= n; i++) {
if (i == fa[i]) {
X[X_len++] = sz[i];
}
}
sort(X, X + X_len);
reverse(X, X + X_len);
// X[0] 并不是最优解，我们还需要把一些可以灵活配置的名额变成两个并查集之
// 间的一条边。
int result = 0;
for (int i = 0; i < GDM; i++) {
result += X[i];
}
// 除了自己之外其他都是熟人。
printf("%d\n", result - 1);
}
return 0;
}E. William The Oblivious
题意
给定一个长度为 \(n\)（\(1 \le n \le 10^5\)）的字符串 \(s\)，而 \(s\) 仅仅由字符 'a'、'b'、'c' 构成。
之后我们有 \(q\)（\(1 \le q \le 10^5\)）个查询，其中每一查询分为两部分，即位置 \(p\) 和字符 \(c\)，表示将 \(s\) 中第 \(p\) 个字符替换成 \(c\)，并问替换后其对应的值（描述见下）。
其中一个字符串对应的值表述为：使得 'abc' 不是该串的 子序列 的最小的有效替换次数，其中有效替换为将串中一个字符替换为 'a'、'b' 或 'c' 的一次操作。
比如，给定 \(s =\) 'aaabccccc'，那么有：
- 第一个查询是 \(p = 4\)，\(c =\)
'a'，那么 \(s =\)'aaaaccccc'，其对应的值是 \(0\)（比如替换为'aaaaccccc'）。 - 第二个查询是 \(p = 4\)，\(c =\)
'b'，那么 \(s =\)'aaabccccc'，其对应的值是 \(1\)（比如替换为'aaaaccccc'）。 - 第三个查询是 \(p = 2\)，\(c =\)
'b'，那么 \(s =\)'ababccccc'，其对应的值为 \(2\)（比如替换为'aaaaccccc'）。
如果一个串 \(a\) 是串 \(b\) 的子序列，当且仅当我们可以通过删除 \(b\) 的一些字符（可以为空）来待到 \(a\)。
分析
这道题我们不妨这么想：
首先，我们如何判断一个串中是否含有子序列 'abc'：我们可以用两个指针，一个指向'abc'，另一个指向该串。第二个指针开始遍历，如果两个指针指向的东西相同，那么第一个指针也向后走一步。通过这个方法，我们能得到一个串中是否含有该子序列。
然后我们多加一个限制条件，我们还可以 多次 修改该串的情况下，依然要求判断这个串中是否含有该子序列。如果每一次修改了之后都用之前 \(O(n)\) 的时间复杂度去找的话，很可能会导致时间复杂度太高。那么我们可以考虑把这个问题分解一下，如果一个串有 'abc' 这个子序列，那么把该串划分为两个子串，即左串和右串，那么有且仅有四种情况：
- 左串有
'abc'这个子序列。 - 右串有
'abc'这个子序列。 - 左串有
'a'这个子序列，右串有'bc'个子序列。 - 左串有
'ab'这个子序列，右串有'c'这个子序列。
那么我们可以考虑用一个线段树，其中每一个节点，考虑维护它对应的子串中是否含有 'a'、'b'、'c'、'ab'、'bc'、'abc' 这些子序列这些状态。
最后，我们再回过来考虑题目，那么题目对应的问题该如何求解呢？
题目问的是，我们可以 多次 修改该串的情况下，每一次修改之后，求我们需要多少次才能够搞掉所有的 'abc' 子序列。
我们对于一个串 \(s\) 而言，如果它的左串（记为 \(l\)），和它的右串（记为 \(r\)），如果 \(l\) 存在子序列 'ab'，而 \(r\) 存在子序列 'c'，那么 \(s\) 一定存在 'ab'、'c'、'abc' 这三个子序列。
我们只需要考虑 'a'、'b'、'c'、'ab'、'bc' 这五个子序列，这是因为其他的子序列并不会直接构成 'abc'。
那么如果只考虑上面五个子序列中，如果 \(l\) 包含了 'a'、'c'，而 \(r\) 包含了 'ab'，那么 \(s\) 一定包含了 'a'、'ab'、'c'。那么如果我们把状态压缩成一个数字（我们把它映射成二进制，那么我们可以用 \([1, 31]\) 内的数字来表示这个状态），那么我们可以打表来快速得到，如果左边是状态 \(i\)，右边是状态 \(j\)，自己的状态会是什么。如果自己会包含 'abc'，那么就说明自己是一个废串，记作 \(-1\)。
我们考虑可以对于每个节点而言，维护一个动态规划的数组 \(d\)，它可以通过子节点的 \(d\) 来进行更新和维护。而其中 \(d\) 的下标 \(i\) 表示这个节点变化到的不包含 'abc' 的第 \(i\) 状态时最少变化的步数。
比如说我们不妨假设该节点对应的子串为 'abc'，而如果 \(i = 0\) 对应的指它啥都不包含的情况，那么自然 \(d_0 = +\infty\)；而如果 \(i = 1\) 对应它只包含 'a' 的情况，那么自然 \(d_1 = 2\)（变化到 'aaa' 即可）；而如果 \(i = 12\) 表示它只包含 'bc' 和 'a' 的情况，那么自然 \(d_{12} = 3\)（变化到 'bca' 即可）。
现在我们已经知道了左右节点 \(l\) 和 \(r\)，那么如何解出本节点 \(s\) 的 \(d\) 数组呢？如果 \(i\) 对应的状态和 \(j\) 对应的状态合并后会变成 \(k\)，那么有 \(s.d_k = \min(s.d_k,\, l.d_i + r.d_j)\)。
参考代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int inf=0x3f3f3f3f;
bool contain(const char *a,const char *sub){
int subi=0;
for(int ai=0;a[ai]&&sub[subi];ai++){
if(a[ai]==sub[subi]){
subi++;
}
}
return !sub[subi];
}
const char *BIT[]={"a","b","c","ab","bc"}; // 2^5 < 40
// merge[i][j] 表示如果左串是状态 i，右串是状态 j，其能得到的状态。
int mergeMask[40][40];
void init(){
// 枚举左右状态。
for(int i=1;i<(1<<5);i++){
for(int j=1;j<(1<<5);j++){
// 合并的状态肯定包含左右状态。
int result=i|j;
// 是否可以推导出来 "abc"。
bool flg=false;
// 枚举左右状态的子序列。
for(int ii=0;ii<5;ii++){
if(!((1<<ii)&i)) continue;
for(int jj=0;jj<5;jj++){
if(!((1<<jj)&j)) continue;
// 把左右状态的子序列链接起来。
static char tmp[10];
tmp[0]='\0';
strcat(tmp,BIT[ii]);
strcat(tmp,BIT[jj]);
// 如果包含了 "abc"，那么 merge[i][j] 就废掉了。
if(contain(tmp,"abc")){
flg=true;
break;
}
// 把没有的子序列对应的位拿出来看看在不在链接起来的序列中。
for(int i=0;i<5;i++){
if((1<<i)&result) continue;
if(contain(tmp,BIT[i])){
result|=(1<<i);
}
}
}
// 废掉的数据
if(flg){
break;
}
}
mergeMask[i][j]=(flg?-1:result);
}
}
}
constexpr int LEN=1e5+16;
struct node{
int l,r;
int dp[40];
}seg[LEN<<2];
static char S[LEN];
// 根据自己的左右节点更新自己。
void calc(int i){
for(int ii=1;ii<32;ii++) seg[i].dp[ii]=inf;
// 枚举左右节点的状态
for(int ii=1;ii<32;ii++){
if(seg[i*2].dp[ii]==inf) continue;
for(int jj=1;jj<32;jj++){
if(seg[i*2+1].dp[jj]==inf) continue;
// 更新 ii 和 jj 合并对应的状态 state
int state=mergeMask[ii][jj];
if(state == -1) continue;
seg[i].dp[state]=min(seg[i].dp[state], seg[i*2].dp[ii] + seg[i*2+1].dp[jj]);
}
}
}
// 构造线段树。
void build(int i,int l,int r){
seg[i].l=l,seg[i].r=r;
// 叶子节点
if(l==r){
for(int ii=1;ii<32;ii++) seg[i].dp[ii]=inf;
seg[i].dp[1]=seg[i].dp[2]=seg[i].dp[4]=1;
seg[i].dp[1<<(S[l]-'a')]=0;
return;
}
// 非叶子节点
build(i*2,l,(l+r)/2);
build(i*2+1,(l+r)/2+1,r);
calc(i);
}
// 更新线段树
void update(int i,int pos,char ch){
// 叶子节点
if(seg[i].l==seg[i].r){
for(int ii=1;ii<32;ii++) seg[i].dp[ii]=inf;
seg[i].dp[1]=seg[i].dp[2]=seg[i].dp[4]=1;
seg[i].dp[1<<(ch-'a')]=0;
return;
}
// 非叶子节点
if(pos<=seg[i*2].r)update(i*2,pos,ch);
else update(i*2+1,pos,ch);
calc(i);
}
int main(){
// 读入。
int n,q;scanf("%d%d",&n,&q);
scanf("%s",S+1);
// 预处理
init();
// 构造线段树。
build(1,1,n);
for(int i=0;i<q;i++){
int pos;char ch;scanf("%d %c",&pos,&ch);
update(1,pos,ch);
int res=inf;
for(int i=1;i<32;i++){
res=min(res,seg[1].dp[i]);
}
printf("%d\n",res);
}
return 0;
}