D. Tokitsukaze, CSL and Stone Game （思维、game）

今天药忘吃喽~ 2021-07-16 12:13 365阅读 0赞

[题目][Link 1]

思路：  
先手必输的情况：  
1.有两个以上两堆石子数目相同。  
2.有3堆以上石子数目相等、有两堆0石子。  
3.有一个两堆数目(k)相同的石子，且有一堆数目为k-1的石子。

除掉上面的情况后，将石子从小到大排个序，大家都不想输，贪心之下把小的先减完可以保证过程中不会出现两堆石子数目相等的情况,所以对排序后的第i堆石子可以减到i-1个，也就是说总共可以执行p=sum(全部石子数)-((n-1)\*n)/2次操作，p%2==0 cslnb 反之另一个nb

#include<iostream>
    #include<map>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll lst[Max];
    
    int main()
    { 
    	FAST;
    	ll n;cin >> n;
    	map<int, int> ma;
    	ll ans = 0;
    	for (int i = 1;i <= n;i++)
    	{ 
    		cin >> lst[i];
    		ma[lst[i]]++;
    		ans += lst[i];
    	}
    	sort(lst + 1, lst + 1 + n);
    	int num = 0, f = 0;
    	for (auto i = ma.begin();i != ma.end();i++)
    	{ 
    		if (i->second >= 3)f = 1;
    		if (i->second >= 2)
    		{ 
    			num++;
    			if (ma[i->first - 1] >= 1)f = 1;
    		}
    		if (i->first == 0 && i->second >= 2)f = 1;
    	}
    	if (num >= 2)f = 1;
    	if (f)cout << "cslnb" << endl;
    	else
    	{ 
    		ll sum = n * (n - 1) / 2;
    		ans = ans - sum;
    		if (ans % 2 == 0)cout << "cslnb" << endl;
    		else cout << "sjfnb" << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1191/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，365人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 877. Stone Game (Java版; Meidum)

[welcome to my blog][] LeetCode 877. Stone Game (Java版; Meidum) 题目描述 Alex a

r囧r小猫/ 2023年07月18日 02:54/ 0 赞/ 9 阅读

相关 Stone Game（C++石子游戏）

解题思路：（1）贪心算法 class Solution { public: bool stoneGame(vector<int>& pil

旧城等待，/ 2023年01月07日 03:58/ 0 赞/ 132 阅读

相关 HDU_2580 A simple stone game

刚开始看这一题时，就知道这根本不是一道简单题（对当时没学K倍动态减法的我来说），因为前几天刚做完一道斐波那契额数列的博弈而且它仅仅是这道题k=2的一个特例而已-\_-|||。

蔚落/ 2022年08月12日 14:59/ 0 赞/ 5 阅读

相关 Again Stone Game （通过SG函数找规律）

Again Stone Game （通过SG函数找规律）：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=1126

旧城等待，/ 2022年07月29日 11:41/ 0 赞/ 124 阅读

相关 POJ - 1740 A New Stone Game （博弈）

A New Stone Game Description Alice and Bob de

不念不忘少年蓝@/ 2022年05月19日 02:37/ 0 赞/ 463 阅读

相关 B. Nastya Is Playing Computer Games（思维）

题目链接： [http://codeforces.com/problemset/problem/1136/B][http_codeforces.com_problemse

心已赠人/ 2022年02月20日 12:07/ 0 赞/ 164 阅读

相关 D - Game on a Graph

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

水深无声/ 2022年01月30日 08:09/ 0 赞/ 177 阅读

相关 CF1067D Computer Game

[link][] 题意：有 n 道题，每个题可以做很多次但只能领悟一次，一开没有领悟任何题。对于第 i 个题，正确率为 $p\_i$ 。领悟之前，做对这个题

迷南。/ 2022年01月07日 14:19/ 0 赞/ 177 阅读

相关 Game with Chips（思维）

[题目][Link 1] 思路：一开始看题时表示很懵，觉得很难，情况也很复杂。想不出来，突然想起队友通过看其他人提交过的时间和空间找题目眉头，然后我也去看了一下s

心已赠人/ 2021年07月16日 19:20/ 0 赞/ 360 阅读

相关 D. Tokitsukaze, CSL and Stone Game （思维、game）

[题目][Link 1] 思路：先手必输的情况： 1.有两个以上两堆石子数目相同。 2.有3堆以上石子数目相等、有两堆0石子。 3.有一个两堆数

今天药忘吃喽~/ 2021年07月16日 12:13/ 0 赞/ 366 阅读