![[Acwing] 第 19 场周赛](http://www.mshxw.com/aiimages/31/879876.png "[Acwing] 第 19 场周赛")
传送门 :
3992. 树上有猴
t
a
g
:
tag :
tag: 合法问题 有效区间 数学分析
题意 :
给定一个
a
[
]
a[]
a[],对于
a
[
i
]
a[i]
a[i]表示使得当前的
c
n
t
+
a
[
i
]
cnt+a[i]
cnt+a[i],询问有多少个合法的
c
n
t
cnt
cnt
其中各个期间的
c
n
t
cnt
cnt需要满足
m
≥
c
n
t
≥
0
m ge cnt ge 0
m≥cnt≥0
思路 :
首先因为每个状态都是独立的,因此我们可用对
a
[
i
]
a[i]
a[i]求前缀和
s
[
i
]
s[i]
s[i],表示当前这个时间段和初始相差的数量
则我们可用设一开始的数量为 x x x
0 ≤ x ≤ w 0 ≤ x + s 1 ≤ w 0 ≤ x + s 2 ≤ w . . . . . begin{aligned} & 0 le x le w\ & 0 le x+s_1 le w\ & 0 le x+s_2 le w\ &..... end{aligned} 0≤x≤w0≤x+s1≤w0≤x+s2≤w.....
化简式子我们我们可用得
0 ≤ x ≤ w − s 1 ≤ x ≤ w − s 2 ≤ x + ≤ w . . . . . begin{aligned} & 0 le x le w\ & -s_1 le x le w\ & -s_2 le x+ le w\ &..... end{aligned} 0≤x≤w−s1≤x≤w−s2≤x+≤w.....
因此我们只需要找到所有区间的交集即可,即使得左边最大右边最小
Code :
int a[N],sum[N];
int n,m;
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],sum[i] = sum[i-1] + a[i];
int maxn = m ;
int minn = 0;
for(int i=1;i<=n;i++){
maxn = min(maxn, m - sum[i]);
minn = max(minn, -sum[i]);
}
cout<
3993. 石子游戏
t
a
g
:
tag:
tag:值域 枚举 前缀和优化
题意 :
给定一个数组
a
[
]
a[]
a[],询问最小的操作次数使得所有元素相同
操作定义如下 :
- 每次选取一个
h
h
h为上限
- 将所有
a
[
i
]
>
k
a[i]>k
a[i]>k的部分全部取出
每次操作取出的总和不得超过
k
k
k
思路 :
首先一个非常暴力的解法是
每次从大往小的取
h
h
h,尽可能的取
h
h
h使得
s
u
m
sum
sum每次减小的最大
但是如何判断这个
h
h
h呢 ?
n
2
n^2
n2的判断必然超时
因为对于
a
[
i
]
≤
2
×
1
0
5
a[i]le2×10^5
a[i]≤2×105我们可用对
a
[
i
]
a[i]
a[i]进行前缀和操作
前缀和
s
u
m
[
i
]
sum[i]
sum[i]表示高度小于等于
i
i
i 的
a
[
i
]
a[i]
a[i]的总个数
因此我们就可用每次记录一下
t
o
t
a
l
+
=
s
u
m
[
m
a
x
n
]
−
s
u
m
[
j
−
1
]
total +=sum[maxn]-sum[j-1]
total+=sum[maxn]−sum[j−1]
每次减去尽可能多的值即可
Code :
int sum[N];
int n,m;
void solve(){
cin>>n>>m;
int minn = INF , maxn = 0 ;
for(int i=1;i<=n;i++){
int x;cin>>x;sum[x]++;
//对区间按高度进行分类
minn = min(minn,x);
maxn = max(maxn,x);
}
for(int i=1;i<=maxn; i ++) sum[i] +=sum[i-1];
//前缀和
int res = 0 ;
for(int i= maxn ; i > minn;){
int j = i , total = 0 ;
while(j > minn && total + sum[maxn] - sum[j-1] <= m){
total += sum[maxn] - sum[j-1];
j -- ;
}
++res;
i = j ;
}
cout< 
