首页 > 其他分享 >[题解]SP10606 Balanced Numbers

[题解]SP10606 Balanced Numbers

时间:2024-04-13 22:35:50浏览次数:24  
标签:sta int 题解 30 pos vis Balanced 优化 SP10606

SP10606 Balanced Numbers

关于优化方式的说明详见数位dp例题及详解-下

SPOJ注册不上所以暂时无法提交w,但是3份代码与正解对拍没有问题。

使用\(vis[0\sim 9]\)表示\(0\sim 9\)的访问情况,\(sta[0\sim 9]\)表示\(0\sim 9\)填写个数的奇偶性(奇数为\(1\),偶数为\(0\))。暴搜先打出来,然后考虑怎么记忆化。我们发现如果两个状态(\(limit=false\))填写到同一位置\(pos\),而且\(vis\)和\(sta\)都相同,那么这两个状态答案相同。

所以用\(f[pos][vis][sta]\)来记忆化,空间\(20*1024*1024\),不会MLE(1.46G的内存)

注意到数据范围,可能需要开unsigned long long,注意这样\(f\)数组就不能初始化为\(-1\)了,可以再开一个bool类型的\(fv\)表示\(f\)的这个状态是否计算出答案了。

1.1 Code
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,l,r,a[30];
bitset<10> vis,sta;
bool fv[30][1024][1024];
int f[30][1024][1024];
int dfs(int pos,bool limit,bool zero){
	if(pos==0){
		for(int i=0;i<=9;i++) if(vis[i]&&sta[i]==i%2) return 0;
		return 1;
	}
	int numvis=vis.to_ullong(),numsta=sta.to_ullong();
	if(!limit&&!zero&&fv[pos][numvis][numsta])
		return f[pos][numvis][numsta];
	int rig=limit?a[pos]:9,ans=0;
	for(int i=0;i<=rig;i++){
		bool is=(zero&&i==0);
		bool tvis=vis[i],tsta=sta[i];
		if(!is) vis[i]=1,sta[i]=!sta[i];
		ans+=dfs(pos-1,limit&&i==rig,is);
		vis[i]=tvis,sta[i]=tsta;
	}
	if(!limit&&!zero) f[pos][numvis][numsta]=ans,fv[pos][numvis][numsta]=1;
	return ans;
}
int solve(int x){
	int len=0;
	while(x){
		a[++len]=x%10;
		x/=10;
	}
	return dfs(len,1,1);
}
signed main(){
	memset(fv,0,sizeof fv);
	cin>>t;
	while(t--){
		cin>>l>>r;
		cout<<solve(r)-solve(l-1)<<endl;
	}
	return 0;
}

空间优化

(第3种优化方式)

其实上面的就能过了,但是我们注意到还有优化空间。

上面的表示其实就是四进制,但是我们发现\(vis[i]=0,sta[i]=1\)的情况不存在,所以我们可以优化成三进制,状压一下就可以了。总空间\(20*(3^{10})=20*59049\)。

按道理说应该只是优化了空间而没有优化时间,因为上面所说的情况根本不会搜索到。

(但很奇怪的是这份代码跑得奇快,具体见下面的时间对比,如果大家有解答请在评论区告诉我,谢谢!)

