CSP-J/S认证 2023游记_csp-j2023游记

初一，SH，第一次线下参赛，菜鸡选手。

万恶的CCF组织……

提示：

        非void函数一定要return！

        非void函数一定要return！

        非void函数一定要return！

否则，O2优化后果：       

        CE、RE、MLE、TLE、WA……

        J2：

                305分 -> 205分

        S2：

                140分 -> 40分

Ade，我的一等奖！Ade，我这一年的努力！

——鲁迅《从自信满满到直接爆零》

初赛

考试时高烧39°，好吧。

初赛也不是怎么很重要，尽量考到个过线就行了，没怎么复习。

 J84 S49 勉强勉强（居然还过了）

J1

普及组我们考场树的遍历那道题改了两次，害我前面折腾了12mins（居然有认为一个答案太明显，再改一次的，考试一个多小时了才改，也真是绝了，令人不由叹服）

考试时发昏，居然哈夫曼编码那道题最后琢磨25% 30% 45%谁大谁小，结论45%和25%一起，30%单独，结果没这个选项，随便选一个B，光荣扣分。

阅读程序J组比较简单，程序填空好像连环错了不少。

// 题目代码
int edit_dist_dp(string str1, string str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = ①;
            else if (j == 0)
                dp[i][j] = ②;
            else if (③)
                dp[i][j] = ④;
            else
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
        }
    }
    return dp[m][n];
}

见过离谱的没见过这么离谱的，算法竞赛谁会把dp数组开vector套vector，算你二阶张量学的挺好是吧，真是欺负人啊……

不可救药的民族中，一定有许多英雄，专向孩子们瞪眼。这些孱头们！孩子们在瞪眼中长大了，又向别的孩子们瞪眼。

——鲁迅

S1 

下午继续高烧，比分数线高那么一点，擦线通过，侥幸侥幸。

上来Linux、排列组合，马马虎虎，第三道直接比较时间复杂度，考场上直接极限运算，出的不得不让人叹为观止，不过可喜的是，仍然尽心尽力地给广大学子出了个θ而不是O

小明准备参加2022年的CSP-J/S第一轮认证， 在琢磨计数排序，基数排序和桶排序的区别， 以及研究O(n inf+1)这个无限还带常数的不标准大O复杂度之时， 转瞬间，一望无际的天空被撕裂出了一道巨大的口子，顿时电闪雷鸣， 他被一道来自外太空的暗紫色宇宙射线击中， 因此和车牌上的O和I一起， 来到了一个这个有趣的考场。

——2022CSP第一轮有感

第11道题考g++使用的，在糟糕IDE——DevC++的精心呵护下，我从未用过终端编译，从未用过Linux，不得不说，这估计也就是复赛我int f()不写return 0的主要导火索。

第14题最后统计没有用16进制，-2；第15题最后终于检查出来，我还纳闷呢，这么简单的模板是S组选择压轴？糊弄人呢。考试前最后我才检查出来，CCF为了出题，这种脑筋急转弯已经是层出不穷了，没事，去年（22年）的改掉的这道题似乎更搞笑一点：

int i, j, k = 0;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j*=2) {
        k = k + n / 2;
    }
}

不是吗？

完善程序和阅读开始瞎做，最后30分完善拿了3分，我随便全蒙一个字母貌似还多对一点，其实这次的确是简单的，2021年S组就吓人了：

(2) （ RMQ 区间最值问题） 给定序列{a0​,⋯,an−1​}, m 次询问，每次询问给定 l,r，求max{al​, ...,ar​}。

为了解决该问题，有一个算法叫 the Method of Four Russians ，其时间复杂度为 O(n+m) 

——2021年S1

听都没听过，还有如下：

A. 求圆的面积并

B. 求球的体积并

C. 求球的体积交

D. 求椭球的体积并

——2021年S1

另外你acos1/2写成pai/3会怎么样吗？

综上所述，今年除了如下已经很良心了。

std::vector<int> pre(a + mid, a + r);
std::vector<long long> sum(r - mid + 1);

（莫名其妙的码风）

复赛考前

