目录
字符串模拟
1. 东东哥的等式（简单模拟）
例题1：东东哥的等式
东东哥又在玩字符串啦，他有一个长度为n的十进制串(n<=36),他想在这个串里插入一个’+‘和一个’=’(’+‘必须在’='前面)，使其变为x+y=z的形式，x,y,z为十进制数并且不允许包含前导0.请输出这个式子，如果有多个请输出x最小的那个。保证至少存在一个答案而且仅存在一个满足x最小的答案。东东哥实在想不出来怎么做这题，你能帮帮他吗？
思路：简单的字符串模拟，注意用char数组，用string会数组越界。分别截取转换成数字，符合要求即输出，要特判保证没有前导零
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
char s[105];
typedef unsigned long long ll;
ll stoi(char *ss,ll l,ll r)//自己写一个字符串转整数。想知道为什么cstring里包含的stoi()用不了
{
ll res=0;
if(l>r)return 0;
for (ll i=l;i<=r;i++)
{
res*=10;
res+=ss[i]-'0';
}
return res;
}
bool valid(char *c,ll l,ll r)
{
if(l!=r&&c[l]=='0')return false;
return true;
}
int main()
{
cin>>t;
while(t--)
{
scanf("%s",s);
int len=strlen(s);
for(int i=0;i<=len/2+1;i++)
{
for(int j=i+1;j<=len-1;j++)
{
if(!valid(s,0,i)||!valid(s,i+1,j)||!valid(s,j+1,len-1))continue;
ll le=stoi(s,0,i);
ll mid=stoi(s,i+1,j);
ll ri=stoi(s,j+1,len-1);
if(le+mid==ri)//if(le+mid==ri&&(s[i+1]!='0'||i+1==j)&&(s[j+1]!='0'||j+1==strlen(s)-1))
{
cout<<le<<"+"<<mid<<"="<<ri<<endl;
goto flag;
}
}
}
flag:;
}
return 0;
}
2.有几个zucc（字符数，简单排列组合）
例题2:有几个zucc
字符串 AAZBCZCUCIOCQWC 共包含6个 ZUCC。
例如，第3位(Z)，第8位(U)，第9位©，第12位©可以形成一个ZUCC;
第6位(Z)，第8位(U)，第12位©，第15位©也可以形成一个 ZUCC。
下面给定一个长度不超过 100000且仅包含大写 A-Z 字母的字符串。一共可以形成多少个 ZUCC？
输入格式:
输入只有一行，包含一个长度不超过 100000。
输出格式:
输出该字符串中包含的 ZUCC 个数。
输入样例:
AAZBCZCUCIOCQWC
输出样例:
6
思路:从后往查，n个C，两个一组，n*(n-1)/2种。只要有U,每多一个Z，多一倍。
#include<stdio.h>
#include<string.h>
char s[100001];
int main()
{
int c=0;
int len=0;
long long usum=0;
long long sum=0;
scanf("%s",s);
len=strlen(s);
for(int i=len-1;i>=0;i--){
if(s[i]=='C') c++;
else if(s[i]=='U') usum+=c*(c-1)/2;
else if(s[i]=='Z') sum+=usum;
}
printf("%lld\n",sum);
return 0;
}
3.拼数（简单字符串，小技巧）
3.拼数
设有n个正整数(n≤20)，将它们联接成一排，组成一个最大的多位整数。
思路：利用c++中字符串string的性质排序即可
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n;
string s[maxn];
bool cmp(string a,string b)
{
return a+b>b+a; //直接按字典序排序先拼接到一块看那个大
}
int main()
{
cin>>n;//利用字符串可以更加简便
for(int i=0;i<n;i++)
cin>>s[i];
sort(s,s+n,cmp);
for(int i=0;i<n;i++)
cout<<s[i];
cout<<endl;
return 0;
}
4.CF1295B 【Infinite Prefixes】（字符串，前缀和，数论）
题目表达的很难看懂，简单来说就是给一个长度已知可以无限重复的字符串，只有0和1两种字符，问有几个点可以使0比1多x个，比如样例1, 010010 1个子串0比1多2个，所以前四个子串结束后0一共比1多了8个，而0比1多10个将在下一个子串中出现，也就是第28 30 和32位的时候。
用一个前缀和pre[N]数组来表示当前0和1的个数差值，然后特判即可。具体的直接看代码。
#include<bits/stdc++.h>
#define debug cout<<"ok"<<endl
using namespace std;
typedef long long ll;
const int N=1e5+7;
const int mod=1e9+7;
ll n,x,t,pre[N];
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n>>x>>s;
ll ans=0;bool flag=0;pre[0]=0;
for(int i=0;i<s.length();i++)
{
if(s[i]=='0')pre[i+1]=pre[i]+1;//前缀和数组，pre[i]表示0的个数与1的个数的差值
else pre[i+1]=pre[i]-1;
}
ll date=pre[s.length()];
for(int i=0;i<=s.length();i++)//要<=因为看走完如果是否满足题意
{
if(pre[i]==x)ans++;
if(pre[i]==x&&date==0)flag=1;
if(i!=0&&pre[i]<x&&date>0&&(x-pre[i])%date==0)ans++;/*走到这儿是1多，但是走完一遍是0多，那么如果x-pre[i]%date==0那么往后延伸一定能出现0比1多x的情况，所以ans++;*/
if(i!=0&&pre[i]>x&&date<0&&(pre[i]-x)%(-date)==0)ans++;
}
if(!flag)
cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}
5.CF1295C - Obtain The String（模拟取字符串子序列）
题目大意：
给定两个字符串s和t，你有一个空字符串z
每次可以取s的任意一个子序列加到z后面
问至少要取多少次才能让z等价于t
题解
6.nozomi和字符串 (字符串，滑动窗口，贪心)
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int a[N];
string s;
int n,m;
int main()
{
cin>>n>>m;
cin>>s;
queue<int>q1;
queue<int>q2;
q1.push(-1);
q2.push(-1);
int maxxx=0,maxn=0,ans=0;
for(int i=0;i<n;i++)
{
if(s[i]=='0')
q1.push(i);
if(q1.size()>m+1)
q1.pop();
int temp=i-q1.front();
if(temp>maxn)
maxn=temp;
if(s[i]=='1')
q2.push(i);
if(q2.size()>m+1)
q2.pop();
int t=i-q2.front();
if(t>maxxx)
maxxx=t;
ans=max(maxxx,maxn);
}
cout<<ans<<endl;
}
7.潜伏者（字符串，密码解密）
加密问题
潜伏者
题目描述
RR R国和S S S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于S S S国的R RR 国间谍小C C C终于摸清了 SSS 国军用密码的编码规则：1． SS S国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母‘AAA’-‘ZZZ’构成（无空格等其他字符）。2． SS S国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换为其对应的“密字”。3． 每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以和原字母相同。例如，若规定‘AAA’的密字为‘AAA’，‘BBB’的密字为‘CCC’（其他字母及密字略），则原信息“ABAABAABA”被加密为“ACAACAACA”。现在，小C CC 通过内线掌握了S SS 国网络上发送的一条加密信息及其对应的原信息。小C CC希望能通过这条信息，破译S SS 国的军用密码。小 CCC 的破译过程是这样的：扫描原信息，对于原信息中的字母x xx（代表任一大写字母），找到其在加密信息中的对应大写字母y yy，并认为在密码里 yy y是x x x的密字。如此进行下去直到停止于如下的某个状态：1． 所有信息扫描完毕，‘AAA’-‘ZZZ’ 所有 2626 26个字母在原信息中均出现过并获得了相应的“密字”。2． 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。3． 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反 SSS 国密码的编码规则）。例如某条信息“XYZXYZXYZ”被翻译为“ABAABAABA”就违反了“不同字母对应不同密字”的规则。在小 CCC 忙得头昏脑涨之际，RRR 国司令部又发来电报，要求他翻译另外一条从 SS S国刚刚截取到的加密信息。现在请你帮助小C CC：通过内线掌握的信息，尝试破译密码。然后利用破译的密码，翻译电报中的加密信息。
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
string s1,s2,s3,s="";
int n,m,cnt,vis[maxn],a[maxn],vis2[maxn];
int main()
{
cin>>s1>>s2>>s3;
memset(vis,-1,sizeof(vis));
memset(vis2,-1,sizeof(vis2));
int len=s1.length();
for(int i=0;i<len;i++)
{
if(vis[s1[i]-'A']==-1&&vis2[s2[i]-'A']==-1)//都没被连过才使它们连接到一块
{vis[s1[i]-'A']=s2[i]-'A';vis2[s2[i]-'A']=0;}
else {
if(vis[s1[i]-'A']!=s2[i]-'A')//要注意这一句要放到里面特判，因为放到外面没办法保证同时满足条件
{cout<<"Failed"<<endl;return 0;}//发现被连过了且想跟它连的是非法的就输出
}
}
for(int i=0;i<26;i++)
if(vis[i]==-1){cout<<"Failed"<<endl;return 0;}
for(int i=0;i<s3.length();i++)
s+=vis[s3[i]-'A']+'A';
cout<<s<<endl;
return 0;
}
/*调之前挂掉的点：QWERTYUIOPLKJHGFDSAZXCVBNM QWERTYUIOPLKJHGFDSAZXCVBNN HIJACK Failed*/
8. CF16A Flag（字符串,getchar()的秒用）
CF16A Flag
题目描述
根据一项新的ISO标准，每一个国家的国旗应该是一个n×m的格子场，其中每个格子最多有10种不同的颜色。并且国旗应该有条纹：旗帜的每一行应包含相同颜色的方块，相邻的行的颜色应该是不同的。Berland政府要求你找出他们的国旗是否符合新的ISO标准。
输入格式：
输入的第一行包含数n和m（ ( 1<=n,m<=100 ），其中n为行数，m为列数。接下来
是对旗的描述：以下N行中的每一行包含m个字符。每个字符是0到9之间的数字，代表相应正方形的颜色。
输出格式：
如果国旗符合标准就输出YES，否则输出NO。
注意getchar的使用
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3;
int n,m;
char ch,now,last=' ';
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();//只使用getchar()的话一定要用这句话来接收换行空格等字符；
for(int j=1;j<m;j++)
{
now=getchar();
if(now!=ch){cout<<"NO"<<endl;return 0;}
}
if(last==now){cout<<"NO"<<endl;return 0;}
last=ch;
}
cout<<"YES"<<endl;
return 0;
}
9.nozomi和字符串(字符串,滑动窗口,01子串,0变1/1变0)
nozomi看到eli在字符串的“花园”里迷路了，决定也去研究字符串问题。 她想到了这样一个问题： 对于一个 “01”串而言，每次操作可以把 0 字符改为 1 字符，或者把 1字符改为 0 字符。所谓“01”串，即只含字符 0和字符 1 的字符串。 nozomi有最多k次操作的机会。她想在操作之后找出一个尽可能长的连续子串，这个子串上的所有字符都相同。 nozomi想问问聪明的你，这个子串的长度最大值是多少？ 注： k次操作机会可以不全部用完。 如果想知道连续子串的说明，可以去问问eli，nozomi不想再讲一遍。
输入描述:
第一行输入两个正整数 n 和 k 
输出描述:
一个正整数，为满足条件的子串长度最大值。
输入：
5 1
10101
输出：
3
送一个输入：
5 1
00100
输出：
5
思路：贪心的想，显然操作要么全1变0，要么全0变1。用队列维护l左界，用i代表r右界，就一滑动窗口，跟单调队列有点像的解法
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int a[N];
string s;
int n,m;
int main()
{
cin>>n>>m;
cin>>s;
queue<int>q1;
queue<int>q2;
q1.push(-1);//要push的是-1而不是0！！因为下面是i-q1.front()而i是从0开始的
q2.push(-1);
int maxxx=0,maxn=0,ans=0;
for(int i=0;i<n;i++)
{
if(s[i]=='0')
q1.push(i);
if(q1.size()>m+1)
q1.pop();
int temp=i-q1.front();
if(temp>maxn)
maxn=temp;
if(s[i]=='1')
q2.push(i);
if(q2.size()>m+1)
q2.pop();
int t=i-q2.front();
if(t>maxxx)
maxxx=t;
ans=max(maxxx,maxn);
}
cout<<ans<<endl;
}
10.丢人！问最少需要几步实现又没非得让你写代码实现！！！
草（一种植物）
题目看起来是编辑距离的模板题，其实就是一个很简单的题目，贪心地考虑问题。先考虑两个字符串相同的部分，显然，只要把原字符串和新字符串不同的字符修改就行了；对于两个字符串后面不同的部分，如果原字符串比较长，就全部删掉；如果原字符串比较短，就对照第二个字符串添加字符。所以，只要按照两个字符串较大的长度进行遍历，比较两个字符串不同的字符有几个就可以了。如果一个字符串比较短，那么它后面的部分可以看成\0，同样可以参与字符串比较。
这里不能用string因为C++的string类是动态开内存的，当s1，s2长度不一样s[i]就会越界错误
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+7;
char s1[N],s2[N];
int main()
{
ll n,sum=0,m;
cin>>n>>m;
scanf("%s%s",s1,s2);
ll len=max(n,m);
for(int i=0;i<len;i++)
{
if(s1[i]!=s2[i])
sum++;
}
cout<<sum<<endl;
return 0;
}
京公网安备 11010502036488号