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;

}

AtCoder Beginner Contest 169 题解的相关教程结束。