T1 T4 杀卵题不说。
做了 COCI 的原题。
T3 Rolete
为什么先说 T3 ，因为 T3 很简单。
首先先预处理出按 \(x\) 次按钮需要的时间。
根据直觉，我们观察到一个显然的贪心：如果在 \(x\) 按了 \(p_x\) 次，那么在 \(x-1\) 拉的次数 \(p_{x-1}\ge p_x\)。反证即可证明。
直接上决策单调性优化即可。
时间复杂度 \(O(n\log n)\) 。
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int n,t,s,k,m;
int q;
int a[N];
ll tim[N],sum[N*2],cnt[N*2];
ll res,cur;
ll ans[N];
void solve(int l,int r,int al,int ar)
{
if(l>r) return;
int mid=(l+r)/2,pos;
ll res=1e18;
for(int i=al;i<=ar;i++)
{
ll v=tim[i]+1ll*(sum[i+mid]-1ll*cnt[i+mid]*(i+mid))*t;
if(v<res) res=v,pos=i;
}
ans[mid]=res;
solve(l,mid-1,pos,ar);
solve(mid+1,r,al,pos);
}
int main()
{
scanf("%d%d%d%d",&n,&t,&s,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),m=max(m,a[i]),cnt[a[i]]++,sum[a[i]]+=a[i];
cur=cnt[0];
for(int i=1;i<=m;i++)
{
res+=1ll*cur*k+s;
cur+=cnt[i];
tim[i]=res;
}
for(int i=m;i>=0;i--) cnt[i]+=cnt[i+1],sum[i]+=sum[i+1];
solve(0,m,0,m);
scanf("%d",&q);
while(q--)
{
int x;
scanf("%d",&x);
printf("%lld ",ans[x]);
}
return 0;
}
T2 海盗
我们考虑每个区间对答案的贡献。
具体来说，对于区间 \([l,r]\)，我们先考虑区间 \([l,r]\) 独立成段的条件。我们发现 \([1,l-1]\) 需要刚好分割成完整的区间，\([r+1,n]\) 可以随便填。我们可以使用预处理一个 dp 算出长度为 \(L\) 时成一个完整区间的方案，对于 \([r+1,n]\)，方案数是 \(2^{n-r}\)。
由于要我们输出 \(n\) 以内的所有答案，所以我们考虑差分数组 \(d\)，具体的，如果是 \([l,r]\) 区间贡献 \(w\)，我们在 \(r\) 差分加上 \(w\)，之后处理完所有区间后，我们对差分数组进行前缀求和，具体的，\(d_i=d_{i-1}\times 2+d_i\)。
现在问题转化为考虑长度为 \(L\) 的区间贡献。
对于区间内每个数，我们考虑每个数对区间的贡献。