poj 2185 Milking Grid(KMPnext数组的性质+lcm)

news/2024/6/2 9:02:10 标签: output, input, 算法, blog, im, c

cle class="baidu_pl">

cle_content" class="article_content clearfix">

content_views" class="htmledit_views"> color:rgb(154,151,150); font-family:sclass="tags" href="/tags/IM.html" title=im>imsun; font-size:14px; line-height:21px; background-color:rgb(0,0,0)">

color:initial; list-style-type:none; list-style-position:initial; word-wrap:normal; word-break:normal; line-height:21px"> 【题目大意】：给出一个n*m的字符矩阵࿰c;求出一个最小的子矩阵࿰c;使得其在不断复制后可以形成一个新的矩阵覆盖原矩阵。如下面的sanmple࿰c;最小的子矩阵是“AB”࿰c;经过复制后形成的矩阵是：ABABAB > ABABA

color:initial; list-style-type:none; list-style-position:initial; word-wrap:normal; word-break:normal; line-height:21px"> ABABAB ABABA

color:initial; list-style-type:none; list-style-position:initial; word-wrap:normal; word-break:normal; line-height:21px"> Sample Input

ce:normal">2 5 ABABA ABABA

color:initial; list-style-type:none; list-style-position:initial; word-wrap:normal; word-break:normal; line-height:21px"> Sample Output

ce:normal">2

ce:normal">

ce:normal">【解题思路】：color:rgb(154,151,150); font-family:sclass="tags" href="/tags/IM.html" title=im>imsun; font-size:14px; line-height:21px; background-color:rgb(0,0,0)">ce:normal">最小子矩阵复制后要覆盖原矩阵࿰c;也就是说子矩阵必须包含原来矩阵的所有字母࿰c;因此我们只需要求的每一行࿰c;每一列的最小重复子串即可࿰c;这个求解利用到了kmpclass="tags" href="/tags/SuanFa.html" title=算法>算法中next数组的一个性质࿰c;详见：博客中poj 2406的解释。 再求出各行列的最小重复子串后࿰c;只需对所有行的答案求其最小公倍数和所有列的答案求其最小公倍数就可以得到最终答案了。
ce:normal">（*************当所求出的最小公倍数大于其列数（行数）时࿰c;将其修改为行（列）的长度~~࿰c;当年的class="tags" href="/tags/BLOG.html" title=blog>blog写着我在此处我WA了n次~！！！！！！）
ce:normal">
ce:normal">【代码】：
ce:normal"><code class="language-cpp">#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cctype>
#include <map>
#include <iomanip>
                   
using namespace std;
                   
#define eps 1e-8
#define pi acos(-1.0)
#define inf 1<<30
#define pb push_back
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define lowbit(x) (x & (-x))
#define ll long long

char s[100010][80],pp;
int next[100010],n,m,temp,a,b;

int gcd(int x,int y){
    if (!x||!y) return x>y?x:y;
    for (int t;t=x%y;x=y,y=t);
    return y;    
}

int lcm(int x,int y){ 
    int d;
    d=gcd(x,y);
    return x*y/d;
}

int solve_kmp_next_row(int k){
    next[0]=0;
    next[1]=0;
    for(int i=1; i<m; i++){
    temp=next[i-1];
    while(temp && s[k][temp]!=s[k][i])
    temp = next[temp-1];
    if(s[k][temp]==s[k][i])
        next[i]=temp+1;
    else
        next[i]=0;
    }
    return m-next[m-1];      
}

int solve_kmp_next_column(int k){
    next[0]=0;
    next[1]=0;
    for(int i=1; i<n; i++){
        temp=next[i-1];
    while(temp && s[temp][k]!=s[i][k])
    temp=next[temp-1];
    if(s[temp][k]==s[i][k])
        next[i]=temp+1;
    else
        next[i]=0;
    }
    return n-next[n-1];      
}

int main(){
    scanf("%d%d",&n,&m);
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++)
            cin >> s[i][j];
        scanf("%c",&pp);
    }
    a=solve_kmp_next_row(0);
    b=solve_kmp_next_column(0);
    for (int i=1; i<n; i++){
        a=lcm(a,solve_kmp_next_row(i));
        if (a>=m) { a=m; break; }
    }
    for (int i=1; i<m; i++){
        b=lcm(b,solve_kmp_next_column(i));
        if (b>=n) { b=n; break; }
    }    
    printf("%d",a*b); 
    return 0;    
}
code>