CSP 2022 游寄

· · 个人记录

八月

重心我放在了 OI 上，差不多每天都要上一车课，认识了很多大佬，其中和我关系最好的是djh @昒昕

在八月的下半月，终于意识到了初赛的重要性，于是开始狂刷初赛题。把普及全刷了一遍，提高几乎没看，因为我知道我看也是看天书，一时半会儿提升不了这么多。

感觉CSP2021真的很恶心，阅读程序变量名几乎没什么意义，而且题目计算量又很大，这是让我们模仿计算机？

九月

开——学——啦—— 作业前一天晚上补完了

看初赛选择题知识点，学到了什么随机存储，只读存储，局域网广域网城域网的缩写，但是考试都没用到。

然而我初赛很菜，去年就止步于初赛，一直到今天都在担心。而且们教练居然说今年报初赛的人多了，而且复赛可以腾出来的机器很少，那我岂不是要凉了？

而且通知了是线上考试，怎么回事啊！

9.18 初赛当天

上午考PJ，下午考TG，我还是非常担心的，考前还在看初赛知识点

J组准考证00916，S组准考证00514（514，悲）

9:30

开始考试！

看选择题第一题，什么鬼啊，完全不知道……

选择题做完已经过了40分钟了我很慌。而且搞了半天几乎没什么初赛必考知识点，子串我漏算了空串，我做对的选择排序还是我很早就知道的，坑人啊

选择题做完果断扔掉看阅读程序。阅读程序居然一眼看过去都看得懂？差点半场开香槟。

冷静下来做第一题，这次的PJ第一题比去年的 base64 要友好114514倍，第三题的开根也非常无聊，主要难点在第二题。我看懂了两个函数，但是我却不知道有什么巧算的方法，所以两道题目死算，但是死算需要大量时间，果断蒙题，利用赛前定的策略：如果一道题需要大量（一小时及以上）的时间，直接扔色子决定答案。

然后看完善程序，第一题简直是太智障了，第四题有个大写的 I 是什么鬼？我觉得是小写的 i 。老师还不给提问，差评。第二题广搜也挺无聊的，快速做完。最后两分钟检查出了一个错误，纯纯的犯病，惊险交卷。

11:35

考完和同学对了答案，同学用 dev c++ 来验证答案，没想到我选择题错了2-4题，阅读程序和完善程序全对？不是吧，而且我阅读程序三道蒙的都蒙对了？rp -= 2147483647 了，下午的S要凉了

1:30

进了 S 的会议，然后一直在玩 phigros，同学也在玩，可我们两个不在一个会议。

S 组就是 S 组，做事情贼有效率，上午的J是一个一个查准考证号的，结果到了S：“请大家打开摄像头，我看一遍你们的准考证”，这样就能让 45 分钟的巨大长时间变成了 1 分钟。

2:30

开始考试！

看第一题，nnd，Linux我不会用啊，随便蒙一个上去。阅读程序第七题考了三叉树，乐，这次选择题做了足足 1 小时，主要时间花在了看着我不会的指针题发呆。

然后发现阅读程序比往年友好很多。

三道题我都口胡了算法，然后赛后证明我三个算法都是对的，太棒了！！！但是第三题忘记负数怎么化进制了，我是憨批。完善程序第一题归并，我以前看过逆序对的归并代码，但是现在忘得差不多了，全凭感觉做，第二题简直就是在送分，难度差不多是 CSP-J 2019 完善程序最后一题，递归复读机。

4:30

比赛结束后暗暗告诉自己CSP 2022 RP += INF。不知道老师听见了没有。

初赛赛后

用民间数据自测了一下，J 是 92.5，S 是 68 ，不知道能不能过初赛。我问了下同学:

djh J 是 85 ，S是 45，whx J 是 76 ，chy J 91，S 62。

晚上看了J和S的讲评，老师都针对题目的大量错误做出了反馈，收获是知道了计数排序（不是基数排序，是计数排序）和桶排序的区别。然后补作业补到了半夜

PJ估分，TG估分

9.22

初赛分数出来了，PJ 91，TG 65；chy PJ和我一样，TG60；whx PJ 70+，TG 39.5 。。。

队长hcyTG达到了69.5，甚至比高中的学生还高！%%%

9.27

分数线出来了！我很顺利过了初赛，S复赛罚坐预定，但是分数线很低，我也不知道为什么，照道理说今年不仅简单，报的人多，复赛机位少，SH 应该分数线大升啊。。。

按道理说我应该很高兴的，可是当天得了重感冒，甚至有流感病毒，现在好了来更一下

10.2?

寄，复赛取消了，等会儿做做模拟赛吧

10.29

来做自测了

看T1发现是签到，心里瞬间百感交集，如果我这时候上场，或许已经一等了吧。。。

怀念了过去，顺便把T1切了。

