CSP2023复赛复盘合集

CSP-J2 DAY2 复盘

T1

AC！！！

水题

直接使用 $substr$ 通过取模稍微优化一下就好了

AC 代码：

#include <bits/stdc++.h>
using namespace std;

string s;
int n, l, r, k;

int main(){
	cin >> s;
	s = ' ' + s;
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> l >> r >> k;
		string t = s.substr(l, r - l + 1);
		if (k % t.size() == 0) continue;
		string t1 = t.substr(t.size() - k % t.size(), k % t.size()), t2 = t.substr(0, t.size() - k % t.size());
		s = s.substr(0, l) + t1 + t2 + s.substr(r + 1);
	}
	cout << s.substr(1);
	return 0;
}

T2

在考虑 $cmp$ 第二条件的时候理解反了，应是小于号而不是大于号，推导时理所当然的觉得应该是大于

AC 代码：

#include <bits/stdc++.h>
using namespace std;

int n, cnt;
struct node{
	int a, b;
}t[100005];

bool cmp(node x, node y){
	if (x.a == y.a) return x.b < y.b;
	return x.a < y.a;
}

int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> t[i].a >> t[i].b;
	sort(t + 1, t + n + 1, cmp);
	int temp = 1;
	for (int i = 2; i <= n; i++){
		if (t[i].a > t[temp].a && t[i].b < t[temp].b) cnt++;
		else temp = i;
	}
	cout << cnt;
	return 0;
}

T3

思路没问题，代码实现上在预处理完之后统计部分有问题

没考虑到 $memset$ 的时间复杂度为 $O(n)$，应使用 $set$ 来代替数组进行去重操作。

AC 代码：

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int n, m, cnt;
int vis[1005][1005], res[1005][1005], ans[1005][1005];
char s[1005][1005];

void dfs(int x, int y){
	for(int i = 0; i < 4; i++){
		int nx = x + dx[i], ny = y + dy[i];
		if (nx > 0 && nx <= n && ny > 0 && ny <= m && vis[nx][ny] == 0 && s[nx][ny] == '.'){
			vis[nx][ny] = 1, res[nx][ny] = cnt;
			sum[cnt]++;
			dfs(nx, ny);
		}
	}
}

int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++) cin >> s[i][j];
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (s[i][j] == '.' && vis[i][j] == 0){
				vis[i][j] = 1, res[i][j] = ++cnt;
				sum[cnt]++;
				dfs(i, j);
			}
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (s[i][j] == '*'){
				set<int> st;
				for (int k = 0; k < 4; k++){
					int nx = i + dx[k], ny = j + dy[k];
					st.insert(res[nx][ny]);
				}
				ans[i][j] = 1;
				for (auto it : st) ans[i][j] += sum[it];
			}
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (s[i][j] == '*') cout << ans[i][j] % 10;
			else cout << s[i][j];
		}
		cout << endl;
	}
	return 0;
}

T4

赛场上通过打制表格成功骗到了 60pts

参考了一下别人的代码，发现思路很简单，就是纯模拟 + 递归，特判一下输出最小值或最大值就好了

老师讲的玄学剪枝忘了

AC 代码：

#include <bits/stdc++.h>
using namespace std;

int t, flag;
int ans[100005];
string s;
vector<int> v;

bool chk(){
	vector<int> g;
	for (int i = 1; i <= v.size() / 2; i++) g.push_back(7);
	for (int i = 1; i <= v.size() / 2; i++) g.push_back(4);
	for (int i = 0; i < v.size(); i++){
		if (g[i] < v[i]) return true;
		if (g[i] > v[i]) return false;
	} 
	return false;
}

void dfs(int k, int cnt1, int cnt2, int f1){
	if ((v.size() - k) % 2 != (cnt1 % 2 - cnt2 % 2 + 2) % 2) return ;
	if (abs(cnt1 - cnt2) > (v.size() - k)) return ;
	if (flag) return ;
	if (k >= v.size() && cnt1 == cnt2){
		for (int i = 0; i < v.size(); i++) cout << ans[i];
		cout << "\n";
		flag = 1;
		return ;
	}
	if (v[k] > 7 && !f1) return ;
	int f2 = f1;
	if (v[k] <= 4 || f1){
		ans[k] = 4;
		if (v[k] < 4) f2 = 1;
		dfs(k + 1, cnt1 + 1, cnt2, f2);
		f2 = f1;
		ans[k] = 7;
		if (v[k] < 7) f2 = 1;
		dfs(k + 1, cnt1, cnt2 + 1, f2);
	}
	else{
		ans[k] = 7;
		if (v[k] < 7) f2 = 1;
		dfs(k + 1, cnt1, cnt2 + 1, f2);
	}
}

