#创作计划# 挑战赛 #22 全题解

复仇者_帅童

2025-09-07 22:01:29

发布于：广东

33阅读

0回复

0点赞

题目	做法难度
T1 可以，枫总司令	$\red{入门}$
T2 巴仈博弈	$\orange{普及-}$
T3 欢乐赛T6	$\orange{普及-}$
T4 爬山	$\orange{普及-}$
T5 看着简单做着难	$\green{普及+/提高}$
T6 保证思维量与使用数据结构难度成反比	$\green{普及+/提高}$ （ $\blue{提高+/省选-}$ ）

T1

可以，枫总司令。

注意到 $i=j$ 时， $\max_{k=i}^j A_k=A_i=\sum_{k=i}^j A_k$ ，所以对于任意数组，一定存在符合要求的数对，直接输出 YES 即可。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--){
		cout << "YES\n";
	}

	return 0;
}

时间复杂度： $O(t)$ ？不到啊。

T2

典型的无脑博弈。

注意到如果 $n$ 为奇数，则偶数下标的数都会被隐藏，奇数下标剩一个；否则奇数下标的数被隐藏，偶数下标的数剩一个。

所以只要 $n$ 为奇数时，小午选一个奇数不隐藏，当 $n$ 为偶数时，小枫选一个偶数不隐藏即可必胜。关键就在于他们有没有。

#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
bool flag1, flag2;
int n;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(i % 2 && a[i] % 2) flag1 = 1;
		else if(i % 2 == 0 && a[i] % 2 == 0) flag2 = 1;
	}
	if(n % 2){
		if(flag1) cout << "Noon";
		else cout << "Maple";
	}else{
		if(flag2) cout << "Maple";
		else cout << "Noon";
	}
	

	return 0;
}

时间复杂度： $O(n)$ 。

T3

本题做法有很多，这里贴一个最无脑的 DP 做法。

$dp[i][0]$ 表示前 $i$ 个数选择的结果为偶数的最大值， $dp[i][1]$ 表示奇数的最大值。则：

当 $A_i$ 为奇数时， $dp[i][0]=\max\{dp[i-1][0],dp[i-1][1]+A_i\}$ ， $dp[i][1]=\max\{dp[i-1][1],dp[i-1][0]+A_i\}$ 。
当 $A_i$ 为偶数时， $dp[i][0]=dp[i-1][0]+A_i,dp[i][1]=dp[i-1][1]+A_i$ 。

注意不存在不选数结果为奇数的情况，所以应把 $dp[0][1]$ 设置成 $-\infty$ 。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[1000005];
int dp[1000005][2];
int n;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	dp[0][1] = -0x3f3f3f3f3f3f3f3fll;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(a[i] & 1){
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + a[i]);
			dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + a[i]);
		}else{
			dp[i][0] = dp[i - 1][0] + a[i];
			dp[i][1] = dp[i - 1][1] + a[i];
		}
	}
	cout << dp[n][0];

	return 0;
}

时间复杂度： $O(n)$ 。

T4

这么一眼的吗，滚去 T2。

很显然，差分+前缀最大值+二分即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[500005], b[500005], pre[500005];
int n, m;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		b[i] = a[i] - a[i - 1];
		pre[i] = max(pre[i - 1], b[i]);
	}
	while(m--){
		int val;
		cin >> val;
		cout << a[upper_bound(pre + 1, pre + n + 1, val) - pre - 1] << ' ';
	}

	return 0;
}

时间复杂度： $O(m\log n)$ 。

T5

怎么突然开始上难度了。

拼尽全力无法想出 $O(qn)$ 解法，只能写一个 $O(qn\log n)$ 卡常过了。

考虑单次询问怎么做。

注意到如果完成前 $i$ 个解密，那肯定选前 $i$ 个挑战中前 $k$ 小的时间。加上 $A_i$ 前缀和求最小值即可。显然可以用大根堆 $O(n\log k)$ 解决。

但是堆的常数有亿点大， $100\times (2\times 10^5)\times \lceil\log_2(2\times 10^5)\rceil=3.6\times 10^8$ ，稍微带点常数就寄了。看来我们需要使用一个常数更小的数据结构。

有什么数据结构可以常数小、能 $O(\log n)$ 求出前 $i$ 个元素的前 $k$ 小的元素呢？很显然，树状数组神力！

我们离散化一下，确定每个 $B_i$ 对应的位置 $C_i$ ，使得 $C_i$ 各不相同且对于 $i,j$ ，当 $B_i\lt B_j$ 时 $C_i\lt C_j$ ；

