算法竞赛入门【码蹄集进阶塔335题】(MT2201-2225）

算法竞赛入门【码蹄集进阶塔335题】(MT2201-2225）

前言

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。

目录

1. MT2201 字符串转换

（1）题目描述
对于两个字符串A和B，需要找出最少的变换次数使得A与B一致。

每次变换可以选择如下三种操作的其中一种:
1.删除一个字符，
2.插入一个字符，
3.将一个字符改写为另一个字符。

格式

输入格式: 输入两行，每行一个非空字符串分别对应A和B，字符串仅由小写字母组成。
.
输出格式: 输出一个整数，代表将A变为B所需的最小操作次数。

样例1

输入:
asdfghjkl
ssdghjkl
.
输出: 2

备注：

字符串长度不超过2000。

（2）参考代码

#include <stdio.h>
 #include <string.h>
 #include <algorithm>
 using namespace std;

 int dp[2005][2005];
 char a[2005], b[2005];

 int main(){
 scanf("%s", a+1); scanf("%s", b+1);
 int len_a = strlen(a+1), len_b = strlen(b+1);

 for (int j = 0; j <= len_b; j++) dp[0][j] = j;
 for (int i = 0; i <= len_a; i++) dp[i][0] = i;

 for (int i = 1; i <= len_a; i++) {
 for (int j = 1; j <= len_b; j++) {
 dp[i][j] = 0x3fffffff;
 if (a[i] == b[j]) { dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
}

 dp[i][j] = min(dp[i][j], 1 + dp[i][j-1]);
 dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]);
 dp[i][j] = min(dp[i][j], 1 + dp[i-1][j-1]);
 }
 }

 printf("%d\n", dp[len_a][len_b]);
 return 0;
 }

2. MT2202 Summer Pockets

（1）题目描述

小码妹是一个喜欢字符串的女孩子。

小码妹有一个长度为n 的字符串s 和一个大小为m 的字符集。

现在小码妹希望通过在s 两端增加或删去字符，使得s 变为一个回文串。但是增加或删去不同字符需要花费的代价不同。

小码妹希望花费最少的代价达成目标，于是她想寻求你的帮助。

格式

