首页 > ACM题库 > HDU-杭电 > HDU 4718-The LCIS on the Tree-字符串-[解题报告]HOJ
2015
09-17

HDU 4718-The LCIS on the Tree-字符串-[解题报告]HOJ

The LCIS on the Tree

问题描述 :

For a sequence S1, S2, … , SN, and a pair of integers (i, j), if 1 <= i <= j <= N and Si < Si+1 < Si+2 < … < Sj-1 < Sj , then the sequence Si, Si+1, … , Sj is a CIS (Continuous Increasing Subsequence). The longest CIS of a sequence is called the LCIS (Longest Continuous Increasing Subsequence).
Now we consider a tree rooted at node 1. Nodes have values. We have Q queries, each with two nodes u and v. You have to find the shortest path from u to v. And write down each nodes’ value on the path, from u to v, inclusive. Then you will get a sequence, and please show us the length of its LCIS.

输入:

The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case, the first line is a number N (N <= 105), the number of nodes in the tree.
The second line comes with N numbers v1, v2, v3 … , vN, describing the value of node 1 to node N. (1 <= vi <= 109)
The third line comes with N – 1 numbers p2, p3, p4 … , pN, describing the father nodes of node 2 to node N. Node 1 is the root and will have no father.
Then comes a number Q, it is the number of queries. (Q <= 105)
For next Q lines, each with two numbers u and v. As described above.

输出:

The first line has a number T (T <= 10) , indicating the number of test cases.
For each test case, the first line is a number N (N <= 105), the number of nodes in the tree.
The second line comes with N numbers v1, v2, v3 … , vN, describing the value of node 1 to node N. (1 <= vi <= 109)
The third line comes with N – 1 numbers p2, p3, p4 … , pN, describing the father nodes of node 2 to node N. Node 1 is the root and will have no father.
Then comes a number Q, it is the number of queries. (Q <= 105)
For next Q lines, each with two numbers u and v. As described above.

样例输入:

1
5
1 2 3 4 5
1 1 3 3
3
1 5
4 5
2 5

样例输出:

Case #1:
3
2
3

题意:求算有多少个长度为m*l的子串中的m段没有完全重复的串的个数

解法:直接字符串rk上就可以了 要注意的是起点的选择只需要l个 这个非常重要 直接改变了复杂度呵呵

#include<map>
#include<cstdio>
#include<iostream>
using namespace std;
#define ll  unsigned long long
#define mod 123
#define maxn 111111
map<ll,int>mp;
ll wei[maxn],h[maxn];
char ss[maxn];
int m,l,sum=0;
int main(){
    wei[1]=1;
    for(int i=2;i<=100011;++i)wei[i]=wei[i-1]*mod;
    
    while(~scanf("%d%d%s",&m,&l,ss+1)){
        sum=0;
        int len=(int)strlen(ss+1);
        int duan=m*l;
        h[0]=0;
        for(int i=1;i<=len;++i){
            h[i]=(ss[i]-'a'+1)+h[i-1]*mod;
        }
        ll ans;
        
        for(int i=1;i+duan-1<=len&&i<=l;++i){
            mp.clear();
            int st=i-1,ed=i-1;
            while(ed+=l){
                ans=h[ed]-h[ed-l]*wei[l+1];
                mp[ans]++;
                if(ed-st==duan){break;}
            }
            if(mp.size()==m){
                sum++;
            }
            while(1){
                if(ed+l>len)break;
                st+=l;
                ans=h[st]-h[st-l]*wei[l+1];
                mp[ans]--;
                if(mp[ans]==0)mp.erase(ans);
                ed+=l;
                ans=h[ed]-h[ed-l]*wei[l+1];
                mp[ans]++;
                if(mp.size()==m)sum++;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

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

参考:http://blog.csdn.net/ahjkl007/article/details/39699477