web开发 forms javafx memory foreach split sms vue动态绑定class 后台管理ui 郑州网络 jq去空格 oracle修改字段默认值 安卓小程序源码 eclipse闪退 linux下载器 mysql卸载工具 python3网络编程 python创建数据库 python的文件操作 java正则表达 java替换字符串 java新建文件 java求阶乘 java字符串格式化 linux教程 linuxcat命令 linux如何安装 onenote2003 python游戏代码 maxtoc4d dep bbm注册 blued是什么软件 ansys安装教程 cad特性匹配 子节点 抠图教程 联盟练级路线 字符串分割 x截屏
当前位置: 首页 > 学习教程  > 编程语言

B. Tokitsukaze, CSL and Stone Game

2020/8/31 14:36:59 文章标签:

https://codeforces.com/problemset/problem/1190/B

 展开

题目描述

Tokitsukaze and CSL are playing a little game of stones.

In the beginning, there are nn piles of stones, the ii -th pile of which has a_iai​ stones. The two players take turns making moves. Tokitsukaze moves first. On each turn the player chooses a nonempty pile and removes exactly one stone from the pile. A player loses if all of the piles are empty before his turn, or if after removing the stone, two piles (possibly empty) contain the same number of stones. Supposing that both players play optimally, who will win the game?

Consider an example: n=3n=3 and sizes of piles are a_1=2a1​=2 , a_2=3a2​=3 , a_3=0a3​=0 . It is impossible to choose the empty pile, so Tokitsukaze has two choices: the first and the second piles. If she chooses the first pile then the state will be [1, 3, 0][1,3,0] and it is a good move. But if she chooses the second pile then the state will be [2, 2, 0][2,2,0] and she immediately loses. So the only good move for her is to choose the first pile.

Supposing that both players always take their best moves and never make mistakes, who will win the game?

Note that even if there are two piles with the same number of stones at the beginning, Tokitsukaze may still be able to make a valid first move. It is only necessary that there are no two piles with the same number of stones after she moves.

输入格式

The first line contains a single integer nn ( 1 \le n \le 10^51≤n≤105 ) — the number of piles.

The second line contains nn integers a_1, a_2, \ldots, a_na1​,a2​,…,an​ ( 0 \le a_1, a_2, \ldots, a_n \le 10^90≤a1​,a2​,…,an​≤109 ), which mean the ii -th pile has a_iai​ stones.

输出格式

Print "sjfnb" (without quotes) if Tokitsukaze will win, or "cslnb" (without quotes) if CSL will win. Note the output characters are case-sensitive.

题意翻译

IrresseyIrressey与yurzhangyurzhang在玩一个取石子的游戏

一开始,他们面前有nn堆石子,第ii堆石子有a_iai​颗石头,他们轮流取石子(IrresseyIrressey先取)。每一次,取石子的人会选中一个非空的石子堆并取走其中的一颗石子。如果在某个人的回合前所有的石子堆都是空的,或者在他取完后有两堆的石子数量相同(两堆都没有石子也算),则他输掉游戏。

如果IrresseyIrressey胜利,输出sjfnbsjfnb;如果yurzhangyurzhang胜利,输出cslnbcslnb(假设两个人都按最好的策略去取)

数据范围:

1\le n \le10^51≤n≤105

0\le a_1,a_2,a_3...a_n\le10^90≤a1​,a2​,a3​...an​≤109

输入输出样例

输入 #1复制

1
0

输出 #1复制

cslnb

输入 #2复制

2
1 0

输出 #2复制

cslnb

输入 #3复制

2
2 2

输出 #3复制

sjfnb

输入 #4复制

3
2 3 1

输出 #4复制

sjfnb

说明/提示

In the first example, Tokitsukaze cannot take any stone, so CSL will win.

In the second example, Tokitsukaze can only take a stone from the first pile, and then, even though they have no stone, these two piles will have the same number of stones, which implies CSL will win.

In the third example, Tokitsukaze will win. Here is one of the optimal ways:

  • Firstly, Tokitsukaze can choose the first pile and take a stone from that pile.
  • Then, CSL can only choose the first pile, because if he chooses the second pile, he will lose immediately.
  • Finally, Tokitsukaze can choose the second pile, and then CSL will have no choice but to lose.

In the fourth example, they only have one good choice at any time, so Tokitsukaze can make the game lasting as long as possible and finally win.


其实猜猜两个大佬肯定最后胜负情况挺平均的叭

思路:首先根据题意特判掉几种情况(我就是少特判两种wa了4发)

  1. cnt[a[i]]≥3
  2. cnt[a[i]]≥2 且 cnt[ a[j] ]≥2  (就是有两个>=2次数出现的)
  3. cnt[a[i]]≥2 且 cnt[a[i]−1]≥1 (比如 4 4 5)
  4. cnt[0]≥2(比如 0 0 3,0 0 4)

剩下一种情况模拟发现:最后会变成一个

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
LL a[maxn]; 
map<LL,LL>map1;
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL n;cin>>n;
  LL ans=0;
  for(LL i=1;i<=n;i++){
  	cin>>a[i];
  	map1[a[i]]++;
  	ans+=a[i];
  }
  LL res=0;
  for(map<LL,LL>::iterator it=map1.begin();it!=map1.end();it++)
  {
  	if(it->second>=3)
  	{
  		cout<<"cslnb"<<endl;
  		return 0;
	}
	if(it->second==2)
	{
		res++;
		if(map1[(it->first)-1]!=0)
		{
			cout<<"cslnb"<<endl;
			return 0;
		}
	}
  }
  if(res>=2||map1[0]>=2||map1[0]==n)
  {
  	cout<<"cslnb"<<endl;
  	return 0;
  }
  LL sum=(0+(n-1))*n/2;
  LL cnt=ans-sum;
  if(cnt%2==0)
  {
  	cout<<"cslnb"<<endl;
  }
  else cout<<"sjfnb"<<endl;
return 0;
}

0,1,2,3,.....n-1的等差数列。这时候谁再去拿谁就输了

为啥最后会到这个状态呢?比如 3  5 5,先手拿5,变成3 4 5.然后这时候不想输只能拿最小的.那么整体慢慢变小,最后到0,1,2,3...n-1这种等差的时候到了最终状态.

或者说1 10 1000.最后也回到 0 1 2 这样的状态的

 


本文链接: http://www.dtmao.cc/news_show_150266.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?