输入格式:
第一行输入一个整数n,n表示数据组数。
接下来n行，每行输入一个复数（以类似”a+bi”的格式输入，但不一定最简，可能会有多个项，输入的项的系数是浮点数)。
.
输出格式:
输出n行，按题目描述中“最简情况”输出读入得到的复数，浮点数用cout或printf( "%g”)输出。

样例1

输入:
第一行两个正整数m和n，分别表示字符集大小和s 的长度。
第二行为字符串s。
接下来 m行，每行由一个字符c (数据保证字符c唯一)和两个整数a, gy组成，之间用空格隔开，表示在s两端增加字符c需要α 的代价，删去字符c需要y的代价。
.
输出:
输出一个整数，表示将s 变为回文串需要的最小代价。

备注：

测试数据保证1≤m≤ 26， 1≤n ≤2000, 1≤a, y ≤10000且字符集为小写英文字母的子集。

（2）参考代码

#include<stdio.h>
#include <string.h>
#define min(x,y) (x)<(y)?(x):(y)
int dp[2005][2005];
int cost[30];
int main() 
{ 
    char str[2005];
    int n,m,i,j;
    scanf("%d %d %s",&n,&m,str);
    char c;int add,del;
    for(i=0;i<n;i++){
        scanf(" %c %d %d",&c,&add,&del);
        cost[c-'a']=min(add,del);
    }
    memset(dp,0,sizeof(dp));
    for(j=1;j<m;j++)
        for(i=j-1;i>=0;i--){
            dp[i][j]=min(dp[i+1][j]+cost[str[i]-'a'],dp[i][j-1]+cost[str[j]-'a']);
            if(str[i]==str[j])
            dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
        }
        printf("%d\n",dp[0][m-1]);
 
    return 0; 
}

3. MT2203 s的排列

（1）题目描述
给两个字符串s1和s2，判断s2中是否有s1的排列。

如果是返回true ，否则返回false 。

s1的排列指的是s1字符的不同排列。

格式

输入格式:
第一行输入字符串s1
第二行输入字符串s2
.
输出格式: 输出小写的true或false

样例1

输入:
ab
eidbaooo
.
输出: true

（2）参考代码

// 编写一个判断子串的函数
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

bool checkInclusion(string s1, string s2) {
        if(s1.size()>s2.size())return false;  //剪枝，如果s1.size()>s2.size()，直接返回false;
        vector<int>a1(26,0),a2(26,0); //申请两个容器；
        for(int i=0;i<s1.size();i++){
           a1[s1[i]-'a']++;
           a2[s2[i]-'a']++;  //把s1和s2装入容器中；

        }
        if(a1==a2)return true; //如果相等，直接返回true;

        for(int i=s1.size(),j=0;i<s2.size();i++,j++){  //滑动窗口部分。
            a2[s2[j]-'a']--;
            a2[s2[i]-'a']++;

            if(a1==a2)return true;
        }

    return false;
    }

int main(){
    string s1,s2;
    cin>>s1;
    cin>>s2;   
    if(checkInclusion(s1,s2)) printf("true");
    else printf("false");
    return 0;

}

4. MT2204 字母匹配

（1）题目描述
小码哥有一个字符串s。

现在他想请你判断有多少对(x , gy)满足s[c] =s[y]。其中x可以等于y。

注意(ac, y)和(g, z）是不相同的一对。

格式

输入格式:
第一行一个字符串S，长度小于等于1e5，包含ASClI码从33到125的所有字符。
.
输出格式: 按题目要求输出一行一个整数，表示(x,y)的对数。

样例1：

输入： greaat
.
输出：8

（2）参考代码

import time
from collections import deque, Counter

def main():
    #code here
    c = Counter(input())
    tot=0
    for v in c.values():
        tot+=v**2
    print(tot)


if __name__ == '__main__':
    main();

5. MT2205 数字重排

（1）题目描述
给出n个数和m个字符串，字符串可以重复，而且重复的字符串视为一种字符串，同种字符串所代表的价值相同。

求把n个数分配给k种(注意，这里的k表示在这m个字符串中有k种不同类型的字符串，不过这个k是多少可能需要你自己去求)字符串得到的值的和最小价值和最大价值分别是多少(一个数只能分配一次)。

格式

输入格式:
输入第一行两个整数n, m （1 ≤m ≤100,1≤n ≤100000)。接下来一行n个数字，表示n个数(数字的范围均为1≤a≤1000 )。
接下来m行，分别表示m个字符串，保证每个字符串只含小写字母，长度不超过11且不含空格。
.
输出格式: 输出一行两个整数分别表示可以得到的最小值和最大值。

样例1

输入:
6 5
3 5 1 6 8 1
peach
grapefruit
banana
orange
orange
.
输出: 11 30

备注：

样例解释:
有4种字符串:
peach * 1;
grapefruit * 1;
banana * 1;
orange * 2。
最小值:取1,1,3,5,min = 12＋11＋31＋51 = 11 ，
最大值:取8,6,5,3,maa =82＋61＋51＋31 = 30。

（2）参考代码

#include <bits/stdc++.h>
using namespace std;
string a[105];
int n,m;
int b[100005],c[105],d[105];
int main()
{
cin>>n>>m;
int i,j,t,x=0,y=0;
for(i=0;i<n;i++) cin>>b[i];
sort(b,b+n);
for(i=0;i<m;i++) cin>>a[i];
for(i=0;i<m;i++) c[i]=1;
for(i=0;i<m&&(c[i]!=-1);i++)
{
for(j=i+1;j<m;j++)
{
if(a[j]==a[i])
{
c[i]++;
c[j]=-1;
}
}
}
j=0;
for(i=0;i<m;i++)
{
if(c[i]>0)
{
d[j]=c[i];
j++;
}
}
sort(d,d+j);
for(i=0,t=j-1;t>=0;i++,t--) x+=d[t]*b[i];
for(i=n-1,t=j-1;t>=0;i--,t--) y+=d[t]*b[i];
cout<<x<<" "<<y;
return 0;
}

6. MT2206 萨卡兹人

（1）题目描述
很久很久以前，卡西米尔里住着萨卡兹人，他们彼此争斗不休。有一天，他们想要研究自己的 DNA序列，来证明他们是一个种群。我们首先选取一个好长好长的序列(DNA序列包含26个小写英文字母)，然后我们每次选择两个区间，这两个区间代表两个萨卡兹人的DNA序列，这两个萨卡兹一模一样的唯一可能是他们的DNA序列一模一样。

格式

输入格式:
第一行一个 DNA字符串S。
接下来一个数字m，表示 m次询问。
接下来 m行，每行四个数字l1, r1,l2,r2，分别表示此次询问的两个区间，注意字符串的位置从1开始编号。
.
输出格式: 对于每次询问，输出一行表示结果。如果两个萨卡兹完全相同输出Yes，否则输出No

样例1

输入:
aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2
.
输出:
Yes
No
Yes

备注：

提示
1.1<l≤r1 ≤length(S),1 ≤l≤r2≤length(S)
2.1≤length(S)，m ≤ 1000000

（2）参考代码

#include <bits/stdc++.h>
 #define ULL unsigned long long

 using namespace std;
 const int N=1e6+100;
 ULL h[N],p[N];
 char s[N];
 int main(){
 scanf("%s",s+1);
 int n=strlen(s+1);
 int m;
 scanf("%d",&m);
 //预处理出所有前缀的Hash值和131的幂
 p[0]=1;
 for(int i=1;i<=n;i++){
 p[i]=p[i-1]*131;
 h[i]=h[i-1]*131+s[i];
 }

 while(m--){
 int l1,r1,l2,r2;
 scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
 if(h[r1]-h[l1-1]*p[r1-l1+1]==h[r2]-h[l2-1]*p[r2-l2+1])
printf("Yes\n");
 else printf("No\n");
 }
 return 0;
 }

7. MT2207 建立数据库

（1）题目描述
新用户注册时，他将向系统发送一则内容为其用户名的请求，如果该用户名尚未存在于系统数据库内，则将该用户名插入数据库，同时用户得到回应信息oK表示其已经成功注册。如果用户请求的用户名已经存在于数据库内，那么系统将产生一个新的用户名并将其加入数据库。新用户名由用户请求的用户名与正整数i构成， i为使"用户名i”尚未存在于数据库内的最小的 i。

格式

输入格式: 第一行一个整数n(1≤n ≤105)。接下来n 行，每行表示用户向系统发出的一则请求。每行内容均非空且均为由至多32个小写拉丁字母组成的字符串。
.
输出格式: n 行，每行表示系统对—则请求做出的回应。如果该用户名尚未存在于系统数据库内，则输出oK。如果用户请求的用户名已经被注册，则输出依照规则生成的新用户名。

样例1

输入:
6
first
first
second
second
third
third
.
输出:
OK
first1
OK
second1
OK
third1

（2）参考代码

import java.util.Scanner;
import java.util.*;
import java.util.HashMap;
 import java.util.Map;
 import java.util.Scanner;

 public class Main {
 public static void main(String[] args) {
 Scanner input=new Scanner(System.in);
 int n=input.nextInt();
 input.nextLine();
 Map<String,Integer> map=new HashMap<String,Integer>();
 for(int i=0;i<n;i++){
 String s=input.nextLine();
 if(map.containsKey(s)){
 map.put(s,map.get(s)+1);
 }else{
 map.put(s,map.getOrDefault(s,0));
 }
 if(map.get(s)==0){
 System.out.println("OK");
 }else{
 System.out.println(s+map.get(s).toString());
 }
 }

 }
 }

8. MT2208 雪色雪花余痕

（1）题目描述
小码哥是一个喜欢字符串的男孩子。

小码哥发动THE ORDER时需要在心中默念一大段前摇串。

具体来说，小码哥会在心中默念n个字符串，然后统计每个串出现的次数。

为了备战与小码妹的最终决战，小码哥希望你帮助他完成这个任务来缩短发动THE ORDER的前摇。

格式

输入格式:
第一行一个正整数n，表示前摇串个数。
接下来n 行，每行一个字符串，即为希亚在心中默念的前摇串。
.
输出格式:
对于每一个本质不同的前摇串，输出一行答案，包含这个前摇串本身和它出现的次数，用空格隔开。
答案按照前摇串字典序从小到大排列。

样例1

输入:
5
oaaue
eoeia
oaaue
aoauiio
uuo
.
输出:
aoauiio 1
eoeia 1
oaaue 2
uuo 1

备注：

前摇串的字符集为小写aiueo
所有前摇串的长度的总和不会超过2.5×10的7次。

（2）参考代码

#include<bits/stdc++.h> 
using namespace std;

 int n;
 map<string, int> strs;

 int main()
 {
 ios::sync_with_stdio(false);
 cin >> n;
 for (int i = 0; i < n; i++)
 {
 string str;
 cin >> str;
 strs[str]++;
 }
 for (pair<string, int> aStr : strs)
 {
 cout << aStr.first << ' ' << aStr.second << endl;
 }
 return 0;
 }

9. MT2209 五彩斑斓的曙光

（1）题目描述
小码哥是一个喜欢字符串的男孩子。

小码哥在研究字典序的性质。他发现他可以通过改变字母表的顺序来改变两个字符串的大小关系。

例如，通过将现有的字母表顺序 abcdefghijklmnopqrstuvwxyz 改为abcdefghijklonmpqrstuvwxyz，字符串 omm会小于mom

现在小码哥有n个字符串，对于其中的一个字符串，如果存在某种字母表顺序，使得它在这n个字符串中字典序最小，那这个字符串就是一个「五彩斑斓的串」。

现在小码哥想找出所有五彩斑斓的串，由于小码哥忙于他的研究，找出所有五彩斑斓的串的重任被交到了你的身上。

格式

输入格式: 第一行一个正整数n，表示字符串的个数。接下来n 行，每行一个字符串。
.
输出格式: 输出第一行为一个正整数，为「五彩斑斓的串」的个数。接下来对于每个五彩斑斓的串输出一行。
注意:输出的串的顺序应该和输入一致!

样例1

输入:
4
omm
moo
mom
ommnom
.
输出:
2
omm
mom

备注：

测试数据保证1≤n ≤3×104，所有字符串的总长不超过3×105，且字符集为小写英文字母。

（2）参考代码

#include <bits/stdc++.h>
 #define int long long
 #define end END
 #define endl "\n"
 #define debug(x) cout << "*----" << x << "----*" << endl
 #define show(x) cout << #x "=" << x << endl
 using namespace std;
 typedef long long ll;
 const int N = 3e4 + 7;
 const int INF = 0x3f3f3f3f;
 const int mod = 1e9 + 7;
 string s[N];
 int trie[N * 10][26];
 int tot;
 bool end[N*10];
 void insert(int x)
 {
 int p = 0;
 for (int i = 0; i <s[x].size(); i++) {
 int ch = s[x][i] - 'a';
 if (trie[p][ch] == 0)
 trie[p][ch] = ++tot;
 p = trie[p][ch];
 }
 end[p] = 1;
 }
 int g[26][26];
 bool ask(int x)
 {
 memset(g, 0, sizeof g);
 int p = 0;
 for (int i = 0; i < s[x].size(); i++) {
 int ch = s[x][i] - 'a';
 if (end[p])
 return false;
 for (int j = 0; j < 26; j++) {
 if (j != ch && trie[p][j]) {
        if(g[ch][j]>0) return false;
        }
}
for(int j=0;j<26;j++){
     if (j != ch && trie[p][j]) {
 g[ch][j] = -1;
 g[j][ch] = 1;
 vector<int> a, b;
 for (int k = 0; k < 26; k++) {
 if (g[j][k] == -1) {
 g[ch][k] = -1;
 g[k][ch] = 1;
 b.push_back(k);
 }
 if (g[ch][k] == 1) {
 g[j][k] = 1;
 g[k][j] = -1;
 a.push_back(k);
 }
 }
 for (auto u : a) {
 for (auto v : b) {
 g[u][v] = -1;
 g[v][u] = 1;
 }
 }
 }
 }
 p = trie[p][ch];
 }
 return true;
 }
signed main()
 {
 int n;
 cin >> n;
 int sum=0;
 for (int i = 1; i <= n; i++) {
 cin >> s[i];
 sum+=s[i].size();
 insert(i);
 }
 if(sum>3e5) while(true);
 if(n>3e4) while(true);
 if(tot>3e5) while(true);

 vector<int> ans;
 for (int i = 1; i <= n; i++) {
 if (ask(i))
 ans.push_back(i);
 }
 cout << ans.size() << endl;
 for (auto u : ans) {
 cout << s[u] << endl;
 }
 return 0;
 }

10. MT2210 回文串等级

（1）题目描述
所谓量变产生质变，就比如低级的材料攒多了可以合成更高级的玩意儿，高级的回文串也可以由低级的组成。任意一个字符串都可以是0级的回文串。而一个更高级的长为n的i级回文串则满足其长为n/2(向下取整)的前后缀都为i―1级回文串。现在给你一个字符串，问你其每个前缀的回文串等级。

格式

输入格式: 一行一个字符串S。
.
输出格式: |S|个数，表示其长为1,2,3. …|S|的前缀的回文串等级。

样例1

输入: aaa
.
输出: 1 2 2

备注：

其中: 1≤|S|≤500000 。

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;
typedef long long ll;
 const int N = 5e6 + 100;
 const int INF = 0x3f3f3f3f;
 const int mod = 1e9 + 7;
 const unsigned long long P = 13131;
 char s[N];
 int ans[N];
 unsigned long long p[N];
 unsigned long long pre[N];
unsigned long long suf[N];
int long long hash1(int l, int r)
 {
 if (l <= r)
 return pre[r] - pre[l - 1] * p[r - l + 1];
 else
 return suf[r] - suf[l + 1] * p[l - r + 1];
 }
 int main(){
 scanf("%s", s + 1);
 int n = strlen(s + 1);
 p[0] = 1;
 for (int i = 1; i <= n; i++)
 p[i] = p[i - 1] * P;
 for (int i = 1; i <= n; i++) {
 pre[i] = pre[i - 1] * P + s[i];
 }
 for (int i = 1; i <= n; i++) {
 int x = n - i + 1;
 suf[x] = suf[x + 1] * P + s[x];
 }
 for (int i = 1; i <= n; i++) {
 if (hash1(1, i) == hash1(i, 1))
 ans[i] = ans[i / 2] + 1;
 }
 int sum = 0;
 for (int i = 1; i <= n; i++) {
 printf("%d%c",ans[i]," \n"[i==n]);
 }
 return 0;
 }

11. MT2211 字符串构造

（1）题目描述
你有一个字符串t，它由n个字母组成。

定义一个字符串s的子串为s [1 …r]，表示从位置1到r构成的一个新的串。

你的目标是构造一个字符串s，使得它的可能长度最小，要求s中存在k个位置i,可以找到k个以i为出发点的子串t。

格式

输入格式: 第一行输入两个整数n和k，表示t的长度和需要k个子串，( 1 ≤n, k ≤ le5，保证答案字符串的长度在3e5范围内)。第二行输入字符串t。
.
输出格式: 输出满足条件的长度最小的s。题目保证答案唯一。

样例1

输入:
3 4
aba
.
输出: ababababa

（2）参考代码

 #include<bits/stdc++.h>

using namespace std;

 const int N = 1e6 + 10;
 int f[N]; //失败函数

 void fail(string p,int m){ //失败函数的计算，自己和自己匹配
 int i = 1;
 int j = 0;
 f[0] = -1;
 while(i < m){
 if(p[i] == p[j]) f[i] = j,i++,j++;
 else if(j == 0) f[i] = -1,i++;
 else j = f[j - 1] + 1;
 }
 }
 int main(){
 int n, k;
 scanf("%d %d", &n, &k);
 string str;
 cin>>str;
 fail(str, n); //计算失败函数
 
 int num = f[n - 1] + 1; //即为前缀和后缀有多少个是匹配的
 string tmp = str.substr(num, n - num);
 string ans = str;
 for(int i = 1 ; i < k ; i++){
 ans += tmp;
 }
 cout<<ans;
 
 return 0;
 }

12. MT2212 密码

（1）题目描述
小码哥，小码妹和他们的临时伙伴小码弟、小码姐已经最终找到了和谐寺。然而和谐寺大门紧闭，就连小码妹的运气也没好到能打开它。

不久他们发现了一个字符串S (1<=|S/<=1000000)，刻在和谐寺大门下面的岩石上。小码哥猜想那一定是打开寺庙大门的密码，于是就大声将字符串朗读了出来，然而并没有什么事发生。于是小码哥又猜想密码一定是字符串S的子串T。

小码姐认为T是S的前缀，小码弟认为T是S的后缀，小码妹却认为T应该是S中间的某一部分。

小码哥选择子串T来满足所有伙伴们的想法。同时，在所有可以被接受的子串变形中，小码哥选择了最长的一个(因为小码哥喜欢长的字符串）当小码哥大声读出子串T时，寺庙的大门开了。(也就是说，你需要找到既是S的前缀又是S的后缀同时又在S中间出现过的最长子串)

现在给你字符串S，你需要找到满足上述要求的子串T。

格式

输入格式: 字符串S
.
输出格式: 输出子串T，如果T不存在，输出“Just a legend"，不包含引号。

样例1

输入: fixprefixsuffix
.
输出: fix

备注：

|S |≤1000000

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;
const int maxn=1e6+7;
char s[maxn];
int nxt[maxn],nxt_max=0,k;

int main(){
 scanf("%s",s+1);
 int n=strlen(s+1);
 for(int i=2,j=0;i<=n;i++)
 {
 while(j&&s[i]!=s[j+1])j=nxt[j];
 if(s[i]==s[j+1])j++;
 nxt[i]=j;
 if(i!=n)nxt_max=max(nxt_max,nxt[i]);
 }
 k=nxt[n];
 while(k>nxt_max)k=nxt[k];
 if(k)for(int i=1;i<=k;i++) printf("%c",s[i]);
 else puts("Just a legend");
 return 0;
 }

13. MT2213 最漂亮的工艺品

（1）题目描述
小码哥和小码妹是一对好朋友。

他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。

他们想知道，在仅这一种操作下，最漂亮的工艺品能多漂亮。

两个工艺品美观的比较方法是，从头开始比较，如果第i个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第i＋1个方块。如果全都一样，那么这两个工艺品就一样漂亮。

格式

输入格式:
第一行一个整数n ，代表方块的数目。
第二行n个整数，表示方块瑕疵度的值。
.
输出格式: —行n个整数，代表最美观工艺品从左到右方块瑕疵度的值。

样例1

输入:
10
10 9 8 7 6 5 4 3 2 1
.
输出: 1 10 9 8 7 6 5 4 3 2

（2）参考代码

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int MAX_STR_LEN = 600005;
int xx[MAX_STR_LEN];
int yy[MAX_STR_LEN];
int c[MAX_STR_LEN];
int sa[MAX_STR_LEN];
class SA {
private:
    const int* S;      // 输入字符串，位置从1开始
    int max_char_val;   // 最大字符大小
    bool sa_flag;       // 是否已经计算过sa
    bool height_flag;   // 是否已经计算过height
    int str_len;        // 字符串长度
public:
    
    SA(const int* str, int n, int max_char_val) : S(str-1), max_char_val(max_char_val), sa_flag(false), height_flag(false), str_len(n) {
        memset(xx, 0, sizeof(xx));
        memset(yy, 0, sizeof(yy));
        memset(c, 0, sizeof(c));
        memset(sa, 0, sizeof(sa));
    }
    // 计算sa数组
    int* get_sa() {
        int* x = xx;
        int* y = yy;
        if (sa_flag) {
            return sa;
        }
        int m = max_char_val;
        int n = str_len;
        
        for (int i = 1; i <= n; i ++ )
            c[x[i] = S[i]] ++ ;
        
        for (int i = 2; i <= m; i ++ )
            c[i] += c[i - 1];
        
        for (int i = n; i; i -- )
            sa[c[x[i]] -- ] = i;
        for (int k = 1; k <= n; k <<= 1)
        {
            int num = 0;
            for (int i = n - k + 1; i <= n; i ++ )
                y[ ++ num] = i;
            
            for (int i = 1; i <= n; i ++ )
                if (sa[i] > k)
                    y[ ++ num] = sa[i] - k;
            
            for (int i = 1; i <= m; i ++ )
                c[i] = 0;
            
            for (int i = 1; i <= n; i ++ )
                c[x[i]] ++ ;
            
            for (int i = 2; i <= m; i ++ )
                c[i] += c[i - 1];
            
            for (int i = n; i; i -- )
                sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
            
            swap(x, y);
            
            x[sa[1]] = 1, num = 1;
            for (int i = 2; i <= n; i ++ )
                x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
            
            if (num == n)
                break;
            
            m = num;
        }
        
        sa_flag = true;
        return sa;
    }
};
int arr[MAX_STR_LEN], b[MAX_STR_LEN];
int main(){
#ifdef TEST
    freopen("/Users/grh/Programming/CLionProjects/AlgoCoding/input.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    vector<int> v; v.reserve(n);
    set<int> ss;
    for (int i = 0; i< n; i++) {
        scanf("%d", arr + i);
        ss.insert(arr[i]);
    }
    for (auto val : ss) v.push_back(val);
    sort(v.begin(), v.end());
    unordered_map<int, int> val2idx;
    for (int i = 0; i < v.size(); i++) val2idx[v[i]] = i+1;
    for (int i = 0; i < n; i++) b[i] = b[i+n] = val2idx[arr[i]];
    SA algo(b, 2*n, v.size()+100);
    int* sa_arr = algo.get_sa();
    int start = 0;
    for (int i = 1; i <= 2*n; i++) {
        if (sa[i] <= n) {
            start = sa[i]-1; break;
        }
    }
    for (int idx = start; idx < start+n; idx++) {
        printf("%d ", v[b[idx]-1]);
    }
    printf("\n");
    
    return 0;
}

14. MT2214 天色天歌天籁音

（1）题目描述
小码哥是一个喜欢字符串的男孩子。为了更好地掌握ARTIFACT，小码哥把他的ARTIFACT抽象为了一个字符串s 。

小码哥还有一个记录串 t，记录串最初是空串。小码哥每次使用ARTIFACT时，都会从s 中拿出一个连续子串(可以是空串）拼接在记录串末尾。

小码哥在练习使用ARTIFACT 的时候想到一个问题，当他在记录串为空串的状态下使用k 次ARTIFACT后，可能产生多少种本质不同的记录串?

小码哥很懒，于是解决这个问题的重任被交到了你的身上。

格式

输入格式:
第一行为字符串s。
第二行为一个正整数q，表示小码哥询问你的次数。
接下来q行，每行一个正整数k，表示小码哥的询问。
.
输出格式:
你需要输出q行。
每行一个整数，表示小码哥使用对应次数ARTIFACT后，记录串可能由空串变为多少种本质不同的字符串。
由于答案非常大!你需要将你的结果对10的9次＋7取模后输出。

样例1

输入:
aab
3
1
2
3
.
输出:
6
25
96

（2）参考代码

#include <bits/stdc++.h>
using namespace std;
int f[10000001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=5000000;i++){
        for(int j=i*2;j<10000000;j+=i){
            int b=j-i;
            if((j^b)==i) f[j]++;
        }
    }
    for(int i=1;i<=n;i++) f[i]+=f[i-1];
    cout<<f[n];
} 

15. MT2215 REFLECTION BLUE

（1）题目描述

小码哥是一个喜欢字符串的男孩子,尤其喜欢字符串中的回文串。

现在小码哥拿到了两个字符串s和t，他想知道，这两个串中有多少子串相等且回文。具体来说:他定义 s(a, gj)为s 的第α个字符到第 y个字符组成的子串， t(z, y)类似。

他想知道有多少四元组(a,3,p, q）满足:
1≤a≤y≤|s|;
1≤p≤q≤|t;
s(z, gy) = t(p, q) ;
s(z, gy）为回文串。

如果你帮小码哥解决了这个问题，他就会邀请你到息白岛做客。

格式

输入格式:
第一行为字符串s。
第二行为字符串t。
.
输出格式: 输出一个整数，为满足条件的四元组个数。

样例1

输入:
PUPPY
PUPPUP
.
输出: 17

备注：

测试数据保证1≤|s|,t≤5×10的4次，且s 和t 的字符集均为大写英文字母。

（2）参考代码

#include<bits/stdc++.h> 

using namespace std;
typedef long long ll;

//整数分块
int main( )
{
    ll n,sum=0;
    cin>>n;
    for(int i=1,r;i<=n;i=r+1){
        r = n/(n/i);
        sum += (r-i+1)*(n/i);
    }
    cout<<sum;
    return 0;
}

16. MT2216 01操作

（1）题目描述
刚学二进制的小码哥对加减乘除还不熟，他希望你帮他复习操作。

对于二进制数有如下几个操作:
1.整个二进制数加1;
2.整个二进制数减1;
3.整个二进制数乘2;
4.整个二进制数除2。

(本题不会导致最高位进退位，即若全是1，之后操作加1的情况不会出现)以上的操作是二进制数的对应操作，乘2或除2会导致进退位。

格式

输入格式: 第一行两个正整数n,m，表示二进制数长度和操作数。接下来一行一个二进制数。第三行m个字符，’ +’ ,’ - ‘，’ * , ’ l ，'’对应操作1-4。
.
输出格式: 一行字符表示操作后的二进制数。

样例1

输入:
4 10
1101
/---//
.
输出: 10110

备注：

其中: n≤1000000。

（2）参考代码

#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;
const int N = 6000005;
char buf[6000005];
char val[6000005];
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    scanf("%s", val);
    int jj = n-1;
    scanf("%s", buf);
    for (int i = 0; i < m; i++) {
        char op = buf[i];
        if (op == '*') {
            jj++; val[jj] = '0';
        } else if (op == '/') {
            if (jj >= 1) {
                jj --;
            } else {
                val[jj] = '0';
            }
        } else if (op == '+') {
            for (int k = jj; k >= 1; k--) {
                if (val[k] == '0') {
                    val[k] = '1'; break;
                } else {
                    val[k] = '0';
                }
            }
        } else {
            for (int k = jj; k >= 1; k--) {
                if (val[k] == '1') {
                    val[k] = '0'; break;
                } else {
                    val[k] = '1';
                }
            }
        }
    }
    val[jj+1] = '\0';
    printf("%s\n", val);
    return 0;
}

17. MT2217 进制查询

（1）题目描述
给出一整数n，计算用2~n-1进制表示n时，每一个进制下所有位上的数字的和的平均数(结果用分数表示)。

注意，中间过程及输出均采用10进制。

格式

输入格式: 一行一个正整数n ( 3≤n ≤1000 )
.
输出格式: 一行一个数表示答案（一定要是分数形式，比如3需要写成3/1)

样例1

输入: 10
.
输出: 3/1

（2）参考代码

#include<bits/stdc++.h> 
using namespace std;
int n,sum,fm;
int main( )
{
    cin>>n;
    for(int i=2;i<n;++i){
        int x(n);
        while(x){
            sum+=x%i;
            x/=i;
        }
    }
    fm=n-2;
    int d(__gcd(sum,fm));
    cout<<sum/d<<'/'<<fm/d<<endl;
    return 0;
}

18. MT2218 永恒之2

（1）题目描述
小码哥被困扰住了，因为电脑它又双妤双坏了! ! !

现在还是想让你算一些东西:给出一个十六进制数k，求出在1到k中“2”出现了多少次（1到k都用十六进制表示)，其中k在十六进制下不大于10位。输出的答案请对99999989取余。

格式

输入格式:
第一行一个十进制整数n(1≤n ≤10)，表示k的位数。
第二行一个十六进制数k。
.
输出格式: 一个十进制整数，表示1到k中“2”出现的次数对99999989取余的答案。

样例1

输入:
2
2A
.
输出: 14

备注：

首先将从1到2A的所有数全部以十六进制的方式列出来:
1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,10,11,12,13,14,15,16,17,18,19,1A,1B,1C,1D,1E,1F,20,21,22,23,24,25,26,27,28,29,2A。我们可以数得“2”一共出现了14次。

（2）参考代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
const ll mod=99999989;
int n,len;
char s[20];
ll f[20][20];
ll get(int m,bool op){
    ll ans1=0,ans2=0;
    for(int i=m;i;--i){
        ans1=(ans1*16%mod+s[i]-'0')%mod;
        ans2=(ans2*16%mod+15)%mod;
    }
    if(op==0) return (ans1+1)%mod;
    return (ans2+1)%mod;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(f,0,sizeof(f));
        scanf("%s",s+1);len=strlen(s+1);
        for(int i=1;i<=len;++i) if(s[i]>='A'&&s[i]<='Z') s[i]=s[i]-'A'+'0'+10;
        reverse(s+1,s+len+1);
        ll ans=0; 
        for(int i=1;i<=len;++i){
            for(int j=0;j<=15;++j){
                if(j==2) f[i][j]=(f[i][j]+get(i-1,1))%mod;
                for(int t=0;t<=15;++t){
                    f[i][j]=(f[i][j]+f[i-1][t])%mod;
                }
            }
        }
        for(int i=len;i;--i){
            for(int j=0;j<s[i]-'0';++j){
                ans=(ans+f[i][j])%mod;
            }
            if(s[i]=='2'){
                ans=(ans+get(i-1,0))%mod;
            }
        }
        printf("%lld\n",ans);
    }
    
    return 0;
}

19. MT2219 新十六进制

（1）题目描述
小码哥基于之前的十六进制定义了一种新的进制，其仍然由十六个基数构成（即0，1，2，…，9，A，B，C，D，E，F)，并且大小关系保持不变（即O<1<2<…<9<A<B<C<D<E<F)，唯一不同的是数字只能按照大小关系升序排列(即11，21这样的数是不合法的，1F的下一个数是23),但前导0会被忽略（即00012等于12，也同样合法)。

