A. Recycling Center#
- 将所有袋子按重量升序排序。
- 第 i 小的袋子在被销毁前会被乘 $2^{i-1}$。其判定是否大于 c 只取决于原始重量是否大于 $\frac{c}{2^{i-1}}$。
- 从最轻到最重遍历，若当前袋子经过倍增仍大于 c，则答案 +1。
ac code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| LL n, c;
void solve() {
cin >> n >> c;
vector<LL> a(n);
for(auto& x : a) cin >> x;
vector<int> d;
for(auto x : a){
if(x > c){
d.push_back(-1);
continue;
}
LL k = 0;
while((x << 1) <= c) x <<= 1, ++ k;
d.push_back(k);
}
sort(d.begin(), d.end());
int t = 0, ans = 0;
for(int v : d){
if(v >= t) ++ t;
else ++ ans;
}
cout << ans << '\n';
}
|
B. Deque Process#
贪心 + 小范围前瞻
限制只作用于 连续 $5$ 个元素，因此只需关注最新选出的 $4$ 个元素与下一次即将放入的元素之间的关系。核心贪心思想是：
维护当前已选序列的后缀长度 $\le 4$，保证它不是严格单调。
当后缀已经不是单调时，两端任意一值都不会形成坏序列，可以任选其一。
当后缀正好严格递增/递减时，只要下一元素打断这一趋势即可；至少有一端一定能做到这一点。
为了避免走进死胡同（当前合法，但未来无法继续），再做一步前瞻检查：假设本次取值为 $v_1$，看剩余两端的任意下一取值 $v_2$ 是否仍可避免生成坏序列。如果存在可行，则立即确定本次选择。
ac code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| vector<int> p, q;
int n;
bool check1(int v)
{
int m = q.size();
if(m < 4) return 0;
int a = q[m - 4], b = q[m - 3],
c = q[m - 2], d = q[m - 1];
if(a < b && b < c && c < d && d < v) return 1;
if(a > b && b > c && c > d && d > v) return 1;
return 0;
}
bool check2(int v1, int v2)
{
int m = q.size();
if(m < 3) return 0;
int a = q[m - 3], b = q[m - 2], c = q[m - 1];
if(a < b && b < c && c < v1 && v1 < v2) return 1;
if(a > b && b > c && c > v1 && v1 > v2) return 1;
return 0;
}
char foo(int l, int r)
{
for(char f : {'L', 'R'}){
int v1 = (f == 'L') ? p[l] : p[r];
if(check1(v1)) continue;
int nl = l + (f == 'L');
int nr = r - (f == 'R');
if(nl > nr) return f;
int vL = p[nl], vR = p[nr];
if(!check2(v1, vL) || !check2(v1, vR)) return f;
}
return 'L';
}
void solve()
{
p.clear(), q.clear();
cin >> n;
p.resize(n);
for(int& i : p) cin >> i;
int l = 0, r = n - 1;
string s;
while(l <= r){
char c = foo(l, r);
if(c == 'L') q.push_back(p[l]), ++ l;
else q.push_back(p[r]), -- r;
s.push_back(c);
}
cout << s << '\n';
}
|
C. Leftmost Below#
题目重述#
初始时有长度为 $n$ 的数组 $a=[0,0,\dots,0]$。一次操作如下：
- 任选整数 $x$，要求 $x>\min(a)$。
- 设 $i$ 为最小的下标，使得 $a_i<x$ 并且 $a_j\ge x;(1 \le j<i)$。
- $a_i = a_i + x$ 。
操作次数不限，问能否把 $a$ 变成给定目标数组 $b=[b_1,\dots,b_n]$。
设当前已确定前 $k$ 个位置的最终值，记
$$
m=\min_{1\le j\le k}b_j .
$$
当把 $a_{k+1}$ 加到 $b_{k+1}$ ，增量记为 $x$。
由题可知
- $a_{k+1}^{\text{旧}}<x\le m$（因为 $x$ 不会作用到已完成的前缀，且 $m$ 是它们的最小值）；
- $b_{k+1}=a_{k+1}^{\text{旧}}+x<2x$。
因此
$$
b_{k+1}\le 2x-1\le 2m-1 .
$$
即有目标数组可达，当且仅当
$$
\boxed{b_i\le 2\cdot\min_{1\le j<i}b_j-1\quad(\forall, i\ge 2)}.
$$
ac code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int n;
void solve()
{
cin >> n;
vector<LL> b(n);
for(auto& x : b) cin >> x;
LL mi = b[0];
for(int i = 1; i < n; i ++){
if(b[i] > (mi << 1) - 1){
cout << "NO\n";
return ;
}
mi = min(mi, b[i]);
}
cout << "YES\n";
}
|
D. Sum of LDS#
题目重述#
给定排列 $p_1,\dots ,p_n$，满足
$$
\max(p_i,,p_{i+1}) > p_{i+2}\qquad(1\le i\le n-2).
$$
对每个区间 $[l,r]$ 记
$$
f(l,r)=\text{区间 }p_l,\dots ,p_r\text{ 的LDS长度},
$$
求
$$
\mathrm{Ans}=\sum_{1\le l\le r\le n} f(l,r).
$$
自右向左扫描区间，能够选入最长下降子序列的元素必定是后缀最大。
在题目给定的三元约束下，这些极大值本身就构成LDS，长度等于极大值个数。
因此
$$
f(l,r)=\bigl|{,j\mid l\le j\le r,;p_j>\max_{k>j}p_k}\bigr|.
$$
具体：
设
$$
\operatorname{next}(i)=\min{,j>i\mid p_j>p_i},\qquad\text{若不存在取 }n+1.
$$
- 若区间右端 $r\le\operatorname{next}(i)-1$，则 $p_i$ 是该区间的右侧极大值。
- 区间左端 $l$ 只要 $\le i$ 即可。
故 $p_i$ 对答案的贡献为
$$
i\cdot\bigl(\operatorname{next}(i)-i\bigr).
$$
答案可表示为
$$
\boxed{\displaystyle
\mathrm{Ans}=\sum_{i=1}^{n} i\bigl(\operatorname{next}(i)-i\bigr)
},
$$
其中 $\operatorname{next}(i)$ 为 $i$ 右侧第一个比 $p_i$ 大的位置。
单调栈线性即可求得。
ac code#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int n;
void solve()
{
cin >> n;
vector<int> a(n), nx(n), st;
for(int& i : a) cin >> i;
for(int i = n - 1; ~i; i --){
while(!st.empty() && a[st.back()] < a[i])
st.pop_back();
nx[i] = st.empty() ? n : st.back();
st.push_back(i);
}
LL ans = 0;
for(int i = 0; i < n; i ++)
ans += 1LL * (i + 1) * (nx[i] - i);
cout << ans << '\n';
}
|