AtCoder Beginner Contest 169 题解
这场比赛比较简单，证明我没有咕咕咕的时候到了！
A - Multiplication 1
没什么好说的，直接读入两个数输出乘积就好了。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a*b;
return 0;
}
B - Multiplication 2
让你连乘，同时在答案过大（大于\(10^{18}\)）的时候输出-1。
你可以使用__int128_t。这是一种神奇的类型，可以用上足足128个位，绰绰有余。记得特判乘积是\(0\)的情况。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[100005];
__int128_t ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
ans=1;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]==0){
cout<<0<<endl;
return 0;
}
}
for(int i=0;i<n;i++){
ans*=a[i];
if(ans>1000000000000000000ll){
cout<<-1<<endl;
return 0;
}
}
cout<<(ll)ans<<endl;
return 0;
}
C - Multiplication 3
给你一个整数、一个固定位数的小数，让你计算他们的乘积并舍去小数点后的部分。
由于long long存得下，直接把\(B\)乘以\(100\)化为整数与\(A\)相乘，然后在输出前整除\(100\)即可。最初读入的小数要注意精度问题。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull a,b;
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>a>>s;
b=(s[0]-'0')*100+(s[2]-'0')*10+s[3]-'0';
cout<<a*b/100<<endl;
return 0;
}
D - Div Game
给你一个数\(N\)，每次让你把它除以一个质数的幂（指数为正整数）。最多可以除以多少个不同的数（操作之间互相影响）。
把\(N\)分解质因数，注意到不同的质因子之间操作是互不影响的。那么我们可以把操作归类到多个质数的幂上。
对于一个单独的质数的幂，显然除以这个质数的一次幂，二次幂，三次幂……这么操作下去是最优的，于是我们可以得到这样的程序：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
vector<pair<ll,int>> dvs;//dvs以配对<质数,幂次>的形式把N分解了质因数（其实质数本身不用存）
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
dvs.push_back(make_pair(i,0));
while(n%i==0){
dvs.back().second++;
n/=i;
}
}
}
if(n>1){
dvs.push_back(make_pair(n,1));
}//以上是分解质因数环节
int ans=0;
for(pair<ll,int> &p:dvs){
int i=1;
for(;(1+i)*i/2<=p.second;i++);
i--;//求出操作中最大的那一个数是质数的多少次幂，用到等差数列求和公式
ans+=i;
}
cout<<ans<<endl;
return 0;
}
E - Count Median
给你\(N\)个数，每个的范围在\(A_i\)到\(B_i\)之间。问你中位数有多少种取值可能。特别地，\(N\)为偶数时，中位数是中间两个数的平均数（可能有\(0.5\)的出现）。
容易证明，最小和最大的中位数中间的所有可能的中位数都是一定可以取到的。
现在我们只要求出最小和最大的中位数就好，这个可以贪心地取\(A_i\)或\(B_i\)做到。
程序中使用了一些位运算，可以参考下列文章：
基本位运算芝士：https://blog.csdn.net/jason314/article/details/5719933
运算符的优先级：https://blog.csdn.net/nicky_zs/article/details/4053146
#include<bits/stdc++.h>
using namespace std;
int n,a[200005],b[200005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
if(n&1){//n为奇数时
cout<<b[n+1>>1]-a[n+1>>1]+1<<endl;//最后的+1是为了把答案从左闭右开或左开右闭区间转换为闭区间
}else{//n为偶数时
cout<<b[n>>1]+b[(n>>1)+1]-a[n>>1]-a[(n>>1)+1]+1<<endl;//这里除了最后的+1，前面的被我乘以2计算了，方便写代码
}
return 0;
}
F - Knapsack for All Subsets
能做到F的应该不需要听题意了吧。你个懒猪！写题解还这么懒就给我去**啦！哼！
我们可能会走入一种误区，就是求出集合内元素恰好和是\(S\)的这些集合，然后再去求包含它的这些集合的个数，然而是错的。（也可能是我没有想到，至少它没那么好写（逃））
假如直接按照题目的意思去考虑，可以想到一种很方便的DP方式，那就是dp[i][j]表示大小小于等于i，有至少一个子集的元素和为\(j\)的集合个数。
这样，加入\(A\)中元素的顺序就和这个DP状态无关了，我们可以先把\(i\)的顺序确定下来：从\(1\)到\(N\)遍历数组\(A\)。\(j\)更简单，从小到大枚举即可。
那么转移方程怎么得到呢？首先，对应第\(i\)位的元素\(A_i\)在“元素和为\(j\)的子集”中选不选，都可以加上第一维减一的状态的答案。（假如之前就有一种子集和为\(j\)的选法，那么这个元素对于选法的贡献就不重要了）
然后，假如选了这个元素进“元素和为\(j\)的子集”，就又要加上第一维减一，第二位减去\(A_i\)的状态的答案。方程就可以得到了：
\[dp_{i,j} = dp_{i-1,j} \times 2 + dp_{i-1,j-a_i} \]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,s,a[3005];
ll dp[3005][3005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>s;
dp[0][0]=1;
for(int i=1;i<=n;i++){
cin>>a[i];
for(int j=0;j<=s;j++){
dp[i][j]=dp[i-1][j]*2%mod;
if(j>=a[i])dp[i][j]=(dp[i][j]+dp[i-1][j-a[i]])%mod;
}
}
cout<<dp[n][s]<<endl;
return 0;
}