同学在做这道题，我就一起做了，没想到比他A得还要早。这是一个考试中比较实用的做法。
题目链接
对于\(mn \le
5000^2\)
首先针对nm比较小的情况，由于
1
| "必胜情况存在，当且仅当存在策略，使对手不存在必胜情况"
|
然后我们就得到了dp公式递推公式
时间复杂度\(O(mn)\) ## 对于更大的情况
### 70分做法 我们发现绝大多数情况都是可以必胜的，直接输出1
当然出题人不会这么轻易放过你的，所以只能拿70分 ### 100分做法
我们把打的表格放出来，发现存在一个规律，即必败的点在两条直线上，而且经过原点，这就是规律。
至于为什么在两条直线上，是因为nm是可以互换的。
然后我们求出斜率的平均值，最后判断一下就好了。
判断的时候直接相等肯定是不行的，因为这是浮点数比较，还是我们估计的浮点数，所以我们需要一个eps。这个eps，可以用统计的方法算出来。
#### 求斜率和eps 首先剔除n>m情况的数据
设\(k\)为我们的估计的斜率，有\[k=\sum \frac{y}{x}\] 然后有 \[eps = \frac {\sum |k'-k|} n\]
其中\(k'\)是实际的斜率
在\(|\frac nm - slope| \le
eps\)的情况下，极大概率是必败的。当然也要考虑mn颠倒的情况。 ##
源程序
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, m, vis_r[N], vis_c[N], vis_x[N << 1];
int G[N][N];
double slope = 1.618959789221876;
double eps = 3e-4;
int main() {
scanf("%d%d", &n, &m);
if(n < N && m < N)
{
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= m; j++) {
if(!vis_r[i] && !vis_c[j] && !vis_x[i - j + N]) {
G[i][j] = 0;
vis_r[i] = vis_c[j] = vis_x[i - j + N] = 1;
}
else {
G[i][j] = 1;
}
}
}
cout << G[n][m] << endl;
}
else
{
if(abs(1.0*n/m - slope) <= eps || abs(1.0*m/n - slope) <= eps)
cout << 0 << endl;
else
cout << 1 << endl;
}
return 0;
}
|
附打表和绘图程序
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
|
import matplotlib.pyplot as plt
import numpy
xx = []
yy = []
with open("data.txt", "r") as f:
for line in f:
s = line.split()
x, y = int(s[0]), int(s[1])
xx.append(x)
yy.append(y)
maxslope = 0
minslope = 1e10
slopey = []
slope = 0
for x, y in zip(xx, yy):
maxslope = max(y/x, maxslope)
minslope = min(y/x, minslope)
slope += y / x
slopey.append(y/x)
slope /= len(xx)
plt.scatter(xx, slopey)
x = numpy.linspace(0, 5000, 5000)
print(minslope, slope)
plt.show()
|