int main(){
	cin >> t;
	while (t--){
		v.clear();
		memset(ans, 0, sizeof(ans));
		flag = 0;
		cin >> s;
		for (int i = 0; i < s.size(); i++) v.push_back(s[i] - '0');
		int t = 0;
		if (v.size() % 2 == 0) t = chk();
		if (v.size() % 2 == 1 || t){
			if (t) cout << "4";
			for (int i = 1; i <= (v.size() + 1) / 2; i++) cout << "4";
			for (int i = 1; i <= (v.size() + 1) / 2; i++) cout << "7";
			if (t) cout << "7";
			cou
                t << "\n";
			continue;
		}
		dfs(0, 0, 0, 0);
	}
	return 0;
}

总结

在考虑贪心的时候仔细考虑 $cmp$ 的第二条件，不能凭直觉；

在检查代码的时候先考虑时间复杂度，以免在想思路时算错时间复杂度，然后再检查数组大小

复习 $STL$

CSP-J2 DAY3 复盘

T1

在推导公式的时候有问题

加上没有开 long long 导致错误，没考虑到两个宽相乘会爆 int

AC 代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a, b, c, d;

void print(int x, int y){
	for (int i = 2; i <= min(x, y); i++){
		while (x % i == 0 && y % i == 0) x /= i, y /= i;
	}
	cout << x << "/" << y;
}

signed main(){
	cin >> a >> b >> c >> d;
	if (a * d == b * c) cout << "0/1";
	else print(max(a * d, c * b) - min(a * d, c * b), max(a * d, c * b));
	return 0;
}

T2

AC！！！

很简单的一个贪心，考虑到高位数字越大，数字越大，所以可以从高位到低位枚举看 $k$ 个数以内最大值然后使用 $substr$ 替换

AC 代码：

#include <bits/stdc++.h>
using namespace std;

int t, k;
string s;

int main(){
	cin >> t;
	while (t--){
		cin >> s >> k;
		for (int i = 0; i < s.size() && k > 0; i++){
			int maxn = s[i] - '0', pos = i;
			for (int j = i; j <= i + k && j < s.size(); j++){
				if (s[j] - '0' > maxn){
					maxn = s[j] - '0';
					pos = j;
				}
			}
			s = s.substr(0, i - 0) + s[pos] + s.substr(i, pos - i) + s.substr(pos + 1);
			k -= pos - i;
		}
		cout << s << "\n";
	}
	return 0;
}

T3

纯粹的没开 long long 见祖宗，没考虑到可能会退化成一条链

运气好，在思考的时候考虑到了 $cmp$ 有问题，找到了 $hack$ 数据

同时，在赛场上也想到了优化方案

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, k, ans;
vector<int> g[200005];
struct node{
	int x, sz, dp;
}tr[200005];

bool cmp(node x, node y){
	return (x.dp - x.sz) > (y.dp - y.sz);
}

int dfs(int x, int fa){
	tr[x].dp = tr[fa].dp + 1;
	for (int i = 0; i < g[x].size(); i++){
		int v = g[x][i];
		if (v == fa) continue;
		tr[x].sz += dfs(v, x);
	}
	return tr[x].sz;
}

signed main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++) tr[i].sz = 1, tr[i].x = i;
	for (int i = 1, u, v; i <= n - 1; i++){
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	sort(tr + 1, tr + n + 1, cmp);
	for (int i = 1; i <= k; i++) ans += tr[i].dp - tr[i].sz;
	cout << ans;
	return 0;
}

T4

没思路，暴力代码写挂了，应该是错在统计有多少个不能选上

60pts：将 $a$ 数组映射到 $b$ 数组上，用 $p$ 数组表示 $a_i$ 中的书在 $b$ 上的什么位置。然后发现可以求最长下降子序列，即翻转过来的最长上升子序列

100pts：使用二分优化过的最长上升子序列

主要是没想到能通过映射然后使用 $LIS$

#include <bits/stdc++.h>
using namespace std;

int n, cnt;
int a[1000005], b[1000005], c[1000005], p[1000005], dp[1000005];

