首页 > ACM题库 > HDU-杭电 > HDU 3030- Increasing Speed Limits-动态规划-[解题报告]HOJ
2014
02-27

HDU 3030- Increasing Speed Limits-动态规划-[解题报告]HOJ

Increasing Speed Limits

问题描述 :

You were driving along a highway when you got caught by the road police for speeding. It turns out that they\’ve been following you, and they were amazed by the fact that you were accelerating the whole time without using the brakes! And now you desperately need an excuse to explain that.

You’ve decided that it would be reasonable to say "all the speed limit signs I saw were in increasing order, that\’s why I’ve been accelerating". The police officer laughs in reply, and tells you all the signs that are placed along the segment of highway you drove, and says that’s unlikely that you were so lucky just to see some part of these signs that were in increasing order.

Now you need to estimate that likelihood, or, in other words, find out how many different subsequences of the given sequence are strictly increasing. The empty subsequence does not count since that would imply you didn’t look at any speed limits signs at all!

For example, (1, 2, 5) is an increasing subsequence of (1, 4, 2, 3, 5, 5), and we count it twice because there are two ways to select (1, 2, 5) from the list.

输入:

The first line of input gives the number of cases, N. N test cases follow. The first line of each case contains n, m, X, Y and Z each separated by a space. n will be the length of the sequence of speed limits. m will be the length of the generating array A. The next m lines will contain the m elements of A, one integer per line (from A[0] to A[m-1]).

Using A, X, Y and Z, the following pseudocode will print the speed limit sequence in order. mod indicates the remainder operation.

for i = 0 to n-1
print A[i mod m]
A[i mod m] = (X * A[i mod m] + Y * (i + 1)) mod Z

Note: The way that the input is generated has nothing to do with the intended solution and exists solely to keep the size of the input files low.

1 ≤ m ≤ n ≤ 500 000

输出:

The first line of input gives the number of cases, N. N test cases follow. The first line of each case contains n, m, X, Y and Z each separated by a space. n will be the length of the sequence of speed limits. m will be the length of the generating array A. The next m lines will contain the m elements of A, one integer per line (from A[0] to A[m-1]).

Using A, X, Y and Z, the following pseudocode will print the speed limit sequence in order. mod indicates the remainder operation.

for i = 0 to n-1
print A[i mod m]
A[i mod m] = (X * A[i mod m] + Y * (i + 1)) mod Z

Note: The way that the input is generated has nothing to do with the intended solution and exists solely to keep the size of the input files low.

1 ≤ m ≤ n ≤ 500 000

样例输入:

2
5 5 0 0 5
1
2
1
2
3
6 2 2 1000000000 6
1
2

样例输出:

Case #1: 15
Case #2: 13

//树状数组 + 简单DP
//同hdu 3450,dp的求和操作由树状数组来求执行
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 500010;
const int mod = 1000000007;
__int64 c[maxn],a[maxn],val[maxn],b[maxn];
int tot;
int lowbit(int x){
    return x&-x;
}
void update(int x,__int64 d){
    for(;x<maxn;x+=lowbit(x)){
        c[x]+=d;
        if(c[x]>=mod) c[x]%=mod;
    }
}
__int64 sum(int x){
    __int64 ans=0;
    for(;x>0;x-=lowbit(x)){
            ans+=c[x];
            if(ans>=mod)
                ans-=mod;
    }
    return ans;
}
int main()
{
    int t,cases=1,n,m,i,j;
    __int64 X,Y,Z;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%I64d%I64d%I64d",&n,&m,&X,&Y,&Z);
        for(i=0;i<m;i++)
            scanf("%I64d",&a[i]);
        for(i=0;i<n;i++){
            b[i+1]=a[i%m];
            val[i+1]=b[i+1];
            a[i%m]=(X*a[i%m]+Y*(i+1))%Z;
        }
        sort(b+1,b+n+1);
        tot=unique(b+1,b+n+1)-b;
        memset(c,0,sizeof(c));
        __int64 ans=0;
        for(i=1;i<=n;i++){
            int id=lower_bound(b+1,b+tot+1,val[i])-b;
            __int64 num=sum(id-1);
            ans+=num+1;
            ans%=mod;
            update(id,num+1);
        }
        printf("Case #%d: %I64d\n",cases++,ans);
    }
    return 0;
}

 

参考:http://www.cnblogs.com/wuyiqi/archive/2012/01/31/2333921.html


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  3. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  4. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  5. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }