（Week 15）综合复习（C++，字符串，数学）

T1 [Daimayuan]删删（C++，字符串）

给定一个字符串，你可以删除多个(可以是 $0$) 相同 的字符，这样操作之后，你能否得到一个回文串？如果能，求最小化删除的个数。

输入格式

多组数据。

每一组数据包含两行，分别为字符串的长度 $N$，以及一个仅由小写字母组成的字符串 $S$。

输出格式

对于每一组数据，输出一行。

如果不可能得到一个回文串，输出 $-1$。反之则输出最小操作次数。

样例输入

4
8
bilibili
3
qwq
9
daimayuan
7
xcpcxpc

样例输出

1
0
-1
2

解释：

在第一个例子中，删除开头的 b 得到 ilibili。

第二个例子中，qwq 本身已回文，不需要操作。

第三个例子中，可以看到 daimayuan 不能靠仅删除一种字符得到一个回文串。

数据规模

$1\le N\le 10^5$, 但保证 $\sum N\le 2\times 10^5$

解题思路

并没有巧妙的办法，就是简单的枚举$26$种字母，找出其中删除的最少的即可

检测的思路如下：

从左右两端开始匹配

（1）if str[left] == str[right]，left++, right--

（2）if str[left] != str[right]

如果左侧字符可以删除，那么删除左侧字符（left++）

如果右侧字符可以删除，那么删除右侧字符（right--）

如果左右都不可以删除，本轮删除失败，继续尝试下一个字符

#include <iostream>
#include <string>
using namespace std;
const int max_n = 2e5;
const string compose = "abcdefghijklmnopqrstuvwxyz";string str;
int n1, n2;int main() {cin >> n1;for (int i = 0; i < n1; i++) {cin >> n2 >> str;int ans = -1;for (char c: compose) {int l = 0, r = n2 - 1;int temp = 0;while (l <= r) {if (str[l] == str[r]) {l++; r--;}else {if (str[l] == c) {l++;temp++;}else if (str[r] == c) {r--;temp++;}else {temp = -1;break;}}}if (temp != -1)if (ans == -1) ans = temp;else ans = min(ans, temp);}cout << ans << endl;}return 0;
}

T2 [Daimayuan]快快变大（C++，区间DP）

给定一个长度为 $n$ 的数组 $a_1,a_2,\dots ,a_n$，接下来进行 $n-1$ 次操作。每次选择一个下标 $x$ ，将 $a_x$ 和 $a_{x+1}$ 合并成 $a_x\ast a_{x+1}mod1000003$ ，并且你会获得 $(a_x-a_{x+1}{)}^2$ 的分数。

所以每次操作后，数组的长度将会减 $1$，当最后只剩下一个元素时停止操作。输出最终能获得的最大分数。

输入格式

第一行一个数字 $n$。

接下来一行 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

输出格式

一个数，表示答案。

样例输入

3
1 2 3

样例输出

26

数据规模

所有数据保证 $1\le n\le 300,1\le a_i\le 10^6$。

解题思路

是没见过的船新版本DP

首先简单说明一下每轮操作的含义

对于要合并的长度为$len$的区间$[l,r]$，我们先分别合并左右两部分$[l,k]$和$[k+1,r]$，那么容易知道：

dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + (num[l][k] - num[k + 1][r]) ** 2)

也就是说合并区间$[l,r]$所得到的分数等于分别合并左右区间得到的分数再加上最后一次合并得到的分数

$DP$的基本思想就是对于任意一个长度为$len$的区间（第一重循环），我们尝试其所有可能的划分（第三重循环），找出其中的最大值

第二重循环？它负责遍历每一个长度为$len$的区间

而我们从小到大遍历$len$，保证了在动态规划过程中，所有长度小于$len$的区间最优结构已经得到，所以$DP$是可行的

AC代码如下