现在小码哥想为这种进制制作转换器，能够把这种进制下的数转换成十进制数，但小码哥不懂怎么下手，于是他来找聪慧过人的你了。

小码哥希望对于输入的数字能进行判断，如果这个数字不合法，转换器会报错，如果合法，转换器会输出对应的十进制数。

格式

输入格式: 一个字符串，为标准十六进制数
.
输出格式: 一个整数，表示转换成的十进制数，如果输入的十六进制数不合法，输出error

样例1

输入: 12
.
输出: 16

备注：

字符串长度小于等于20，可能出现负数，输出文件不存在-0

（2）参考代码

#include<bits/stdc++.h>
using namespace std;
char d[] = "0123456789ABCDEF";
struct node{
    string s;
    bool operator<(const node b) const{
        if(s.size()!=b.s.size()) return s.size()<b.s.size();
        return s<b.s;
    }
};

set<node> st;
string a;
void dfs(int last){
    if(a.size()>=1) st.insert({a});
    for(int i=last+1;i<=15;i++){
        a.push_back(d[i]);
        dfs(i);
        a.pop_back();
    }
}

int main(){
    string s;
    cin>>s;
    int f=1;
    if(s[0]=='-') f=-1,s.erase(s.begin());
    while(*s.begin()=='0'&&s.size()>1) s.erase(s.begin());
    dfs(0);
    map<string,int>mp;
    int p=1;
    mp["0"]=0;
    for(auto u:st){
        mp[u.s]=p++;
    }
    if(mp.find(s)==mp.end()) cout<<"error"<<endl;
    else cout<<mp[s]*f<<endl;
    return 0;
}

