tc srm 632 500 (规律)

We have a sequence of N positive integers: a[0] through a[N-1]. You do not know these integers. All you know is the number of trailing zeros in their binary representations. You are given a vector <int> d with N elements. For each i, d[i] is the number of trailing zeros in the binary representation of a[i].

For example, suppose that a[0]=40. In binary, 40 is 101000 which ends in three zeros. Therefore, d[0] will be 3.

You like geometric sequences. (See the Notes section for a definition of a geometric sequence.) You would like to count all non-empty contiguous subsequences of the sequence a[0], a[1], ..., a[N-1] that can be geometric sequences (given the information you have in d).

More precisely: For each pair (i,j) such that 0 <= i <= j <= N-1, we ask the following question: "Given the values d[i] through d[j], is it possible that the values a[i] through a[j] form a geometric sequence?"

For example, suppose that d = {0,1,2,3,2}. For i=0 and j=3 the answer is positive: it is possible that the values a[0] through a[3] are {1,2,4,8} which is a geometric sequence. For i=1 and j=4 the answer is negative: there is no geometric sequence with these numbers of trailing zeros in binary.

Compute and return the number of contiguous subsequences of a[0], a[1], ..., a[N-1] that can be geometric sequences.

Definition

Class:	PotentialGeometricSequence
Method:	numberOfSubsequences
Parameters:	vector <int>
Returns:	int
Method signature:	int numberOfSubsequences(vector <int> d)
(be sure your method is public)

Limits

Time limit (s):	2.000
Memory limit (MB):	256

Notes

A geometric sequence is any sequence g[0], g[1], ..., g[k-1] such that there is a real number q (the quotient) with the property that for each valid i, g[i+1] = g[i]*q. For example, {1,2,4,8} is a geometric sequence with q=2, {7,7,7} is a geometric sequence with q=1, and {18,6,2} is a geometric sequence with q=1/3.

Constraints

N will be between 1 and 50, inclusive.

d will contain exactly N elements.

Each element of d will be between 0 and 100, inclusive.

d是二进制下这个数的末尾的0的个数，求其子序列里能够构成的等比序列的个数。

分析：求其等差子序列的个数

这应该算是一个看数字的规律题吧，我找的也挺慢的，不过想想二进制下每一位代表的数字比较一下规格，应该不难猜出来这个等比和等差的规律

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #define LL __int64

 const double eps = 1e-;

 const int maxn = +;

 using namespace std;

 class PotentialGeometricSequence

 {

  public:

     int numberOfSubsequences(vector <int> d)

     {

         int n = d.size();

         int i, j, ret = n+n-, f, x, k, y;

         for(i = ; i < n; i++)

         {

             for(j = ; j < n; j++)

             {

                 if(j+i < n)

                 {

                     f = ;

                     x = d[j+]-d[j];

                     for(k = j+; k <= j+i; k++)

                     {

                         y = d[k]-d[k-];

                         if(y!=x)

                         f = ;

                     }

                     if(f == )

                     ret ++;

                 }

             }

         }

         return ret;

     }

 };

巴特西

tc srm 632 500 (规律)

Definition

Limits

Notes

Constraints

最新文章

热门文章