解题报告：Codeforces 768B Code For 1

Codeforces 768B Code For 1

题义

有一个序列，刚开始，只有1个数\(n\)，接着按照以下规则变化找到序列中任意一个\(>1\)的数\(p\)，将他变为 \(\lfloor\frac{p}{2}\rfloor\), \(p \% 2\), \(\lfloor\frac{p}{2}\rfloor\)。不断进行直到序列中只剩下\(0\)和\(1\)。要问你最后生成的\(01\)序列的区间和。

以\(n=17\)为例：

                    17

            8       1       8

        4   0   4       4   0   4

      2 0 2   2 0 2   2 0 2   2 0 2

     101 101 101 101 101 101 101 101

     -------------------------------

     1010101010101011101010101010101

俺的思路

观察上面那个树，我们可以发现一些对称性，并且每个\(>1\)的\(p\)生成的中间那个\(p \% 2\)不再变动，保留到最后的序列；\(\lfloor\frac{p}{2}\rfloor\)放在自己的两边，之后继续生成直到变成\(1\)。

我们可以先把每一层的\(p \% 2\)记录下来。最后的\(1\)也记录下来了。

vector<ll> v;

while(n>1){

	v.push_back(n%2);

	n/=2;

}

v.push_back(n);

后来一想好像根本不用vector，直接位移都可以。

然后大概可以通过一些关系找出每个\(p \% 2\)在生成序列中出现的位置？

下图中的数字\(i\)指代第\(i\)层的\(p \% 2\)，也即v的下标，从\(0\)开始。

                  0

          1               1

      2       2       2       2

    3   3   3   3   3   3   3   3

   4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

   -------------------------------

   4342434143424340434243414342434

好像规律也不是很难找，你看\(4\)的周期是\(2\)，\(3\)的周期是\(4\)，\(2\)的周期是\(8\)，\(1\)的周期是\(16\)，\(0\)的周期大概是\(32\)？

好像可以求前缀和了叭。我们大概可以算出来每个\(i\)在前\(x\)中出现的次数，

                    0

            1               1

        2       2       2       2

      3   3   3   3   3   3   3   3

     4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

     -------------------------------

     4342434143424340434243414342434

i=4: 112233445566778899aabbccddeeffg

i=3: 0111122223333444455556666777788

i=2: 0001111111122222222333333334444

i=1: 0000000111111111111111122222222

i=0: 0000000000000001111111111111111

然后乘上\(v_i\)，最后加起来就可以算到。

前缀和怎么算？

推出来这个东西，\(h\)是树高度，\(i\)是要求和的下标，\(x\)是前项数：

\[\lfloor\frac{x+2^{h-i-1}}{2^{h-i}}\rfloor
\]

所以最终要求的前缀和

\[f(x) = \sum\limits_{i=0}^{h-1}v_i\cdot\lfloor\frac{x+2^{h-i-1}}{2^{h-i}}\rfloor
\]

ll f(ll x){

	ll s = 0, h = v.size();

	wlf(i,0,h-1){

		s+=v[i]*((x+(1ll<<(h-i-1)))/(1ll<<(h-i)));

	}

	return s;

}

然后每次查询来个\(f(r)-f(l-1)\)就是答案。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

#define wlf(i,a,b) for(ll i=a;i<=b;++i)

#define tbw(i,a,b) for(ll i=a;i>=b;--i)

#define fill0(b) memset(b,0,sizeof(b))

#define fill1(b) memset(b,-1,sizeof(b))

#define fill3f(b) memset(b,0x3f,sizeof(b))

#define nsort(a,n) sort(a+1,a+1+n)

const ll INF = 0x3f3f3f3f3f3f3f3f;

const ll MOD = 1e9+7;

const ll N = 1e5+10;

ll n,l,r;

vector<ll> v;

ll f(ll x){

	ll s = 0, h = v.size();

	wlf(i,0,h-1){

		s+=v[i]*((x+(1ll<<(h-i-1)))/(1ll<<(h-i)));

	}

	return s;

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);cout.tie(0);

	cin>>n>>l>>r;

	while(n>1){

		v.push_back(n%2);

		n/=2;

	}

	v.push_back(n);

	cout<<f(r)-f(l-1)<<endl;

	return 0;

}

巴特西

解题报告：Codeforces 768B Code For 1

Codeforces 768B Code For 1

题义

俺的思路

代码

最新文章

热门文章