武威 网站建设,做sorry动图的网站,百度竞价推广流程,网站建设毕业设计题目2023河南省赛组队训练赛#xff08;四#xff09; - Virtual Judge (vjudge.net) 约瑟夫最近开发了一款名为Pandote的编辑软件#xff0c;现在他正在测试#xff0c;以确保它能正常工作#xff0c;否则#xff0c;他可能会被解雇!Joseph通过实现对Pandote上字符串的复制和…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 T 5 × 105)。接下来是T测试用例。对于每个测试用例第一行包含字符串S第二行包含字符串T。S和T都由小写拉丁字母和[S] ITI组成。第三行包含两个整数l1和l2(1≤l1, l2≤IS1, l1 # 12)表示每一步可以选择的前缀长度。保证所有测试用例的|S]之和不超过5 × 105。
Sample 1
InputcopyOutputcopy 3
ljhelloh
hellohlj
2 4
thisisastr
htrtsasisi
3 5
abcde
bcdea
1 4yes
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是否在三种情况中出现过
#includeiostream
#includealgorithm
#includestring
#includecstring
#includevector
#includemap
#includequeue
#includeset
using namespace std;
#define int long long
const int N 4e6 10;
typedef pairint, int 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-l1]%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,in - 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,in - 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
