Atcoder Beginner Contest 169 题解

比赛链接：Atcoder Beginner Contest 169，被B和C的精度搞得惨不忍睹，最后没时间想E和F了。。。

A. 大水题

B. Multiplication 2

给出一个序列，求这些值练成的结果，如果结果大于$10^{18}$，输出-1

发现是会爆long long的，所以__int128一发水过

C. Multiplication 3

求整数A乘以小数点后有两位的浮点数B的结果，结果去掉小数部分

发现double的精度不够，所以long double一发水过

D. Div Game

问能将一个数N拆分成多少个质数的幂次的乘积，这些质数的幂次都互不相同

简单数论，直接分解质因数，然后对于N的一个质因数p，假设它的幂次为$p^e$，则表示成$p^1\cdot p^2\cdot p^3 … p^x$，且$\sum_{i=1}^{x}i\le e$，是能将p分解成最多个不同幂次的方案，暴力一下就行了

ll n,cnt,ans;
pair<ll,int> yin[maxn];
int main(){
	read(n);
	for(ll i=2;i*i<=n;i++){
		if(n%i==0){
			yin[++cnt].first=i;
			while(n%i==0) n/=i,yin[cnt].second++;
		}
	}
	if(n!=1) yin[++cnt].first=n,yin[cnt].second++;
	for(int i=1;i<=cnt;i++){
		int dd=1;
		for(int j=1;j<=yin[i].second;j+=++dd){
			ans++;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

E. Count Median

给出n个闭区间，每个区间为$[A_i,B_i]$，问从这些区间里选n个数，这n个数的中位数有多少种不同的取值？

结论：设$A_i$的中位数为$x$，$B_i$的中位数为$y$，则当$n$为奇数时，答案为$y-x+1$，当$n$为偶数时，答案为$2y-2x+1$

int n;
ll a[maxn],b[maxn],zuo,you,sum[maxn];
int main(){
	read(n);
	rep(i,1,n){
		read(a[i]),read(b[i]);
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	if(n&1) printf("%lld\n",b[n/2+1]-a[n/2+1]+1);
	else printf("%lld\n",(b[n/2]+b[n/2+1])-(a[n/2]+a[n/2+1])+1);
	return 0;
}

F. Knapsack for All Subsets

题意：

题解：后来看别人题解才明白，这是一道典型的背包题，可以定义状态$dp[i][j]$：前$i$个数子集至少有一个为$j$的方案数，则对于转移来说，考虑第$i$个数，有两种决策，取或不取：

不取：$dp[i][j]+=dp[i-1][j]$

取：$dp[i][j]+=dp[i-1][j]+((j>=a[i])?dp[i-1][j-a[i]]:0)$

化简得到：

$dp[i][j]+=2\cdot d[i-1][j]+((j>=a[i])?dp[i-1][j-a[i]]:0)$

初始化：$dp[0][0]=1$，答案为：$dp[n][s]$

int n,s,a[maxn];
ll dp[3005][3005];
int main(){
	read(n),read(s);
	rep(i,1,n) read(a[i]);
	dp[0][0]=1;
	rep(i,1,n){
		rep(j,0,s){
			dp[i][j]=(dp[i][j]+dp[i-1][j]*2+((j>=a[i])?dp[i-1][j-a[i]]:0))%mod;
		}
	}
	printf("%lld\n",dp[n][s]%mod);
	return 0;
}