2023 江西省大学生程序设计竞赛

比赛链接：

L

签到题，输出$N-1$，感觉大可不必qwq~

A

签到题，输出 $n\le s\times v$的结果

I

题意：给一棵无向带边权树，有两个操作，第一个操作是让$u-v$这条边的边权异或上 $w$，第二个操作是让所有与$x$相连的边的边权异或和
Solution：用个数组存一下这个点的答案即可

#include <bits/stdc++.h>
using ll = long long;

int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m;

	std::cin >> n >> m;

	std::vector<int> val(n);

	for (int i = 0; i < n - 1; i ++) {
		int u, v, w;
		std::cin >> u >> v >> w;
		u --;
		v --;
		val[u] ^= w;
		val[v] ^= w;
	}

	while (m --) {
		int op;
		std::cin >> op;
		if (op == 1) {
			int u, v, w;
			std::cin >> u >> v >> w;
			u --;
			v --;
			val[u] ^= w;
			val[v] ^= w;
		} else {
			int x;
			std::cin >> x;
			x --;
			std::cout << val[x] << "\n";
		}
	}
	
	return 0;
}

K

题意：有一个长度为$n$的递减序列，有两个操作，第一个操作是让 $a_i=a_{i+1}+a_{i-1}-a_i$ ，第二个操作是把它分成 $k$ 个线段，每个线段的价值是线段内的极差，求出怎么分使得价值和最小。
Solution：首先，它经过操作后仍然是递减序列，对于 $a_i=a_{i+1}+a_{i-1}-a_i>a_{i+1}$ 发现他是显然的。既然是递减序列，那么计算这$n$个数的相邻差，分成 $k$ 段，就需要消除掉 $k-1$ 个相邻数，只需要把最大的删掉即可，也就是相邻差的前 $n-k$ 个数，前缀和处理一下。

#include <bits/stdc++.h>
using ll = long long;

int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;

	std::vector<int> a(n), b;

	for (int i = 0; i < n; i ++) {
		std::cin >> a[i];
		if (i - 1 >= 0)
			b.push_back(a[i - 1] - a[i]);
	}

	sort(b.begin(), b.end());

	std::vector<ll> s(n);

	for (int i = 0; i < n - 1; i ++)
		s[i + 1] = s[i] + b[i];

	int q;
	std::cin >> q;
	while (q --) {
		int op, k;
		std::cin >> op >> k;
		if (op == 1) {
			std::cout << s[n - k] << "\n";
		}
	}
	
	return 0;
}

J

题意：给你 $n$ 个形如 $y=(x-i{)}^2+b_i$ 的函数，其中 $1\le i\le n\le 10^5$ 有两个操作，第一个操作，给出 $x=a$，求所有函数的最小值，第二个操作，给出$a,c$，增加一条函数 $y=(x-a{)}^2+c$
Solution：因为最大$n\le 10^5$，求最小值的话，只需要枚举 $\sqrt{n}$内的函数就行，第二个操作只需对原有的函数对 $b_i$ 取个min就行，因为要求最小值。

#include <bits/stdc++.h>
using ll = long long;

int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;

	std::vector<int> b(n + 1);

	for (int i = 1; i <= n; i ++) {
		std::cin >> b[i];
	}

	int m;
	std::cin >> m;

	int B = std::sqrt(n);

	while (m --) {
		int op;
		std::cin >> op;
		if (not op) {
			int a, c;
			std::cin >> a >> c;
			b[a] = std::min(b[a], c);
		} else {
			int a;
			std::cin >> a;
			int l = std::max(1, a - B - 1);
			int r = std::min(n, a + B + 1);
			int ans = 1E9;
			for (int i = l; i <= r; i ++) {
				ans = std::min(ans, (a - i) * (a - i) + b[i]);
			}
			std::cout << ans << "\n";
		}
	}
	
	return 0;
}

B

队友写的，还不会qwq