#include <iostream>
using namespace std;
const int mod_num = 1000003;
const int max_n = 300;long long num[max_n + 1][max_n + 1], dp[max_n + 1][max_n + 1];
int n;int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> num[i][i];for (int i = 1; i < n; i++) {for (int j = i + 1; j <= n; j++) {num[i][j] = num[j][j];num[i][j] = (num[i][j] * num[i][j - 1]) % mod_num;}}for (int len = 2; len <= n; len++) {for (int l = 1, r = len; r <= n; l++, r++) {for (int k = l; k < r; k++) {dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + (num[l][k] - num[k + 1][r]) * (num[l][k] - num[k + 1][r]));}}}cout << dp[1][n] << endl;return 0;
}

T3 [Daimayuan]饿饿 饭饭2（C++，数学）

接着《饿饿 饭饭》 的故事，在两天后，食堂的工作人员回来了，整个食堂又回到了原来井井有条的状态。

两个月后，由于天气越来越热，大家的胃口越来越小了，作为食堂管理员的$CC$非常担心孩子们的身体健康，所以他决定开展一个活动来调动孩子们吃饭的积极性，顺便考验一下孩子们的数学水平。活动内容如下：

先让每一个孩子都抽一个球，每一个球上有一个数字， 然后给这个孩子$n$个数字，每一个孩子都有无数次操作机会，每一次都会选中一个数将它乘上$2$，或者乘上$3$，请问这个孩子可以通过上面的操作将这$n$个数都变成相同的吗？

如果回答正确，这个回答正确的孩子就可以得到一份免费的午餐，但是这对于孩子们来说是在是太困难了，但是他们都想吃到免费的午餐，所以他们都想请你告诉他们正确的答案，让他们都迟到免费的午餐。

输入格式

第$1$行给定一个数$T$，表示有$T$个小孩子请你告诉他正确的答案。

第$2$到$T+1$行，第$1$个数是每个孩子抽到的数字$n$，第$2$到$n+1$个数是对应的$n$个数字。

输出格式

如果可以变成相同的，输出YES。如果不能变成相同的，输出NO。

数据规模

$1\le T\le 100,1\le n\le 2\times 10^5,1\le a_i\le 10^9$

数据保证${\sum }_{i=1}^{T}n\le 2\times 10^5$

样例输入

2
4 75 150 75 50
3 100 150 250

样例输出

YES
NO

解题思路

将每个数字拆解成两部分的乘积：$2、3$和其他数字

我们尝试把所有数字的第一部分除去，如果剩余部分相等，输出YES

反之，输出NO

AC代码如下

#include <iostream>
using namespace std;
const int max_t = 100;
const int max_n = 2e5;
const int max_a = 1e9;int t, n;
int num_arr[max_n];int main() {cin >> t;for (int i = 0; i < t; i++) {cin >> n;for (int j = 0; j < n; j++) {cin >> num_arr[j];while (num_arr[j] % 2 == 0) num_arr[j] /= 2;while (num_arr[j] % 3 == 0) num_arr[j] /= 3;}int j, same = num_arr[0];for (j = 1; j < n; j++) if (num_arr[j] != same) break;if (j != n) cout << "NO" << endl;else cout << "YES" << endl;}return 0;
}

T4 [Daimayuan]子串分值和（C++，字符串）

对于一个字符串 $S$ ，我们定义 $f(S)$ 为 $S$ 中出现的不同的字符个数。 例如 $f(aba)=2$，$f(abc)=3$,$f(aaa)=1$。

现在给定一个字符串 $S$ (假设长度为 $len$)，请你计算 ${\sum }_{i=0}^{len-1}{\sum }_{j=i}^{len-1}f(S[i:j])$ 。

输入格式

输入一行包含一个由小写字母组成的字符串 $S$ 。

输出格式

输出一个整数表示答案。

样例输入

ababc

样例输出

28

数据规模

所有数据保证字符串长度 $len\le 1000000$，字符串下标从 $0$ 到 $len-1$。

解题思路

直接正面求解每一个字符串的分值显然会$TLE$，那么尝试其他方法

我们的想法是单独处理每一个字符的分值，然后累加起来

