版权声明:欢迎关注我的博客,本文为博主【炒饭君】原创文章,未经博主同意不得转载 https://blog.csdn.net/a1061747415/article/details/36910333
Public Sale
Problem Description
尽管不想,可是现实总归是现实,Lele始终没有逃过退学的命运。由于他没有拿到奖学金。如今等待他的,就是像FarmJohn一样的农田生涯。
要种田得有田才行,Lele听说街上正在举行一场别开生面的拍卖会,拍卖的物品正好就是一块20亩的田地。
要种田得有田才行,Lele听说街上正在举行一场别开生面的拍卖会,拍卖的物品正好就是一块20亩的田地。
于是。Lele带上他的所有积蓄。冲往拍卖会。
后来发现。整个拍卖会仅仅有Lele和他的死对头Yueyue。
通过打听。Lele知道这场拍卖的规则是这种:刚開始底价为0,两个人轮流開始加价,只是每次加价的幅度要在1~N之间,当价格大于或等于田地的成本价 M 时,主办方就把这块田地卖给这次叫价的人。
Lele和Yueyue尽管考试不行。可是对拍卖却十分精通,并且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。
由于Lele字典序比Yueyue靠前。所以每次都是由Lele先開始加价,请问,第一次加价的时候。
Lele要出多少才干保证自己买得到这块地呢?
Input
本题目包括多组測试,请处理到文件结束(EOF)。
每组測试占一行。
每组測试包括两个整数M和N(含义见题目描写叙述,0<N,M<1100)
Output
对于每组数据,在一行里按递增的顺序输出Lele第一次能够加的价。
两个数据之间用空格隔开。
假设Lele在第一次不管怎样出价都无法买到这块土地,就输出"none"。
Sample Input
4 2
3 2
3 5
Sample Output
1
none
3 4 5
Author
Linle
Source
解题思路:
解题代码:这题运用到了经典的博弈论的核心思想,也就是总共 m 个 ,每次取值范围是 [1,n] 。两个人玩的话,你取1个,我就取N个。你取2个。我就取N-1个....... 每轮总和始终保持N+1,所以考虑对n+1求余就可以,这题就用了这个思想。当然也能够通过SG函数来提取必胜和必输状态。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n,m;
void solve(){
if(n>=m){
printf("%d",m);
for(int i=m+1;i<=n;i++) printf(" %d",i);
printf("
");
}else{
if(m%(n+1)==0) printf("none
");
else printf("%d
",m%(n+1));
}
}
int main(){
while(scanf("%d%d",&m,&n)!=EOF){
solve();
}
return 0;
}