A.序列变换

考察点：二分答案、构造

最小的最大值（让最大值尽可能小），很容易联想到二分答案。

答案最小 $0$ ，最大 $10^6 - 1$ ，对于每个 $mid$ ，设计 $check$ 函数看能不能构造出这样的序列。

设构造出的序列为 $b$ ，令 $x = mid$

首先，为了保证严格单调上升，前面的数肯定要尽可能的小，所以将第一个数设为可能的最小值： $b[0] = a[0] - x$ 。

对于后面的每个数，要满足两点：1. 要比前面的数大 2.要所有可能的数中最小的

很容易想到：满足条件的最小值是 $b[i] = b[i - 1] + 1$ 。

就有下面的几种情况：

$a[i] \le b[i - 1]$ ：此时 $a[i]$ 比较小，那就看能不能给 $a[i]$ 加到 $b[i - 1] + 1$ ，也就是看是否满足 $b[i - 1] + 1 - a[i] \le x$ ，如果能加到，就令 $b[i] = b[i - 1] + 1$ ，如果加不到，说明第 $i$ 个数构造不出来，直接返回 $false$ 。
$a[i] > b[i - 1]$ ：此时 $a[i]$ 比较大，那就看能不能给 $a[i]$ 减到 $b[i - 1] + 1$ ，也就是看是否满足 $a[i] - (b[i - 1] + 1) \le s$ ，如果能减到，就令 $b[i] = b[i - 1] + 1$ ，如果减不到，最小能减到多少就是多少，令 $b[i] = a[i] - x$ 。

如果 $n$ 个位置都能构造出来，就返回 $true$ 。

顺便在这说一下二分答案怎么判断向左找还是向右找的问题，拿这道题举例子：当 $check(mid) = true$ 时，满足题意，最大值能找出来。然后读题：图中要的是让最大值尽可能小，也就是在满足条件的时候继续压缩区间向左搜，看看左边还有没有更小的符合条件的答案，也就是 $r = mid$ 。

其他题也是同理：

他要最小值尽可能大

既然是尽可能大

那就是满足条件时 $l = m i d$ ，看看能不能再大点

满足条件的时候就往不满足条件那个方向移，不满足条件的时候就往满足条件的方向移。

满足条件的时候就是 $if(check(mid))$ 后面跟的

ACcode

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;

int n;
int a[N], b[N];

bool check(int x){
	memcpy(b, a, sizeof a);
	b[0] -= x;
	for(int i = 1; i < n; i++){
		if(b[i] <= b[i - 1]){
			if(b[i] + x > b[i - 1]) b[i] = b[i - 1] + 1;
			else return false;
		}
		else if(b[i] - x > b[i - 1]) b[i] -= x;
		else b[i] = b[i - 1] + 1;
	}
	return true;
}

void solve(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	int l = 0, r = 1e6;
	while(l < r){
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

B. 分奖牌

考察点：模拟+贪心，或者暴力

ACcode1：暴力

$for$ 循环暴力枚举，给 $i$ 个队伍发金牌、给 $j$ 个队伍发银牌，给 $n-i-j$ 个队伍发铜牌，然后看现在还需要定做多少块金银铜牌，加在一起，所有情况取最小值即可。

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
// const int N =  ;

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, a, b, c;
	cin >> n >> a >> b >> c;
	int res = 1e9;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			int k = n - i - j;
			int need1 = max(0, 3 * i - a);
			int need2 = max(0, 3 * j - b);
			int need3 = max(0, 3 * k - c);
			res = min(res, need1 + need2 + need3);
		}
	}
	cout << res << endl;
	return 0;
}

ACcode2：模拟+贪心