直接去找该字符出现在多少字符串中并不容易，正难则反，我们尝试去寻找该字符没有出现在多少字符串中

举个例子ababc，其中a没有出现的字符串显然只有b,b,c,bc

所以想要找到所有没有出现a的字符串，我们只需要保存a出现过的每一个位置，然后根据间隔字符串长度计算即可

AC代码如下

#include <iostream>
#include <vector>
using namespace std;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const int max_len = 1e6;vector<int>vocab[26];
long long ans = 0;inline long long calc(long long num) {return num * (num + 1) / 2;
}int main() {string str;cin >> str;int len = str.size();for (int i = 0; i < len; i++) {vocab[str[i] - 'a'].push_back(i);}for (char c : alpha) {long long sum = calc(len);if (!vocab[c - 'a'].empty()) {int l = 0;auto iter = vocab[c - 'a'].begin();while (iter != vocab[c - 'a'].end()) {sum -= calc(*iter - l);l = *iter + 1; iter++;}sum -= calc(len - l);ans += sum;}}cout << ans << endl;return 0;
}

后排提醒：要开long long，否则会炸

T5 [Daimayuan]蒟蒻（C++，STL）

便利蜂的货架上摆了一排蒟蒻果冻，搞得鶸尛鱻眼花缭乱…

对于每个果冻，都有一个价格 $w$ 和口感 $t$。鶸尛鱻有一个购物篮子，在挑选蒟蒻果冻的时候，他有以下几种操作：

• 操作 $1$：把一个价格为 $w$，口感为 $t$ 的果冻放入篮子。
• 操作 $2$：拿出篮子中 最为廉价 的果冻。
• 操作 $3$：拿出篮子中 口感最差 的果冻。（$t$ 越小，口感越差）

鶸尛鱻不喜欢重复，当操作 $1$ 的 价格或口感 与篮中已有果冻重复时，他会立刻将其放回货架。

经过 $n$ 次操作后，鶸尛鱻确定了要购买的若干果冻，请你帮他求出篮子里果冻的总价格。

输入格式

第 $1$ 行一个正整数 $n$，代表操作次数。

第 $2$ 行至第 ($n+1$)($n+1$) 行，每行 一个或三个 整数，分别表示 $op$，$w$，$t$。

$w$ 和 $t$ 当且仅当 $op=1$ 时存在。

输出格式

输出一个整数，表示篮子里果冻的总价格。

样例输入

6
1 1 1
1 2 5
2
1 3 3
3
1 5 2

样例输出

7

数据规模

所有数据保证 $1\le n\le 10^5$，$1\le w,t\le 10^6$，且保证输入合法。

解题思路

需要维护两个顺序，一个是价格的升序排序，一个是口感的升序排序

显然需要维护两个数组，关键在于使两个数组维持同步

利用map的erase操作可以根据键值删除元素的性质，可以很容易实现这一点

AC代码如下

#include <iostream>
#include <map>
using namespace std;
const int max_n = 1e5;
const int max_w = 1e6;
const int max_t = 1e6;map<int, int>m1, m2;
int w, t, n, op;
long long ans;int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> op;if (op == 1) {cin >> w >> t;if (m1.count(w) == 0 && m2.count(t) == 0) {m1[w] = t;m2[t] = w;}}else if (op == 2) {m2.erase(m1.begin()->second);m1.erase(m1.begin());}else {m1.erase(m2.begin()->second);m2.erase(m2.begin());}}for (auto it : m1) {ans += (long long)(it.first);}cout << ans << endl;return 0;
}

T6 [Daimayuan]锦标赛（C++，模拟）

有$n$个玩家参加比赛，他们分别有能力值$a_1,a_2,\dots ,a_n$。

需要进行$n-1$轮比赛，每一轮在剩下的玩家里任选两个玩家$i,j$。如果$|a_i-a_j|>K$，那么其中能力值高的玩家会获胜，能力值低的玩家会被淘汰。如果$|ai-aj|\le K$，那么两个玩家都有可能获胜，另一个玩家被淘汰。