开两个树状数组 $t_1,t_2$ ，在更新第 $i$ 个数时，将 $t_1[C_i]$ 的值 $+1$ ， $t_2[C_i]$ 的值 $+B_i$ ；查询时直接树状数组二分，找到第一个（最后一个也行） $i$ 使得 $(\sum_{j=1}^i t_1[j])\ge k$ ，然后查询 $\sum_{j=1}^i t_2[j]$ 即可。

离散化、修改树状数组的时间复杂度为 $O(n\log n)$ ，常数很大，但不影响；而查询的时间复杂度为 $O(qn\log n)$ ，常数约为 $1$ 。这样就可以在规定时间内通过该题。

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <memory.h>
#define int long long
using namespace std;
int a[200005], b[200005], c[200005], q[105];
map <int, int> mp;
int ans[105];
int tr1[200005], tr2[200005];
int n, m;
void modify(int idx, int val){
	for(int i = idx; i <= n; i += (i & (-i))){
		tr1[i]++;
		tr2[i] += val;
	}
}
int query(int val){
	int idx = 0, cur = 0, ans = 0;
	for(int i = 18; i >= 0; i--){
		if(idx + (1 << i) <= n && cur + tr1[idx + (1 << i)] <= val){
			idx += (1 << i);
			cur += tr1[idx];
			ans += tr2[idx];
		}
	}
	return ans; 
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i], c[i] = b[i];
	sort(c + 1, c + n + 1);
	for(int i = 1; i <= n; i++){
		mp[c[i]] = lower_bound(c + 1, c + n + 1, c[i]) - c;
	}
	for(int i = 1; i <= n; i++){
		c[i] = (mp[b[i]]++);
	}
	for(int i = 1; i <= m; i++) cin >> q[i];
	int cur = 0;
	memset(ans, 63, sizeof(ans));
	for(int i = 1; i <= n; i++){
		cur += a[i];
		modify(c[i], b[i]);
		for(int j = 1; j <= m; j++){
			if(q[j] > i) continue;
			ans[j] = min(ans[j], cur + query(q[j]));
		}
	}
	for(int i = 1; i <= m; i++){
		cout << ans[i] << '\n';
	}

	return 0;
}

时间复杂度： $O(qn\log n)$ ，常数特小可以通过。

T6

大脑[思维] = 0;
大脑[数据结构] = LLONG_MAX;

将式子转换一下：

$\max_{k=i}^j A_k\ge\sum_{k=i}^j A_k\\\space\\ \sum_{k=i}^j A_k\le\max_{k=i}^j A_k\\\space\\ \sum_{k=i}^j A_k-\max_{k=i}^j A_k\le 0$

所以我们只需要对于每个 $i$ ，判断 $\max_{j=1}^i(\sum_{k=j}^i A_k-\max_{k=j}^i A_k)\ge 0$ 即可。注意， $i$ 是连续的，所以可以根据前面的结果推出后面的结果。

先看和的部分。

很简单，开一颗线段树，更新 $A_i$ 时在 $[1,i]$ 加上 $A_i$ 即可。

然后就要思考如何求最大值了。

假设原来的区间最值为 $[9,9,6,4,4,4,3,2,2,0,0]$ （ $0$ 是给第 $10,11$ 个元素占位用的），现在添加了第 $10$ 个元素 $5$ ，那么就需要将区间最值变为 $[9,9,6,5,5,5,5,5,5,5,0]$ ，则你需要：

将区间 $[4,6]$ 的值加 $1$ 。
将区间 $[7,7]$ 的值加 $2$ 。
将区间 $[8,9]$ 的值加 $3$ 。

而这时再添加第 $11$ 个元素 $7$ 呢？区间最值就变为了 $[9,9,7,7,7,7,7,7,7,7,7]$ ，你只需要将区间 $[3,3]$ 的值加 $1$ ， $[4,11]$ 的值加 $2$ 即可。

注意到这个操作完全可以用单调栈实现。弹出时更新线段树即可。