随后运用战术：签到打完先把后面的题都看一遍，发现怎么题目都像洛谷月赛里的？？？太离谱了，没有一点点小故事，爷青结。

第二题发现是 whk 刚教的一二方程题，把它给切掉了。

随后看看 T3，看看 T4，觉得都没什么想法，保险起见，先开了我认为更简单的 T4.

暴力算法很简单，就是枚举任意两点之间，然后计算距离。然后过了20分钟发现好像直接可以预处理每两个点之间需要额外增加的点，然后进行dp运算即可，好像T4 就做完了？

一个多小时，300pts 到手，然后想一想T3，然后想到了做法，但是不想做了。

题解（目前先写PJ的A，B，D，其他等期中考试之后再补）

A

做法：可以用快速幂，时间复杂度降到log级

水题，只需要写好特判就可以了，时间复杂度 O(b)

#include<bits/stdc++.h>
using namespace std;
long long a,b,ans=1;
int main(){
    ios::sync_with_stdio(false);
    cin>>a>>b;
    if(a>1000000000){cout<<-1<<endl;return 0;}
    if(b==1){cout<<a<<endl;return 0;}
    if(a==1){cout<<1<<endl;return 0;}
    if(b>=60){cout<<-1<<endl;return 0;}
    for(int i=1;i<=b;i++){ans*=a;if(ans>1000000000){cout<<-1<<endl;return 0;}}
    cout<<ans<<endl;
    return 0;
}

B

做法：

由题，易得 p+q 和 pq，然后题目想要让你求 p,q 分别是多少，推导式子：

(p+q)^2=p^2+2pq+q^2 (p-q)^2=p^2-2pq+q^2 \therefore p-q=\sqrt{(p+q)^2-4pq}

由 p+q ，p-q 可得 （令 p>q）

p=\frac{p+q+(p-q)}{2} q=\frac{p+q-(p-q)}{2}

时间复杂度 O(k)

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,e,d;
int k;
int main(){
    ios::sync_with_stdio(false);
    cin>>k;
    while(k--){
        cin>>n>>e>>d;
        long long a=n-e*d+2;
        long long d=sqrt(a*a-4*n);
        if(d*d==a*a-4*n&&(a-d)%2==0&&a-d>0){
            long long ans1,ans2;
            ans1=(a+d)/2;ans2=(a-d)/2;
            cout<<ans2<<" "<<ans1<<endl;
        }else cout<<"NO"<<endl;
    }
    return 0;
}

C

做完以后看题解发现真的有人和我做法一样

考虑到一个式子，如果当前的数是1而且是|那么短路，如果当前数是0而且是‘|’也是短路，对于短路来说，如果后面有括号那么全跳，如果当前符号是‘|’而且是 & 短路那么短路结束，如果一个括号搜完了，也就是当前是）短路也结束。如果不是短路那么接下来继续判断是哪个短路就行了。30 min 搞定

#include<bits/stdc++.h>
using namespace std;
string s;
int len,flag,ans1,ans2,now,ans;
int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    len=s.size();
    for(int i=0;i<len;i++){
        if(flag){
            if(s[i]=='('){
                now=1;
                while(now!=0){
                    i++;
                    if(s[i]=='(')now++;
                    if(s[i]==')')now--;
                }
            }else if(s[i]=='|'&&flag==1)flag=0;
            else if(s[i]==')')flag=0;
            else if(s[i]=='&'&&flag==1)ans1++;
            else if(s[i]=='|'&&flag==2)ans2++;
        }else{
            if(s[i]=='1')ans=1;
            if(s[i]=='0')ans=0;
            if(s[i]=='&'&&ans==0){
                flag=1;
                ans1++;
            }else if(s[i]=='|'&&ans==1){
                flag=2;
                ans2++;
            }
        }
    }cout<<ans<<endl<<ans1<<" "<<ans2<<"\n";
    return 0; 
}

D

很好玩的一道题，做起来挺爽的。

读题发现这道题很像图论，所以我就转成了图论来做，一共 n 个点， n^2 条边。

第一步：暴力枚举每一条边，而两点之间的那条边的边权则是需要加的点数（即曼哈顿距离减一）。

第二步：用 Floyd 求全源最短路，得出任意两点之间的最短路。

第三步：dp，求出最长的联通块。

时间复杂度 O(n^3)

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=514;
int n,k;
long long x[maxn],y[maxn],f[maxn][maxn],ans=-1;
int distanc(int a,int b){return abs(x[a]-x[b])+abs(y[a]-y[b]);}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i!=j&&x[i]<=x[j]&&y[i]<=y[j])f[i][j]=distanc(i,j)-1;else f[i][j]=2147483647;}
    for(int kk=1;kk<=n;kk++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][kk]+f[kk][j]);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(f[i][j]<=k)ans=max(ans,distanc(i,j)-f[i][j]+k+1);
    cout<<ans<<endl;
    return 0;
}

那么我 J 算 AK 了？