首页 > ACM题库 > HDU-杭电 > HDU 4436-str2int-字符串-[解题报告]HOJ
2015
07-16

HDU 4436-str2int-字符串-[解题报告]HOJ

str2int

问题描述 :

In this problem, you are given several strings that contain only digits from ’0′ to ’9′, inclusive.
An example is shown below.
101
123
The set S of strings is consists of the N strings given in the input file, and all the possible substrings of each one of them.
It’s boring to manipulate strings, so you decide to convert strings in S into integers.
You can convert a string that contains only digits into a decimal integer, for example, you can convert "101" into 101, "01" into 1, et al.
If an integer occurs multiple times, you only keep one of them.
For example, in the example shown above, all the integers are 1, 10, 101, 2, 3, 12, 23, 123.
Your task is to calculate the remainder of the sum of all the integers you get divided by 2012.

输入:

There are no more than 20 test cases.
The test case starts by a line contains an positive integer N.
Next N lines each contains a string consists of one or more digits.
It’s guaranteed that 1≤N≤10000 and the sum of the length of all the strings ≤100000.
The input is terminated by EOF.

输出:

There are no more than 20 test cases.
The test case starts by a line contains an positive integer N.
Next N lines each contains a string consists of one or more digits.
It’s guaranteed that 1≤N≤10000 and the sum of the length of all the strings ≤100000.
The input is terminated by EOF.

样例输入:

5
101
123
09
000 
1234567890

样例输出:

202

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents   
by—cxlove  

给出多个数字串,求出所有不同子串的和

http://acm.hdu.edu.cn/showproblem.php?pid=4436 

类似SA一样,在串之间加上特殊字符,这里用数字10就行了,建立SAM。

然后对SAM进行拓扑一次,从前往后统计。

记录到达该节点的路径数量cnt,以前到达该结点的和sum。

则子节点的和则加上,当前节点的和*10+cnt*j,j表示在末尾添加的数字。

拓扑部分,可以用经典的线性,也可以暴力对Len排序。

但是有一些要注意的地方:

1、10是添加的特殊字符,关于10的边是不转移的,这比较显然,只不过是为了不计算重复子串,将所有串拼在一起

2、前导0是要忽略的,也就是从root转移的时候,不能走0,不然会重复计算 

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 100000005
#define M 40
#define N 210005
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL unsigned long long
#define MOD 2012
#define lson step<<1
#define rson step<<1|1
#define sqr(a) ((double)(a)*(a))
#define Key_value ch[ch[root][1]][0]
#define test puts("OK");
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
struct SAM
{
    SAM *pre,*son[11];
    int len,cnt,sum;
}*root,*tail,que[N],*b[N];
int tot;
char str[N/2];
void add(int c,int l)
{
    SAM *p=tail,*np=&que[tot++];
    np->len=l;
    while(p&&p->son[c]==NULL) p->son[c]=np,p=p->pre;
    if(p==NULL) np->pre=root;
    else
    {
        SAM *q=p->son[c];
        if(p->len+1==q->len) np->pre=q;
        else
        {
            SAM *nq=&que[tot++];
            *nq=*q;
            nq->len=p->len+1;
            np->pre=q->pre=nq;
            while(p&&p->son[c]==q) p->son[c]=nq,p=p->pre;
        }
    }
    tail=np;
}
bool cmp(int x,int y)
{
    return que[x].len<que[y].len;
}
int len,c[N];
int slove()
{
    mem(c,0);
    for(int i=0;i<tot;i++) c[que[i].len]++;
    for(int i=1;i<len;i++) c[i]+=c[i-1];
    for(int i=0;i<tot;i++) b[--c[que[i].len]]=&que[i];
    root->cnt=1;
    root->sum=0;
    int ans=0;
    for(int i=0;i<tot;i++)
    {
        SAM *p=b[i];
        for(int j=0;j<10;j++)
        {
            if(i==0&&j==0) continue;
            if(p->son[j])
            {
                SAM *q=p->son[j];
                q->cnt=(q->cnt+p->cnt)%MOD;
                q->sum=(q->sum+p->sum*10+p->cnt*j)%MOD;
            }
        }
        ans=(ans+p->sum)%MOD;
    }
    return ans;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        tot=0;
        root=tail=&que[tot++];
        len=1;
        while(n--)
        {
            scanf("%s",str);
            for(int i=0;str[i];i++) add(str[i]-'0',len++);
            add(10,len++);
        }
        printf("%d\n",slove());
        for(int i=0;i<tot;i++) que[i].sum=que[i].cnt=0,que[i].pre=NULL,mem(que[i].son,NULL);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/8234200