HDU4436---str2int 后缀树组（12年天津区域赛）

str2int

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1568 Accepted Submission(s): 540

Problem Description

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.

Input

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.

Output

An integer between 0 and 2011, inclusive, for each test case.

Sample Input

5 101 123 09 000 1234567890

Sample Output

202

Source

2012 Asia Tianjin Regional Contest

题意: n个字符串，对于每一个子串可以表示为一个数字，求所有子串的数字和相加对2012取模，，相同数字只算一次。

这题可以先把n个字符串用一个没有出现过的字符隔开连起来。然后求sa， lcp。

我们可以先看一个简单的例子。

s = 12345

num[1] = 1 sum[1] = 1

num[2] = 12 sum[2] = 1 + 12

num[3] = 123 sum[3] = 1 + 12 + 123

num[4] = 1234 sum[4] = 1 + 12 ＋ 123 + 1234

num[5] = 12345 sum[5] = 1 + 12 + 123 + 1234 + 12345

如果求[3, 4] ，只需要 sum[5] - sum[2] - num[2] * (10 + 100 + 1000)；

判重时只要从 i+ lcp[rank[i]] 开始算就可以了，，因为公共前缀那一部分在前面已经算了。

上代码。。

  1 #include <set>
  2 #include <map>
  3 #include <cmath>
  4 #include <ctime>
  5 #include <queue>
  6 #include <stack>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 typedef unsigned long long ull;
 16 typedef long long ll;
 17 const int inf = 0x3f3f3f3f;
 18 const double eps = 1e-8;
 19 const int mod = 2012;
 20 const int maxn = 2e5+100;
 21 int sum [maxn], num[maxn];
 22 string s;
 23 int sa[maxn], Rank[maxn], tmp[maxn], lcp[maxn];
 24 int k, len;
 25 bool cmp(int i, int j)
 26 {
 27     if (Rank[i] != Rank[j])
 28         return Rank[i] < Rank[j];
 29     else
 30     {
 31         int x = (i+k <= len ? Rank[i+k] : -1);
 32         int y = (j+k <= len ? Rank[j+k] : -1);
 33         return x < y;
 34     }
 35 }
 36 void build_sa()
 37 {
 38     for (int i = 0; i <= len; i++)
 39     {
 40         sa[i] = i;
 41         Rank[i] = (i < len ? s[i] : -1);
 42     }
 43     for (k = 1; k <= len; k *= 2)
 44     {
 45         sort (sa,sa+len+1,cmp);
 46         tmp[sa[0]] = 0;
 47         for (int i = 1; i <= len; i++)
 48         {
 49             tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1],sa[i])? 1 : 0);
 50         }
 51         for (int i = 0; i <= len; i++)
 52             Rank[i] = tmp[i];
 53     }
 54 }
 55 
 56 void Get_lcp()
 57 {
 58     for (int i = 0; i < len; i++)
 59         Rank[sa[i]] = i;
 60     int h = 0;
 61     lcp[0] = 0;
 62     for (int i = 0; i < len; i++)
 63     {
 64         int j = sa[Rank[i]-1];
 65         if (h > 0)
 66             h--;
 67         for (; h+i < len && h+j < len; h++)
 68             if (s[i+h] != s[j+h])
 69                 break;
 70         lcp[Rank[i]] = h;
 71     }
 72 }
 73 bool isdigit(char &ch)
 74 {
 75     return ch >= '0' && ch <= '9';
 76 }
 77 int vec[maxn], board[maxn], tot;
 78 int SUM[maxn];
 79 int solve (int l, int r)
 80 {
 81     if (l > r)
 82         return 0;
 83     int res ;
 84     res = sum[r] - sum[l-1];
 85     res = ((res%mod)+mod)%mod;
 86     res -= num[l-1] * SUM[r-l+1];
 87     res = ((res%mod)+mod)%mod;
 88     return ((res%mod)+mod)%mod;
 89 }
 90 int main()
 91 {
 92 #ifndef ONLINE_JUDGE
 93     freopen("in.txt","r",stdin);
 94 #endif
 95     int n;
 96     SUM[1] = 10;
 97     for (int i = 2; i < maxn; i++)
 98     {
 99         SUM[i] = (SUM[i-1] + 1) * 10 % mod;
100     }
101     while (~scanf ("%d", &n))
102     {
103         s = "";
104         tot = 0;
105         memset(sum, 0, sizeof(sum));
106         memset(num, 0, sizeof(num));
107         for (int i = 0; i < n; i++)
108         {
109             string tmp;
110             cin >> tmp;
111             s += tmp + "#";
112         }
113         len = s.size();
114         int val = 0;
115         for (int i = 0; i < len; i++)
116         {
117             if (s[i] != '#')
118             {
119                 val = (val * 10 + s[i] - '0') % mod;
120                 num[i] = val;
121                 sum[i] = (sum[i-1] + num[i]) % mod;
122                 board[i] = tot;
123             }
124             if (s[i] == '#')
125             {
126                 vec[tot++] = i;
127                 num[i] = val;
128                 sum[i] = sum[i-1] + val;
129             }
130         }
131         build_sa();
132         Get_lcp();
133         int ans = 0;
134         for (int i = 0; i < len; i++)
135         {
136             int t1 = i + lcp[Rank[i]];
137             if (s[i] == '0')
138                 continue;
139             if (isdigit(s[i]) && i+lcp[Rank[i]] < vec[board[i]])
140             {
141                 int t2 = vec[board[i]] -1;
142                 int ans1 = solve(i, t2);
143                 int ans2 = solve(i , t1-1);
144                 ans = (ans + solve(i, t2) - solve(i, t1-1)) % mod;
145                 if (ans < 0)
146                     ans += mod;
147             }
148         }
149         printf("%d
", ans%mod);
150     }
151     return 0;
152 }