int find(int x){
	int l = 1, r = cnt;
	while (l < r){
		int mid = (l + r) >> 1;
		if (dp[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i], c[b[i]] = i;
	for (int i = n; i >= 1; i--) p[n - i + 1] = c[a[i]];
	dp[++cnt] = p[1];
	for (int i = 2; i <= n; i++){
		if (p[i] > dp[cnt]) dp[++cnt] = p[i];
		else dp[find(p[i])] = p[i];
	}
	cout << cnt;
	return 0;
}

总结

在推导数学公式的时候思路不清晰，应用多种方法验证公式的正确性

仔细分析数据范围，避免没开 long long 见祖宗

在思考图论问题的时候，特别是树，考虑是否会退化

对于 $LIS$ 的模型转换

CSP-J2 DAY4 复盘

T1

AC！！！

水题

只用记录每一个空缺的区间有多少个然后一个除二向上取整，另一个加上区间的长度

AC 代码：

#include <bits/stdc++.h>
using namespace std;

int n, k, c, a, b, cnt, ans1, ans2;
int mp[4005];

int main(){
	cin >> n >> k;
	for (int i = 1; i <= k; i++){
		cin >> c;
		if (c == 1) cin >> a >> b;
		else cin >> a;
		mp[a] = mp[b] = 1;
	}
	for (int i = 1; i < n; i++){
		if (mp[i] == 0) cnt++;
		else{
			ans1 += (cnt + 1) / 2, ans2 += cnt;
			cnt = 0;
		}
	}
	ans1 += (cnt + 1) / 2, ans2 += cnt;
	cout << ans1 << " " << ans2;
	return 0;
}

T2

只考虑到了单个差分在前缀和，没考虑到可以记录端点出现次数然后累加总和

AC 代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, k, x, y;
int a[100005], l[100005], r[100005], cnt[100005], c[100005], s[100005];

signed main(){
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> l[i] >> r[i] >> c[i];
	for (int i = 1; i <= k; i++){
		cin >> x >> y;
		cnt[x]++, cnt[y + 1]--; 
	}
	for (int i = 1; i <= m; i++){
		cnt[i] += cnt[i - 1];
		s[l[i]] += c[i] * cnt[i];
		s[r[i] + 1] -= c[i] * cnt[i];
	}
	for (int i = 1; i <= n; i++){
		s[i] += s[i - 1];
		cout << a[i] + s[i] << " ";
	}
	return 0;
}

T3

AC！！！

一眼看过去发现可以枚举每一个电量，然后想到二分答案，去二分最终电量的可能值，如果比 $mid$ 大的数减去损失比小的数要大就可以增加最终电量，满足单调性

注意精度，比题目要求的稍微高一点，最好和题目样例输出的精度相同

#include <bits/stdc++.h>
using namespace std;

double n, k, sum;
double a[10005];

bool check(double x){
	double cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++){
		if (a[i] >= x) cnt1 += a[i] - x;
		else cnt2 += x - a[i];
	}
	return cnt1 * (1 - k / 100.0) >= cnt2;
}

int main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		sum += a[i];
	}
	double l = 0, r = sum;
	while (r - l > 1e-9){
		double mid = (l + r) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}
	printf("%.9lf", l);
	return 0;
}

T4

赛场上只想到暴力的做法，通过 $dfs$ 加上玄学剪枝骗到了 50 分

正解是将非负数标记成 1，负数标记成 0，求出最大更换数量，即每遇到一个与前一个不一样的就 $cnt++$。然后将连续的 1 串的长度从小到大排序，贪心一下，发现在一串 1 中（不在最前面和最后面）也使用防寒胎可以使 $cnt$ 减少 2；在最前面没有作用，最后面只能减少 1

50 pts：

#include <bits/stdc++.h>
using namespace std;

int n, k, cnt, ans = 0x3f3f3f3f;
int t[200005];

void dfs(int x, int res, int day, int f, int num){
	if (day > k || res >= ans || k - day < num) return ;
	if (k - day == num){
		int sum = 0;
		for (int i = 1; i <= n; i++){
			if ((t[i] < 0 && t[i - 1] >= 0) || (t[i] >= 0 && t[i - 1] < 0)) sum++;
		}
		ans = min(ans, sum);
		return ;
	}
	if (x == n + 1){
		ans = min(ans, res);
		return ;
	}
	if (f == 0 && t[x] < 0) dfs(x + 1, res + 1, day + 1, 1, num - 1);
	else if (f == 1){
		if (t[x] >= 0) dfs(x + 1, res + 1, day, 0, num), dfs(x + 1, res, day + 1, 1, num);
		else dfs(x + 1, res, day + 1, 1, num - 1);
	}
	else if (f == 0 && t[x] >= 0) dfs(x + 1, res, day, 0, num);
}

int main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> t[i];
		if (t[i] < 0) cnt++;
	}
	if (cnt == 0) return cout << "0", 0;
	if (cnt > k) return cout << "-1", 0;
	dfs(1, 0, 0, 0, cnt);
	if (ans == 0x3f3f3f3f) cout << "-1";
	else cout << ans;
	return 0;
}

正解：

#include <bits/stdc++.h>
using namespace std;

int n, k, cnt;
int t[200005];
vector<int> v;

int main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> t[i];
		if (t[i] < 0) cnt++;
	}
	k -= cnt;
	if (k < 0) return cout << "-1", 0;
	int len = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++){
		if (t[i] < 0) continue;
		int pos = i;
		while (t[pos] >= 0 && pos <= n) pos++;
		if (i > 1 && pos <= n) v.push_back(pos - i);
		else if (i > 1) len = pos - i;
		i = pos;
	}
	int ans = 0;
	if (cnt) ans = 2 * (v.size() + 1);
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++){
		if (k >= v[i]) k -= v[i], ans -= 2;
	}
	if (cnt && k >= n - len - 1) ans--;
	cout << ans;
	return 0;
}

