CF1954E Chain Reaction
正在寫數(shù)論分塊，發(fā)現(xiàn)這道題竟然是向上取整的數(shù)論分塊，我直接就去寫了。
題意概括
有 \(n\) 個(gè)怪獸，對于一個(gè)傷害 \(k\)，每一次會(huì)對一段連續(xù)的存活的怪物打出 \(k\) 的傷害，對于一堆 \(k\) 求出每一個(gè) \(k\) 的最小攻擊次數(shù)。
我們先考慮一下對于一個(gè) \(k\) 而言，它的答案是什么。
可以算每一對相鄰的貢獻(xiàn)是多少，看得出來就是 \(max(0,ceil(\frac{a_i}{k})-ceil(\frac{a_{i-1}}{k}))\)。
整體就是 \(\sum_{i=1}^{n}max(0,ceil(\frac{a_i}{k})-ceil(\frac{a_{i-1}}{k}))\)
這個(gè)顯然是數(shù)論分塊可求的。
熱知識(shí)：對于 \(ceil(\frac{n}{l})\)，對應(yīng)的右端點(diǎn)是 \(floor(\frac{n-1}{floor(\frac{n-1}{l})})\)。
我們感覺會(huì)做了，但是我們發(fā)現(xiàn)似乎沒有什么好的辦法清空每一次，寫數(shù)據(jù)結(jié)構(gòu)太麻煩，而且這個(gè)題似乎卡常？反正多了一個(gè) log 是絕對不可能過的。
所以我們便采取新的策略，計(jì)算每一對相鄰的點(diǎn)對于所有 \(k\) 的貢獻(xiàn)。
我們使用差分，做數(shù)論分塊就行了。
注意這個(gè)題卡常，define int long long 會(huì) T。
代碼。
點(diǎn)擊查看代碼
#include <bits/stdc++.h>
using namespace std;
namespace BaiBaiShaFeng{
const int MN=3e5+315;
int n, a[MN], maxn=0;
long long d[MN];
void update(int l, int r, int val){
if(val<0) return;
d[l]+=val; d[r+1]-=val;
}
void solve(){
cin>>n; d[0]=1;
for(int i=1; i<=n; ++i) cin>>a[i];
for(int i=1; i<=n; ++i) maxn=max(maxn,a[i]);
for(int i=1; i<=n; ++i){
int vala=a[i], valb=a[i-1];
for(int l=1, r; l<=maxn; l=r+1){
int mra, mrb;
if(l>=vala) mra=maxn+1;
else mra=((vala-1)/((vala-1)/l));
if(l>=valb) mrb=maxn+1;
else mrb=((valb-1)/((valb-1)/l));
r=min(mra,mrb);
if(r==maxn+1) break;
update(l,r,(vala-1)/l-max((int)0,valb-1)/l);
}
}
for(int i=1; i<=maxn; ++i) d[i]+=d[i-1];
for(int i=1; i<=maxn; ++i) cout<<d[i]<<" ";
}
}
signed main(){
//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
BaiBaiShaFeng::solve();
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)