趁着还有的那些时间，又赶忙复习了下，可惜我只记得main函数别漏写return0，天公不作美，不知道其他函数漏写return0仿佛更重要一点。

floyd、dijkstra ✔（没用上）

kruskal ✔（没用上，prim早忘了）

图、树的遍历 ✔（没用上）

前缀和与差分、树状数组、线段树、ST表、倍增、分块……一干RMQ、RSQ ✔（没用上）

区间DP ✔（用上了，然后T2我能想到栈像括号匹配那么O(n^2)做能得50分的得了O(n^3)的35分）

DFS、BFS ✔（用上了，T1爆零了）

string的操作 ✔（没用上）

一大堆stl ✔（没用上）

我真是悲催+倒霉……

复赛 

尽管我已是非常仔细地检查了所有可能爆零的地方，可惜人算不如天算，还是有非void函数没写返回值（准确的说我以前都不知道这事，希望解答）。

J组自我估分

100 100 100 10

实际（民间估分）

100 95 0 10

S组自我估分

100 35 15 0

实际（民间估分）

0 35 5 0

这就是void函数不写返回值的问题，可惜我uqe和lock还检查了好几遍，变了不少样例。

我确信我已发现了一种AC的做法，可惜这里的空白太少（下一篇再说），写不下。

爆零的代码：

uqe.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
 
const int maxn = 4e3+7;
int n, m;
 
int qpow(int a, int b) {
	if(b == 0) return 1;
	int tmp = qpow(a, b / 2);
	if(b & 1) return tmp * tmp * a;
	else return tmp * tmp;
}
 
int gcd(int a, int b) {
	if(b == 0) return a;
	else return gcd(b, a % b);
}
 
int ta, tb, qa, qb, tl;
string dv(int a, int b, bool chk) {
	if(b < 0) a = -a, b = -b;
	if(a == 0) {
		if(chk) ta = 0, tb = b;
		else qa = 0, qb = b;
		return "0";
	}
	int g = gcd(a, b);
	a /= g, b /= g;
	if(b < 0) a = -a, b = -b;
	if(chk) ta = a, tb = b;
	else qa = a, qb = b;
	if(b == 1) return to_string(a);
	else return to_string(a) + "/" + to_string(b);
}
 
string sq_div(int a, int b) {
	if(a == 0) {
		ta = a;
		tb = b;
		tl = 1;
		return "0";
	}
	int k = 1, l = 1;
	int ca = a;
	for(int i=2; i*i<=ca; i++) {
		int tmp = 0;
		while(a % i == 0) tmp++, a /= i;
		k *= qpow(i, tmp / 2);
		l *= qpow(i, tmp - tmp / 2 * 2);
	}
	l *= a;
	string t = dv(k, b, true);
	tl = l;
	if(l == 1) return t;
	else if(ta == 1 and tb == 1) return "sqrt(" + to_string(l) + ")";
	else if(ta == 1) return "sqrt(" + to_string(l) + ")/" + to_string(tb);
	else if(tb == 1) return to_string(ta) + "*" + "sqrt(" + to_string(l) + ")";
	else return to_string(ta) + "*" + "sqrt(" + to_string(l) + ")/" + to_string(tb);
}
 
 
int test(int a, int b, int c) {
	if(a < 0) a = -a, b = -b, c = -c;
	if(b*b-4*a*c < 0) cout << "NO" << endl;
	else if(c == 0) {
		if(a*b > 0) cout << "0" << endl;
		else cout << dv(-b, a, false) << endl; 
	}
	else {
		string q = dv(-b, 2*a, false);
		string p = sq_div(b*b-4*a*c, 2*a);
		if(tl == 1) {
			int p = qa * tb + qb * ta;
			int q = qb * tb;
			cout << dv(p, q, false) << endl;
		} else {
			if(q == "0") cout << p << endl;
			else if(p == "0") cout << q << endl;
			else cout << q << '+' << p << endl;
		}
	}
}
 
 
signed main() {
	cin.tie(0), cout.tie(0); 
	cin >> n >> m;
	for(int i=1, a, b, c; i<=n; i++) {
		cin >> a >> b >> c;
		test(a, b, c);
	}
	return 0;
}