先考虑现有的金银铜牌够几个队伍分（除3向下取整），如果还有队伍没牌子，接着看还剩多少块奖牌（取模3），最优的解法肯定是先给现有的奖牌补全，而不是去买3块新的奖牌，可以用一个 $while$ 循环加排序（每次先排序保证某个位置一定是需要定做补全的最少的）或者几个 $if$ 来实现“补全”这个操作。补全之后如果还有队伍没有牌子，剩下的队伍就一个队伍定做三块牌子。

还是暴力好写

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	int a[3];
	cin >> n >> a[0] >> a[1] >> a[2];
	n -= (a[0] / 3 + a[1] / 3 + a[2] / 3);
	a[0] %= 3, a[1] %= 3, a[2] %= 3;
	if(n <= 0){
		cout << 0 << endl;
		return 0;
	}
	int res = 0;
	while(n > 0 && (a[0] || a[1] || a[2])){
		sort(a, a + 3);
		n--;
		res += 3 - a[2];
		a[2] = 0;
	}
	if(n) res += 3 * n;
	cout << res << endl;
	return 0;
}

C.今夕是何年II

考察点：bfs

简单的 $bfs$ 求最小步数，一开始将 $0$ 入队，每次取出队头，队头下一步能到的时间就是 $(队头+1) \% n$ 和 $(队头+k) \% n$ 。

用一个数组存到第 $i$ 秒所需的最小次数，一开始都初始化成 $-1$ 表示没调到过这个时间，给起点（ $0$ ）初始化成 $0$ ，剩下的就是最基础的 $bfs$ 了。

ACcode

#include <iostream>
#include <cstring>
#include <queue>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;

int cnt[N];

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, k;
	cin >> n >> k;
	queue<int> q;
	q.push(0);
	memset(cnt, -1, sizeof cnt);
	cnt[0] = 0;
	while(!q.empty()){
		int t = q.front();
		q.pop();
		for(int i : {1, k}){
			int next = (t + i) % n;
			if(~cnt[next]) continue;
			cnt[next] = cnt[t] + 1;
			q.push(next);
		}
	}
	int res = 0;
	for(int i = 1; i < n; i++){
		res = max(res, cnt[i]);
	}
	cout << res << endl;
	return 0;
}

D.排兵布“車”

考察点：快速幂预处理阶乘和逆元求组合数

根据题意可以看出：每行只能有一个車，每列也只能有一个車，因此只能摆 $min(n, m)$ 个車。

用 $n > m$ （行比列多）的情况来举例：每列只能摆放一个車，还要摆满，还要满足新增加的条件，可以看出：如果从上往下第 $i$ 个車在第 $c$ 列，那从上往下第 $i + 1$ 个車一定在第 $c + 1$ 列。

因此问题就变成了：从 $n$ 行中选 $m$ 行来放車，每个选择摆放方案都唯一。

$n \le m$ 的情况也是一样的道理。

综上，答案就是 $\binom{max(n, m)}{min(n, m)}$ 。

求组合数需要用快速幂预处理阶乘和逆元，套模板即可。

#include <iostream>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;