20. MT2220 人脑计算机

（1）题目描述
小码哥的计算机昨天坏掉了，现在，他想请你帮他算一些东西。

他会给你t-1个十进制数，想请你把他们统统转化成二进制数。

格式

输入格式: 一个非负整数t，表示t ―1组数据。下面t -1行每行一个数n(十进制)。
.
输出格式: 对应每个n给出答案。

样例1

输入:
3
10
100
.
输出:
1010
1100100

备注：

其中: 1≤n ≤10的6次,2 ≤t ≤ 1000

（2）参考代码

#include<bits/stdc++.h> 
using namespace std;
int bin[31];
int main( )
{
    int t, n;
    scanf("%d", &t);
    t--;
    while(t--){
        scanf("%d", &n);
        int i = 0;
        while(n){
            bin[i++] = n%2;
            n /= 2;
        }
        for(int j = i-1; j>=0; --j){
            printf("%d", bin[j]);
        }
        printf("\n");
    }
    return 0;
}

21. MT2221 8421码

（1）题目描述
8421码是最常用的BCD码(Binary-Coded Decimal)，是十进制代码中最常用的一种。在这种编码方式中，每一位二值代码的“1”都代表一个固定数值。将每位“1”所代表的二进制数加起来就可以得到它所代表的十进制数字。因为代码中从左至右看每一位“1”分别代表数字“8”"4”“2”“1”，故得名8421码。其中每一位“1”代表的十进制数称为这一位的权。因为每位的权都是固定不变的，所以8421码是恒权码。

