2020 CSP-J 赛后总结
_脑波_
2020-11-13 22:38:54
## 这次考试纯属意外，心态炸了
------------
**~~我诅咒出题人没有肺泡，只有骨骼肌！（当场去世）~~**
------------
还是总结一下吧：
## 进入考场
我提前60分钟进入考场，找到座位后老师便让我出去等到考试前五分钟进入考场。比较有缘的是，我初赛时前面的人和后面的人都进入了第二轮，我们也是相邻而坐。我的同学ZC也来得很早，于是我们和一些其他学校的人攀谈起来。听说成都某外国语学校的光辉事迹——全校去考初赛为了补录名额，但在这里得到了成都某外国语学校的同学否认了。
## 开考
考试开始后，那个密码我的旁边的人一直输入输入不起，老师和我都过来看了，最后都不成。于是老师借了我的U盘拷到了他的电脑上（U盘是放在袋子里，放在教室前面的），于是浪费了10min。。。
## T1
[题目传送门](https://www.luogu.com.cn/problem/P7071)
before做T1时，我浏览了一下所有的题，发现最后一题好像类似一个我们模拟赛（教练自己出题）时考的奇怪的贪心题。心情大好，一下子就用2进制把第一题A了。
贴上你们最爱的代码（考试时）：
```cpp
#include<bits/stdc++.h>
#define N 35
using namespace std;
int n,w;
bool a[N]={},sf=0;
void cf(int num){
if(n==0)return ;
if(n%2==1){
w=num;
a[num]=1;
}
n=n/2;
cf(num+1);
}
int main(){
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
cin>>n;
cf(0);
if(a[0]==1)cout<<-1;
else{
for(int i=w;i>=1;i--){
if(a[i]==1)cout<<(1<<i)<<" ";
}
}
return 0;
}
```
## T2
[题目传送门](https://www.luogu.com.cn/problem/P7072)
我看到第二题，想到了大家都能想到的，每次加入一个数，然后sort一遍就可以了。但自己算了一下复杂度最多50分，所以开始想优化。开始想它每次都会插入一个数继续排序，于是就想到了每次插入一个后冒泡升上去（或者插入到指定位置，插入排序）+一个二分查找，但我觉得有点麻烦。后来，我看到了一个让我兴奋的东西，每人的分数<=600，伟大的桶排就出现了。桶排的思路也就是每次对应的桶++，然后倒序查找。
又是最美丽的代码（考试时）：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,w;
int tp[650];bool ok;
int xs,gs,maxn=0,yq;
int main(){
freopen("live.in","r",stdin);
freopen("live.out","w",stdout);
cin>>n>>w;
for(int i=1;i<=n;i=-~i){
cin>>xs;
maxn=max(maxn,xs);
++tp[xs];
gs=0;yq=max(1,int(i*w/100));ok=0;
for(int i=maxn;;i--){
if(tp[i]!=0){
int fj=tp[i];
while(1){
if(fj==0)break;
--fj;
++gs;
if(gs==yq){
cout<<i<<" ";
ok=1;
break;
}
}
}
if(ok) break;
}
}
return 0;
}
```
## T3
[题目传送门](https://www.luogu.com.cn/problem/P7073)
第三题我的第一个思路就是二叉树优化，但是呢，好像代码很难写，我又去想另一个思路。我于是发现了好像可以用记忆化搜索，就是记录每一次的处理值，如果没有改变，那后面的也不会改变。但是在存的时候却不好存，看到时间只有一小时了，所以我果断暴力栈。。。
又是代码。。。
```cpp
#include<bits/stdc++.h>
using namespace std;
char c[1000001];
bool x[100001];
stack<bool>n;
int s,q,fm;int sum,js;
char getch(){
++js;
return c[js];
}
bool ans(){
js=0;
char ch=getch();
while(ch!='\n'){
if(ch>='a'&&ch<='z'){
int num=0;ch=getch();
while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getch();
n.push(x[num]);
}
if(ch=='!'){
bool fj=n.top();
n.pop();
n.push(!fj);
}
if(ch=='|'){
bool fj1=n.top();
n.pop();
bool fj2=n.top();
n.pop();
n.push(fj1|fj2);
}
if(ch=='&'){
bool fj1=n.top();
n.pop();
bool fj2=n.top();
n.pop();
n.push(fj1&fj2);
}
ch=getch();
}
return n.top();
}
int main(){
//freopen("expr.in","r",stdin);
////////freopen("expr.out","w",stdout);
char dick=getchar();
while(dick!='\n'){
++sum;
c[sum]=dick;
dick=getchar();
}
c[sum+1]='\n';
cin>>s;
for(int i=1;i<=s;i=-~i)cin>>x[i];
cin>>q;
while(q--){
cin>>fm;
x[fm]=!x[fm];
cout<<ans()<<endl;
n.pop();
x[fm]=!x[fm];
}
}
```
## T4
[题目传送门](https://www.luogu.com.cn/problem/P7074)
第四题开始我一看是DP，看到上下左（并不是下左），哦嚯！我放弃了，所以怒写一个爆搜。写完之后发现还有30分钟，于是写了一个记忆化搜索，就开了3 * 1001 * 1001的数组，但我觉得好像这个数组会超，于是在最后写了一个
```cpp
cout<<sizeof(jyh);
```
发现没有超，心里十分开心！满以为自己能考省一。
代码如下（考试源代码）
```cpp
#include<bits/stdc++.h>
#define N 1002
using namespace std;
int jz[N][N],n,m;
long long jyh[3][N][N];
long long dfs(int x,int y,short syb/*0> 1^ 2\/*/){
if(jyh[syb][x][y]!=-1e18)return jyh[syb][x][y];
if(x==n&&y==m)return jz[x][y];
long long maxn=-1e18;
if(x==n){//x在最下面一行
maxn=max(dfs(x,y+1,0),maxn);// 向右走
if(syb==0)maxn=max(dfs(x-1,y,1),maxn);//下面边界，上一步是右可以向上走
}
if(y==m)maxn=max(dfs(x+1,y,2),maxn);
if(x==1){//如果在最上一行
if(y!=m){//如果y不在最后一列
maxn=max(dfs(x,y+1,0),maxn);//向右走
if(syb==0)maxn=max(dfs(x+1,y,2),maxn);//shang面边界，上一步是右可以向下走
}
}
if(x!=1&&x!=n&&y!=m){
maxn=max(dfs(x,y+1,0),maxn);
if(syb==0){
maxn=max(dfs(x-1,y,1),maxn);
maxn=max(dfs(x+1,y,2),maxn);
}
if(syb==1)maxn=max(dfs(x-1,y,1),maxn);
if(syb==2)maxn=max(dfs(x+1,y,2),maxn);
}
jyh[syb][x][y]=maxn+jz[x][y];
return maxn+jz[x][y];
}
int main(){
//freopen("number.in","r",stdin);
//freopen("number.out","w",stdout);
for(int i=1;i<=1001;i=-~i)
for(int j=1;j<=1001;j=-~j)
jyh[0][i][j]=-1e18,jyh[1][i][j]=-1e18,jyh[2][i][j]=-1e18;
cin>>n>>m;
for(int i=1;i<=n;i=-~i)
for(int j=1;j<=m;j=-~j)
cin>>jz[i][j];
cout<<dfs(1,1,0);
cout<<sizeof(jyh);
}
```
## 民间数据
当民间数据出来时，我就把发下来的代码交了上去，结果100+95（莫名T了一个点）+35+0，最后一题爆0令我很惊奇！我查看了代码，当仔细浏览一遍时，我呆住了，我的最后一行写着大大的“cout<<sizeof(jyh)”，我小心翼翼得删掉了它，交到洛谷上去。
……
AC，你通过了此题……
这是我最大的遗憾。。。
## 总结
~~这次难度偏低，总体在DP难度之下，最主要是我的最后一题，唉，明年努力吧！~~
### 常记洛谷刷咕，AC不知何处。大佬皆姓周，误入黑题深处。呕吐，呕吐，写一行while(true)