$n-1$轮比赛之后，只剩下一个玩家。问有多少个玩家可能是最后获胜的玩家。

输入格式

第一行，两个整数$n,K$，表示玩家的总人数，和获胜条件中的参数。

接下来一行$n$个整数$a_1,a_2,\dots ,a_n$，表示玩家的能力值。

输出格式

一个整数，表示最后可能获胜的玩家个数。

样例输入1

5 3
1 5 9 6 3

样例输出1

5

样例输入输出2

见下发文件。

数据规模

共$10$组数据。

测试点$1$满足$n\le 5$。

测试点$2$满足$n\le 10$。

测试点$3,4,5$满足$n\le 1000$。

对于$100$%的数据，满足$n\le 10^5$,$1\le a_i,K\le 10^9$。

解题思路

能力值越高的越容易获胜，这是显然的

如果我们要计算最多有多少人可能获胜，自然要求出能获胜的最低能力值是多少

题目中给出了一个能够以弱胜强的最大能力差值$K$，能力差值大于$K$的时候弱的一方不可能获胜

所以我们让能力值大的先开始比赛，每次比赛都让能力值小的一方获胜（前提是能获胜）

最后当能力值小的一方不可能获胜的时候，我们就得到了最多有多少人可能获胜

AC代码如下

#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = 1e5;
const int max_a = 1e9;
const int max_k = 1e9;int n;
long long k, gamer[max_n + 1];int main() {cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> gamer[i];}sort(gamer + 1, gamer + 1 + n, greater<long long>());long long ans = 1;long long buffer = gamer[1];for (int i = 2; i <= n; i++) {if (buffer - gamer[i] <= k) {ans++;buffer = gamer[i];}else break;}cout << ans << endl;return 0;
}

T7 [Daimayuan]可重排列（C++，字符串）

请按字典序从小到大的顺序输出所有序列，满足序列中有 $p_1$ 个 $1$, $p_2$ 个 $2$, $...$ , $p_n$ 个 $n$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_1$,$p_2$,…,$p_n$。

输出格式

按字典序从小到大的顺序一行一行输出所有满足条件的序列，每行一个序列，相邻两个数字需要用空格隔开。

样例输入

3
1 2 2

样例输出

1 2 2 3 3
1 2 3 2 3
1 2 3 3 2
1 3 2 2 3
1 3 2 3 2
1 3 3 2 2
2 1 2 3 3
2 1 3 2 3
2 1 3 3 2
2 2 1 3 3
2 2 3 1 3
2 2 3 3 1
2 3 1 2 3
2 3 1 3 2
2 3 2 1 3
2 3 2 3 1
2 3 3 1 2
2 3 3 2 1
3 1 2 2 3
3 1 2 3 2
3 1 3 2 2
3 2 1 2 3
3 2 1 3 2
3 2 2 1 3
3 2 2 3 1
3 2 3 1 2
3 2 3 2 1
3 3 1 2 2
3 3 2 1 2
3 3 2 2 1

数据规模

对于 $100$% 的数据，保证 $1\le n\le 9$,$1\le p_i\le 9$，保证满足条件的序列个数不超过 $10^5$ 个。

解题思路

这里我们隆重介绍一个新的偷懒工具，next_permutation和prev_permutation

传入的参数是数组的起止位置指针，功能是对数组本身操作，得到下一个/上一个字典序排列

然后怎么做就不用我说了吧$qwq$

AC代码如下

#include <iostream>
#include <algorithm>
using namespace std;void read(string& str) {int n1, n2;cin >> n1;for (int i = 1; i <= n1; i++) {cin >> n2;str.append(n2, i + '0');}
}int main() {string str = ""; read(str);int len = str.size();do {for (int i = 0; i < len; i++) printf("%c ", str[i]);printf("\n");}while (next_permutation(str.begin(), str.end()));return 0;
}

T8 [Daimayuan]进制转换（C++）

题面

让我看看是谁不会进制转换，哦原来是我

---

