Codeforces

https://codeforces.com/contest/1191/problem/D

好像在哪里见过类似的?

相当于在棋盘上面移动棋子,每次只能左移一格,移动完之后有棋子重叠或本身就是不能移动就输。

那么只有一颗棋子的情况,判断奇偶就行。

当有多颗棋子,假如检测到某两颗棋子重叠,那么左边那颗棋子立刻左移一位并break,重新检测,要是没有重叠则可以继续,否则一开始就是输的。

然后大家就尽可能地把棋子往左边挪,明显挪的次数是恒定的,和策略没有任何关系。只和棋子之间的空格的总和的奇偶性有关。

每颗棋子的可移动数恰好就是它左侧所有的空格数。

所以考虑数空格就可以了。

记录b[i]表示a[i]-a[i-1]。要是遇到某个b[i]==0,那么就说明初始有相等对,必须把a[i-1]--,处理好细节,包括a[i-1]本身是0,还有本次移动的一步。这种情况处理掉了所有包含多个0的情况。

然后再看看还有没有b[i]==0,这样表示走了第一步之后还是输。

最后不能走的状态必然是自然数序列,所以每个数减去他到那个情况所需的步数。

最后看看步数的奇偶性。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[100005];
int b[100005];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
    //freopen("Yinku.out", "w", stdout);
#endif // Yinku
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + 1 + n);
        for(int i = n; i >= 2; --i) {
            b[i] = a[i] - a[i - 1];
        }
        bool alfail = false;
        bool almove = false;
        for(int i = 2; i <= n; ++i) {
            if(b[i] == 0) {
                b[i]++;
                b[i - 1]--;
                a[i - 1]--;
                //把第一个遇到的相等对拆开
                almove = true;
                if(a[i - 1] < 0)
                    alfail = true;
                //相等对是0,fail
                break;
            }
        }
        for(int i = 2; i <= n; ++i) {
            if(b[i] == 0) {
                alfail = true;
                //移动完之后仍有相等对,fail
                break;
            }
        }
        ll sum = 0;
        for(int i = 1; i <= n; i++) {
            sum += a[i] - (i - 1);
            //第1个元素移动到0
            //第2个元素移动到1
            //第3个元素移动到2
            //也就是变成自然数序列所需的步数
        }
        if(almove)
            sum++;
        if(sum % 2 == 0) {
            alfail = true;
        }
        puts(alfail ? "cslnb" : "sjfnb");
    }
}
原文地址:https://www.cnblogs.com/Yinku/p/11179273.html