梦熊 CSP—S模拟赛 T1 youyou的垃圾桶
原题链接
题目大意：
现在有
n
个敌人，第
i
个敌人的初始攻击力为正整数
a
i
。初始生命值
为正整数
W
。
定义如下流程为一场战斗：
从第
1
个敌人开始，每个敌人依次循环进行攻击。第
i
个敌人发起攻
击时，生命值
W
减去
a
i
，同时
a
i
翻倍。
当
W
≤
0
时，本场战斗立刻结束。然后重置生命值
W
以及所有敌人
的攻击力
a
i
。定义本次战斗的评分为接受敌人攻击的次数（不包括致
命攻击）。
q
次询问，每次询问给出三个数
l
,
r
,
d
，表示对第
[
l
,
r
]
个敌人进行强化，
使每个敌人的
a
i
增加
d
，然后立刻进行一场战斗。输出此次战斗的评
分。
询问之间相互影响。
解题思路：
那会在比赛的时候是没想出来的，暴力也没打，这道题感觉还行。
我们可以设所有垃圾桶当前攻击力总和为S。先考虑暴力做法，毕竟暴力出奇迹，因为当前生命值W≤10e18，攻击力是翻倍递增的，因此最多只会打log W轮。因此暴力的时间复杂度为O(nq logW) ，可以获得20pts。
接下来考虑正解。
假设这场战斗完整地打了
k
轮，那么这
k
轮需要消耗的生 命值为 S
×
(2
0
+ 2
1
+
· · ·
+ 2
k
−
1
) =
S
×
(2
k
−
1)
。 即要求出最大的 m
，使得
∑
m
i
=1
a
i
≤
W
−
S
×
(2
k
−
1)
。
答案即为 k
×
n
+
m
。显然，对于每一次修改，
S 只会增加 (
r
i
−
l
i + 1)
×
d
i。
对于每一个询问，我们需要求出最大的 k
。 发现 k
不需要每次都枚举，因为每次操作后，答案只会变小，也就是 k
是递减的。 对于相同的 k
递减。于是用指针维护
m
的值，同时用两个差分数组维护区间加即可。对于不同的 k
，暴力求解即可。
时间复杂度
O
(
n
log
W
+
q
)
。
正解代码如下：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
ll a[maxn];
namespace seg{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll sum[maxn << 2], tag[maxn << 2], len[maxn << 2];
void up(int x){
sum[x] = sum[l(x)] + sum[r(x)];
}
void down(int x){
tag[l(x)] += tag[x], sum[l(x)] += tag[x] * len[l(x)];
tag[r(x)] += tag[x], sum[r(x)] += tag[x] * len[r(x)];
tag[x] = 0;
}
void build(int x, int l, int r){
len[x] = r - l + 1;
if(l == r){
sum[x] = a[l];
return;
}
int mid = l + r >> 1;
build(l(x), l, mid), build(r(x), mid + 1, r);
up(x);
}
void update(int x, int l, int r, int ql, int qr, ll k){
if(ql <= l && r <= qr){
sum[x] += k * len[x], tag[x] += k;
return;
}
down(x);
int mid = l + r >> 1;
if(ql <= mid) update(l(x), l, mid, ql, qr, k);
if(qr > mid) update(r(x), mid + 1, r, ql, qr, k);
up(x);
}
ll query(int x, int l, int r, int ql, int qr){
if(ql <= l && r <= qr) return sum[x];
down(x);
int mid = l + r >> 1;
ll res = 0;
if(ql <= mid) res += query(l(x), l, mid, ql, qr);
if(qr > mid) res += query(r(x), mid + 1, r, ql, qr);
return res;
}
int query2(int x, int l, int r, ll k){
if(k == 0) return 0;
if(l == r) return l;
down(x);
int mid = l + r >> 1;
if(sum[l(x)] >= k) return query2(l(x), l, mid, k);
else return query2(r(x), mid + 1, r, k - sum[l(x)]);
}}
ll qpow(ll a, ll x){
ll res = 1;
while(x){
if(x & 1) res *= a;
a *= a;
x >>= 1;
}
return res;
}
int main(){
int n, q;
ll W;
scanf("%d %d %lld", &n, &q, &W);
for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
seg::build(1, 1, n);
while(q --){
int l, r;
ll d;
scanf("%d %d %lld", &l, &r, &d);
seg::update(1, 1, n, l, r, d);
ll sum = seg::query(1, 1, n, 1, n), rnd = logl(1.0 * W / sum + 1) / logl(2), po = qpow(2, rnd);
ll now = (po - 1) * sum;
ll rst = seg::query2(1, 1, n, (W - now - 1) / po + 1);
printf("%lld\n", rnd * n + rst - 1);
}
return 0;
}暴力代码（50pts）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
struct Tree {
int val, lz, l, r;
}tr[N];
int n, Q, a[N], w;
string A;
void build(int id, int l, int r) {
tr[id].l = l, tr[id].r = r, tr[id].lz = 0;
if (l == r) {
tr[id].val = a[l];
return ;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
tr[id].val = tr[id * 2].val + tr[id * 2 + 1].val;
}
void push_down(int id) {
tr[id * 2].lz += tr[id].lz;
tr[id * 2 + 1].lz += tr[id].lz;
tr[id * 2].val += (tr[id * 2].r - tr[id * 2].l + 1) * tr[id].lz;
tr[id * 2 + 1].val += (tr[id * 2 + 1].r - tr[id * 2 + 1].l + 1) * tr[id].lz;
tr[id].lz = 0;
}
void upd(int id, int l, int r, int k) {
if (l <= tr[id].l && tr[id].r <= r) {
tr[id].lz += k;
tr[id].val += (tr[id].r - tr[id].l + 1) * k;
return ;
}
push_down(id);
if (tr[id * 2].r >= l) upd(id * 2, l, r, k);
if (tr[id * 2 + 1].l <= r) upd(id * 2 + 1, l, r, k);
tr[id].val = tr[id * 2].val + tr[id * 2 + 1].val;
}
int sum(int id, int l, int r) {
if (l <= tr[id].l && tr[id].r <= r) {
return tr[id].val;
}
push_down(id);
int ans = 0;
if (tr[id * 2].r >= l) ans += sum(id * 2, l, r);
if (tr[id * 2 + 1].l <= r) ans += sum(id * 2 + 1, l, r);
return ans;
}
int solve(int x) {
int cnt = 0, y = x, kw = w;
int qwq = 0;
while (kw > 0) {
if (kw - y < 0) break;
kw -= y;
qwq += y;
y *= 2;
cnt++;
}
if (kw == 0) {
return cnt * n - 1;
}
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
int s = sum(1, 1, mid) * (1<<cnt);
if (s + qwq >= w) r = mid - 1;
else {
l = mid + 1;
ans = mid;
}
}
return ans + cnt * n;
}
signed main() {
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0) ;
cin >> n >> Q >> w;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
build(1, 1, n);
while (Q--) {
int l, r, d;
cin >> l >> r >> d;
upd(1, l, r, d);
cout << solve(sum(1, 1, n)) << '\n';
}
return 0;
}