以不同进制的形式输入 $n$ 个非负整数，求出它们的和并以 $m$ 进制的形式输出。

使用大写字母 A ~ Z 依次代表 $10$ ~ $35$， 小写字母 a ~ z 依次代表 $36$ ~ $61$。

输入格式

第一行输入两个整数 $1\le n\le 10$ ， $2\le m\le 62$ 。

接下来 $n$ 行，每行输入一个整数 $2\le t\le 62$， 一个 $t$ 进制数 $0\le x\le 10^9$。

输出格式

一个 $m$ 进制数，为最终的结果

输入样例1

2 2
2 1
6 10

输出样例1

111

输入样例2

1 10
52 aA0

输出样例2

97864

输入样例3

2 52
36 AMD
52 YES

输出样例3

dJD

解题思路

由任意进制转换为十进制：

遍历每一位上的数字，乘以其位权重，累加

由十进制转换为任意进制：

对十进制数进行取模，余数插入转换后结果的左侧，然后将十进制数除以$10$，循环操作直到十进制数为$0$

AC代码如下

#include <iostream>
#include <map>
#include <string>
using namespace std;
const int max_n = 10;
const int max_m = 62;
const int max_t = 62;
const int max_len = 64;
const string sign_set = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";int n, t;
long long m;
string num;
map<char, int>convert;
char output[max_len + 1];void init() {int len = sign_set.size();for (int i = 0; i < len; i++) {convert.insert(pair<char, int>(sign_set[i], i));}
}int main() {init();cin >> n >> m;long long decimal = 0;for (int i = 0; i < n; i++) {cin >> t >> num;int p = 1;int len = num.size() - 1;for (int i = len; i >= 0; i--) {decimal += (long long)(convert[num[i]] * p);p *= t;}}int idx = max_len - 1;while (decimal != 0) {output[idx--] = sign_set[decimal % m];decimal /= m;}cout << &(output[++idx]) << endl;return 0;
}

T9 [Daimayuan]循环子串（C++，字符串）

题目描述

一个字符串$S$是另一字符串$T$的循环子串当且仅当存在$k$, $T$所有字符循环右移$k$位后得到的新串$T\prime$，满足$S$是$T\prime$的子串。

例如: abc 是 cefab的循环子串。 (cefab循环右移$2$位得到abcef, abc是abcef的子串)

一个串$P$是完全循环串当且仅当对于它的任一子串$H$, 都有$Hreverse$是$P$的循环子串 ($Hreverse$ 为 $H$的倒转, 如abc $reverse$后 为cba)。

给一个长度为$n$的字符串, 判断它是不是完全循环串。

输入格式

第一行一个正整数$t$, 表示测试数据组数。

对于每一组数据，第一行一个正整数$n$, 表示字符串的长度。接下来一行一个长度为$n$的字符串. 仅包含小写字母。

输出格式

对于每组测试数据，如果这个串是完全循环串, 输出YES，否则输出NO。每组测试数据之间输出换行。

数据范围

对于所有数据 有 $1\le t\le 100$, $1\le n\le 10^3$, $\sum n\le 10^3$。

样例输入

2
4
ccca
11
eeaafbddfaa

样例输出

YES
NO

提示

1. 本道题目只需要语法知识就可以解决。

2. 任意子串是什么意思呢？

3. 如果一个子串包含另一个子串，那么我们是不是只需要求出大子串的合法情况，就可以推出小子串的合法情况。

4. 从大的子串向小的子串考虑 最大的子串是什么呢？

解题思路

假设abc是循环子串，那么cba也应该是循环子串，则有***abc***cba***

*注：这里将abc与cba调换也可以，*的数量可以是任意的

进一步假设abcd是循环子串，则有***abcd*dcba***

不难发现，如果abcd是循环子串，则abc自然也是循环子串

所以我们只需要证明最大的循环子串符合条件即可

也就是将给定字符串反转，然后寻找其是否存在

而对于可以循环右移的字符串，我们只需要将其复制然后拼接，在处理之后的字符串中寻找即可

