部分分
2025-07-26 17:15:32
发布于:浙江
依旧是前言
刚好赶着 2025 年的 csp,想着可以蹭蹭热度。又突然想到这类专题应该每个机构在考前都会讲,根本轮不到我,可是想到的时候我已经写好多了,果断决定放弃“#创作计划#”(笔者不想当小丑),继续硬着头皮写下去。
另外说明一下:如果您已经得到了 csp-j 1= 或是更高的奖项,那么您没必要继续阅读,因为笔者没有权力去教您部分分。
正文
事实上,如果您是一名 OI 的初学者,想要今年得到 csp-j 1= 的成绩,但因为实力问题,无法在赛场上场切 T3,但可以确保 AC 前两题,那么本篇文章将会非常适合您。
为了保证赛场上不要由于心态问题发挥失常,练习标准肯定要高一些,所以接下来我们就以强省(ZJ)为分数线 (主要原因是我是 ZJ 进行练习。
人)
例题
2025.06 GESP 八级 T2
口说无凭,我们以一道例题举例 - P13020,题目呢是今年六月份 GESP 八级的第二题,难度标的是绿,而去年 csp-j T3 是黄,所以只要能保证可以场切绿,在赛场 1= 可是轻轻松松。
可是不然,我们是蒟蒻,做不到,但也不能空手而归,所以即使无法 AC,也要拿点部分分。
先读题面,大致意思就是给定一棵无根树,求有多少种不同的 DFS 序。显然对于 的数据。如果只是枚举每个点为根进行树形 DP,复杂度为 ,显然过不了。但是我们可以过 的数据,这样就无脑获得了 分的好成绩,再加上前两题的分数,共 ,在一些弱省中已经可以获得 1= 了,可是我们的目标是强省 1=,所以还不够。
再仔细读数据范围,容易发现还有 的测试点满足给出的无根树是一条链,由于笔者写的不是题解,所以对思路不加赘述,但事实上,如果您勤于思考,容易发现答案始终为 。那么这样我们就共得到了 的成绩,只需要在 T4 中得到 分即可获得 的成绩,就达到了 ZJ 去年 1= 的分数线。另外再说明一点,去年 T3 的难度为黄,而刚刚的例题难度为绿,所以真正在赛场上我们可以在 T3 取得的分数 。
2023 csp-j T4
当然,如果只是用 GESP 的题目,显然不具备信服力,所以我又找了一道 csp 真题 P9751,这是 2023 年的 T4,该题部分分巨多,让我们一个一个讲。这里事先声明,当年 csp-j 1= ZJ 的分数线是 ,同样假设 AC 了前两题,所以我们需要在后两题中得到 分。
对于这种存在 -1
又没有多测,显然可以直接输出,能拿多少看 CCF 愿意施舍多少,在这道题中可以得到 分。
对于 且 的情况,我们直接跑一个最短路板子即可,可以得到 分,再加上上面的 分,共 分。事实上当年 T3 可以非常轻易的得到 分,如果这样我们可以获得 1= 了,可以分卡得这么紧,如果挂分就炸了。所以展示容错
另外这边笔者去年备考 csp 的时候写了一份 分的代码,过的测试点非常神奇,由于自己忘记做法了,所以就贴一下代码(放附录了),读者可以自己思考一下(((
然后我们可以通过上述两份代码进行合并取并集,就可以得到一份 分代码,具体代码也放附录了。
继续观察题面数据,容易发现对于 时,显然从 时刻进入园区时最优的,因为所有地点都没有时间限制。而当 则满足当走到园区门口时可以直接出来而不需要等待,可以用神秘 BFS 过掉。这样我们就可以得到高贵的 分,就算 T3 爆零,就算 T2 挂 分,我们依旧可以获得 1=。
朋友请注意,这只是 T4,如果我们 T3 也这么玩一遍,将会得到多少分呢?
实战练习
多说无益,还是让我们直接模拟去年的 csp 试试效果(您可以先自己做一遍,题目在题库里可以找到,记住,一定要模拟 OI 赛制,不要交太多遍)。
T1
用 map
或是 set
都可以做,这里就不讲了。
T2
别看题面长,其实难度比 23 年的 T2 简单多了,按题意模拟即可,不过记住多测清空(反正我有个朋友就是这样 T2 爆零的
T3
T3 往往都是决定 1= 的重头戏。
先是暴力的 ,不要白不要。
然后注意特殊性质 A 和 B,都和 有关,这就暗示了正解的突破口将从 展开。经过肉眼观察容易发现,数码 8
所需火柴棒刚好为 且最大,去年坐在凳子上的笔者突然想到了一个很简单又很容易忽视的特点“比较数字大小优先比较数位”,换句话说,为了让数字最小,一定要先让数位最少,而让数位最少,就一定要保证每一位所用火柴棒最多也就是尽量用 8
。那么就简单了,对于 ,显然将每一位都放 8
最优,对于 ,则选择先放 10
,然后跟着放若干位 8
。
再结合暴力的 分,我们共得到了 分,总分 ,这也就达到了笔者去年的水平。
然后再仔细想,正解就一目了然了,对 的结果分讨。无奈的是,笔者写完 分后将所有时间投入 T4 无果,在最后 min 想出正解思路,并超了 分钟写完了代码,这个时候监考员已经走到我身边,我根本不敢动,虽然代码写好了,但由于没有测样例,所以最终还是不敢按下 Ctrl+s
,遗憾离场。
T4
md,T4 真毒瘤,这里就不讲了 (其实是累了)。
总结
只要在赛场上注意观察每道题的数据范围,即使不会也可以得到好看的分数,从而斩获 1=。
最后祝大家在今年的 csp 中常常发挥,取得自己满意的成绩!
代码
如果您需要上述六道题的 AC 代码,可以私信我,一般都会给出的。
附录
分代码如下:
#include<bits/stdc++.h>
using namespace std;
int n, m, k, u[20005], v[20005], a[20005], road[10005][10005];
long long dp[10005];
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
dp[i] = 9e18;
for (int j = 1; j <= n; j++) {
road[i][j] = -1;
}
}
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> a[i];
road[u[i]][v[i]] = a[i];
}
dp[1] = k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
continue;
}
if (road[i][j] != -1) {
if (dp[i] >= road[i][j]) {
dp[j] = min(dp[j], dp[i] + 1);
} else {
dp[j] = min(dp[j], (long long)road[i][j] + 1);
}
}
}
}
if (dp[n] == 9e18) cout << "-1";
else cout << ceil(1.0 * dp[n] / k)*k;
return 0;
}
分代码如下:
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
namespace work1 {
int u[20005], v[20005], a[20005], road[10005][10005];
long long dp[10005];
void work() {
for (int i = 1; i <= n; i++) {
dp[i] = 9e18;
for (int j = 1; j <= n; j++) {
road[i][j] = -1;
}
}
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> a[i];
road[u[i]][v[i]] = a[i];
}
dp[1] = k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
continue;
}
if (road[i][j] != -1) {
if (dp[i] >= road[i][j]) {
dp[j] = min(dp[j], dp[i] + 1);
} else {
dp[j] = min(dp[j], (long long)road[i][j] + 1);
}
}
}
}
if (dp[n] == 9e18) cout << "-1";
else cout << ceil(1.0 * dp[n] / k)*k;
}
}
namespace work2 {
int d[10010];
bool vis[10010];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
vector<pair<int, int>>e[10010];
void work() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
for (int i = 1; i <= m; i++) {
int u, a, v;
cin >> u >> v >> a;
e[u].push_back(make_pair(v, a));
}
int s = 1, t = n;
memset(d, 0x3f, sizeof d);
d[s] = 0;
q.push({0, s});
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto j : e[u]) {
int v = j.first, w = 1;
if (d[v] >= d[u] + w) {
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
cout << d[t];
}
}
int main() {
cin >> n >> m >> k;
if (k == 1) work2::work();
else work1::work();
return 0;
}
全部评论 4
d
昨天 来自 浙江
0还好我第一次考,T3直接想正解去了,省了一大堆时间(((
6天前 来自 湖南
0cao
6天前 来自 浙江
0
T4本来骗了前三个点,结果只拿了5分
6天前 来自 湖南
0为了不被骂,把帖子放灌水了
6天前 来自 浙江
0(((
6天前 来自 浙江
0
有帮助,赞一个