学步园

MiYu原创, 转帖请注明 : 转载自 ______________白白の屋    

 

题目地址:

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

题目描述:

Counting Sequences

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/65536 K (Java/Others)
Total Submission(s): 312    Accepted Submission(s): 105

Problem Description

For a set of sequences of integers｛a1，a2，a3，...an｝, we define a sequence｛ai1,ai2,ai3...aik｝in which 1<=i1<i2<i3<...<ik<=n, as the sub-sequence of ｛a1，a2，a3，...an｝. It is quite obvious that a sequence with the length n has 2^n sub-sequences. And for a sub-sequence｛ai1,ai2,ai3...aik｝，if it matches the following qualities: k >= 2, and the neighboring 2 elements have the difference not larger than d, it will be defined as a Perfect Sub-sequence. Now given an integer sequence, calculate the number of its perfect sub-sequence.

 

Input

Multiple test cases The first line will contain 2 integers n, d（2<=n<=100000，1<=d=<=10000000） The second line n integers, representing the suquence

 

Output

The number of Perfect Sub-sequences mod 9901

 

Sample Input

4 2
1 3 7 5

 

Sample Output

4

 

题目分析 :

( 线段树 || 树状数组 ) + DP  

可以使用线段树 或 树状数组来做,  可惜本人现在还不会线段树, 下面是 树状数组 解题的分析 :

因为题目要求的 是 k >= 2 ,  而且 相邻元素 之差的绝对值 不大于 d,  这里纠结了很久 , 一直没明白 "and the

neighboring 2 elements have the difference not larger than d" 这句话的意思, 英语水平太差了.  最后在

Amb 的解释下才明白,  0rz...........  

为了使问题简单化, 我们不凡讨论 k >= 1 的情况:

 因为 输入数据的范围比较大,  2<=n<=100000，1<=d=<=10000000 , 所以先要将 数据排序后 用 hash[max] 做离散化处理.

当然, 原数组需要另开一个数组保存起来. 处理完成后,  我们可以这样理解 :   用树状数组 com[pos], ( pos 为 num 在 hash 数组中的位

置 ) . 记录 能与 num 构成 完美串的个数.     初始状态的 完美子串 为0, 每次加入一个数, 那么这个数 num 与 比他小且差不超过d的第一

个数 而且与 比他大且差不超过d的第一个数  构成完美串 . 更新树状数组. 最后求出所有的子串和 sum,  因为算法是以 k >= 1 来做的,而

题目要求 k >= 2, 也就是说, 对 N 个数, 就多计算了 N 次, 因此 (sum - N ) % 9901 即为所求. ( 别忘了MOD....... )

 

代码如下 :

/*

MiYu原创, 转帖请注明 : 转载自 ______________白白の屋

          http://www.cnblog.com/MiYu

Author By : MiYu

Test      : 1

Program   : 3450

*/

#include <iostream>

#include <algorithm>

using namespace std;

const int MAX = 100010;

const int MOD = 9901;

int nCount = 0;

int com[MAX];

int hash[MAX];

int num1[MAX];

int num2[MAX];

int N,D;

inline int low ( int x ) {

       return x & ( -x );

}

void modify ( int x, int val ){     // 修改 

     while ( x <= nCount ){

            com[x] += val; x += low ( x );

     }     

}

int quy ( int x ){                  // 查询 

    int sum = 0;

    while ( x > 0 ){

           sum += com[x]; x -= low ( x );

    }

    return sum ;

}

int find1 ( int val ){         // 二分 找 <= val 的第一个数 

    int beg = 1, end = nCount; int mid = ( beg + end ) >> 1; int res = mid;

    while ( beg <= end ){

           if ( hash[mid] <= val ){

                beg = mid + 1; res = mid;

           }else{

                end = mid - 1; 

           }

           mid = ( beg + end ) >> 1;

    }

    return res;

}

int find2 ( int val ){         // 二分 找 <= val 的第一个数 

    int beg = 1, end = nCount; int mid = ( beg + end ) >> 1; int res = mid;

    while ( beg <= end ){

           if ( hash[mid] < val ){

                beg = mid + 1;

           }else{

                end = mid - 1; res = mid;

           }

           mid = ( beg + end ) >> 1;

    }

    return res;

}

inline bool scan_d(int &num)      // 输入 

{

        char in;bool IsN=false;

        in=getchar();

        if(in==EOF) return false;

        while(in!='-'&&(in<'0'||in>'9')) in=getchar();

        if(in=='-'){ IsN=true;num=0;}

        else num=in-'0';

        while(in=getchar(),in>='0'&&in<='9'){

                num*=10,num+=in-'0';

        }

        if(IsN) num=-num;

        return true;

}

int main ()

{

    while ( scan_d ( N ) && scan_d ( D ) ){

           for ( int i = 0; i < N; ++ i ){

                scan_d ( num1[i] );  num2[i] = num1[i];  

           }

           sort ( num1, num1 + N );

           hash[1] = num1[0];  nCount = 1;

           for ( int i = 1; i < N; ++ i ){               // 数据 离散化 

                if ( num1[i] != num1[i-1] ) hash[++nCount] = num1[i];

           }

           memset ( com, 0, sizeof ( com ) );

           for ( int i = 0; i < N; ++ i ){

                int pos = find1 ( num2[i] );             // 找当前元素的 hash 下标   

                int pre = find1 ( num2[i] + D );         // 找 <=  num2[i] + D 的第一个数 

                int tail = find2 ( num2[i] - D );        // 找 >= num2[i] - D  的第一个数 

                int val = quy ( pre ) - quy ( tail - 1 ) + 1;  // 区间 [ num2[i] - D, num2[i] + D ] 的元素个数 + 新增的一个元素 

                modify ( pos, val % MOD );

           }

           cout << ( quy ( nCount ) - N  ) % MOD << endl;  //以 一个元素 的 [ elem - D, elem + D ] 计算, 题目要求 k >= 2, 减掉 N 个 

    }

    return 0;

}