ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0

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;
}

 

 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理