浅谈骗分

QZKago_Req · 2024-06-06 19:56:15 · 算法·理论

本文主要讲几种骗分的方式。

万能输出

很多题目都会有这句话“若无解，请输出 -1”。这时，我们直接输出就能骗到 10 分，20 分，甚至 30 分！举个例子：
P2252 [SHOI2002] 取石子游戏|【模板】威佐夫博弈
这题要求计算博弈论，但是只有三种情况，于是我们直接输出 1，这题由于数据过水，直接就拿到了 70 分！还有其他的题，这里不讲。

模拟暴力

输出无解是个好方法，但是有些题设置无解的测试点极少，还有的，使用捆绑测试，使你一分不得，这时，就需要用到模拟了。比如说：
P3372 【模板】线段树 1
本题需要使用 O(m \log{n}) 的线段树，但是，我们用如下代码打一个暴力：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,a[100010],op,x,y,k;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            for(int j=x;j<=y;j++) a[j]+=k;
        }else if(op==2){
            cin>>x>>y;
            int sum=0;
            for(int j=x;j<=y;j++) sum+=a[j];
            cout<<sum<<endl;
        }
    }
}

虽然无法通过，但是也是直接骗到了 70 分，而如果打线段树，可能需要花费 20 分钟，可是，3 分钟都能拿 70 分，为什么要白白浪费 20 分钟呢？这就给后面的难题留下了很多的时间。

搜索

搜索是暴力中一个重要算法，骗分时，一般用基础的 DFS 或 BFS 就行，但 DFS 简洁明了，这对于你的骗分是至关重要的。比如说，一些动态规划题，可以 DFS；数学题，可以 DFS；剪枝的题，更能 DFS。下面以一道动态规划题为例，解释一下 DFS 骗分。
P1048 [NOIP2005 普及组] 采药
虽然说很水，但是还是介绍一下骗分方法，我们对准 30\% 的数据，n\le10，很明显，可以用 O(2^n) 的 DFS 算法骗分。

void DFS(int d,int c){
    if(d==n){
      ans=max(ans,c);
      return;
    }
    DFS(d+1,c+w[i]);
    DFS(d+1,c);
}

上面暴力枚举了每种药选或不选，得 30 分。

猜想——另辟蹊径

听天由命

如果你认为自己 rp++，可以试试随机数，现展示一下代码：

#include<cstdlib>//随机函数头文件
#include<ctime>
#include<cstdio>
#include<iostream>
int rnd(int l,int r){
    return l+rand()%(r-l+1);
}
int main(){
    srand(unsigned(time(0)));
    cout<<rnd(l,r);//输出从l到r之间的随机数
}

我们还是拿威佐夫博弈举例，在第一章，我们已经用输出得到 70 分，现在我们试试用随机数做：

#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<iostream>
int rnd(int l,int r){
    return l+rand()%(r-l+1);
}
int main(){
    srand(2252);
    cout<<rnd(0,2)-1;
}

如代码，随机输出三种结果，随机种子是作者精心挑选的，此代码得 80 分。

人脑打表

在数据范围很小时，可以打表解决问题，表中的每一个数据都代表一个情况，先看一个例子：
P1817 棋盘染色
这题要用插头 DP 做，但是注意到 n\le 7 和 m \le 8，并且没有其他输入，直接用一个 DFS 打表：

#include<bits/stdc++.h>
using namespace std;
int v[10][10],n,m,dx[5]={0,0,1,-1},dy[5]={1,-1,0,0};
long long ans;
void dfs(int x,int y){
    if(x<1||x>=n||y<1||y>=m){
        ans++;
        return;
    }
    v[x][y]=1;
    for(int i=0;i<=3;i++){
        if(!v[x+dx[i]][y+dy[i]]){
            dfs(x+dx[i],y+dy[i]);
        }
    }
    v[x][y]=0;
}
int main(){
    for(n=1;n<=7;n++){
        for(m=1;m<=8;m++){
            for(int i=1;i<m;i++){
                v[0][i-1]=0;
                v[0][i]=1;
                dfs(1,i);
            }
            v[0][m-1]=0;
            for(int i=1;i<n;i++){
                v[i-1][0]=0;
                v[i][0]=1;
                dfs(i,1);
            }
            cout<<ans*2<<endl;
        }
    } 
}