int qmi(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

LL inv(LL n, int p){
	return qmi(n, p - 2, p);
}

LL fact[N], infact[N]; // 预处理阶乘和阶乘的逆元

LL Cnk(int n, int k){ // Cnk即为C_n^k
	if(k < 0 || k > n) return 0;
    return (LL)fact[n] * infact[k] % mod * infact[n - k] % mod;
}

void init(){
	fact[0] = 1;
	for(int i = 1; i < N; i++){
        fact[i] = fact[i - 1] * i % mod;
    }
    infact[N - 1] = inv(fact[N - 1], mod);
    for(int i = N - 1; i > 0; i--){
        infact[i - 1] = infact[i] * i % mod;
    }
}

void solve(){
	int n, m;
	cin >> n >> m;
	cout << Cnk(max(n, m), min(n, m)) << endl;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	init();
	while(T--){
		solve();
	}
	return 0;
}

E.造数据

考察点：分组背包+前缀和

转化一下问题，首先，看到”如果要将某题的第 $j$ 组数据存入内存，必须保证该题前 $j - 1$ 组数据也一并存入内存“，肯定要用前缀和，再看，每道题有几组数据，每道题的数据有几个前缀，每道题选一个前缀，几个为一组，从几个里选一个，是不是可以转化成分组背包问题？每个前缀的数据是不是可以看成一个物品？每道题是不是可以看成一组物品？

再接着看：要让系统从硬盘读取数据的总次数最少，是不是也就是写入内存的数据的总读取次数最多？

接着就可以转化成一个分组背包问题：内存容量就是背包容量，第 $i$ 道题的前 $j$ 组数据所占内存容量的和就是第 $i$ 组第 $j$ 件物品的体积，第 $i$ 道题的前 $j$ 组数据的每日读取次数的和就是第 $i$ 组中第 $j$ 件物品的价值。接着题就转化成了：在 $n$ 组物品中选，总体积不超过内存容量的最大价值。

一开始用一个变量 $sum$ 记录一下所有数据的读取次数的和，最后用 $sum$ 减去 $dp[n][m]$ 即可。

ACcode

#include <iostream>
#include <cstring>
using namespace std;
using LL = long long;
const int N = 105, M = 5050;

LL v[N][N], w[N][N];
LL dp[N][M];

void solve(){
	int n, m, s;
	cin >> n >> s >> m;
	LL sum = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= s; j++){
			cin >> v[i][j] >> w[i][j];
			sum += w[i][j];
			 v[i][j] += v[i][j - 1];
			 w[i][j] += w[i][j - 1];
		}
	}
	memset(dp, 0, sizeof dp);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= m; j++){
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			for(int k = 1; k <= s; k++){
				if(j >= v[i][k]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
			}
		}
	}
	cout << sum - dp[n][m] << endl;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

F.网络工程

考察点：图论、dfs或并查集求联通块

读题，每个传送门只能传送到一个特定的行星。每个行星都拥有一台传送门，并且只能被一台传送门传送到；

由此可以发现，实际上所有的图都是一个又一个首尾相连的环（因为每个点一定有一个出边、也一定有一个入边，如果有链的话，一定有一个点没有出边、一个点没有入边）。

那题意就转化成了：给你一个有若干环的图，每次操作可以交换两条边的终点，问给这个图变成一整个大环的最小操作次数。

拿只有两个环的情况举例，只需要在两个环中任取两条边操作即可变成一个大环，然后再拿这个大环去合并另一个环...

可以看出，如果有 $cnt$ 个环（联通块），那只需要合并 $cnt - 1$ 次，也就是答案。

问题也就转化成了求联通块，用 $dfs$ 或并查集都可以。

ACcode1

#include <iostream>
#include <vector>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;

vector<int> g[N];
bool st[N];

void dfs(int u){
	st[u] = true;
	for(auto v : g[u]){
		if(st[v]) continue;
		dfs(v);
	}
}

void solve(){
	int n;
	cin >> n;
	memset(st, false, sizeof st);
	for(int i = 1; i <= n; i++){
		g[i].clear();
		int x;
		cin >> x;
		g[i].push_back(x);
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(!st[i]){
			dfs(i);
			cnt++;
		}
	}
	cout << cnt - 1 << endl;
}


int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

ACcode2

#include <iostream>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;

int fa[N];

int find(int x){
	if(fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}

void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		fa[i] = i;
	}
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;
		fa[find(i)] = find(x);
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(fa[i] == i) cnt++;
	}
	cout << cnt - 1 << endl;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

G.拼夕夕

考察点：暴力、二进制枚举或dfs

ACcode1

