链接:https://ac.nowcoder.com/acm/contest/11334/B
来源:牛客网
题目描述
牛牛感觉在上一次赌约中,情况对于自己非常不利,所以决定再赌一场。
这时候,牛蜓队长出现了:第一,绝对不意气用事;第二,绝对不漏判任何一件坏事;第三,绝对裁判的公正漂亮。
牛蜓队长带他们来到了一个棋盘游戏,棋盘左上角是(0,0)(0,0),这个棋盘在(x,y)(x,y)的位置有一个棋子,牛牛和牛可乐轮流移动这个棋子,这个棋子可以左移也可以上移,可以移动一格或者两格,直到不能再移动(即到(0,0)(0,0))的那个人算输。
如果原本在(x,y)(x,y),左移一格即为(x,y -1)(x,y−1),上移一格即为(x-1,y)(x−1,y)
这个时候,牛牛为了弥补上一局的不公平,决定要自己先手,如果两个人都用最优的策略,最后牛牛是否能获胜。
输入描述:
有多组输入样例,第一行为样例组数t(t\leq 1×10^6)t(t≤1×10
6
)
接下来 tt 行每行有一个整数 xx 和 yy,分别表示初始位置(x,y\leq 1×10^9)(x,y≤1×10
9
)
输出描述:
输出t行,如果牛牛获胜,就输出”yyds”(不带引号)
否则输出”awsl”
示例1
输入
复制
2
0 0
0 2
输出
复制
awsl
yyds
首先这道题数据这么大,一般情况一定是找规律的,而找规律的·题目我们打表是最快有效的方法,所以我先写了一个暴力程序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <map>
using namespace std;
#define int long long
map<int, int> f;
int sg(int x){
if (f[x]) return f[x];
unordered_set<int> S;
for (int i = 1; i <= 2; i ++){
if (x > i) S.insert(sg(x - i));
}
for (int i = 0; ; i ++){
if (!S.count(i))
return f[x] = i;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
scanf("%d", &T);
//memset(f, -1, sizeof f);
while(T --){
int x, y;
cin >> x >> y;
int res = sg(x) ^ sg(y);
if (res) cout << "yyds" << endl;
else cout << "awsl" << endl;
}
return 0;
}
一般是先手必胜的概率是大于后手的
通过我反复无常的尝试,我发现如果x和y的差的绝对值是3的倍数的话,那么此时是必败的,否则是必胜的,所以此时代码是
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
signed main(){
int T;
scanf("%d", &T);
while(T --){
int x, y;
scanf("%d%d", &x, &y);
if (abs(x - y) % 3 == 0) cout << "awsl" << endl;
else cout << "yyds" << endl;
}
return 0;
}