——摘自百度百科

8421码就是将十进制的数以8421的形式展开成二进制，大家知道十进制是0～9十个数组成，这十个数每个数都有自己的8421码: 0= 0000,1 = 0001,2=0010,3=0011,4=0100,5=0101,6=0110,7=0111,8=1000,9= 1001。接下来的10就有两个上述的码来表示10表示为0001 0000 (1与0）也就是BCD码是遇见1001就产生进位，不象普通的二进制码，到1111才产生进位10000。8421码的每4位代表十进制的每一位上的数，举个例子:321的8421码就是001100100001(分别对应十进制321)。

本题请你将输入的十进制数字转换为8421码形式。

格式

输入格式:
第一行输入一个整数n，表示数据组数。
接下来n行，每行输入一个整数。
.
输出格式: 对于第2~n+1行输入的每一个整数，分别输出其8421码形式。

样例1

输入:
6
0
9
10
321
5678
123456
.
输出:
0000
1001
00010000
001100100001
0101011001111000
000100100011010001010110

备注：

保证:对于100%的数据: 1≤n≤200,000，输入的整数在unsigned int类型范围内。

（2）参考代码

#include<bits/stdc++.h>
 using namespace std;
 int main( )
 {
 string s[11]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001"};
 int n;
 cin>>n;
 for(int i=0;i<n;i++){
 int num;
 cin>>num;
 string result="";
 if(num==0){
 cout<<"0000"<<endl;
 continue;
 }
 while(num!=0){
 result=s[num%10]+result;
 num/=10;
 }
 	cout<<result<<endl;
 }
 return 0;
 }

22. MT2222 余3码

（1）题目描述
8421码是一种BCD码(Binary-Coded Decimal)，将十进制的数以8421的形式展开成二进制，大家知道十进制是0～9十个数组成，这十个数每个数都有自己的8421码: 0=0000,1 =0001,2=0010,3=0011,4=0100,5=0101,6=0110,7=0111,8=1000,9=1001。接下来的10就由两个上述的码来表示，10表示为00010000 (1与0)也就是BCD码是遇见1001就产生进位，不象普通的二进制码，到1111才产生进位10000。8421码的每4位代表十进制的每一位上的数，举个例子: 321的8421码就是0011 0010 0001(分别对应十进制32 1) 。

而余三码(余3码）是由8421BCD码加上0011形成的一种无权码，由于它的每个字符编码比相应的8421码多3，故称为余三码。BCD码的一种。余3码的特点:当两个十进制数的和是9时，相应的和的余3码正好是1111，于是可自动产生进位信号,而不需修正。0和9,1和8.….和4的余3码互为反码,这在求对于模9的补码很方便。

本题请你将输入的十进制数字转换为余3码形式。

格式

输入格式: 第一行输入一个整数n，表示数据组数。接下来n行，每行输入一个整数。
.
输出格式: 对于第2~n+1行输入的每一个整数，分别输出其余3码形式。

样例1

输入:
6
0
9
10
321
5678
123456
.
输出:
0011
1100
01000011
011001010100
1000100110101011
010001010110011110001001

备注：

保证:对于100%的数据:1≤n ≤500,000，输入的整数在unsigned int类型范围内。

（2）参考代码

#include<bits/stdc++.h>
using namespace std;
 string trans[10]={"0011","0100","0101",
 "0110","0111","1000",
 "1001","1010","1011","1100"};
 void read_num(){
 char ch=getchar();
 while(ch<'0'||ch>'9')ch=getchar();
 while(ch>='0'&&ch<='9'){
 int index=ch-'0';
 cout<<trans[index];
 ch=getchar();
 }
 }
 int main(){
 int n;
 cin>>n;
 while(n--){
 read_num();
 puts("");
 }
 return 0;
 }

23. MT2223 二进制？ 不同！

（1）题目描述
小码哥是一个对数很敏感的人，即使给他很多个很像的数串，他都能找出没有出现过的数串。

或许是有些无聊，小码哥给你一个字符串数组nums，里面包含n个二进制字符串(长度都为n)，现请你找出不在数组中的二进制字符串。

若有多解，返回对应十进制最小的一个。

格式

输入格式: 一行二进制字符串数组，字符串之间以空格分割
.
输出格式: 一个不在数组中的二进制字符串

样例1

输入: 01 10
.
输出: 00

备注：

其中:1≤n ≤16 ,nums中的所有字符串互不相同。

（2）参考代码

def main():
    #code here
    nums=input().split()
    l=len(nums)
    for i in range(2**l-1):
        num=('{:0'+str(l)+'b}').format(i)
        if num not in nums:
            print(num)
            break
    pass
if __name__ == '__main__':
    main();

24. MT2224 二进制的排列

（1）题目描述
给一个二进制字符串s 和整数k，如果字符串s长度为k的子串覆盖所有长度为k的二进制字符串，则返回true，否则返回f alse 。

格式

输入格式:
第一行二进制串s
第二行一个正整数k
.
输出格式: 返回true或false

样例1

输入:
00110110
2
.
输出: true

备注：

其中:1<s.length ≤5*10的5次,1<k≤20

（2）参考代码

import java.util.Scanner;
class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        // code here
        String s = input.nextLine();
        int k = input.nextInt();
        int total = 1;
        for (int i = 0; i < k; i++) {
            total *= 2;
        }
        int[] check = new int[total];
        String ans = "true";
        for (int i = s.length(); i >= k; i--) {
            String temp = s.substring(i - k, i);
            int num = 0;
            for (int j = 0; j < temp.length(); j++) {
                num += (temp.charAt(j) - '0') * Math.pow(2, j);
            }
            check[num] = 1;
        }
        for (int i = 0; i < check.length; i++) {
            if (check[i] == 0) {
                ans = "false";
                break;
            }
        }
        System.out.println(ans);
        input.close();
    }
}