每个成员都可以选可以不选，一共 $2^{m}$ 种方案，恰好可以用 $0$ ~ $2^m - 1$ 这 $2^m$ 个二进制数来表示，如果某一位是 $1$ 就表示选这个人，是 $0$ 就表示不选，用一个 $cnt$ 数组记录每种属性有多少个人拥有，如果选这个人，就给这个人拥有的所有属性在 $cnt$ 数组中对应的位置 $+1$ 。对于每种方案，先看选的人数是不是 $k$ （用 $\_\_builtin\_popcount()$ 统计二进制中 $1$ 的个数），如果是，用 $sum$ 记录当前方案合格属性的价值总和，遍历一遍所有的属性，如果 $cnt \ge 2$ ，就给 $cnt$ 和属性的价值的乘积累加到 $sum$ ，最后所有的 $sum$ 取最小值即可。

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 30;

int n, m, k;
int w[N];
vector<int> a[N];

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		cin >> w[i];
	}
	for(int i = 0; i < m; i++){
		int x;
		cin >> x;
		while(x--){
			char c;
			cin >> c;
			a[i].push_back(c - 'A');
		}
	}
	LL res = 0;
	for(int i = 0; i < (1 << m); i++){
		int c = __builtin_popcount(i);
		int cnt[26] = {0};
		if(c == k){
			for(int j = 0; j < m; j++){
				if(i >> j & 1){
					for(int t : a[j]) cnt[t]++;
				}
			}
			LL sum = 0;
			for(int j = 0; j < n; j++){
				if(cnt[j] >= 2) sum += (LL)w[j] * cnt[j];
			}
			res = max(res, sum);
		}
	}
	cout << res << endl;
	return 0;
}

ACcode2

$dfs$ 指数型枚举，每个成员都可以选可以不选，一共 $2^{m}$ 种方案，用一个 $cnt$ 数组记录每种属性有多少个人拥有，如果选这个人，就给这个人拥有的所有属性在 $cnt$ 数组中对应的位置 $+1$ ，对于每种方案，先看选的人数是不是 $k$ ，如果是，用 $sum$ 记录当前方案合格属性的价值总和，遍历一遍所有的属性，如果 $cnt \ge 2$ ，就给 $cnt$ 和属性的价值的乘积累加到 $sum$ ，最后所有的 $sum$ 取最小值即可。

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 30;

int n, m, k;
int w[N];
vector<int> a[N];
int cnt[N];
bool st[N];
LL res;

void dfs(int x, int c){
	if(x >= m){
		if(c == k){
			LL sum = 0;
			for(int i = 0; i < n; i++){
				if(cnt[i] >= 2) sum += (LL)w[i] * cnt[i];
			}
			res = max(res, sum);
		}
		return;
	}
	st[x] = 1;
	for(auto i : a[x]) cnt[i]++;
	dfs(x + 1, c + 1);
	st[x] = 0;
	for(auto i : a[x]) cnt[i]--;

	st[x] = 2;
	dfs(x + 1, c);
	st[x] = 0;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		cin >> w[i];
	}
	for(int i = 0; i < m; i++){
		int x;
		cin >> x;
		while(x--){
			char c;
			cin >> c;
			a[i].push_back(c - 'A');
		}
	}
	dfs(0, 0);
	cout << res << endl;
	return 0;
}

H.旧活新整

考察点：签到

签到题，输出两句话中的任意一句都是对的。

细心观察可以发现，这题写了special judge。

ACcode1

#include <iostream>
#define endl '\n'
using namespace std;
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout << "wo xiang jie xun" << endl;
	return 0;
}

ACcode2

#include <iostream>
#define endl '\n'
using namespace std;
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout << "wo bu xiang jie xun" << endl;
	return 0;
}

I.最短路

考察点：图论、dijkstra求最短路

ACcode1

可以写两个 $dijkstra$ 的模板，一个求所有边都可以走的最短路，一个求只能走标记为 $1$ 的边的最短路，答案很显然只有下面两种情况。

不拿钥匙直接走到 $n$ （只走标记为 $1$ 的边从 $1$ 到 $n$ 的最短路）
先去拿钥匙，再走到 $n$ （先只走标记为 $1$ 的边从 $1$ 走到 $k$ ，然后走任意边从 $k$ 走到 $n$ ）

