目錄
- AtCoder Beginner Contest 153 題解
- A - Serval vs Monster
- 題意
- 做法
- 程式
- B - Common Raccoon vs Monster
- 題意
- 做法
- 程式
- C - Fennec vs Monster
- 做法
- 程式
- D - Caracal vs Monster
- 做法
- 程式
- E - Crested Ibis vs Monster
- 做法
- 程式
- F - Silver Fox vs Monster
- 做法
- 程式
- 感謝
- A - Serval vs Monster
AtCoder Beginner Contest 153 題解
這次的AtCoder明顯變水了居然我都能AK，題目質量有所下降，好多板子啊（逃
今年的第一篇博客，要是肺炎來了怕不是就是最后一篇力（呸呸呸），
A - Serval vs Monster
題意
給你\(H\)和\(A\)，問你多少個\(A\)比\(H\)大，
做法
輸出\(\lceil \frac H A \rceil\)即可，可以轉化為\(\lfloor \frac {H+A-1} A \rfloor\)，此處\(\lceil a \rceil\)和\(\lfloor a \rfloor\)分別代表對\(a\)上取整和下取整，
程式
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h,a;
cin>>h>>a;
cout<<(h+a-1)/a<<endl;
return 0;
}
B - Common Raccoon vs Monster
題意
給你\(H\)和\(N\)，\(N\)個陣列成的陣列\(A\)，問你陣列里的數都減一次能不能把\(H\)減到\(0\)及以下，
做法
判斷陣列所有元素的和是否大于等于\(H\)即可，
程式
#include<bits/stdc++.h>
using namespace std;
int h,n;
int a[100005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>h>>n;
for(int i=0;i<n;i++){
cin>>a[i];
h-=a[i];
}
if(h>0){
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
}
return 0;
}
C - Fennec vs Monster
從C開始不解釋題目意思了，大家肯定都看得懂（就是我懶），
做法
貪心地找出HP最大的\(K\)個怪物先用技能打死，之后的只能平A了，
程式
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
int h[200005];
ll ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++)cin>>h[i];
sort(h,h+n);
for(int i=0;i<n-k;i++){
ans+=h[i];
}
cout<<ans<<endl;
return 0;
}
D - Caracal vs Monster
做法
定義一個操作是對場上當前的所有怪物都攻擊一次，這樣場上的怪物一直都是相同的血量，例如：
- 開始有\(1\)只HP為\(4\)的怪物
- 攻擊\(1\)次后有\(2\)只HP為\(2\)的怪物
- 攻擊\(2\)次后有\(4\)只HP為\(1\)的怪物
- 攻擊\(4\)次后所有怪物死亡
總共\(7\)次攻擊，
為什么呢？方便計算啊，只要記錄場上怪物的HP和總數就好了，
之后做法顯然
程式
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll h,cnt,ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>h;
cnt=1;
while(h){
ans+=cnt;
h>>=1;
cnt<<=1;
//>>和<<不是cincout運算子，是位運算的右移和左移，可自行查閱檔案了解
//也可替換成：
//h/=2;
//cnt*=2;
}
cout<<ans<<endl;
return 0;
}
E - Crested Ibis vs Monster
做法
背包板子啊，AtCoder你變力，
直接DP上，定義dp[i][j]為計算完前i個咒語造成了j點傷害最少使用的MP量，那么狀態轉移方程是顯然的：
好了，問題解決了，邊界條件詳見程式，
程式
#include<bits/stdc++.h>
using namespace std;
int h,n;
int a[1005],b[1005];
int dp[1005][20005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>h>>n;
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
for(int j=0;j<=h+10000;j++){//由于可能傷害不是正好殺死，一定要預留一點傷害的量
if(j+a[i]<=h+10000)dp[i][j+a[i]]=min(dp[i][j+a[i]],dp[i][j]+b[i]);
dp[i+1][j]=min(dp[i+1][j],dp[i][j]);//此處為計算方便我正著dp了
}
}
int ans=0x3f3f3f3f;
for(int i=h;i<=h+10000;i++){
ans=min(ans,dp[n][i]);
}
cout<<ans<<endl;
return 0;
}
F - Silver Fox vs Monster
做法
首先，正常人都會選擇把這些怪物們按坐標排個序，
然后，我們可以看出，對于每一個怪物\(A\)，我們都可以找到一個它右邊的怪物\(B\)，\(A\)和\(B\)可以被同一個炸彈炸到，但\(B\)右邊的怪物不可以，這個可以用two pointers（中文是尺取法來著？）在\(O(N)\)時間里計算，可以看這篇博客了解，
我們就從左到右地回圈怪物\(A\)，每一次都炸很多次把它炸死，可以證明，此時炸彈位置在波及到\(A\)的情況下，越向右放越好，也就是波及了\(A\)到\(B\)的所有怪物，這個用線段樹維護每個怪物的血量就好了，又是板子，AtCoder出題人偷懶（
程式
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,d,a,sz;
ll data[800005];
ll lazy[800005];
pair<int,int> mon[200005];
void build(int bk,int l,int r){
if(l==r){
if(l<=n){
data[bk]=mon[l].second;
}
return;
}
build(bk<<1,l,(l+r)>>1);
build(bk<<1|1,((l+r)>>1)+1,r);
data[bk]=data[bk<<1]+data[bk<<1|1];
}
void upd(int bk,int l,int r,int ql,int qr,ll val){
if(qr<l||r<ql)return;
if(ql<=l&&r<=qr){
lazy[bk]+=val;
data[bk]+=val*(r-l+1);
return;
}
lazy[bk<<1]+=lazy[bk];
data[bk<<1]+=lazy[bk]*((r-l+1)>>1);
lazy[bk<<1|1]+=lazy[bk];
data[bk<<1|1]+=lazy[bk]*((r-l+1)>>1);
lazy[bk]=0;
upd(bk<<1,l,(l+r)>>1,ql,qr,val);
upd(bk<<1|1,((l+r)>>1)+1,r,ql,qr,val);
data[bk]=data[bk<<1]+data[bk<<1|1];
}
ll qry(int bk,int l,int r,int ql,int qr){
if(qr<l||r<ql)return 0;
if(ql<=l&&r<=qr){
return data[bk];
}
lazy[bk<<1]+=lazy[bk];
data[bk<<1]+=lazy[bk]*((r-l+1)>>1);
lazy[bk<<1|1]+=lazy[bk];
data[bk<<1|1]+=lazy[bk]*((r-l+1)>>1);
lazy[bk]=0;
return qry(bk<<1,l,(l+r)>>1,ql,qr)+qry(bk<<1|1,((l+r)>>1)+1,r,ql,qr);
}
ll ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>d>>a;
sz=1;while(sz<n)sz<<=1;
for(int i=1;i<=n;i++){
cin>>mon[i].first>>mon[i].second;
}
sort(mon+1,mon+1+n);//讀入，對怪物排序
build(1,1,sz);//建立線段樹
int l=1,r=1;
while(l<=n){
while(mon[r+1].first-mon[l].first<=d+d&&r<n){
r++;
}//尺取法
ll lft=qry(1,1,sz,l,l);//cerr<<lft<<endl;
if(lft<=0){//如果怪物死了就不計算了，我還因為這個wa了一次qaq
l++;
continue;
}
ll tms=(lft+a-1)/a;//殺掉這個怪物需要多少炸彈
ans+=tms;
upd(1,1,sz,l,r,(-tms)*a);//我也不知道為什么要加上括號qaq
l++;
}
cout<<ans<<endl;
return 0;
}
感謝
感謝閱讀，我寫得很爛您還讀完了，太感謝了qaq
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/100432.html
標籤：其他
上一篇：PAT乙級1021
下一篇：240. 食物鏈（并查集+數論）