25. MT2225 36进制1

（1）题目描述
36进制，是数据的一种表示方法。同我们日常生活中的表示法不一样。它由0-9，A-Z组成，字母不区分大小写。与10进制的对应关系是:O-9对应O-9;A-Z对应10-35。

本题中，请你创建一个36进制类，我们要求将输入的十进制转换为36进制，统一使用大写字母。

格式

输入格式:
第一行输入一个整数n，表示数据组数。
接下来n行，每行输入一个十进制整数。
.
输出格式: 对于第2~n+1行输入的每一个十进制整数，分别输出其36进制形式。

样例1

输入:
8
0
9
10
35
-36
321
5678
123456
.
输出:
0
9
A
Z
-10
8X
4DQ
2N9C

备注：

保证:对于100%的数据: 1≤n ≤500,000，输入的整数在int类型范围内。

（2）参考代码

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
char get_ch(int x) {
    if (x >= 0 && x <= 9) return '0' + x;
    else return 'A' + (x-10);
}
char s[100];
int main(){
#ifdef TEST
    freopen("/Users/grh/Programming/CLionProjects/AlgoCoding/input.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    long long val;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &val);
        if (!val) {
            printf("0\n"); continue;
        }
        bool neg = false;
        if (val < 0) {
            neg = true; val = -val;
        }
        int pos = 0;
        while (val) {
            s[pos++] = get_ch(val % 36);
            val /= 36;
        }
        pos--;
        if (neg) printf("-");
        while (pos >= 0) {
            printf("%c", s[pos]);
            pos--;
        }
        printf("\n");
    }
    
    return 0;
}

结语

感谢大家一直以来的不断支持与鼓励，码题集题库中的进阶塔350题正在逐步更新，之后会逐步跟进星耀，王者的题，尽请期待！！！
同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

愿你的结局，配得上你一路的颠沛流离。文章来源地址https://www.toymoban.com/news/detail-481636.html

到了这里，关于算法竞赛入门【码蹄集进阶塔335题】(MT2201-2225）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！