CSP-J2 DAY5 复盘

T1

水题

AC！！！

非常简单，只需要记录每一个得分有多少人，然后模拟模拟增加一遍就好了

AC 代码：

#include <bits/stdc++.h>
using namespace std;

int n, k, cnt;
int a[105], mp[105];

int main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		mp[a[i]]++;
	}
	while (mp[k] != n){
		cnt++;
		for (int i = k - 1; i >= 1; i--){
			if (mp[i]) mp[i]--, mp[i + 1]++;
		}
	}
	cout << cnt;
	return 0;
}

T2

AC！！！

也挺水的，很容易想到贪心，根据奇偶性可以得到要取奇数个奇数，偶数取正数，只需要特判一下奇数中负数的情况就好了。

注意下标不要越界，赛场上发现样例有时能过，有时不能，最后发现是 $vector$ 下标越界了。

AC 代码：

#include <bits/stdc++.h>
using namespace std;

int t, n;
int a[100005];
vector<int> od, ev;

int main(){
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		ev.clear(), od.clear();
		for (int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			if (a[i] % 2 == 0) ev.push_back(a[i]);
			else od.push_back(a[i]);
		}
		sort(ev.begin(), ev.end(), greater<int>());
		sort(od.begin(), od.end(), greater<int>());
		int sum = 0;
		for (int i = 0; i < od.size(); i++){
			if (i % 2 == 1){
				if ((i + 1 < od.size() && od[i] + od[i + 1] <= 0) || i + 1 == od.size()) break;
				else sum += od[i];
			}
			else{
				sum += od[i];
				if (od[i] < 0) break;
			}
		}
		for (int i = 0; i < ev.size(); i++){
			if (ev[i] > 0) sum += ev[i];
			else break;
		}
		printf("%d\n", sum);
	}
	return 0;
}

T3

赛场上想用快速幂暴力水 10 分，结果一分没有骗到，听了老师的讲解后发现是一个离谱的 $dp$，先用一个三维 $dp$ 初始化一下选 $n$ 个数中与大的和相等的有多少个，然后再用一个二维 $dp$ 就好了

T4

赛场上有点脑瘫，只想到了枚举起点和终点，实际上可以只枚举起点，然后通过起点在往外搜两层，时间复杂度少了一个 $n$。

然后再排列组合就好了。

AC 代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, ans;
int vis[3005], cnt[3005], dep[3005];
vector<int> g[3005];

void dfs(int x, int st){
	if (st == 2) return ;
	for (int i = 0; i < g[x].size(); i++){
		int v = g[x][i];
		if (vis[v] == 1) continue;
		dep[v] = max(dep[v], st + 1);
		if (st == 1) cnt[v]++;
		vis[v] = 1;
		dfs(v, st + 1);
		vis[v] = 0;
	}
}

signed main(){
	scanf("%lld%lld", &n, &m);
	for (int i = 1, u, v; i <= m; i++){
		scanf("%lld%lld", &u, &v);
		g[u].push_back(v);
	}
	for (int i = 1; i <= n; i++){
		memset(dep, 0, sizeof(dep));
		memset(vis, 0, sizeof(vis));
		memset(cnt, 0, sizeof(cnt));
		vis[i] = 1;
		dfs(i, 0);
		for (int j = 1; j <= n; j++){
			if (dep[j] == 2) ans += cnt[j] * (cnt[j] - 1) / 2;
		}
	}
	printf("%lld", ans);
	return 0;
}

总结

赛场上先仔细思考能不能将暴力的复杂度降低一点，等到实在想不出来或超过预计时间了再去打暴力

第一遍检查代码的时候先检查数组有没有越界等低级错误，再去判断代码的逻辑错误

本栏目推荐文章
• 2023年度总结
• CSP-J/S 2023 游记
• Libevent [补档-2023-08-29]
• 本地套接字 [补档-2023-07-24]
• UDP通信 [补档-2023-07-22]
• 多路io复用Select [补档-2023-07-16]
• 多路io复用pool [补档-2023-07-19]
• 多路io复用epoll [补档-2023-07-20]
• socket编程 [补档-2023-07-10]
• OFBiz RCE漏洞复现（CVE-2023-51467）

复赛 2023 CSP复赛 试题csp-j 2023 复赛 随笔csp-s 2023 复赛 游记csp-s 2023 复赛2023 csp 复赛csp-s 2023 csp 复赛 游记2023 csp 复赛 试题 答案csp-j 复赛 试题csp-x 2023 复赛 简要 思路csp-j 复赛 游记csp-j csp