免费装wordpress,惠州谷歌优化,wordpress如何通过后台增加主菜单,国外空间洛谷传送 牛客网题一 牛客网题二 没错牛客网有两个题#xff0c;牛客网题一和洛谷是一样的题#xff0c;牛客网题二是题一的变形 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO Format: %lld 链…洛谷传送 牛客网题一 牛客网题二 没错牛客网有两个题牛客网题一和洛谷是一样的题牛客网题二是题一的变形 时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld 链接https://ac.nowcoder.com/acm/contest/4860/G 来源牛客网 输入描述: Line 1: A single encrypted string of length at most 100. 输出描述: Line 1: The number of ways FJ could have produced this string with one or more successive operations applied to some initial string of length at least 2, written out modulo 2014. If there are no such ways, output zero. 题一
示例1 输入
ABABA输出
8题意 一个长度至少为2仅包含字符A~Z的字符串。为了加密他的消息FJ对这条消息进行了一系列“操作”。一次对字符串S的“操作”是指去掉S开头的若干个字母但不是全部或末尾的若干个字母但不是全部然后将原来的S拼接到开头或末尾。 给你操作后的字符串问你操作前有几种情况 我们看看样例 ABABA 输出是8哪8种呢如下 Start with ABA - ABABA Start with ABA - ABABA Start with AB - ABA - ABABA Start with AB - ABA - ABABA Start with BA - ABA - ABABA Start with BA - ABA - ABABA Start with ABAB - ABABA Start with BABA - ABABA 我们注意到什么样的可以作为操作前的候选串至少可以通过拆分构造出原串的头和尾 我们可以这么想
分三种情况 第一种看头和尾 样例 A B A B A 首先首尾的两个字符相等都是A那也就是开头的可以被省掉因为省掉后BABA可以通过去除BAB后剩下A再加上原串BABA构成原本的ABABA好好想想是不是那同理结尾的A也可省略了省略后就是ABAB。 省略后的BABA也进行这样的过程 看首尾分别是BA不相等那指针都向中间移动再看首BA尾BA是否相等发现相等那首可以省略吧那尾也可以省略吧 这就是两种情况了。一直进行下去直到字符串的长度为2或者不满足条件 第二种看开头 样例A B A B C id 0 1 2 3 4 比较第一个开头Aid0和第二个开头Bid1发现不一样范围同时扩大第一个开头就是A Bid0,1第二个开头就是A Bid2,3发现相同那么第一个开头就可以省略了就剩下ABC但注意第二个开头不能省略因为不能在中间断开然后对ABC再进行操作 第三种看结尾 样例C A B A B 其实第二种与第三种相同看结尾就是倒着来从开始BA然后ABAB所以最后这个尾ABid34就可以省略剩下CAB _ _下划线为省去的部分,然后再进行操作 我们进行的顺序是第一种到第二再到第三每次再进行操作时都要从第一种开始 在操作中我们需要截取字符串就可以用substrxy,从第idx位开始截取长度为y 但这题还有一个坑方案数用ans表示开始必须为1就是他本身表示不变换但是应该输出变化后的方案所以还要-1 对了每个出现的字符串都记录长度下次遇见时直接返回值
#includebits/stdc.h
const int mod2014;
using namespace std;
mapstring,inta;string find(string s,int x,int y)
{
// cout6 s.substr(x,y)endl;return s.substr(x,y);
}
int count(string s)
{// cout4 sendl;if(a[s])return a[s];// cout5 sendl;int ans1;int lens.size();for(int i1;i*2len;i){if(find(s,0,i)find(s,len-i,i)){ansanscount(find(s,i,len-i))count(find(s,0,len-i));// cout1 s.substr(i,len-i) s.substr(0,len-i)endl;// cout7 ansendl;}if(find(s,0,i)find(s,i,i)){ansanscount(find(s,i,len-i));// cout2 s.substr(i,len-i)endl;// cout7 ansendl;}if(find(s,len-i,i)find(s,len-i-i,i)){anscount(find(s,0,len-i)); // cout3 s.substr(0,len-i)endl;// cout7 ansendl;} }
// cout7 ansendl;a[s]ans%mod;return a[s];
}
int main()
{string c;cinc;int sum 0;sum (count(c))%mod;coutsum-1;return 0;}
//AAAAAAAAAAAAAAAAAAAA代码中注释部分为我一开始用来调试的因为一开始我将ans定义为全局变量而被疯狂卡o(╥﹏╥)o **
题二
** 链接https://ac.nowcoder.com/acm/contest/4860/J 来源牛客网
输入描述:
Line 1: A string of length at most 100.
输出描述:
Line 1: The number of different ways FJ could have produced this string by applying one or more successive operations to some source string of length at least 2. If there are no such ways, output zero. 示例1 输入
ABABA输出
6说明
Here are the different ways FJ could have produced ABABA:
Start with ABA - ABABAStart with ABA - ABABAStart with AB - ABA - ABABAStart with AB - ABA - ABABAStart with BA - ABA - ABABAStart with BA - ABA - ABABA 题解 我一开始以为两个一样直接提交代码痛wa两次 题二也就是题一变形不同处在于 一次对字符串S的“操作”是指去掉S开头的一个字母而非原本的若干或末尾的一个字母而非若干 看样例 ABABA 也就是ABAB和BABA这两种情况不存在因为只能删去一个的话删后字符串长为3再加上原本的47超过了目标长度5 我们设满足条件的字符串长度为x目标字符串长度为len那么删后为x-1加在一起就是2x-1要求2x-1n 解得x(n1)/2 在代码中我们每次所截代码长度为len-i详细看上个代码所以len-i(n1)/2时就不满足题意continue不理这种情况直接下一个。
#includebits/stdc.h
//const int mod2014;
using namespace std;
mapstring,long long inta;string find(string s,int x,int y)
{
// cout6 s.substr(x,y)endl;return s.substr(x,y);
}
long long int count(string s)
{// cout4 sendl;if(a[s])return a[s];// cout5 sendl;long long int ans1;long long int lens.size();for(int i1;i*2len;i){if((len-i)(len1)/2)continue;//不同之处if(find(s,0,i)find(s,len-i,i)){ansanscount(find(s,i,len-i))count(find(s,0,len-i));// cout1 s.substr(i,len-i) s.substr(0,len-i)endl;// cout7 ansendl;}if(find(s,0,i)find(s,i,i)){ansanscount(find(s,i,len-i));// cout2 s.substr(i,len-i)endl;// cout7 ansendl;}if(find(s,len-i,i)find(s,len-i-i,i)){anscount(find(s,0,len-i)); // cout3 s.substr(0,len-i)endl;// cout7 ansendl;} }
// cout7 ansendl;a[s]ans;return a[s];
}
int main()
{string c;cinc;long long int sum 0;sum count(c);coutsum-1;return 0;}
//AAAAAAAAAAAAAAAAAAAA
