ACM-Tem

Posted on 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
    //递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了
    if(pos==-1) return 1;/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
    //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
    /*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/
    int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
    ll ans=0;
    //开始计数
    for(int i=0;i<=up;i++)//枚举，然后把不同情况的个数加到ans就可以了
    {
        if() ...
        else if()...
        ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
        /*这里还算比较灵活，不过做几个题就觉得这里也是套路了
        大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论
        去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目
        要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类，
        前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/
    }
    //计算完，记录状态
    if(!limit && !lead) dp[pos][state]=ans;
    /*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/
    return ans;
}
ll solve(ll x)
{
    int pos=0;
    while(x)//把数位都分解出来
    {
        a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来，反正注意数位边界就行
        x/=10;
    }
    return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛
}
int main()
{
    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri))
    {
        //初始化dp数组为-1,这里还有更加优美的优化,后面讲
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//不怕别人比你聪明，就怕别人比你聪明还比你努力
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <set>
#include <stack>
#include <map>
#include<vector>
#include <iterator>
#define INF 0x3f3f3f3f
#define ll long long

using namespace std;
const int MAXN = 500;
int n,w;
char str[MAXN];
int SA[MAXN];
int buc[MAXN];
int x[MAXN],y[MAXN],len;
int rank[MAXN],height[MAXN];///rank[i] 用来记录后缀 i 在 SA 数组的位置,表示字符串i的排名
///height[i] 记录后缀 SA[i] 和 SA[i - 1] 的 LCP 的长度。
int h[MAXN]; //h[i] = height[rank[i]]:排名为i的后缀与排名靠前一位的最长公共前缀

//rank:这个排在第几，SA：排在第几的是谁
void da()
{
    scanf("%s",str);
    len = strlen(str);
    int m = 127;
    for(int i= 0 ;i < m;i ++) buc[i] = 0;
    for(int i = 0;i < len;i ++) buc[x[i] = str[i]] ++;
    for(int i = 1 ;i < m;i ++) buc[i] += buc[i-1];
    for(int i = len -1;i >= 0;i --) SA[-- buc[x[i]]] = i;
    for(int k = 1;k <= len;k <<= 1)
    {
        int p = 0;
        for(int i = len- 1;i >= len - k;i --) y[p++] = i;
        for(int i =0 ;i < len;i ++) if(SA[i] >= k) y[p++] = SA[i] - k;

        for(int i= 0 ;i < m;i ++) buc[i] = 0;
        for(int i =0 ;i <len;i ++) buc[x[y[i]]] ++;
        for(int i =1 ;i < m;i ++) buc[i] += buc[i-1];
        for(int i = len-1;i >= 0;i -- ) SA[ -- buc[x[y[i]]]] = y[i];

        swap(x,y);
        p = 1;x[SA[0]] = 0;
        for(int i = 1;i < len;i ++)
        {
           if(y[SA[i-1]] == y[SA[i]] && y[SA[i-1]+k] == y[SA[i]+k])
                x[SA[i]] = p-1;
           else
                x[SA[i]] = p++;
        }
        if(p >= len) break;
        m = p;
    }
}

//如果直接求的话，复杂度为O(n^2)，但是我们按照h[1],h[2],h[3]....的顺序求解，并利用h数组的性质，时间复杂度可以降为O(n)
//h[i] >= h[i-1]+1                   h[i] = height[rank[i]]

void get_height()
{
    for(int i =0 ;i < len;i ++) rank[SA[i]] = i;
    int k = 0;
    for (int i = 0; i < len; i++)
    {
        if (rank[i] == 0) {height[0] = 0; continue;} // 第一个后缀的 LCP 为 0。
        if (k) k--; // 从 k - 1 开始推
        int j = SA[rank[i] - 1];
        while (str[i + k] == str[j + k] && i + k < len && j + k < len) k++;
        height[rank[i]] = k;
    }
}

int main()
{
    da();
    get_height();
    cout<<"height: ";
    for(int i =0 ;i < len;i ++)
        cout<<height[i]<<" ";
    cout<<endl;
    cout<<"  rank: ";
    for(int i = 0;i < len;i ++)
        cout<<rank[i]<<" ";
    cout<<endl;
    for(int i=0; i<len; ++i)
    {
        printf("sa[%2d ] = %2d\t",i,SA[i]);
        for(int j=SA[i]; j<len; ++j)
            printf("%c",str[j]);
        printf("  %d",height[i]);
        puts("");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
void get_height()
{
    for(int i =0 ;i < len;i ++) rank[SA[i]] = i;
    int k = 0;
    for (int i = 0; i < len; i++)
    {
        if (rank[i] == 0) {height[0] = 0; continue;} // 当排名为0时，因为他前面没有字符串，所以这里就应该定为0
        if (k) k--; // 从 k - 1 开始推，这里我们就利用了上面h数组的性质
        int j = SA[rank[i] - 1];   //得到上一名的开始位置
        while (str[i + k] == str[j + k] && i + k < len && j + k < len) k++;//相同的话，我们就一直向后加
        height[rank[i]] = k; //更新height数值
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//不怕别人比你聪明，就怕别人比你聪明还比你努力
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <set>
#include <stack>
#include <map>
#include<vector>
#include <iterator>
#define INF 0x3f3f3f3f
#define ll long long

using namespace std;
const int MAXN = 500;
int n,w;
char str[MAXN];
int SA[MAXN];
int buc[MAXN];
int x[MAXN],y[MAXN],len;
//x数组表示第一元素，y数组表示第二元素

void da()
{
    //SA表示我排在第几位的是谁，SA[k] = i，排在第k位的是第i个后缀
    scanf("%s",str);
    len = strlen(str);
    int m = 127;//m表示第一次我们字符串的范围
    //在进行倍增之前首先对每一个元素进行一次基数排序，然后放到数组SA中
    for(int i =0 ;i < m;i ++) buc[i] = 0;
    for(int i =0 ;i < len;i ++) buc[x[i] = str[i]] ++;
    for(int i = 1;i < m;i ++) buc[i] += buc[i-1];
    for(int i = len-1;i >= 0;i --) SA[ -- buc[x[i]]] = i;
    for(int k = 1;k <= len; k <<= 1)    //进行倍增
    {
        int p = 0;
        for(int i = len - 1; i >= len -k; i --) y[p++] = i;    //我们要得到第二元素，因为要向后移动k个，所以这里表示的是添零操作
        //因为零一定会排在最前面，所以y[p++] = i;表示排在第p位的是第i个后缀，表示的就是最后面的后缀
        for(int i = 0;i < len;i ++) if(SA[i] >= k) y[p++] = SA[i] - k;   //然后我们删除前面几个跳过的元素，这些跳过的元素都是在k之前的，也就是SA[i] < k
        //比如我们要排序的数是：92,81,30,24,57,96；
        //我们得到的y数组是对第二元素进行的排序，即：y[] = 3,2,1,4,6,5
        //x[y[]] = 30,81,92,24,96,57  ：即表示对第二元素进行排序的结果
        //下面的排序就和只有一个元素的排序相同了

        for(int i =0 ;i < m;i ++) buc[i] = 0;        //再进行一次基数排序
        for(int i = 0;i < len;i ++) buc[x[y[i]]] ++;
        for(int i = 1;i < m;i ++) buc[i] += buc[i-1];
        for(int i = len-1;i >= 0;i --) SA[ -- buc[x[y[i]]]] = y[i];

        swap(x,y);  //交换之后现在y表示每个位置上现在的数字
        //SA表示现在排在第几位置上的是谁
        p = 1;x[SA[0]] = 0;  //首先是将排在第0位置上的
        for(int i = 1;i < len;i ++)   //这里我们要更新最大的范围，只有当前面和后面不相同的时候我们才进行p++操作，否则表示上一个数
        {
            if(y[SA[i-1]] == y[SA[i]] && y[SA[i-1]+k] == y[SA[i] + k])
                x[SA[i]] = p-1;
            else
                x[SA[i]] = p++;
        }//当
        if(p >= len)//当每一个元素都是不同的排名的时候，可以结束循环
            break;
        m = p;//更新范围
    }
}
int main()
{
    da();
    //最终我们得到的后缀数组内容就在SA数组中,
    for(int i=0; i<len; ++i)
    {
        printf("sa[%2d ] = %2d\t",i,SA[i]);
        for(int j=SA[i]; j<len; ++j)
            printf("%c",str[j]);
        puts("");
    }
}