题解 | #西格玛先生想要学算法!# -- JXNU
西格玛先生想要学算法!
https://ac.nowcoder.com/acm/contest/19810/A
是一个博弈的板子(指的是很基础的意思)
但是来欺负新生也太可恶了(╬ ̄皿 ̄)=○#( ̄#)3 ̄)
就是基础的巴什博奕
巴什博奕的重点是只有一堆,
如果n % (m + 1) != 0 则先手赢,
证明:如果n = m + 1,先手最多拿m个,肯定有剩下的,所以先手必输,所以碰到k(m + 1)的局面的人必输。
那么如果n = k(m + 1) + s,这个k 就是系数,s < m + 1,那么只要先手拿掉s个,这样后手面对的就是k(m + 1)局面,所以先手在
n % (m + 1) != 0时必输。
代码
#include <iostream> using namespace std; int main(){ int t,n,m; cin>>t; while(t--){ cin>>n>>m; if(n % (m + 1) != 0){ cout<<"cpnb"<<endl; }else{ cout<<"zzyyyds"<<endl; } } return 0; }