首页 > ACM题库 > HDU-杭电 > HDU 3450-Counting Sequences-分治-[解题报告]HOJ
2014
03-23

HDU 3450-Counting Sequences-分治-[解题报告]HOJ

Counting Sequences

问题描述 :

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.

输入:

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

输出:

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

样例输入:

4 2
1 3 7 5

样例输出:

4

吐吐槽吧:本来思路完全对了,但是那个二分查找搞错了,我还以为一个就可以了,结果查找上界和下界分别要一个查找函数(WA时就看了一下别人的代码,发现别人都是用两个查找函数的,模仿别人写的查找函数),自己得好好揣摩揣摩。。。

还有就是最后的结果可能是负数。。。因为get_sum的值是小于9901的,而N的值可大于9901

Counting Sequences代码如下:

#include <cstdio>
 #include <cstring>
 #include <algorithm>
 
 const int mod = 9901;
 const int maxn = 100000 + 100;
 
 int a[maxn];
 int val[maxn];
 int c[maxn];
 int N,D,num;
 
 int binary_find1(int x,int l,int r)
 {
     int ans = r;
     while(l <= r)
     {
         int mid = (l + r) / 2;
         if(val[mid] <= x) l = mid + 1,ans = mid;
         else r = mid - 1;
     }
 
     return ans;
 }
 
 int binary_find2(int x,int l,int r)
 {
     int ans = l;
     while(l <= r)
     {
         int mid = (l + r) / 2;
         if(val[mid] < x) l = mid + 1;
         else r = mid - 1,ans = mid;
     }
     return ans;
 }
 int get_sum(int x)
 {
     int sum = 0;
     while(x > 0)
     {
         sum += c[x];
         sum = sum % mod;
         x -= (x & (-x));
     }
 
     return sum;
 }
 
 void insert(int x,int v)
 {
     while(x < num)
     {
         c[x] += v;
         c[x] = c[x] % mod;
         x += (x & (-x));
     }
 }
 
 int main()
 {
     while(scanf("%d%d",&N,&D) == 2)
     {
         for(int i = 1;i <= N;i ++)
         {
             scanf("%d",&a[i]);
             val[i] = a[i];
         }
         std::sort(val + 1,val + N + 1);
         num = 2;
         for(int i = 2;i <= N; i ++)
         {
             if(val[i] != val[i -1])
                 val[num ++] = val[i];
         }
         memset(c,0,sizeof(c));
         for(int i = 1;i <= N;i ++)
         {
             int k = binary_find1(a[i],1,num - 1);
             int x = binary_find1(a[i]+ D,1,num -1);
             int y = binary_find2(a[i] - D,1,num-1); 
             int ans = 1;
             ans += get_sum(x);
             ans -= get_sum(y - 1);
             ans %= mod;
             insert(k,ans);
         }
 
         printf("%d\n",((get_sum(num-1) - N)%mod +mod)%mod);
     }
 
     return 0;
 }

 

 

参考:http://www.cnblogs.com/Shirlies/archive/2012/04/30/2477030.html


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?