打卡信奥刷题（3145）用C++实现信奥题 P7656 [BalticOI 1996] A NUMBER GAME (Day 2)

P7656 [BalticOI 1996] A NUMBER GAME (Day 2)

题目描述

下面是一个游戏。首先我们赋给变量n nn和变量m mm整数值。玩家 A 和 B 开始轮流移动（A 先）。每次移动都会选择一个正整数k ≤ min ⁡ { m , n } k \le \min \lbrace m,n \rbracek≤min{m,n}，这会将变量n nn的值减少k kk。但是，不允许使用一个或另一个玩家在之前的移动中已经使用的数字。当其中一名玩家无法移动时，游戏结束。 走最后一步的玩家是赢家。
请编写一个程序，说明哪个玩家有获胜策略。

输入格式

第一行包含两个整数n nn和m mm，用空格分隔。

输出格式

第一行：谁有获胜策略；接下来的行：A 的所有可能的第一步动作依次递增，然后是单词 “winning” 或 B 的一个获胜答案。

输入输出样例 #1

输入 #1

3 2

输出 #1

B wins 1 2 2 1

输入输出样例 #2

输入 #2

7 4

输出 #2

A wins 1 winning 2 winning 3 4 4 3

说明/提示

数据规模与约定

对于100 % 100 \%100%的数据，0 < n ≤ 70 0 < n \le 700<n≤70，0 < m ≤ 20 0 < m \le 200<m≤20。

分值说明

本题分值按 BOI 原题设置，满分40 4040。

题目说明

来源于 Baltic Olympiad in Informatics 1996 的 Day 2:A NUMBER GAME。
由 @求学的企鹅 翻译整理。

C++实现

#include<iostream>usingnamespacestd;intn,m;intmem[1<<21|1];//=0表示失败；非零数字表示需要选择mem[x]就会必赢boolvis[1<<21|1];intdfs(intx){if(vis[x])returnmem[x];intcurn=n;for(inti=1;i<=m;i++){if(x>>i&1){curn-=i;}}for(inti=min(curn,m);i>=1;i--){if(x>>i&1)continue;intres=dfs(x|(1<<i));if(res==0){vis[x]=true;returnmem[x]=i;}}vis[x]=true;returnmem[x]=0;}intmain(){cin>>n>>m;if(dfs(0)){cout<<" A wins\n";}else{cout<<" B wins\n";}for(inti=1;i<=m&&i<=n;i++){if(i<=9)cout<<" ";cout<<i<<" ";intres=dfs(1<<i);if(res==0){cout<<"winning"<<"\n";}else{cout<<res<<"\n";}}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容