然后把数据填入表中：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
    cin>>n>>m;
    if(n==1&&m==1) cout<<0;
    if(n==1&&m==2) cout<<2;
    if(n==1&&m==3) cout<<4;
    if(n==1&&m==4) cout<<6;
    if(n==1&&m==5) cout<<8;
    if(n==1&&m==6) cout<<10;
    if(n==1&&m==7) cout<<12;
    if(n==1&&m==8) cout<<14;
    if(n==2&&m==1) cout<<2;
    if(n==2&&m==2) cout<<12;
    if(n==2&&m==3) cout<<30;
    if(n==2&&m==4) cout<<56;
    if(n==2&&m==5) cout<<90;
    if(n==2&&m==6) cout<<132;
    if(n==2&&m==7) cout<<182;
    if(n==2&&m==8) cout<<240;
    if(n==3&&m==1) cout<<4;
    if(n==3&&m==2) cout<<30;
    if(n==3&&m==3) cout<<104;
    if(n==3&&m==4) cout<<286;
    if(n==3&&m==5) cout<<700;
    if(n==3&&m==6) cout<<1598;
    if(n==3&&m==7) cout<<3488;
    if(n==3&&m==8) cout<<7390;
    if(n==4&&m==1) cout<<6;
    if(n==4&&m==2) cout<<56;
    if(n==4&&m==3) cout<<286;
    if(n==4&&m==4) cout<<1228;
    if(n==4&&m==5) cout<<4862;
    if(n==4&&m==6) cout<<18368;
    if(n==4&&m==7) cout<<67206;
    if(n==4&&m==8) cout<<240180;
    if(n==5&&m==1) cout<<8;
    if(n==5&&m==2) cout<<90;
    if(n==5&&m==3) cout<<700;
    if(n==5&&m==4) cout<<4862;
    if(n==5&&m==5) cout<<32000;
    if(n==5&&m==6) cout<<204294;
    if(n==5&&m==7) cout<<1274660;
    if(n==5&&m==8) cout<<7807790;
    if(n==6&&m==1) cout<<10;
    if(n==6&&m==2) cout<<132;
    if(n==6&&m==3) cout<<1598;
    if(n==6&&m==4) cout<<18368;
    if(n==6&&m==5) cout<<204294;
    if(n==6&&m==6) cout<<2228788;
    if(n==6&&m==7) cout<<23896710;
    if(n==6&&m==8) cout<<252488208;
    if(n==7&&m==1) cout<<12;
    if(n==7&&m==2) cout<<182;
    if(n==7&&m==3) cout<<3488;
    if(n==7&&m==4) cout<<67206;
    if(n==7&&m==5) cout<<1274660;
    if(n==7&&m==6) cout<<23896710;
    if(n==7&&m==7) cout<<441524056;
    if(n==7&&m==8) cout<<8056291934;
}

注意这里用了一个一个判断，是打表的另一种写法。打表非常高效，上述代码能直接 AC。缺点在于局限性很大，只有少数题目可以使用。

你贪心吗

奇妙的算法

众所周知，贪心作为一种常用算法，简单且高效，这里不多谈贪心算法，感兴趣的读者可以搜集资料。

本身就要贪心

前面讲解了多种骗分方法，于是我们根据数据范围，使用不同的骗分方法，把骗的分结合起来，如：

#include<bits/stdc++.h>
using namespace std;
void init(){
    /*输入部分*/
}
int main(){
    init();
    if(/*条件1*/) //
    else if(/*条件2*/) //
    ....
}

这样十分十分的凑，就可以拿到更多分。

c++专属福利

请 P 党跳过此章。

头文件 algorithm 包含了各种 c++ 自带的容器、算法，关于基本函数，可以参考这个网址。这里有两道题用 STL 可以水过去:
P3369 【模板】普通平衡树
P3391 【模板】文艺平衡树
巨佬会写平衡树，我们只好用STL水过去了。

#include<bits/stdc++.h>
using namespace std;
vector<int>m;
int op,x,q;
int main(){
    cin>q;
    while(q--){
        cin>>op>>x;
        if(op==1) m.insert(lower_bound(m.begin(),m.end(),x),x);
        if(op==2) m.erase(lower_bound(m.begin(),m.end(),x));
        if(op==3){
            cout<<lower_bound(m.begin(),m.end(),x)-m.begin()+1<<endl;
        }
        if(op==4) cout<<m[x-1]<<endl;
        if(op==5) cout<<*--lower_bound(m.begin(),m.end(),x)<<endl;
        if(op==6) cout<<*upper_bound(m.begin(),m.end(),x)<<endl;
    }
}

#include<bits/stdc++.h>
#include<ext/rope>
using namespace __gnu_cxx;
using namespace std;
rope<int> x,y;
int n,m,l,r;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) x.append(i),y.append(n-i+1);
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        rope<int> f=x.substr(x.begin()+l-1,x.begin()+r);
        x=x.substr(x.begin(),x.begin()+l-1)+y.substr(y.end()-r,y.end()-l+1)+x.substr(x.begin()+r,x.end());
        y=y.substr(y.begin(),y.end()-r)+f+y.substr(y.end()-l+1,y.end());
    }
    for(int i=0;i<n;i++) cout<<x[i]<<" ";
}

可以发现，上百行的平衡树被我们用 STL 取代了（第二个并非 STL，是另一种高效容器，使用需谨慎）。

其他与实战

下面是一些针对性的骗分习题。

第一章
- P3366 【模板】最小生成树
- P8819 [CSP-S 2022] 星战
- P1083 [NOIP2012 提高组] 借教室
第二章
- P3372 【模板】线段树 1
- P3373 【模板】线段树 2
- P3369 【模板】普通平衡树
- P3391 【模板】文艺平衡树
第三章
- P1044 [NOIP2003 普及组] 栈
- P1380 T型骨牌
第四章把前面的题组合起来
第五章
- B3614 【模板】栈
- B3616 【模板】队列

如果你在上面所有题目中拿到了 500 分以上，那么说明你已经掌握了基础的骗分方法，现在，让我们走向正解，向巨佬的路进发吧！