【蓝桥每日一题]-字符串（保姆级教程 篇1）#atcoder324C~E题

今天来讲字符串题型

目录

题目：atcoder324C题

思路：

题目：atcoder324D题

思路：

题目：atcoder324E题

思路：

---

      

             

题目：atcoder324C题

给一个T字符串，然后给出n个S串，对于每个一个S串若可以经过一次字符修改，删除，添加可以变成T串，则输出该串的序号。

       

思路：

（c题一般不是很难，只要有点基础基本可以敲出来）

修改：两个串长度相等，且只有一个字符是不同的（这个最好处理）

     
删除：T只比S小1，且T串一定是S的子串

     
添加：S只比T小1，且S串一定是T的子串（这两种都是只需要判断是不是子串即可）
 

 相信你也注意到了，对于比给定串恰好大1的情况，完全可以使用子串匹配来做

       

#include <bits/stdc++.h>
using namespace std;
const int MAX_N=500000;
int ans[MAX_N],ans_num;
int check1(string s1,string s2){//判断s1和s2是不是只有1个或0个不同int res=0,sz=s1.size();for(int i=0;i<sz;i++){if(s1[i]!=s2[i])res++;}if(res<=1)return 1;else return 0;
}
int check2(string s1,string s2){//判断s1是否是s2的子串，因为s2只比s1大1，所以非常简单int sz=s1.size(),r=sz,l=0;for(int i=0;i<sz;i++){if(s1[i]!=s2[l])break;l++;}for(int i=sz-1;i>=0;i--){if(s1[i]!=s2[r])break;r--;}return l>=r;
}
int main(){int n; string t;cin>>n>>t;int sz=t.size();for(int i=1;i<=n;i++){string s; cin>>s;int sz1=s.size();if(sz1==sz){if(check1(t,s))  ans[++ans_num]=i;}else if(sz+1==sz1){if(check2(t,s))  ans[++ans_num]=i;}else if(sz==sz1+1){if(check2(s,t))  ans[++ans_num]=i;}}cout<<ans_num<<'\n';//满足题意的个数for(int i=1;i<=ans_num;i++){cout<<ans[i];//输出序号if(i+1<=ans_num)	cout<<' ';else	cout<<'\n';}}

      

      

题目：atcoder324D题

给一个长n的字符串，问进行排列后最多能拼成几个完全平方数 （n<13）

       

思路：

最不应该的做法就是将字符串进行全排列然后逐个检查，因为阶乘太大了一定会超时。

    

应该先把小于最大n的平方数全部打表出来，然后检查每个平方数是不是这个字符串的重排列：                                                       

这里要用到to_string函数可以快速将数型转化成字符型，然后检查重排列即可。

如何检查一个字符串是不是另一个的重排列呢？

     
方法：将两个字符串都排序一下，然后检查排序后的一样不一样即可。

      
注意一点：字符串100应该等于1和100，但是只有数字100的字符串（001）和字符串100的（001）完全相同，数字1的字符串需要自动添加前缀（00）才能！
 

          

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500000;
int main(){int n;string s;//输入长度和字符串cin>>n>>s;sort(s.begin(),s.end());//默认升序if(s.back()=='0'){cout<<"1\n";return 0;}int ans=0;for(ll x=1;;x++){//逐个比较每个字符串ll tmp=x*x;//防止隐式转化越界，故x为ll型string t=to_string(tmp);//to_string()  stoi ll d()int st=t.size();if(st>n)  break;else {sort(t.begin(),t.end());t=string(n-st,'0')+t;//t长度不够，自动加一定数量的‘0’if(s==t)  ans++;}}cout<<ans<<'\n';
}

       

最后：补充一下string的排序，两种降序办法

bool cmp(char a,char b){return a>b;
}
int main(){string s;cin>>s;sort(s.begin(),s.end());//方法1sort(s.begin(),s.end());//方法2reverse(s.begin(),s.end());//方法2cout<<s;
}

        

         

题目：atcoder324E题

给一个t字符串和n个字符串，我们将n个字符串进行n^2次相互拼接，问最终t会是几个拼接成的字符串的子序列（N<=5e5）

      

思路：

补充：子序列 && 子串：子序列不是字符串可以跳跃下标，子串是字符串不能跳跃下标 

     
t是拼接成的字符串的子序列，就相当于  前部分字符串的子序列字符个数  加  后部分字符串子序列字符个数  大于等于t即可

       
统计子序列方法：串的子序列字符个数就是当前的下标数，贪心统计即可 。

     
然后就转变成了从两个数组中分别找一个数相加大于指定数值的问题：两种O(N)方法，一种是后缀和统计法，另一种就是lower_bound,upper_bound
     

           

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//后缀和统计法：将元素的数值直接填入标记数组中，然后使用后缀和计算个数
const int N=500050;//测试点有个500000整的，很恶心
int ar[N];
ll sum[N],ans;
int main(){int n;string t;cin>>n>>t;int st=t.size();string s[n];for(int i=0;i<n;i++)cin>>s[i];for(int i=0;i<n;i++){//遍历每个字符串int ptr=0;for(int j=0,sz=s[i].size();j<sz;j++){if(ptr<st&&t[ptr]==s[i][j])ptr++;//统计每个对应的子序列字符的个数，个数也是下标数}ar[ptr]++;//将数值填入标记数组}for(int i=st;i>=0;i--)sum[i]=sum[i+1]+ar[i];//后缀和数组reverse(t.begin(),t.end());//颠倒一下，把统计后缀子序列问题转化成统计前缀子序列问题for(int i=0;i<n;i++){int ptr=0;reverse(s[i].begin(),s[i].end());for(int j=0,sz=s[i].size();j<sz;j++){//一模一样的代码if(ptr<st&&t[ptr]==s[i][j])ptr++;}ans+=sum[st-ptr];//st是最大值}cout<<ans<<'\n';
}//做法二  lower_bound：将数组数值排序，然后二分查找满足条件的临界数的下标，向后计算个数即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500050;
int ar[N],br[N];
ll ans;
int main(){int n,len1=0,len2=0;string t;cin>>n>>t;int st=t.size();string s[n];for(int i=0;i<n;i++)cin>>s[i];for(int i=0;i<n;i++){int ptr=0;for(int j=0,sz=s[i].size();j<sz;j++){if(ptr<st&&t[ptr]==s[i][j])ptr++;}ar[len1++]=ptr;//直接保存数据}sort(ar,ar+len1);//默认升序reverse(t.begin(),t.end());for(int i=0;i<n;i++){int ptr=0;reverse(s[i].begin(),s[i].end());for(int j=0,sz=s[i].size();j<sz;j++){if(ptr<st&&t[ptr]==s[i][j])ptr++;}int pos=lower_bound(ar,ar+len1,st-ptr)-ar;//找到下标ans+=len1-pos;//后面的都是满足的}cout<<ans<<'\n';
}