POJ 2185 Milking Grid KMP循环节周期
循环 poj Grid KMP 周期
2023-09-11 14:21:00 时间
题意:至少要多少大的子矩阵 能够覆盖全图
比如例子 能够用一个AB 组成一个
ABABAB
ABABAB 能够多出来
思路:每一行求出周期 总共n个 求这n个周期的最小公倍数 假设大于m 取m
每一列求出周期 总共m个求这个m个周期的最小公倍数 假设大于n取n
答案就是2个最小公倍数的积
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; const int maxn = 10010; char a[maxn][77]; char b[77][maxn]; int f[maxn][77]; int f2[77][maxn]; int gcd(int a, int b) { return b?gcd(b, a%b):a; } void getFail(char* p, int* f) { int m = strlen(p); f[0] = f[1] = 0; for(int i = 1; i < m; i++) { int j = f[i]; while(j && p[i] != p[j]) j = f[j]; f[i+1] = p[i] == p[j] ? j+1 : 0; } } int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%s", a[i]); getFail(a[i], f[i]); } for(int i = 0; i < m; i++) { for(int j = 1; j <= n; j++) { b[i+1][j-1] = a[j][i]; } b[i+1][n] = 0; } for(int i = 1; i <= m; i++) getFail(b[i], f2[i]); int ans1 = 1, ans2 = 1; for(int i = 1; i <= n; i++) { ans1 = ans1/gcd(ans1, m-f[i][m])*(m-f[i][m]); if(ans1 > m) { ans1 = m; break; } } for(int i = 1; i <= m; i++) { ans2 = ans2/gcd(ans2, n-f2[i][n])*(n-f2[i][n]); if(ans2 > n) { ans2 = n; break; } } printf("%d\n", ans1*ans2); return 0; }
相关文章
- c语言中各个循环的流程图——方便记忆
- Google Earth Engine(GEE)——容易犯的错误6(reduceRegion()与. reduceRegions()与. for循环)
- 90 python高级 - 循环导入
- C#【基础篇】 C# 循环
- Swift流程控制之循环语句和判断语句详解
- 鸿蒙基础之UnownedOuter 内部类以消除循环引用 (HarmonyOS鸿蒙开发基础知识)
- 循环取月的三位英语名 Jan Feb
- QT中|Qt::Tool类型窗口自动退出消息循环问题解决(setQuitOnLastWindowClosed必须设置为false,最后一个窗口不显示的时候,程序会退出消息循环)
- 《Unity开发实战》——3.10节通过循环加载一组材质实现动画纹理(例如模拟视频)
- 【POJ 2406】Power Strings(KMP循环节)
- javascript for in 循环时,会取到Array.prototype
- 第2章 数字之魅——数组循环移位
- 测试递归与循环的执行效率与系统开销
- Spring 循环引用问题
- 循环链表解决约瑟夫环问题