首页 > 其他分享 >B. 【20省选十联测day2】bitrev

B. 【20省选十联测day2】bitrev

时间:2024-09-12 22:17:08浏览次数:9  
标签:右边 左边 rep day2 j1 枚举 bitrev 省选十 进位

B. 【20省选十联测day2】bitrev

求 \(\sum_{i-1}^R popcount(i+g(i))\),其中 \(g(i)\) 表示把 \(i\) 的二进制(不含前导 \(0\))reverse 得到的数。

\(R\le 10^{14}\)。

显然这种东西我们会想到数位 DP。于是正解是一个很恶心的数位 DP。

首先我们要按枚举有效位数 \(x\),显然 \(x=1\) 时 \(ans=1\),因为此时只有 \(1+g(1)=2,popcount(2)=1\)。当 \(x>1\),我们发现往其中一边填一个数字是不好处理的,因为你填了 \(mid-1\) 的位置,已填的数字翻转后,\(mid+1,g_{mid-1}\) 都还没有确定,你无法计算 \(i+g(i)\) 的和的 \(popcount\)。因此我们考虑两边同时填,即一次填两位。

如果我们这样从中间往外填,就会发现不好处理上界问题。如果 \(x<len\) 显然有前导 \(0\),肯定到不了上界,此时不用管上界问题。但是 \(x=len\) 时,你无法保证填出来的数字不超过上界。

处理上界一般是从高至低位枚举。于是我们考虑从外面往里面枚举。记录答案(1 的个数的和),以及出现一个新的 \(1\) 是更新答案要用的填写的方案数。

思考我们计算答案还需要什么信息。我们枚举目前这一层两个位置填写什么数字,然后我们需要知道他们加起来以及加上其他地方来的进位后有没有进位,所以我们还需要对两个位置分别记录它有没有从低一位获得进位,以及它有没有向高一位进位(但是因为你已经枚举了这个位置填写什么和上一层有没有(被)进位,所以其实你只需要记录左边的位置是否被进位(因为这个你是无法确定的,只能枚举)(因为如果左边的左边被进位,则左边的位置一定进位,所以你不需要记录左边的位置是否进位的状态,枚举上一层的状态即可)以及右边的位置是否进位(因为如果右边的右边进位,则右边的位置一定被进位,所以你不需要记录右边的位置是否被进位,枚举上一层的状态即可))。然后枚举填写的数字时,我们还需要知道左边已填的数字是否达到上界。统计答案时,我们还需要知道如果左半边达到了上界,右半边是否超过上界。这样 DP 的雏形就出来了(好复杂我太菜了)。

然后统计答案时分 \(x\) 的奇偶性讨论。如果 \(x\) 为偶数,那简单,只要左边不触碰上界或者左边和右边都不超过上界就行,然后如果右边有进位的贡献,左边的状态就是获得了进位。

对于 \(x\) 为奇数的情况,我们枚举中间点 \(mid\) 填什么,枚举左右两边的状态,计算加起来后 \(mid\) 这一位会不会有新的 \(1\) 出现,大概就这样。

时间复杂度 \(O(\log V)\) 乘上若干个 \(2\)。因为 \(\log\) 足够小,所以 \(2\) 可以随便乘。

超级详细的代码

进位 指这一位向高一位进位,被进位 指低一位向这一位进位。

下标均从 \(1\) 开始。

#include<bits/stdc++.h>
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=70;
ll f[N][2][2][2][2][2];
//位数(从外往里)、左边是否到达上限、右边是否超过上限、左边被进位、右边进位、记录的是方案数或和
ll n;
int len;
ll ans; 
int a[N];
void solve(int x){
	if(x==1) {
		ans++;
		return ;
	}//当只有1位有效,只有i=1有贡献,贡献为1
	memset(f,0,sizeof(f));
	//初始条件,初始第0层两个位置都填0
	f[0][x<len][1][0][0][0]=1;// 左边只要有前导0就一定不顶上界(否则第0高位填了0,顶了上界)、右边没有超出上界(第0低位填0,并没有超出上界)、左边没有被进位、右边没有进位(显然0+0没有进位)的方案数
	f[0][x<len][1][1][0][0]=1;//左边被进位也是有可能的,因为我们无法确定,所以这种情况也有一种填数字方案,即第0层两个位置都填0
	f[0][x<len][1][1][0][1]=1;//如果左边被进位,那么加起来就会有1个1了
	rep(i,1,x/2)//枚举,从两边的层到中间 
		rep(j1,0,1)//上一层左边有没有顶上界
			rep(j2,0,1)//上一层右边有没有超出上界
				for(int k1=i==1;k1<=1;k1++){//左边的位置填什么 
					if(!j1&&k1>a[x-i+1]) continue;//已填的左边顶了上界而且这一层左边超出上界
					rep(k2,0,1)//右边的位置填什么
						rep(l1,0,1)//左边有没有被进位 
							rep(l2,0,1) {//右边有没有被进位 
								int u1=j1|(k1<a[x-i+1]),u2=(k2<a[i])|(k2==a[i]&&j2);//这一层左边、右边限制
								int v2=l2+k1+k2,v1=k1+k2+l1; //右边的和,左边的和(可以由此算出左、右边有没有进位) 
								f[i][u1][u2][l1][v2>1][0]+=f[i-1][j1][j2][v1>1][l2][0];
								f[i][u1][u2][l1][v2>1][1]+=f[i-1][j1][j2][v1>1][l2][1]+f[i-1][j1][j2][v1>1][l2][0]*((v1&1)+(v2&1)); 
							}
				} 
	if(x&1){//中间还有一个没有考虑的位置 
		rep(j1,0,1)//左边有没有限顶上界
			rep(j2,0,1) //右边有没有限制(右边有限制表示右边填的东西超过了上限) 
				rep(k,0,1)//中间填什么
					rep(l,0,1){//右边有没有进位 
						int u1=j1,//左边限制
						u2=(k<a[x/2+1])|(k==a[x/2+1]&&j2);//右边限制
						int y=k*2+l;//中间的和 
						if(u1|u2) ans+=f[x/2][j1][j2][y>1][l][1]+f[x/2][j1][j2][y>1][l][0]*(y&1); 
						//左边、右边有一个没有限制,说明数字小于等于上界 
					} 
	}else{
		rep(j1,0,1)//左边限制 
			rep(j2,0,1)//右边限制
				if(j1|j2) //左边右边有一个没有限制 
					rep(k,0,1)//右边有没有进位及左边有没有被进位(显然右边进位了左边也就进位了)
						ans+=f[x/2][j1][j2][k][k][1]; 
	}
}
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("my.out","w",stdout);
	#endif
	sf("%lld",&n);
	while(n) a[++len]=n&1,n>>=1;
	for(int i=1;i<=len;i++){
		solve(i);//几位有效 
	}
	pf("%lld\n",ans);
}

