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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47524.html
標籤：其他
下一篇：一道偶然邂逅的動規引發的首篇隨筆