CSP-J 2020 游记
Zirnc
2020-11-09 13:30:09
> 他山之石，可以攻玉。
# CSP-J1
入学你校几乎两个月都在搞初赛。
~~结果初一还是只有两个人过了~~
最后是 $73.5$ 分，水过去了。
------
# CSP-J2
## Day 0
要去大学城的广大附中，就去住酒店了。
在 tjl 大佬房间里 ~~玩~~，其实是在看凤凰台。
依稀记得那晚上拜登和特朗普的比分是 264 : 214，林郑去北京见韩正了。
~~CCTV-7 上面中科院在帮农民种橘子~~？
十点多就回去昏昏沉沉地睡了，还挺香（
## Day 1
早上六点半就醒了。
在酒店吃了顿自助早餐，真香。
到处都是石实的大佬 %%% 。
然后搭着同校热心家长的车前往广大附中。
门口还挺热闹的。
在门口好像发生了许多事情：
- 黄老师身份证不见了，~~其实藏在袋子里~~
- 某大佬没带准考证
- 还有没带粤康码的
于是感到很庆幸，没入考场的时候也是一场考验。。所以说带齐资料很重要。
很快就进考场了。
电脑有 8G 内存，装的是 Windows 10 神州网信政府版，感觉只是开始菜单看上去稍有不同。
下发题目之后几分钟我还在打 A+B，打完之后才一愣一愣地抄密码解压题目。
翻了一下，发现第一题好难，于是从第二题开始做。
T2 刚开始竟然用了 sort，到了最后试大样例的时候才看到一卡一卡的，于是又改成了插入排序，以为没问题了。
```cpp
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) { return a > b; }
int a[100005];
int main()
{
int n, w;
scanf("%d%d", &n, &w);
for (int i = 0; i < n; i++) {
int inp;
scanf("%d", &inp);
int j = 0;
for (; j < i; j++) {
if (a[j] < inp) break;
}
for (int k = i; k >= j; k--) {
a[k+1] = a[k];
}
a[j] = inp;
int planNum = max(1, (int)((i+1)*0.01*w));
printf("%d ", a[planNum-1]);
}
return 0;
}
```
然后 T3 看了好久才弄懂，就暴力 stack 了。
```cpp
#include <iostream>
#include <stack>
#include <algorithm>
#include <string>
#include <fstream>
#include <cstdio>
using namespace std;
int n;
int a[100003];
int main()
{
string expr;
getline(cin, expr);
const int exprlen = expr.length();
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int q;
scanf("%d", &q);
stack<int> s;
for (int i = 0; i < q; i++) {
int t;
scanf("%d", &t);
a[t] = !a[t];
string cur;
for (int j = 0; j < exprlen+1; j++) {
if (j == exprlen || expr[j] == ' ') {
if (cur == "!") {
int t = s.top();
s.pop();
s.push(!t);
} else if (cur == "&") {
int t = s.top();
s.pop();
int t2 = s.top();
s.pop();
s.push(t && t2);
} else if (cur == "|") {
int t = s.top();
s.pop();
int t2 = s.top();
s.pop();
s.push(t || t2);
} else if (cur[0] == 'x') {
int xb = 0;
for (int k = 1; k < cur.length(); k++) {
xb *= 10;
xb += cur[k]-'0';
}
s.push(a[xb]);
}
cur.clear();
} else cur += expr[j];
}
printf("%d\n", s.top());
if (!s.empty()) s.pop();
a[t] = !a[t];
}
return 0;
}
```
接下来才开始构思第一题，一直摸不着头绪，就随随便便写了一个爆搜，枚举 2 的幂相加。
```cpp
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
int n;
const int a[23] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608};
int ansn = 0, ans[24];
int dfs(int step, int sum) {
if (sum > n) return 0;
if (step > 23) return 0;
if (sum == n) {
return 1;
}
for (int i = 1; i <= 22; i++) {
int t1 = dfs(step+i, sum + a[step]);
if (t1) {
ans[ansn++] = a[step];
return 1;
}
}
}
int main()
{
cin >> n;
if (n % 2 != 0) {
cout << -1 << endl;
return 0;
}
for (int i = 0; i < 23; i++) {
if (n == a[i]) {
cout << a[i] << endl;
return 0;
}
}
dfs(0, 0);
for (int i = 0; i < ansn; i++) {
cout << ans[i] << ' ';
}
return 0;
}
```
第四题直接无脑爆搜，能拿到暴力分就 ok。
```cpp
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
long long ans = -99999999999;
int a[1005][1005], n, m;
bool vis[1005][1005];
const int dx[3] = { -1, 1, 0 };
const int dy[3] = { 0, 0, 1 };
void dfs(int x, int y, long long sum) {
if (x == n && y == m) { // 终点
ans = max(ans, sum+a[x][y]);
return ;
}
for (int i = 0; i < 3; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
if (vis[nx][ny]) continue ;
vis[nx][ny] = 1;
dfs(nx, ny, sum + a[x][y]);
vis[nx][ny] = 0;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
vis[i][j] = false;
}
}
dfs(1, 1, 0);
printf("%d\n", ans);
return 0;
}
```
出了考场之后和 tjl 对答案，才知道第一题考的是二进制，第二题要用桶排序。。。
然后那时竟然还挺乐观的，觉得我的也没问题。。。
甚至还开始讨论有没有 1= 。。。。。。。。。
直到洛谷上了民间数据自测。
$100 + 80 + 30 + 15 = 225$
还是看看能不能有二等吧。。
总之达到了考前的期望，考后还是太自信了一点点。也没什么遗憾，正常发挥出了自己的水平。
那么就：
**CSP-J/S 2021 RP++**
------
**2020/11/25 UPD**: CCF 官方成绩 $85+85+30+15=215$