How many HDU - 2609

技术文章 1年前 (2020) 完美者
308 0

标签:min()   else   表示   href   pre   ++   any   type   man   

题目链接

题意:求本质不同的串有多少

思路:求出最小表示法,如果最小表示法的字符串不同则本质不同。用一个人set记录,最后求得size。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+20;
const int mod=1e9+7;
char s[maxn];
int len;
int GetMin(){
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len){
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(t==0)k++;
        else{
            if(t>0)i=i+k+1;
            else j=j+k+1;
            if(i==j)j++;
            k=0;
        }
    }
    return min(i,j);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        set<string> ss;
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            len=strlen(s);
            int t=GetMin();
            char y[110];
            for(int j=0;j<len;j++)
            {
                y[j]=s[(j+t)%len];
            }
            string u(y);
            ss.insert(u);
        }
        printf("%d\n",ss.size());
    }
}

 

How many HDU - 2609

标签:min()   else   表示   href   pre   ++   any   type   man   

原文地址:https://www.cnblogs.com/2462478392Lee/p/13652817.html

版权声明:完美者 发表于 2020-09-17 22:13:44。
转载请注明:How many HDU - 2609 | 完美导航

暂无评论

暂无评论...