L - Let‘s Swap(哈希 + 规律)
创始人
2024-05-29 16:19:52
0次

2023河南省赛组队训练赛（四） - Virtual Judge (vjudge.net)

约瑟夫最近开发了一款名为Pandote的编辑软件，现在他正在测试，以确保它能正常工作，否则，他可能会被解雇!Joseph通过实现对Pandote上字符串的复制和粘贴以及反向操作开始了他的测试。更具体地说，在每一步中，如果屏幕上的字符串是S，他将按顺序进行以下操作。1. 选择长度为l(1≤l≤IS)的前缀，则S可表示为AB (IA] = 1)，注意字符串B可以为空。2. 交换这两个部分，得到字符串BA。3.反转整个字符串，得到字符串(BA)"但是，由于Pandote的功能有限，他在每一步中只能选择长度不同的前缀l1和l2。现在Joseph想知道他是否可以通过几个(可能是零)步骤将字符串S转换为T。输入输入的第一行给出了测试用例的数量T (1

Sample 1

InputcopyOutputcopy
3
ljhelloh
hellohlj
2 4
thisisastr
htrtsasisi
3 5
abcde
bcdea
1 4

yes
no
yes

 题解:
我们通过枚举样例可以发现如果连续两个l1或l2操作,原字符串是不变的

(假设l1 > l2)

并且如果进行(l1,l2)

相当于把字符串向左(先l1后 l2) l1 - l2个单位

或向右移动(先l2 后l1) l1 - l2个单位

那么最终答案只可能会是

(l1,l2),l1,l2...  只在原字符串上进行向左或向右移动

l1,(l1,l2),(l1,l2)...  先进行一次l1,再同上

l2,(l1,l2),(l1,l2)...   先进行一次l2,在同上

由于我们要找循环节,所以字符串都变成二倍长度

然后哈希三种情况,看字符串T是否在三种情况中出现过

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
const int N = 4e6 + 10;
typedef pair PII;
string s,s1,s2,c;
int n,m,a,b;
int h1[N],h2[N],h[N],p[N];
int x = 133331;
int mod = 1e9 + 7;
int res;
int get(int h[],int l,int r)
{return (h[r] - h[l-1]*p[r-l+1]%mod + mod)%mod;
} 
int check(int l,int r)
{if(get(h,l,r) == res)return 1;if(get(h1,l,r) == res)return 1;if(get(h2,l,r) == res)return 1;return 0;}
void solve() 
{cin >> s >> c >> a >> b;n = s.size();s1 = s.substr(a) + s.substr(0,a);reverse(s1.begin(),s1.end());s2 = s.substr(b) + s.substr(0,b);reverse(s2.begin(),s2.end());s = s + s;s = " " + s;s1 = s1 + s1;s1 = " " + s1;s2 = s2 + s2;s2 = " " + s2;c = " " + c;res = 0;p[0] = 1;for(int i = 1;i <= 2*n;i++){p[i] = (p[i-1]*x%mod);h[i] = (h[i-1]*x%mod + s[i])%mod;h1[i] = (h1[i-1]*x%mod + s1[i])%mod;h2[i] = (h2[i-1]*x%mod + s2[i])%mod;if(i <= n)res = (res*x%mod + c[i])%mod;}if(a < b)swap(a,b);for(int i = 1,j = 1;j <= n;j++){if(check(i,i+n - 1)){cout <<"yes\n";return  ;}i = i + n - a + b;if(i >= n + 1){i = i%(n);if(!i)i = n;}}for(int i = 1,j = 1;j <= n;j++){if(check(i,i+n - 1)){cout <<"yes\n";return  ;}i = i + a - b;if(i >= n + 1){i = i%(n);if(!i)i = n;}}cout <<"no\n";
}signed main() 
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;cin >> t;
//scanf("%lld",&t);while (t--) {solve();}
}
//3 F
//5 B
//6 F
//9 F
//10 B
//12 F
//15 FB
//18 FB

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：计算机文化基础Word 2010复习导案

