首尾相接的数组,其旋转后恢复原状的循环节的性质
2022/6/10 23:20:20
本文主要是介绍首尾相接的数组,其旋转后恢复原状的循环节的性质,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
对于一个首尾相接的数组,设其旋转k1、k2、k3...次后可以恢复原状。
且k1<k2<k3<...。
则可以肯定,k1为这个数组的循环节,且k2、k3...均为k1的倍数。
一种求循环节的方法为:
对长度为n的循环字符串,先从小到大遍历可能的循环节的长度i,判断是否n%i==0,然后对其中的除第一个循环节内的每一个字符进行判断
参考代码如下(By * A_G, contest: Codeforces Round #797 (Div. 3), problem: (F) Shifting String)
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
int period(string& s) { int n = s.size(); for (int i = 1; i <= n/2; i++) { if (n%i == 0) { bool good = 1; for (int j = i; j < n; j++) { if (s[j-i] != s[j]) { good = 0; break; } } if (good) return i; } } return n; }View Code
例题 Codeforces Round #797 (Div. 3) F. Shifting String
https://codeforces.com/contest/1690/problem/F
代码如下
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL gcd(LL num1, LL num2) { if (num1%num2 == 0) return num2; return gcd(num2, num1%num2); } void YD() { int n; cin >> n; string str; cin >> str; vector<int> p(n); for (int i = 0; i < n; i++) { cin >> p[i]; p[i]--; } vector<bool> vis(n,false); LL ans = 1; for (int i = 0; i < n; i++) { if (!vis[i]) { string cir; cir+=(str[i]); vis[i] = true; int cur = p[i]; while (cur != i) { cir += (str[cur]); vis[cur] = true; cur = p[cur]; } int nn = cir.size(); for (int ii = 1; ii <= nn / 2; ii++) { if (nn%ii == 0) { bool flag = true; for (int jj = ii; jj < nn; jj++) { if (cir[jj] != cir[jj - ii]) { flag = false; break; } } if (flag) { nn = ii; break; } } } ans = ans / gcd(ans, LL(nn))*LL(nn); } } cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { YD(); } }View Code
这篇关于首尾相接的数组,其旋转后恢复原状的循环节的性质的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)