CSPJ组脑子瓦特记
luomuran
2020-11-08 14:31:37
初赛80，进了就好。
------------
坐标zj，jh，紫金港赛区
------------
因为不是hz人所以星期五下午翘了3节课（刚好不用参加英语竞赛了~开森，然后可亲可敬可爱的英语老师说免试进复赛！！！），和其他两个学校的同学一起坐大巴，6点半的样子到了oym酒店
（~~杭州的路是真的堵啊！！！mb还那么多单行线，掉个头就要十多分钟，心梗了啊~~）
晚上本来还想去无印良品，还答应了同学帮忙带货。结果吃完饭就7点多了，然后去老师房间听老师~~bb~~到8点半。看了看百度地图，发现最快的是骑自行车，但是那个破地方前不着村后不着店连共享单车都没有QAQ。打的的话要20多分钟肯定是来不及。
------------
8点不到的时候就到了xj门口，进学校。
比赛前老师说的是可以先打模板，就是不能看题目。但其实考试前连模板都打不了，监考老师一直在巡逻，不让动鼠标&键盘。无聊.jpg。幸好是win7系统，可以玩桌面小工具库里把方块移来移去的那啥……额……名字忘了
（顺便说一句，这次主办方~~很有良心~~地开了文件扩展名。虽然老师前一天晚上刚讲了怎么开扩展名，可我还是搞了半天也没找到那个什么高级选项，最后发现其实本来就是开的？？？……IEE）
8:30 考试开始！！！
9点零几的时候就敲完了T1T2。
T1是真的……没法说，数据范围里都那么~~直白~~地说到了奇数。这也太明显了叭……是奇数就输出-1；是偶数就二进制拆分
T2，成绩在600以内，还是非负整数。桶排！！！Hmm……结果脑子瓦特了（详情见代码）
T3一开始没思路（连模拟都打不出来），就先去了T4.一开始觉得是记搜，然后发现不对。因为从不同方向走到同一点对后面的影响是不同的。~~记搜不行就爆搜，dfs走起！然后我还迷之自信地以为暴力能拿七八十分？？？~~事实证明是我太天真了，做了几组数据发现只能拿十来分QWQ。枯了
T3最后打了个模拟（想了好久好久呢~）~~我太天真了以为模拟拉满，然后今天测了一下30分嘤嘤嘤~~。
------------
放代码放代码
T1
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;
int s[30]={1},len=-1,n,u[30];
int main()
{
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
scanf("%d",&n);
if(n%2==1)
{
printf("-1");
return 0;
}
while(n)
{
u[++len]=n%2;
n/=2;
}
for(int i=1;i<=len;i++) s[i]=s[i-1]*2;
for(int i=len;i>=0;i--)
{
if(u[i]) printf("%d ",s[i]);
}
return 0;
}
```
T2
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;
int n,tong[605],w,x,num,sum,sm=605,la;
int main()
{
freopen("live.in","r",stdin);
freopen("live.out","w",stdout);
scanf("%d%d",&n,&w);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
sm=min(sm,x);
la=max(la,x);
tong[x]++;
num=max(1,i*w/100);
sum=0;
int j;
for(j=la;j>=sm;j--)
{
for(int k=1;k<=tong[j];k++) sum++;//改成sum+=tong[j]就满分了啊啊啊！！！我tm脑子有病QAQ
if(sum>=num)
{
printf("%d ",j);
break;
}
}
}
return 0;
}
```
T3
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;
string s;
int num[100005],ss[1000005],a[100005],n,q,qe,len,sl;
int w(int l,int r)
{
int shuzi=0,zifu=0;
if(l==r&&ss[l]<=1) return ss[l];
else if(ss[r]==2) return !w(l,r-1);
else if(l+2==r&&ss[l]<=1&&ss[l+1]<=1&&ss[r]>=2)
{
if(ss[r]==4) return ss[l]&&ss[l+1];
if(ss[r]==3) return ss[l]||ss[l+1];
}
else for(int i=r-1;i>=1;i--)
{
if(ss[i]<=1) shuzi++;
else if(ss[i]>=3) zifu++;
if(shuzi-1==zifu)
{
if(ss[r]==4) return w(l,i-1)&&w(i,r-1);
if(ss[r]==3) return w(l,i-1)||w(i,r-1);
}
}
return 0;
}
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
getline(cin,s);
sl=s.size();
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=0;i<sl;i++)
{
if(s[i]==' ') continue;
if(s[i]=='!') ss[++len]=2;
else if(s[i]=='|') ss[++len]=3;
else if(s[i]=='&') ss[++len]=4;
else
{
int sum=0;
for(i++;s[i]!=' ';i++)
sum=sum*10+s[i]-'0';
ss[++len]=a[sum];
num[sum]=len;
}
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d",&qe);
ss[num[qe]]=!ss[num[qe]];;
printf("%d\n",w(1,len));
ss[num[qe]]=!ss[num[qe]];
}
return 0;
}
```
T4
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[1005][1005],f[1005][1005],u[1005][1005],
bx[4]={0,1,-1,0},by[4]={0,0,0,1};
bool check(int x,int y)
{
return (x>=1&&x<=n&&y>=1&&y<=m&&!u[x][y]);
}
void dfs(int x,int y,int sum)
{
int nx,ny;
f[x][y]=max(f[x][y],sum);
for(int i=1;i<=3;i++)
{
nx=x+bx[i];
ny=y+by[i];
if(check(nx,ny))
{
u[nx][ny]=1;
dfs(nx,ny,sum+a[nx][ny]);
u[nx][ny]=0;
}
}
}
int main()
{
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=-10005;
u[1][1]=0;
dfs(1,1,a[1][1]);
printf("%d",f[n][m]);
return 0;
}
```
------------
考试的最后半小时真的是思维大爆发的时刻
先是发现T4是dp，因为不能往左走，所以没有后效性。然鹅我是个只会背背包模板的蒟蒻，状态转移方程推死也推不出来。~~算了算了，暴力出奇迹~~
T2做了组数据，发现超时了。然而我就是没有看出自己多加了一层循环，还在想用前缀和or差分？？？IEE
------------
虽然说可以带吃的（事实上基本所有人都带了），但其实吃得挺少。一方面是没时间，另一方面也不怎么饿。
------------
~~经验传授？？？：~~
# dp一定一定一定要学好！！！！
什么暴力拿一等，那前提是暴力分得拿满！！！
相信我，暴力分拿满并不容易。不是说题目难，而是考场上脑子经常出问题。如果想稳一点的话最好靠dp拿拿分。
------------
好了好了不管怎样考完就好了，搞whk去了（11.16期中考，rp++！）