文章

小小马

## 描述 鸡尾酒是小小马的粉丝,于是他比较喜欢研究关于“马”的问题。 给你一个n*m的棋盘,每次可以在任意点放一个象棋中的“马”,假设在x,y点放置一个马,则马对应移动的8个位置都不能放置其他马。 即(x+1,y+2),(x-1,y+2),(x+1,y-2),(x+1,y-2),(x+2,y-1),(x+2,y+1),(x-2,y+1),(x-2,y-1)这八个点都不能再放置马。 鸡尾酒邀请了wls来玩这个游戏,wls先手,首先无法操作的人输。 假设对阵双方都玩得很好,请问谁会赢得这场比赛。 ## 输入 输入两个整数n,m(1<=n,m<1e18) ## 输出 如果先手赢,输出wls,否则输出cocktail ## 输入样例 1  1 1 ## 输出样例 1

`wls`

## 输入样例 2 

`1 2`

## 输出样例 2

`cocktail`

* * *

## 分析 初级思路——搜索 乍一看,这道题有点像搜索题,也就是一个一个枚举cocktailwls的棋子,再把(x+1,y+2),(x-1,y+2),(x+1,y-2),(x+1,y-2),(x+2,y-1),(x+2,y+1),(x-2,y+1),(x-2,y-1)这些位置标记掉。 事实上,题目当然不会那么简单。来康康几位同学的结果:

![](https://blog.amzcd.top:32323/wp-content/uploads/2021/03/image-4.png)
全WA了……

用这样的方法,不是TLE就是RE(还有WA),看来我们急需更简单一些的方法。 更进一步——归纳规律 于是,笔者使用表格模拟棋盘,进行归纳:

提示
_keyboard_arrow_down_

(括号)里的数字表示该棋子是第几回合下的; (数字+)表示该回合下的棋同时占用的位置(不是每个马会使8个位置不能下棋吗)。

1×1的时候:

(1)wls
wls胜

1×2的时候:

(1)wls (2)cocktail
cocktail胜

1×3的时候:

(1)wls (2)cocktail (3)wls
wls胜

2×2的时候:

(1)wls (2)cocktail
(3)wls (4)cocktail
cocktail胜

2×3的时候:

(1)wls (3)wls (2)cocktail
(2+) (4)cocktail (1+)
cocktail胜

3×3的时候:

(1)wls (2+) (5)wls
(2+) (4)cocktail (1+)
(3)wls (1+) (2)cocktail
wls胜

> warning 注意 > 题目描述里明确规定,“对阵双方都玩得很好”,所以不用考虑下棋顺序的先后,最后所呈现出的棋盘布局和胜负都是唯一的。 列个表归纳总结一下:

长×宽 1 2 3
1 wls cocktail wls
2 cocktail cocktail cocktail
3 wls cocktail wls

有兴趣的童鞋如果继续列表探索下去的话,就会发现如下规律: > 当长&times;宽为偶数时,cocktail总赢; > > 反之,当长&times;宽为奇数时,wls总赢。 于是简单地给出了代码:

`#include
   <bits tdc++.h="">

  using namespace std;
  long long a,b;
  int main(){
    cin>>a>>b;
    if((a*b)%2==0){
      cout<<"cocktail";
    }else{
      cout<<"wls";
    }
    return 0;
  }`
   </bits>

> warning 提示 > 注意数据范围:n,m(1<=n,m<1e18)。 * * *

## 你以为这就结束了? 一提交上去,又WA了。仔细一看上面提示的数据范围n,m(1&lt;=n,m&lt;1e18)。 试求n&times;m1&lt;=n*m&lt;=1e36!这连long long都存不下啊! 于是,只好分别判断两个数的奇偶性了。 ## 最终示例代码 #include <bits tdc++.h=""> using namespace std; long long a,b; int main(){ cin&gt;&gt;a&gt;&gt;b; if(a%2==0||b%2==0){ cout&lt;&lt;&quot;cocktail&quot;; }else{ cout&lt;&lt;&quot;wls&quot;; } return 0; } </bits>

本文由作者按照 CC BY 4.0 进行授权

© Dignite. 保留部分权利。 由  提供CDN加速。

浙ICP备2023032699号 | 使用 Jekyll 主题 Chirpy