（test函数返回值）

lock.cpp

#include<bits/stdc++.h>
using namespace std;
 
 
const int maxn = 10;
int n;
int stat[maxn][7];
int v[7];
int ans;
 
 
int dis(int a, int b) {
	return ((a - b) % 10 + 10) % 10;
}
int chk() {
	for(int i=1; i<=n; i++) {
		int difs = 2, ok = true, crt = true;
		for(int j=1; j<=5; j++) {
			if(!ok) difs -= 1;
			if(stat[i][j] != v[j]) {
				if(difs == 1 && dis(v[j], stat[i][j]) != dis(v[j-1], stat[i][j-1])) { crt = false; break; }
				if(difs <= 0 and ok == false) { crt = false; break; }
				ok = false;
			}
		}
		if(!crt or ok) return false;
	}
	return true;
}
 
int dfs(int st) {
	if(st == 6) 
		ans += chk();
	else {
		for(int i=0; i<=9; i++) {
			v[st] = i;
			dfs(st+1);
		}
	}
}
 
int main() {
	cin >> n;
	for(int i=1; i<=n; i++) for(int j=1; j<=5; j++) cin >> stat[i][j];
	dfs(1);
	cout << ans;
	return 0;
}

（dfs函数返回值）

有识之士估计已经发现我哪里错了。

另外，我的devc++居然编译选项没调，根本不知道。

J2

这次的题还比较良心，偏简单的，J组T1、T2不说了，T3巨简单（尽管我没写返回值RE）T4没写，估计也写不出来。

这次T3码量不大，分类讨论复杂点，但不需要什么算法，应该没有人不知道辗转相除法求gcd，比去年好，另外，CCF组织是一元二次方程考上瘾了是吧，参见去年J组T2解密，delta=b^2-4ac这是种病，得治。

T3考场上考出根号这一段我貌似还想了很久：

int k = 1, l = 1;
int ca = a;
for(int i=2; i*i<=ca; i++) {
	int tmp = 0;
	while(a % i == 0) tmp++, a /= i;
	k *= qpow(i, tmp / 2);
	l *= qpow(i, tmp - tmp / 2 * 2);
}
l *= a;

关于在根号n的时间里把a开成最简根式是否可行，也就是最后剩下来的a是否一定是素数。考场时写的乱七八糟的过程：

证明不存在正数p,q.p^2>n,q^2>n,pq|n.

PF: 采取反证法，若pq|n，则pq<=n，同时(pq)^2>n^2，pq显然大于n，矛盾，原命题得证，QED.

真是叹服……

S2

S组T1纯暴力（尽管我没写返回值TLE/MLE）

考试时我们华二紫竹考场提供Linux虚拟机，当然我一下也没用，DevC++虽然很差劲，但起码比我从来没用过的Vim和Emacs好一点，考试前虚拟机还坏了，还好一位老师帮我调好了，万分感谢！

S组T2好像其实也不难，我居然写了个朴素的区间DP，妄图拿到O(n^3)的分，不过估计35分还是稳的（T1爆零以后也没几分了）

T3好像可以模拟拿点分，但是我把漫长的时间放在T2的优化上了，尽管无功而返，我认为T3我应该是题没有清楚，导致我想拿的前三个测试点只拿了第一个，没事能骗到点都是好的。我还没看过题解，我后来觉得一个struct代表struct，一个struct代表struct xxx的对象是不是能拿到所有特殊ABC的分数。算了，T1都爆零了，往事随风去。

S组T4没有任何考虑的必要。

这次JS偏简单，估计分数线比往年高（JS分别爆零也没有考虑分数线的必要了）

重要的事说三遍

非void函数一定要return！

非void函数一定要return！

非void函数一定要return！

现在才初一呢，来日还有机会，不负光阴，不负韶华，明年再战，不要被Monotonic Queue了，退役之事，还远在天边呢。

等我再研究下题目（下次再爆零就不用研究了），或许会再发几篇题解，学习用，先写到这吧。

愿牛人保佑我，认识的人请在评论区回复。

祝大家不像我这样，别爆零，愿大家都在落幕的CSP中取得好成绩，加油啦~