AC代码如下

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int max_t = 100;
const int max_n = 1e3;string str;
int t, len;int main() {cin >> t;for (int i = 0; i < t; i++) {cin >> len >> str;string rev = str;reverse(rev.begin(), rev.end());str = str + str;if (str.find(rev) != -1)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

T10 [Daimayuan]饿饿 饭饭之暑假大狂欢（C++，数学）

故事接着《饿饿 饭饭 2》，又过了几个月，暑假来啦！！！

这天，$cc$和他的小伙伴们决定一起去游乐园玩，他们一天将游乐园的所有设施玩了个遍，甚至大摆锤，过山车他们还去了很多次，愉快的时间总是很短暂的，很快时间就来到了晚上，但是你以为一天的娱乐时光就这样结束了吗，那你就猜错啦。

晚上，游乐园晚上的$party$就开始啦，其中有一个游戏环节，赢的人可以得到免费的西瓜，饿到不行的$cc$和他的小伙伴非常希望得到这个西瓜。

包括$cc$和他的小伙伴，有$t$个玩家参与了这个游戏，每个玩家都有一张带有数字的卡片。第$i$张卡片上有$n_i$个数字，分别是$m_1,m_2,...m_n$。

游戏过程中，主持人从袋子里一个一个地取出编号的球。 他用洪亮而清晰的声音大声念出球的编号，然后把球收起来。 如果玩家的卡片上有对应的数字，就可以将它划掉。 最先从他的卡片上划掉所有数字的人获胜。 如果多人同时从他们的卡片上划掉所有数字，那么这些人都不能赢得比赛。 在游戏开始时，袋子里有 $100$ 个球，编号从 $1$ 到 $100$，所有球的编号都是不同的。

$cc$偷偷知道了每个玩家的数字。 想请你确定每个玩家是否可以在最有利于他的情况下赢得比赛。

输入格式

第一行给出一个数$t$，代表$t$个玩家。

接下来第二行到$t+1$行，每行第一个数为$n_i$，代表这个人手中有$n$个卡片，接下来给出序列$a_1...a_n$表示这个人所拥有的卡片的数字。

输出格式

输出$t$行，每一行给出第$i$个人在最有利的情况下是否能赢得比赛，可以输出YES, 不可以输出NO。

数据范围

$1\le t\le 100,1\le n\le 100,1\le m_i\le 100$

样例输入

3
1 1
3 2 4 1
2 10 11

样例输出

YES
NO
YES

解题思路

不难发现，如果有一个人不能获胜，那么一定是有其他人的数字集合是他的子集（注：由于可以一次性划去多个数字，重复个数字直接按单个数字处理即可）

那么采用最简单的判断思路——暴力搜索

计算一下时间复杂度：最多需要判断$100$个人，对于每个人需要搜索其余$99$个人，每人最多有$100$个数字，所以时间复杂度上限是$10^6$，可以接受

所以我们可以采用二维bool数组存储每一个人数字，然后进行||的操作：

num_arr[i][k] != (num_arr[i][k] || num_arr[j][k])

当且仅当num_arr[i][k]没有k数字（为$false$），且num_arr[j][k]有k数字（为$true$）时表达式为真

如果表达式为真，就可以停止判断了，因为二者有不同的元素；如果表达式始终为假，那么就说明j的数字集合是i的子集，i不可能获胜

AC代码如下

#include <iostream>
using namespace std;
const int max_n = 100;
const int max_len = 100;bool num_arr[max_n + 1][max_len + 1];
int n, m;int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> m;int num;for (int j = 0; j < m; j++) {cin >> num;num_arr[i][num] = true;}}for (int i = 1; i <= n; i++) {bool win = true;for (int j = 1; j <= n; j++) {if (i == j) continue;int k;for (k = 1; k <= max_len; k++) {if (num_arr[i][k] != (num_arr[i][k] || num_arr[j][k])) {break;}}if (k == max_len + 1) {win = false;break;}}if (win) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}