Gym - 101128H：Sheldon Numbers

题意

给你两个整数X和Y

问你在区间[X,Y]中，有多少数字的二进制满足ABAB或者A这种形式。A是某个数量的1，B是某个数量的0。

分析

因为数据规模很大，直接枚举x和y之间的数字然后判断会超时。所以直接构造符合的二进制串然后判断是不是在区间[X,Y]内就好。因为二进制串的长度最多只有63，所以随便枚举就行。但是写起来确实麻烦，容易出错的地方太多。

下面的代码是在场上两个队友写的，场上的代码嘛~可能有点乱~(好吧是我懒得再写一遍了

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <iostream>

 #include <cmath>

 using namespace std;

 typedef long long LL;

 typedef unsigned long long ull;

 const int INF=;

 const int maxn=+;

 ull l, r;

 string up, down;

 ull ans = ;

 int lup, ldown;

 int check(string &tmp)

 {

     if(tmp == "") return ;

     int len = tmp.size();

     if (len > lup && len < ldown) return ;

     if (len == lup && len != ldown && tmp >= up) return ;

     if (len == ldown && len != lup && tmp <= down) return ;

     if (len == lup && len == ldown && tmp >= up && tmp <= down) return ;

     return ;

 }

 int main(){

     cin >> l >> r;

     up = down = "";

     while(l)

     {

         up = (char)(l %  + '') + up;

         //cout << up << endl;

         l >>= ;

     }

     while(r)

     {

         down = (char)(r %  + '') + down;

         r >>= ;

     }

     lup = up.size(), ldown = down.size();

 //    string t;

 //    cin >> t;

 //    cout << check(t) << endl;

     for (int len = lup; len <= ldown; len++)

     {

         //cout << len << endl;

         string tmp = "";

         for (int i = ; i <= len; i++)

         {

             string one = "";

             for (int tim = ; tim <= i; tim++)

                 one += '';

             for (int j = ; j <= len; j++)

             {

                 if(i + j > len) continue;

                 string zero = "";

                 for (int tim = ; tim <= j; tim++)

                     zero += '';

                 if (len%(i+j) !=  && len%(i+j) != i) continue;

                 tmp = "";

                 int maxtim = len/(i+j);

                 for (int tim = ; tim <= maxtim; tim++)

                     tmp += one+zero;

                 if (len % (i+j) != )

                     tmp += one;

                 if (check(tmp))

                 {

                     ans++;

                     //cout << tmp << endl;

                 }

                 //cout << tmp << endl;

             }

         }

         tmp = "";

         for (int tim = ; tim <= len; tim++)

             tmp += '';

         if (check(tmp))

         {

             ans++;

             //cout << tmp << endl;

         }

     }

     cout << ans << endl;

     return ;

 }

巴特西

Gym - 101128H：Sheldon Numbers

最新文章

热门文章