作者：单均浩
学习内容（复赛）：（全部自己总结）
学习内容（初赛）：（全部自己总结）
必做题题目解析+关键代码
T1 字串计算
题目描述
给出一个只包含0和1的字符串（长度在1到100之间），求其每一个子串出现的次数。
输入格式
一行，一个01字符串。
输出格式
对所有出现次数在1次以上的子串，输出该子串及出现次数，中间用单个空格隔开。
按子串的字典序从小到大依次输出，每行一个。
题目解析
考虑map,定义一个map，用string映射int
开始枚举，用substr取每个字符串，O(n2)
用map遍历，大于一的输出，O(n)
关键代码
T2 小信反转串
题目描述：
小信有一个长为 n 的只含 0 和 1字符串 s。 他可以进行最多 k 次如下操作：
选择字符串 s 的一个子串，将其中的字符反转（0 变成 1，1 变成 0）。
求在操作过程中（操作数可为0）出现过的最长的连续的 1 的长度。
输入格式：
第一行，2 个正整数 n,k； 第二行，字符串 s。
输出格式：
输出不超过 k 次操作后，最长的连续的 1 的长度。
题目解析
关键代码
T3 卡牌
题目描述：
小信有很多组卡牌，每组卡牌的形式像这样，x,x+1,x+2,…,x+m−1，x是这组卡牌的第一张数值，m是这组卡牌的长度。
但有一天他不小心把所有卡牌搞混在了一起。比如他一开始有两组卡牌[2,3,4,5]和[3,4]，混在一起之后变成了[3,3,4,5,4,2]。
给定搞混后的卡牌，问你小信最初最少有多少组卡牌。
输入格式：
第一行包含一个整数 T，表示测试数据组数。
对于每组测试数据，第一行一个整数 n，代表所有卡牌混在一起后的总长度。
第二行n个整数，a1,a2,…,an，代表混合后的卡牌序列。
输出格式：
对于每组测试数据，输出一个整数表示最初最少有多少组卡牌。
题目解析
multiset+暴力枚举走天下 O(n)
注意T组数据
while (!s.empty()){
int x=*s.begin();
s.erase(s.find(x));
x++;
while (s.count(x)!=0){
s.erase(s.find(x));
x++;
}
ans++;
}
T4 简单的求和
题目描述：
给定一个长度为 n 的数组a 和 k，小信想知道数组中有多少对数相加等于 k 。
输入格式：
第一行包含两个整数 n,k。
第二行 n 个整数 ai。
输出格式：
输出一个整数表示有多少对。
题目解析
Sort排序一遍 O(nlongn)
尺取法一遍（上课例题参考）O(n)
while (l<r){
if (a[l]+a[r]==k){
if (a[l]==a[r]){
long long t=r-l+1;
sum=sum+t*(t-1)/2;
break;
}
else{
long long tl=1,tr=1;
while (a[l]==a[l+1]){
tl++;
l++;
}
l++;
while (a[r]==a[r-1]){
tr++;
r--;
}
r--;
sum=sum+tl*tr;
}
}
else if (a[l]+a[r]>k){
--r;
}
else{
++l;
}
}
T5 数位和问题
题目描述：
数位之和的意思是某个整数每一位之和。比如123的数位之和就是6。
小信现在给你一个长度为 n 的数组 a ，然后操作 q 次，有两种操作：
1 l r 代表将下标范围在 [l,r] 内所有的 ai ， 修改为 ai 的数位之和
2 x 代表输出ax 。
输入格式：
第一行两个整数 n, q，
第二行包括 n 个 整数，a1,a2,…,an。
接下来q 行，每行代表一次操作。
输出格式：
对于每次操作2，输出一个整数表示答案。
题目解析
如果你直接暴力，就会……
void f(int x){
int cnt=0,m=a[x];
while(m!=0){
cnt+=m%10;
m/=10;
}
a[x]=cnt;
}
接着，我们就会用到上课学过的神奇的STL之——set！！！
因为这道题数位和操作只需进行几次就可，用set记录需要数位和操作的数的下标，再通过一些奇奇怪怪的操作干一些奇奇怪怪的事情（lower_bound,upper_bound,auto……）
总而言之，就是用set优化
int c[1000001],p=0;
auto st=s.lower_bound(l);
auto en=s.upper_bound(r);
for(auto it=st;it!=en;++it){
f(*it);
if (a[*it]<10){
c[++p]=*it;
}
}
for(int i=1;i<=p;++i){
s.erase(c[i]);
}
T6 排队
题目描述：
幼儿园里的小朋友在玩排队游戏，他们会根据老师的要求排队。
老师共进行 n 次操作，操作分为以下三种：
1 x : 将一名身高为 x 的小朋友加入队尾
2 : 输出队列最前面的小朋友的身高，并让他出队列，保证进行该操作时队列非空
3 : 将队列里的小朋友按照身高升序排序
输入格式：
第一行，包含一个正整数 n，表示操作次数。
加下来n行按照以下格式之一输入操作：
1 x
2
3
输出格式：
对应操作进行输出。
题目解析
关键代码
if (op==1){
int x;
scanf("%d",&x);
q.push(x);
}
if (op==2){
if (!q2.empty()){
printf("%d\n",q2.top());
q2.pop();
}
else{
printf("%d\n",q.front());
q.pop();
}
}
if (op==3){
while(!q.empty()){
q2.push(q.front());
q.pop();
}
}