浅谈信息学竞赛中的骗分技巧

前言

由于信息学竞赛的特殊性：黑箱评测，只用有限的一些数据来判断选手的程序是否正确。再加上 CCF（Coin Collect Foundation） 用脚造数据，所以在 NOIp/CSP 中，如果事先了解一些骗分技巧，往往可以得到非常高的分数。

在 OI 界已经有过名为《骗分导论》的论文，但作者个人认为该论文的骗分技巧不多，而且论文产生于若干年前，有点过时。因此本人想再写一篇类似《骗分导论》的文章，分享一些骗分技巧。

由于作者个人水平有限，所以如果各位有其他的骗分技巧，也欢迎分享出来。你可以在评论区里回复你的技巧，我会把你分享的内容加入本文章中。本文章将持续更新。

卡时

在随机化算法中，如果我们不断地随机，那么得到的结果会越来越接近最后的正确答案。但过多地随机，就会使程序tle。我们可以在程序中对当前已经运行的时间进行判断，如果已经超时就不再进行随机。

卡时往往与随机化算法结合会得到非常好的效果，我们在后面讲解一些随机化的做法时再细讲。

下面给出一个卡时的例子。

例1: CSP-S 2022 T3 星战
如果我们发现如果所有据点可以“连续穿梭”，则一定可以“实现反击”，那么本题的暴力就可以非常简单实现：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define _ 500005
#define int long long
#define ull unsigned long long
using namespace std;
const int mod=0;

inline int read(){
	int res=0,ch=getchar(),f=1;
	while(!isdigit(ch) and ch!=EOF){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		res=(res<<3)+(res<<1)+(ch-'0');
		ch=getchar();
	}
	return res*f;
}

struct Edge{int next,to;} edge[_];
int out[_],head[_],size,ans;
inline void adde(int u,int v){edge[++size].to=v,edge[size].next=head[u],head[u]=size;}
set<int> tag[_];
inline void del(int u,int v){
	if(tag[v].count(u)) return;
	tag[v].insert(u);
	int flag1=out[u];
	out[u]--;
	int flag2=out[u];
	if(flag1==1&&flag2!=1) ans--;
	if(flag1!=1&&flag2==1) ans++;
}
inline void add(int u,int v){
	if(tag[v].count(u)==0) return;
	tag[v].erase(u);
	int flag1=out[u];
	out[u]++;
	int flag2=out[u];
	if(flag1==1&&flag2!=1) ans--;
	if(flag1!=1&&flag2==1) ans++;
}

