P398字符串压缩

发表于 更新于 分类于 阅读次数：

多校Day1

我是个菜菜…….

D-Chocolate

大概题意

有 $n \times m$大小的巧克力，Alone 和 Kelin 轮流吃巧克力。

每轮行动方选择一个坐标 $(i,j)$，将所有满足 $x \leq i$ 和 $y \leq j$ 的 $(x,y)$ 上的巧克力吃掉。

每轮至少吃一个巧克力，吃最后一个巧克力的人输。

假设两人采取最优策略，Kelin 先手，求谁获胜。

题解

  • 很容易看出来在 $n = m = 1$ 的时候是 Alone 赢。
  • 在 $ n>1 $ 或 $m > 1$ 的时候，假设 Kelin 选择 $(1,1)$ ，并且 Alone 赢了，那么 Kelin 都可以选择复制 Alone 的策略，抢走 Alone 的必胜态从而获胜。故此情况下 Kelin 必胜。

code

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if(a==1&&b==1)cout<<"Walk Alone"<<endl;
    else cout<<"Kelin"<<endl;
    return 0;
}

赛场

  • 第一眼看到的时候题看错了，以为是一行和一列的巧克力，背大锅。
  • 路走歪了，一直在用 dp 的思路在想。
  • 大概五十分钟的时候交了一发，过了，所以还是要大胆假设小心求证。

咕咕咕了先，晚上再写。