显然，单调栈最多只能弹出 $O(n)$ 次，所以整体时间复杂度还是 $O(n\log n)$ 的。

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define int long long
using namespace std;
class Segtree{
	private:
	vector <int> tree, lazytag, left, right;
	int n;
	void push_up(int u){
		tree[u] = max(tree[u << 1], tree[u << 1 | 1]);
	}
	void push_down(int u){
		if(!lazytag[u]) return;
		lazytag[u << 1] += lazytag[u];
		lazytag[u << 1 | 1] += lazytag[u];
		tree[u << 1] += lazytag[u];
		tree[u << 1 | 1] += lazytag[u];
		lazytag[u] = 0;
	}
	void build(int u, int l, int r){
		left[u] = l, right[u] = r;
		if(l == r) return;
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
	void _modify(int u, int l, int r, int val){
		if(left[u] >= l && right[u] <= r){
			tree[u] += val;
			lazytag[u] += val;
			return;
		}
		push_down(u);
		int mid = left[u] + right[u] >> 1;
		if(l <= mid) _modify(u << 1, l, r, val);
		if(r > mid) _modify(u << 1 | 1, l, r, val);
		push_up(u); 
	}
	
	int _query(int u, int l, int r){
		if(left[u] >= l && right[u] <= r) return tree[u];
		push_down(u);
		int ans = -0x3f3f3f3f3f3f3f3fll;
		int mid = left[u] + right[u] >> 1;
		if(l <= mid) ans = max(ans, _query(u << 1, l, r));
		if(r > mid) ans = max(ans, _query(u << 1 | 1, l, r));
		return ans;
	}
	
	public:
	Segtree(){}
	Segtree(int n){
		this -> n = n;
		tree.resize(n << 2 | 1, -0x3f3f3f3f3f3f3f3fll);
		left.resize(n << 2 | 1, 0);
		right.resize(n << 2 | 1, 0);
		lazytag.resize(n << 2 | 1, 0);
		build(1, 1, n);
	}
	void modify(int l, int r, int val){
		_modify(1, l, r, val);
	}
	int query(int l, int r){
		return _query(1, l, r);
	}
	
};
void solve(){
	int n;
	cin >> n;
	vector <int> a(n + 1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	Segtree tr(n + 1);
	stack <int> s;
	for(int i = 1; i <= n; i++){
		tr.modify(i, i, 0x3f3f3f3f3f3f3f3fll);// 先变为0
		if(i == 1){
			s.push(i);
			continue;
		}
		tr.modify(1, i, a[i]);
		int cur = i, tmp = 0;
		while(!s.empty() && a[s.top()] <= a[i]){
			int idx = s.top();
			tr.modify(idx + 1, cur, tmp - a[i]);
			tmp = a[idx];
			cur = idx;
			s.pop();
		}
		if(cur){
			if(s.empty()){
				tr.modify(1, cur, tmp - a[i]);
			}else{
				int idx = s.top() + 1;
				tr.modify(idx, cur, tmp - a[i]);
			}
		}
		s.push(i);
		if(tr.query(1, i) > 0){
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();
	
	return 0;
}

时间复杂度： $O(\sum n\log n)$ 。

赛后发现我 T5 优化了个寂寞。甚至有人大根堆解法比我还快。

有帮助，赞一个

去预览

0/2000

全部评论 10

复仇者_帅童
我早知道先拿大根堆试了

2天前来自广东
1
- 复仇者_帅童
  回复复仇者_帅童
  白优化了
  
  2天前来自广东
  1
- 复仇者_澜（不处不加团队）
  回复复仇者_帅童
  优化优了个皮燕子
  
  2天前来自广东
  0
- 复仇者_澜（不处不加团队）
  回复复仇者_帅童
  笑笑蒜了
  
  2天前来自广东
  0
你是不是喜欢c++
%%%感觉好复杂555

2天前来自广东
1
复仇者_帅童
d

2天前来自广东
1
复仇者_帅童
d

2天前来自广东
1
复仇者_澜（不处不加团队）
T3是不是想复杂了，显然设奇数个数为 $a$ ，奇数和为 $b$ ，最小的奇数为 $c$ ，偶数和为 $d$ ，答案显然：

$a\%2==0$ $ans=b+d$
$a\%2==1$ $ans=b+d-c$

2天前来自广东
0
- 复仇者_帅童
  回复复仇者_澜（不处不加团队）
  两种做法都可以
  
  2天前来自广东
  0
复仇者_澜（不处不加团队）
%%%

2天前来自广东
0
Stars_Seeker
@AC君

2天前来自重庆
0
Stars_Seeker
巴巴博一

2天前来自重庆
0
Stars_Seeker
_顶

2天前来自重庆
0
Stars_Seeker
qp

2天前来自重庆
0

T1

T2

T3

T4

T5

T6

全部评论 10

热门讨论