1.2 空间优化Code
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,l,r,a[30];
int sta[10];
bool fv[30][59049];
int f[30][59049];
//0没访问,1访问奇数次,2访问偶数次,10位三进制
//优化掉了“没访问过,奇数次”的状态
int to_num(){
	int ans=0;
	for(int i=0;i<=9;i++) ans=ans*3+sta[i];
	return ans;
}
int dfs(int pos,bool limit,bool zero){
	if(pos==0){
		for(int i=0;i<=9;i++){
			if(sta[i]==0) continue;
			if(sta[i]-1!=i%2) return 0;
		}
		return 1;
	}
	int numsta=to_num();
	if(!limit&&!zero&&fv[pos][numsta])
		return f[pos][numsta];
	int rig=limit?a[pos]:9,ans=0;
	for(int i=0;i<=rig;i++){
		bool is=(zero&&i==0);
		int tsta=sta[i];
		if(!is) sta[i]=(sta[i]==0||sta[i]==2)?1:2;
		ans+=dfs(pos-1,limit&&i==rig,is);
		sta[i]=tsta;
	}
	if(!limit&&!zero) f[pos][numsta]=ans,fv[pos][numsta]=1;
	return ans;
}
int solve(int x){
	int len=0;
	while(x){
		a[++len]=x%10;
		x/=10;
	}
	return dfs(len,1,1);
}
signed main(){
	memset(fv,0,sizeof fv);
	cin>>t;
	while(t--){
		cin>>l>>r;
		cout<<solve(r)-solve(l-1)<<endl;
	}
	return 0;
}

究极时空优化

(第1种优化方式)

结论:只要vis奇数位上1的个数vis偶数位上1的个数sta奇数位上1的个数sta偶数位上1的个数都分别相等,两种状态答案就一样。所以可以直接使用\(f[pos][a][b][c][d]\)来记忆化,也可以直接压缩成\(f[pos][a]\)。空间\(20*(6^4)=20*1296\),时间也是。

为什么呢?如果你一共访问了\(n\)个奇数,其中有\(m(m\leq n)\)个奇数访问了奇数次。那么不用管具体这些奇数是几,因为结果中奇数互相换是不会影响的。比如\(331132377\)满足条件,那么我把\(1\)和\(7\)互换,或者把\(3\)都换成\(9\)……都不会影响结果。偶数同理。

1.3 究极时空优化Code
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,l,r,a[30];
bitset<10> vis,sta;
bool fv[30][1296];
int f[30][1296];
int dfs(int pos,bool limit,bool zero){
	if(pos==0){
		for(int i=0;i<=9;i++) if(vis[i]&&sta[i]==i%2) return 0;
		return 1;
	}
	int num=(vis[0]+vis[2]+vis[4]+vis[6]+vis[8]);
	num=num*6+(vis[1]+vis[3]+vis[5]+vis[7]+vis[9]);
	num=num*6+(sta[0]+sta[2]+sta[4]+sta[6]+sta[8]);
	num=num*6+(sta[1]+sta[3]+sta[5]+sta[7]+sta[9]);
	if(!limit&&!zero&&fv[pos][num])
		return f[pos][num];
	int rig=limit?a[pos]:9,ans=0;
	for(int i=0;i<=rig;i++){
		bool is=(zero&&i==0);
		bool tvis=vis[i],tsta=sta[i];
		if(!is) vis[i]=1,sta[i]=!sta[i];
		ans+=dfs(pos-1,limit&&i==rig,is);
		vis[i]=tvis,sta[i]=tsta;
	}
	if(!limit&&!zero){
		f[pos][num]=ans,fv[pos][num]=1;
	}
	return ans;
}
int solve(int x){
	int len=0;
	while(x){
		a[++len]=x%10;
		x/=10;
	}
	return dfs(len,1,1);
}
signed main(){
	memset(fv,0,sizeof fv);
	cin>>t;
	while(t--){
		cin>>l>>r;
		cout<<solve(r)-solve(l-1)<<endl;
	}
	return 0;
}

运行消耗对比

从上到下分别是洛谷题解排名第一、朴素算法、空间优化、究极时空优化的代码的运行消耗,每个样例测试点均在\(5\)个以内。所以可以看出,朴素算法即可通过此题,而优化后的代码,无论在时间还是空间方面,均比题解优。

标签:sta,int,题解,30,pos,vis,Balanced,优化,SP10606
From: https://www.cnblogs.com/Sinktank/p/18133481