标签:右边,左边,rep,day2,j1,枚举,bitrev,省选十,进位
From: https://www.cnblogs.com/liyixin0514/p/18411196

相关文章

  • NOIP2024集训Day27 DP常见模型4 - 树形
    NOIP2024集训Day27DP常见模型4-树形E.[COCI2014-2015#1]Kamp首先只考虑一个点,发现如果回到原来位置是比较好搞的,就每次走完子树的里面要的就上来,如果子树里面没有要走的就不走。(大概是\(f_x=\sumf_y+2\cdote_x\),因为要走过去走回来,注意\(y\)要保证子树里面有人)......
  • 【题解】Solution Set - NOIP2024集训Day27 树形 dp
    【题解】SolutionSet-NOIP2024集训Day27树形dphttps://www.becoder.com.cn/contest/5521「HDU4661」MessagePassing「BZOJ3935」Rbtree「ARC101E」RibbonsonTree「AGC034E」CompleteCompress「COCI2014.10」Kamp「SCOI2015」小凸玩密室「AGC008F」Black......
  • 贪心算法day28|买卖股票的最佳时机、55. 跳跃游戏、1005. K 次取反后最大化的数组和
    贪心算法day28|买卖股票的最佳时机、55.跳跃游戏、1005.K次取反后最大化的数组和122.买卖股票的最佳时机II55.跳跃游戏1005.K次取反后最大化的数组和122.买卖股票的最佳时机II给你一个整数数组prices,其中prices[i]表示某支股票第i天的价格。在每一......
  • 【转载】mx noip day2 sol
    T1捏捏这个题才是签到题。右边为逆序对总数。为左边的值找一个具体意义,我们将证明这个值不大于等号右边的值。考虑冒泡排序,右边即冒泡排序交换的次数(每交换一次一定减少一个逆序对)。左边一定不大于冒泡排序交换次数,因为左边的值只考虑了复原需要向左移动的数,而未考虑向右移动......
  • 练习 day2
    name=input('输入姓名')ifname=='kk':print('hellokk')ifname=='k':print('hik')name=input('输入姓名')ifname=='kk':print('hellokk')else:print('fxxk')gif......
  • GZOI2024 Day2 T2 乒乓球
    GZOI2024Day2T2【乒乓球】学习了蔡队的题解。\(P,Q\le10^{14}\)。Alice一定是赢了\(Y\)场比赛,每场比赛\(X\)局表示胜利,设Bob赢了\(Z\)场比赛。那么每场比赛赢了的人一定赢了\(X\)局,输了的人一定赢了\(<X\)局。有:\(Z<Y\)\(XY\leP\leXY+Z(X-1)\)\(ZX\le......
  • 【题解】Solution Set - NOIP2024集训Day25 概率期望 dp
    【题解】SolutionSet-NOIP2024集训Day25概率期望dphttps://www.becoder.com.cn/contest/5515「QOJ2606」Gachapon\(f_{i,j}\):用一次合法的level-irolling能够抽到的\(j\)的期望个数。\(h_{i,j,k}\):在\(i\)次操作之内,抽到恰好\(k\)个\(j\)的概率。\[h_{i,j,k......
  • day21
    非递减子序列classSolution{public:voidbacktracking(vector&nums,intstart){if(path.size()>1){ret.push_back(path);}if(start==nums.size()){return;}unordered_setuset;for(inti=start;i<nums.size();++i){if((!path.empty()&......
  • day20打卡
    复原IP地址classSolution{public:boolisValid(strings,intstart,intend){if(start>end){returnfalse;}if(s[start]=='0'&&start!=end){//0开头的数字不合法returnfalse;}intnum=0;for(inti=start;i<=end;i++){i......
  • DAY20240908 VUE:一文带你了解Vue Router中的声明式导航
    VUE:声明式导航一、链接跳转方式-------声明式导航的引入二、声明式导航三、官方文档四、引入一、链接跳转方式-------声明式导航的引入链接跳转可以用location.href跳----编程式跳转js的跳转方式链接跳转可以用超链接跳声明式跳转端口号域名都可以省略。3-13......