对拍

Posted on In

C++ 对拍详解

The Sample

n个数选k个，和为sum的方案数

暴力程序

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
#include <bits/stdc++.h>
using namespace std;

int n, k;
int ans;
int sum;

void dfs(int x, int start) {
	if (x == k+1) {
		if (sum == n) ans++;
		return;
	}
	for (int i = start; sum+i*(k-x+1) <= n; i++) {
		sum+=i;
		dfs(x+1,i);
		sum-=i;
	}
}

int main() {
	
	freopen("data.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	cin >> n >> k;
	dfs(1,1);
	cout << ans;
	return 0;
}

待测程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

int n,k,f[201][7];  //f[k][x] k 分成 x 份 ={f[k-1][x-1],f[k-x][x]}

int main(){
	
	freopen("data.in","r",stdin);
	freopen("dp.out","w",stdout);
	
    cin >> n >> k;
    for (int i=1;i<=n;i++) {f[i][1]=1;f[i][0]=1;}for (int x=2;x<=k;x++) {f[1][x]=0;f[0][x]=0;}  // 边界，为了防止炸，我把有0的也处理了
    for (int i=2;i<=n;i++)
        for (int x=2;x<=k;x++)
            if (i>x) f[i][x]=f[i-1][x-1]+f[i-x][x];
            else f[i][x]=f[i-1][x-1];
    cout<<f[n][k];
    return 0;
}

DataMaker

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;

int main() {
	freopen("data.in","w",stdout);
	srand(time(0));
	cout << rand()%193+7 <<" "<< rand()%4+2;
	return 0;
}

Checker

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n = 100;
	while(n--) {
		system("DataMaker.exe");
		system("dfs.exe");
		system("dp.exe");
		if (system("fc dfs.out dp.out")) {
			break;
		}
	}
	return 0;
}