signed main(){
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	int n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		out[u]++;
		adde(v,u);
	}
	for(int i=1;i<=n;i++) if(out[i]==1) ans++;
	int q=read();
	while(q--){
		int t=read(),u,v;
		if(t==1||t==3) u=read(),v=read();
		if(t==2||t==4) u=read();
		if(t==1){
			del(u,v);
		}else if(t==2){
			for(int i=head[u];i;i=edge[i].next){
				del(edge[i].to,u);
			}
		}else if(t==3){
			add(u,v);
		}else{
			for(int i=head[u];i;i=edge[i].next){
				add(edge[i].to,u);
			}
		}
		if(ans==n) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

可以得到 60 pts

我们继续观察大样例，发现最终结果大部分都是 NO。对于最后几个数据规模较大，暴力肯定超时的点，我们与其tle，不如直接全输出NO。

为了更好地发挥暴力算法的作用，我们可以这样做：执行暴力算法，程序卡时，快要超时就在后面全输出NO。

cpp
1
2
3
4
5
6
7
	while(q--){
		if((double)clock()/CLOCKS_PER_SEC>1.8){
			printf("NO\n");
			continue;
		}
	...
}

在CCF的数据下可以得到80分。

在这里值得一提的是，由于操作次数过多，所以会导致卡时不准。比如上述代码，卡时1.8s，实际测试点最大的运行时间达到了1.9s。如果直接卡1.9s，很可能与暴力同分。我们可以把最后全输出NO的情况单独拿出来写，具体如下

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define _ 500005
#define int long long
#define ull unsigned long long
using namespace std;
const int mod=0;

inline int read(){
	int res=0,ch=getchar(),f=1;
	while(!isdigit(ch) and ch!=EOF){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		res=(res<<3)+(res<<1)+(ch-'0');
		ch=getchar();
	}
	return res*f;
}

struct Edge{int next,to;} edge[_];
int out[_],head[_],size,ans;
inline void adde(int u,int v){edge[++size].to=v,edge[size].next=head[u],head[u]=size;}
set<int> tag[_];
inline void del(int u,int v){
	if(tag[v].count(u)) return;
	tag[v].insert(u);
	int flag1=out[u];
	out[u]--;
	int flag2=out[u];
	if(flag1==1&&flag2!=1) ans--;
	if(flag1!=1&&flag2==1) ans++;
	
}
inline void add(int u,int v){
	if(tag[v].count(u)==0) return;
	tag[v].erase(u);
	int flag1=out[u];
	out[u]++;
	int flag2=out[u];
	if(flag1==1&&flag2!=1) ans--;
	if(flag1!=1&&flag2==1) ans++;
}

signed main(){
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	int n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		out[u]++;
		adde(v,u);
	}
	for(int i=1;i<=n;i++) if(out[i]==1) ans++;
	int q=read();
	while(q--){
		if((double)clock()/CLOCKS_PER_SEC>1.9){
			printf("NO\n");
			break;
		}
		int t=read(),u,v;
		if(t==1||t==3) u=read(),v=read();
		if(t==2||t==4) u=read();
		if(t==1){
			del(u,v);
		}else if(t==2){
			for(int i=head[u];i;i=edge[i].next){
				del(edge[i].to,u);
			}
		}else if(t==3){
			add(u,v);
		}else{
			for(int i=head[u];i;i=edge[i].next){
				add(edge[i].to,u);
			}
		}
		if(ans==n) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	//注意这里
	while(q>0){
		printf("NO\n");
		q--;
	}
	return 0;
}

贪心

我们这里并不用贪心算法去想正解，而是灵活运用贪心的思想来骗分

例1: [USACO18OPEN] Talent Show G

首先我们考虑一个贪心，可能不一定正确。我们把每个牛的才艺与重量的比值从大到小进行排序。一个直观的想法是选择性价比高的牛可能会更好一些。然后我们dfs爆搜。
这里有个做法，就是当遍历到第i个牛时，不去立即选择第i+1个牛，而是向后枚举接下来要选择的牛。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
#define _ 500
using namespace std;

int n,w;
typedef pair<int,int> pii;
pii e[_];

int ans,cnt=0;
void dfs(int x,int nowt,int noww){
	cnt++;
	if(cnt>100000000) return;
	if(noww>=w) ans=max(ans,nowt*1000/noww);
	for(int i=x+1;i<=n;i++) dfs(i,nowt+e[i].first,noww+e[i].second);
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>w;
	for(int i=1;i<=n;i++) cin>>e[i].second>>e[i].first;
	sort(e+1,e+n+1,[](pii x,pii y){return x.first*y.second>y.first*x.second;});
	for(int i=1;i<=n;i++) dfs(i,e[i].first,e[i].second);
	cout<<ans;
	return 0;
} 

结合卡时，上述的代码就可以得到50 pts。

然后我们接下来考虑，因为我们是按照性价比从高到低的顺序选择，如果选择的牛的重量已经满足要求，接下来再去选择，大概率是不会让答案更优的，所以我们将上述代码中的

cpp
1
if(noww>=w) ans=max(ans,nowt*1000/noww);

改为

cpp
1
if(noww>=w) return ans=max(ans,nowt*1000/noww),void();

就可以直接ac 当然这一步风险还是有的