【codeforces 768B】Code For 1

2019-11-08 01:25:33

字体：大中小

来源：转载

供稿：网友

【题目链接】:http://codeforces.com/contest/768/PRoblem/B

【题意】一开始给你一个数字n; 让你用这个数字n根据一定的规则生成序列; (如果新生成的序列里面还有大于1的数字,就一直按着上面的规则重复生成); 最后让你统计在一个区间范围内的1的数目;

【题解】一个树形的样子; 算出总共1的数目(整棵树的叶子节点上和节点的余数上) 这个挺好算的; 然后在从下往上走的时候记录每个节点的子树的size; 和子树所含的1的个数; 不应该先算出总的size; 然后算出1..l-1里面1的数目和r+1..len里面1的数目; (len为最后整个序列的长度); 用总的1的数目减去这两个数目就是答案了; 这里1的数目每次找高度最低的满足siz[rt]<=len-(r+1)+1或者siz[rt]<=l-1的节点,然后把它以下的1的数目统计一下就好; 然后再递归找子树,直到len-(r+1)+1和l-1都变成0为止; 【完整代码】

#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 100;LL n,l,r,a[N],siz[N],cnt1[N],total;LL sz[N];int num = 0;void fix(LL x){ if (x==2 || x==3) { num++; siz[num] = 3; sz[num] = x; if (x==2) cnt1[num]=2; else cnt1[num]=3; } else { fix(x>>1); num++; sz[num] = x; siz[num] = siz[num-1]*2+1; cnt1[num] = cnt1[num-1]*2+(x&1); }}int main(){ //freopen("F://rush.txt","r",stdin); rel(n),rel(l),rel(r); //n==0 || n==1? if (n==0) { puts("0"); return 0; } if (n==1) { puts("1"); return 0; } fix(n); total = siz[num]; //cnt右==size-(r+1)+1 LL cnty = total-(r+1)+1; LL tempy = 0; if (cnty>0) { if (cnty==1) tempy++; else if (cnty==2) { if (cnt1[1]==3) tempy+=2; else tempy+=1; } else { while (cnty>=3) { rep1(i,1,num) if (cnty<=siz[i]) { if (cnty==siz[i]) { cnty=0; tempy+=cnt1[i]; break; } cnty-=siz[i-1]; tempy+=cnt1[i-1]; if (cnty>0) { cnty--; tempy+=(sz[i]&1); } break; } } if (cnty==1) tempy++; else if (cnty==2) { if (cnt1[1]==3) tempy+=2; else tempy+=1; } } } //cnt左==l-1 LL cntz = l-1; LL tempz = 0; if (cntz>0) { if (cntz==1) tempz++; else if (cntz==2) { if (cnt1[1]==3) tempz+=2; else tempz+=1; } else { while (cntz>=3) { rep1(i,1,num) if (cntz<=siz[i]) { if (cntz==siz[i]) { cntz=0; tempz+=cnt1[i]; break; } cntz-=siz[i-1]; tempz+=cnt1[i-1]; if (cntz>0) { cntz--; tempz+=(sz[i]&1); } break; } } if (cntz==1) tempz++; else if (cntz==2) { if (cnt1[1]==3) tempz+=2; else tempz+=1; } } } LL tot = cnt1[num]; LL ans = tot-tempz-tempy; cout << ans <<endl; return 0;}

上一篇：【C语言简单说】十七：数组（补）

下一篇：MFC下ODBC方式连接数据库