两种方案取最小值即可。

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#define endl '\n'
using namespace std;
using LL = long long;
typedef pair<LL, int> PII;
const int N = 2e5 + 10;

struct Edge{
	int v, w, state;
};

int n, m, k;
LL dist[N];
bool st[N];
vector<Edge> g[N];

LL dijkstra1(int s, int e){
	memset(dist, 0x3f, sizeof dist);
	memset(st, false, sizeof st);
	dist[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> q;
	q.push({0, s});
	while(!q.empty()){
		auto t = q.top();
		q.pop();
		int u = t.second;
		if(st[u]) continue;
		st[u] = true;
		for(auto i : g[u]){
			int v = i.v, w = i.w, state = i.state;
			if(!state) continue;
			if(dist[v] > dist[u] + w){
				dist[v] = dist[u] + w;
				q.push({dist[v], v});
			}
		}
	}
	return dist[e];
}

LL dijkstra2(int s, int e){
	memset(dist, 0x3f, sizeof dist);
	memset(st, false, sizeof st);
	dist[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> q;
	q.push({0, s});
	while(!q.empty()){
		auto t = q.top();
		q.pop();
		int u = t.second;
		if(st[u]) continue;
		st[u] = true;
		for(auto i : g[u]){
			int v = i.v, w = i.w, state = i.state;
			if(dist[v] > dist[u] + w){
				dist[v] = dist[u] + w;
				q.push({dist[v], v});
			}
		}
	}
	return dist[e];
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	while(m--){
		int a, b, w, s;
		cin >> a >> b >> w >> s;
		g[a].push_back({b, w, s});
		g[b].push_back({a, w, s});
	}
	LL res1 = dijkstra1(1, n);
	LL res2 = dijkstra1(1, k);
	LL res3 = dijkstra2(k, n);
	LL res = min(res1, res2 + res3);
	cout << (res == 0x3f3f3f3f3f3f3f3f ? -1 : res) << endl;
	return 0;
}

ACcode2

第二种写法就是只写一个 $dijkstra$ ，状态多加一维用来记录拿没拿钥匙，如果没拿钥匙遇到标记为 $0$ 的边就 $continue$ 。同时 $st$ 数组和 $dist$ 数组也要加一维， $dist[i][0]$ 表示没拿钥匙到 $i$ 的最短路， $dist[i][1]$ 表示拿钥匙后到 $i$ 的最短路， $st$ 数组表示对应的状态被没被松弛过。

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 2e5 + 10;

struct Edge{
	int v, w, state;
};

struct Node{
	LL dis;
	int u, state;
	bool operator < (const Node &a) const{
		return dis > a.dis;
	}
};

int n, m, k;
LL dist[N][2];
bool st[N][2];
vector<Edge> g[N];

LL dijkstra(int s, int e){
	memset(dist, 0x3f, sizeof dist);
	memset(st, false, sizeof st);
	priority_queue<Node> q;
	if(k != s){
		q.push({0, s, 0});
		dist[s][0] = 0;
	}
	else{
		q.push({0, s, 1});
		dist[s][1] = 0;
	}
	while(!q.empty()){
		auto t = q.top();
		q.pop();
		int u = t.u, sta = t.state;
		LL dis = t.dis;
		if(st[u][sta]) continue;
		st[u][sta] = true;
		for(auto i : g[u]){
			int v = i.v, w = i.w, state = i.state;
			if(!state && !sta) continue;
			int new_state = sta;
			if(v == k) new_state = 1;
			if(dist[v][new_state] > dis + w){
				dist[v][new_state] = dis + w;
				q.push({dist[v][new_state], v, new_state});
			}
		}
	}
	return min(dist[e][0], dist[e][1]);
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	while(m--){
		int a, b, w, s;
		cin >> a >> b >> w >> s;
		g[a].push_back({b, w, s});
		g[b].push_back({a, w, s});
	}
	LL res = dijkstra(1, n);
	cout << (res >= 0x3f3f3f3f3f3f3f3f ? -1 : res) << endl;
	return 0;
}

J.宝石项链

考察点：思维、贪心、前（后）缀和

对于正数：比如 $\{...1 ...5...3...\}$ 这个序列，如果先取下 $5$ ，那左侧消失， $1$ 就取不到了，肯定没有先取 $1$ 再取 $5$ 优， $3$ 也是同理。对于最优的情况，一定某一个前缀中所有的正数都可以取到，但负数都取不到。

对于负数：比如 $\{...-1 ...-5...-3...\}$ 这个序列，如果先取下 $-5$ ，那右侧断裂， $-3$ 就取不到了，肯定没有先取 $-3$ 再取 $-5$ 优， $-1$ 也是同理。对于最优的情况，一定某一个后缀中所有的负数都可以取到，但正数都取不到。

由此可以看出，最后答案一定是在某个分界点，取了分界点左侧所有的正数和右侧所有的负数。

那就可以遍历一遍所有的分界点 $i$ ，收集到最多的能量就是 $1$ ~ $i$ 所有的正数的和加上 $i + 1$ ~ $n$ 所有的负数的绝对值的和，取最大值即可。

提前预处理一下所有正数的前缀和和所有负数的绝对值的后缀和。

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;

int a[N];
LL pre[N], suf[N];

void solve(){
	int n;
	cin >> n;
	// memset(pre, 0, sizeof pre);
	// memset(suf, 0, sizeof suf);
	for(int i = 0; i <= n + 1; i++){
		pre[i] = 0;
		suf[i] = 0;
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(a[i] > 0) pre[i] = pre[i - 1] + a[i];
		else pre[i] = pre[i - 1];
	}
	for(int i = n; i >= 1; i--){
		if(a[i] < 0) suf[i] = suf[i + 1] + abs(a[i]);
		else suf[i] = suf[i + 1];
	}
	LL res = 0;
	for(int i = 0; i <= n; i++){
		res = max(res, pre[i] + suf[i + 1]);
	}
	cout << res << endl;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

这题有一个刻意避开没卡的超时点。

看数据范围， $T \le 10^4$ ， $n \le 2 \times 10^5, \sum n \le 2 \times 10^5$

因为 $n \le 2 \times 10^5$ ，如果用数组的话，就要开 $> 2 \times 10^5$ 的数组，如果每次都用 $memset$ 初始化整个数组，复杂度就是最大 $O(T \times 2 \times 10^5)$ ，如果没有优化肯定会超时，但实际上有很多组数据可能都是 $n = 1、n = 2 ...$ ，也就相当于初始化了很多没用的位置，这个时候有最常用的两种解决方案：

干脆直接用 $for$ 循环挨个初始化（上面的代码）
直接用 $vector<int> a(n, 0)$ 。

还有一种题，数据范围专卡数组，只能用 $vector$ ，举个例子：数据保证 $n \le 2 \times 10^5, m \le 2 \times 10^5, n \times m \le 2 \times 10^5$ 。

这个时候，就有 $n = 10^5, m = 1$ 和 $n = 1,m = 10^5$ 这种极端数据。

这个时候如果你用数组，就需要开一个 $10^5 \times 10^5$ 的数组，一定会 $MLE$

这个时候就只能用 $vector$

开一个 $n \times m$ 的 $vector$ 并给所有元素都初始化成 $0$

vector<vector<int>> a(n, vector<int> (m, 0))

沈阳化工大学ACM2025春季结训赛题解

A.序列变换

B. 分奖牌

C.今夕是何年II

D.排兵布“車”

E.造数据

F.网络工程

G.拼夕夕

H.旧活新整

I.最短路

J.宝石项链