考场技巧

LinGxIao_0230 · 2022-12-18 21:54:45 · 个人记录

很多时候，我们在考场上写不出正解（、

怎么办捏（？

• 拿部分分

  For example,CSP-S2022T1 考场代码。吐槽一句，今年的题目顺序有点毛病（

  一看，没思路啊，然后去看数据范围，发现——

  哇！k=0 好多分！而且最多转车 0 次的 暴力dfs 代码也很好写，然后不管三七二十一，先写个暴力。OK，40pts 到手。

  然后再看一下 n 的范围。多元最短路径很容易想到 Floyed ，时间复杂度为 O(n^3) ，先求出互相连通的点，然后再用 暴力dfs 跑一遍，就可以 最少 多拿 20pts。

  为什么是最少呢（？因为 中国收钱协会 （CCF） 的数据一年比一年水。

  自信一点，然后这题就拿了 70pts。

  具体怎么操作呢（？好问题。

  这里介绍一个好东西：数据分治。

  这个东西你肯定见过，没错，他也是可以自定义的。 具体用法：直接将分开写的多个程序分别装到不同的 $namespace$ 中即可，具体可以参考下面的代码。 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2502,INF=0x3f3f3f3f; int n,m,k;//因为两个部分分的判别需要k，所以k定义为全局变量 namespace subtask1{//k!=0 int cnt,g[N][N]; LL val[N],ans; bitset<N>vis; bool ok[N][N]; void init(){ for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=INF; for(int i=2;i<=n;i++) scanf("%lld",val+i); for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); g[u][v]=g[v][u]=1; } } void floyed(){ for(int p=1;p<=n;p++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][p]+g[p][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]--; for(int i=1;i<=n;i++) g[i][i]=k+2; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ok[i][j]=(g[i][j]<=k); //for(int i=1;i<=n;i++,putchar('\n'))for(int j=1;j<=n;j++)printf("%d ",ok[i][j]); } void dfs(int u){ //printf("%d ",u); if(u==1&&vis[1]&&cnt==5){ long long s=0; for(int i=1;i<=n;i++) if(vis[i]) s+=val[i]; // printf("%lld\n",s); ans=max(ans,s); return ; } if(vis[u]||cnt==5) return ; vis[u]=true; for(int v=1;v<=n;v++) if(ok[u][v]){ cnt++; dfs(v); cnt--; } vis[u]=false; } int main(){ init(); floyed(); dfs(1); printf("%lld",ans); return 0; } } namespace subtask2{//k==0 int cnt; LL val[N],ans; vector<int>g[N]; bitset<N>vis; void init(){ for(int i=2;i<=n;i++) scanf("%lld",val+i); for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } } void dfs(int u){ //printf("%d ",u); if(u==1&&vis[1]&&cnt==5){ long long s=0; for(int i=1;i<=n;i++) if(vis[i]) s+=val[i]; // printf("%lld\n",s); ans=max(ans,s); return ; } if(vis[u]||cnt==5) return ; vis[u]=true; for(auto v:g[u]){ cnt++; dfs(v); cnt--; } vis[u]=false; } int main(){ init(); dfs(1); printf("%lld",ans); return 0; } } int main(){ // freopen("holiday.in","r",stdin); // freopen("holiday.out","w",stdout); scanf("%d%d%d",&n,&m,&k);//读入后判定是哪个分区的 if(k!=0) subtask1::main(); else subtask2::main(); return 0; }

• 骗分

  For example,CSP-S2022T3

  考场上做到这题的时候已经没有时间了（

  于是，勇敢一点，毫不犹豫地全部输出 NO。

  感谢你，勇敢的孩子，45pts 到手。