江门网站推广软件,成都市建网站公司,成都网站建设服务有什么,cms 官方网站今天来讲字符串题型
目录
题目#xff1a;atcoder324C题
思路#xff1a;
题目#xff1a;atcoder324D题
思路#xff1a;
题目#xff1a;atcoder324E题
思路#xff1a; 题目#xff1a;atcoder324C题
给一个T字符串#xff0c;然后给出n个S串#xff0c;对…今天来讲字符串题型
目录
题目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_N500000;
int ans[MAX_N],ans_num;
int check1(string s1,string s2){//判断s1和s2是不是只有1个或0个不同int res0,szs1.size();for(int i0;isz;i){if(s1[i]!s2[i])res;}if(res1)return 1;else return 0;
}
int check2(string s1,string s2){//判断s1是否是s2的子串因为s2只比s1大1所以非常简单int szs1.size(),rsz,l0;for(int i0;isz;i){if(s1[i]!s2[l])break;l;}for(int isz-1;i0;i--){if(s1[i]!s2[r])break;r--;}return lr;
}
int main(){int n; string t;cinnt;int szt.size();for(int i1;in;i){string s; cins;int sz1s.size();if(sz1sz){if(check1(t,s)) ans[ans_num]i;}else if(sz1sz1){if(check2(t,s)) ans[ans_num]i;}else if(szsz11){if(check2(s,t)) ans[ans_num]i;}}coutans_num\n;//满足题意的个数for(int i1;ians_num;i){coutans[i];//输出序号if(i1ans_num) cout ;else cout\n;}} 题目atcoder324D题
给一个长n的字符串问进行排列后最多能拼成几个完全平方数 n13 思路 最不应该的做法就是将字符串进行全排列然后逐个检查因为阶乘太大了一定会超时。 应该先把小于最大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 N500000;
int main(){int n;string s;//输入长度和字符串cinns;sort(s.begin(),s.end());//默认升序if(s.back()0){cout1\n;return 0;}int ans0;for(ll x1;;x){//逐个比较每个字符串ll tmpx*x;//防止隐式转化越界故x为ll型string tto_string(tmp);//to_string() stoi ll d()int stt.size();if(stn) break;else {sort(t.begin(),t.end());tstring(n-st,0)t;//t长度不够自动加一定数量的‘0’if(st) ans;}}coutans\n;
} 最后补充一下string的排序两种降序办法 bool cmp(char a,char b){return ab;
}
int main(){string s;cins;sort(s.begin(),s.end());//方法1sort(s.begin(),s.end());//方法2reverse(s.begin(),s.end());//方法2couts;
} 题目atcoder324E题
给一个t字符串和n个字符串我们将n个字符串进行n^2次相互拼接问最终t会是几个拼接成的字符串的子序列N5e5 思路
补充子序列 子串子序列不是字符串可以跳跃下标子串是字符串不能跳跃下标 t是拼接成的字符串的子序列就相当于 前部分字符串的子序列字符个数 加 后部分字符串子序列字符个数 大于等于t即可 统计子序列方法串的子序列字符个数就是当前的下标数贪心统计即可 。 然后就转变成了从两个数组中分别找一个数相加大于指定数值的问题两种O(N)方法一种是后缀和统计法另一种就是lower_bound,upper_bound #include bits/stdc.h
using namespace std;
typedef long long ll;//后缀和统计法将元素的数值直接填入标记数组中然后使用后缀和计算个数
const int N500050;//测试点有个500000整的很恶心
int ar[N];
ll sum[N],ans;
int main(){int n;string t;cinnt;int stt.size();string s[n];for(int i0;in;i)cins[i];for(int i0;in;i){//遍历每个字符串int ptr0;for(int j0,szs[i].size();jsz;j){if(ptrstt[ptr]s[i][j])ptr;//统计每个对应的子序列字符的个数个数也是下标数}ar[ptr];//将数值填入标记数组}for(int ist;i0;i--)sum[i]sum[i1]ar[i];//后缀和数组reverse(t.begin(),t.end());//颠倒一下把统计后缀子序列问题转化成统计前缀子序列问题for(int i0;in;i){int ptr0;reverse(s[i].begin(),s[i].end());for(int j0,szs[i].size();jsz;j){//一模一样的代码if(ptrstt[ptr]s[i][j])ptr;}anssum[st-ptr];//st是最大值}coutans\n;
}//做法二 lower_bound将数组数值排序然后二分查找满足条件的临界数的下标向后计算个数即可
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N500050;
int ar[N],br[N];
ll ans;
int main(){int n,len10,len20;string t;cinnt;int stt.size();string s[n];for(int i0;in;i)cins[i];for(int i0;in;i){int ptr0;for(int j0,szs[i].size();jsz;j){if(ptrstt[ptr]s[i][j])ptr;}ar[len1]ptr;//直接保存数据}sort(ar,arlen1);//默认升序reverse(t.begin(),t.end());for(int i0;in;i){int ptr0;reverse(s[i].begin(),s[i].end());for(int j0,szs[i].size();jsz;j){if(ptrstt[ptr]s[i][j])ptr;}int poslower_bound(ar,arlen1,st-ptr)-ar;//找到下标anslen1-pos;//后面的都是满足的}coutans\n;
}