下一篇：麻雀算法SSA优化LSTM长短期记忆网络实现分类算法

相关内容

热门资讯

左半边翅膀初中作文800字（... 篇一：左半边翅膀初中作文800字左半边翅膀是我生活中的助力器生活中，我们每个人都有自己的左半边翅膀，...
童年趣事作文（精选6篇） 童年趣事作文 篇一小时候的我是一个活泼好动的孩子，喜欢和朋友们一起玩耍。其中有一次，我们组织了一场“...
生活在别处初一优秀作文【精简... 生活在别处初一优秀作文 篇一 生活在别处初一优秀作文 篇二生活在别处初一优秀作文 篇三未来的生活当我...
春天是一个令人遐想的季节【经... 春天是一个令人遐想的季节 篇一春天，是四季中最令人遐想的季节。寒冷的冬天过去了，大地开始苏醒，万物复...
此时无声胜有声初中作文【通用... 此时无声胜有声初中作文 篇一随着科技的不断进步和社会的快速发展，人们的生活变得越来越喧嚣。嘈杂的声音...
我们是一家人初中作文600字... 我们是一家人初中作文600字 篇一家，是一个人生活的港湾；家，是一个人成长的摇篮。而对于我来说，家更...
我的执着初一作文（精彩6篇） 我的执着初一作文 篇一执着是一种坚持不懈的品质，它使我在初一的学习生活中取得了许多成就。正是这种执着...
外祖母-初一作文【最新5篇】 外祖母-初一作文 篇一外祖母是我最亲密的长辈，她是一个非常温柔和善良的人。每次我见到她，她都会给我一...
往事如风作文【优选5篇】 往事如风作文 篇一往事如风，岁月如梭。回首过去的时光，仿佛一切都已经过去，只留下了一抹淡淡的回忆。往...
游东沙古镇初一作文1000字... 游东沙古镇初一作文1000字 篇一初一的暑假，我随着家人来到了东沙古镇，这是一个有着悠久历史和独特魅...
捡蘑菇的作文七年级共70篇 捡蘑菇的作文七年级 第一篇雨后，天空一碧如洗，空气也格外清新。小白免皮皮和妈妈跨着竹篮迫不及待地到山...
我的初一生活作文（精选6篇） 我的初一生活作文 篇一初一，是我人生中一个全新的开始。离开了小学的校园，踏入了初中的大门，我怀着激动...
黑与白的初中议论文【经典5篇... 黑与白的初中议论文 篇一黑与白，是一对互补的色彩，代表了对立却又相互依存的存在。在日常生活中，我们常...
初中随笔作文400字【最新5... 初中随笔作文400字 篇一我的偶像每个人都有自己的偶像，他们可以是明星、运动员、作家等等。而我的偶像...
初一餐桌前的谈话作文500字... 初一餐桌前的谈话作文500字 篇一初一餐桌前的谈话今天是我初一的第一天，我很兴奋地回到家中。晚饭时，...
初一作文《假期见闻》（优选6... 初一作文《假期见闻》 篇一我的假期过得非常充实和有意义。在假期中，我参加了一次有趣的亲子旅行，还参加...
八年级作文（精彩6篇） 八年级作文 篇一：我的暑假计划暑假即将来临，我对这个假期充满了期待。我计划度过一个充实而有意义的暑假...
2017年春运火车票购票时间... 2017年春运火车票购票时间表 篇一春运是中国人民一年中最繁忙的出行季节之一，而购票则是春运期间备受...
初中作文题材万能素材积累【优... 初中作文题材万能素材积累 篇一标题：如何保护环境随着工业化和城市化的快速发展，环境问题越来越受到人们...
春天来了初一作文【推荐5篇】 春天来了初一作文 篇一春天来了，大地万物开始苏醒。初一的阳光明媚，温暖的春风轻拂着我们的脸庞，带给我...