相关文章

  • 第十五届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组题解
    试题A:握手问题本题总分:\(5\)分思路:组合计数,用为\(50\)个人握手的总方案数\(C^{2}_{50}\),减去七个人彼此没有握手握手的方案数\(C^{2}_{7}\)即为答案。A:握手问题#include<bits/stdc++.h>#defineintlonglong#definedblongdouble#defineall(f)f.begin()......
  • CF1923B Monsters Attack! 题解
    题目简述数轴上有$n$个怪兽。最初第$i$个怪兽在$x_i$位置上,且血量为$a_i$。你在位置$0$上。在每秒钟会发生:你给任意怪兽发射总共$k$颗子弹,受到攻击的怪兽血量减一。血量小于等于$0$的怪兽死亡。没有死亡的怪兽向你移动一个单位。当一个怪兽来到你的位置,你就输......
  • CF1165E Two Arrays and Sum of Functions 题解
    题目简述已知两个长度均为$n$的数组$a$和$b$。给定一个函数:$f(l,r)=\sum\limits_{l\lei\ler}a_i\cdotb_i$。你的任务是对数组$b$中的元素以任意的顺序重新排序,使$\sum\limits_{1\lel\ler\len}f(l,r)$的值最小。题目分析我们首先进行化简,发现题......
  • CF107A Dorm Water Supply 题解
    题目简述给出一个$n$个点,$m$条边的有向图,边带权。保证每个点的出度和入度最多为$1$。对于每一个入度为$0$,出度为$1$的点,我们在该点建一个水箱。对于每一个入度为$1$,出度为$0$的点,我们在该点建一个水龙头。可以发现,每一个水箱对应一个唯一的水龙头,我们将每对对应......
  • CF1942B Bessie and MEX 题解
    题目简述给定一个长度为$n$的数组$a$,让你构造一个等长的排列$p$,其中从$0$到$n-1$的每个整数恰好出现一次。满足对于每一个位置$a_i=\texttt{MEX}(p_1,p_2,\ldots,p_i)-p_i$,其中数组的$\texttt{MEX}$是不在该数组中出现的最小非负整数。题目分析我们发现正着做并......
  • CF244B Undoubtedly Lucky Numbers 题解
    题目简述给定一个$n$,问有多少个小于等于$n$的数只由两个不同的数字$x$和$y$组成。题目分析直接枚举肯定不行,我们考虑枚举$x$和$y$,再利用深搜,生成所有不大于$n$且只由$x$和$y$组成的数字,利用map去重,统计答案即可。代码#include<iostream>#include<map>usi......
  • 2023CCPC题解
    2023年第五届河南省CCPC大学生程序设计竞赛ProblemA.小水獭游河南#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){stringa;cin>>a;intst[27],ji=0;memset(st,0,sizeof(......
  • CF1946B Maximum Sum 题解
    题目简述你有一个由$n$个整数组成的数组$a$。你要对它进行$k$次操作。在一次操作中,你选择了数组$a$的任意连续子数组(可能为空),并在数组的任意位置插入了该子数组的和。你的任务是找出经过$k$次操作后数组的最大和。题目分析这道题显然是一道贪心题。对于第$1$次操......
  • 集合计数——题解
    题目这篇题解的背景。。。(可以跳过,与题目无关)说实话,有点恼,也觉得自己有点唐,在以为自己已经理解了变量意义的情况下(实际上并没有)去推了半天错式子,甚至我推出了他不对时还给自己否定了,昨天晚三还拉着\(9G\)与我一块推。。。,结果上午发觉好像意义理解错了。。。抽象,就当是一种......
  • CF416E 题解
    前置知识:floyd题意给定一个\(n\)个点\(m\)条边的无向简单图,对于每对\((s,t),1\les<t\len\),求出有多少条边被至少一个\(s\tot\)的路径经过。\(n\le500,m\le\frac{n(n-1)}{2}\)题解首先一个很一眼的做法先floyd一遍求出\(dis(i,j)\),接着枚举\((s,......