注:此非正常方法仅供娱乐,请勿用于比赛或需要他人 Review 的场合。

考完试了,是时候来放 (gao) 松 (dian) 一 (shi) 下 (qing) 了

进入学校的洛谷奥赛团,发现布置了一道新题目:P1996 约瑟夫问题

nn 个人(n100n \leq 100)围成一圈,从第一个人开始报数,数到 mm 的人出列,再由下一个人重新从 11 开始报数,数到 mm 的人再出圈…… 以此类推,直到所有的人都出圈,请输出依次出圈人的编号。

要求用链表做,但我也可以搞点事情嘛~

十分钟后敲出一份 AC 代码:

#include<cstdio>
#include<cstring>
int n, m, i, count, jump;
bool a[100];
int main()
    scanf("%d%d", &n, &m);
    memset(a, false, sizeof(a));
    count = 0;
    i = -1;
    jump = 0;
    while (count < n){
        i++;
        i %= n;
        if (!a[i])
            jump++;
        if (jump == m){
            printf("%d ", i+1);
            a[i] = true;
            count++;
            jump = 0;
        }
    }
    return 0;
}

不断地循环,用一个 bool 数组标记出列。

AC 是 AC 了,但是…… 中规中矩,不符合我们搞事情的风格呀

我们来稍微简化一下 <_<

简化亿下

首先,最关键的就是中间这段 while 循环了,所以我们先从这里入手。

# Step 1

i++;
i %= n;

开始先是指针 i 累加,然后用一个求余处理溢出。

合并一下,变成:

++i %= n;

# Step 2

if (!a[i])
    jump++;

这里需要动点脑筋,我们知道 a[i]bool 型数组,所以就有 TrueFalse 两种情况,作加法运算时转成 int 就是 10 。我们只需要让 jump 累加上 a[i]取反值就好了。

jump += !a[i];

# Step 3

现在 Step 1 和 Step 2 的 4 行代码已经缩成了 2 行

++i %= n;
jump += !a[i];

但是这还不够,我们可以再合并一下:

jump += !a[++i %= n];

# Step 4

if (jump == m){
    printf("%d ", i+1);
    a[i] = true;
    count++;
    jump = 0;
}

接下来是一段 if 逻辑,我们这里需要用三元操作符来代替。

条件 ? 条件为 True 时执行的代码 : 条件为 False 时执行的代码

我们把三元操作符塞进 printf 函数里面:

printf(jump == m ? "%d" : "" , i+1);

但是剩下的三行赋值怎么办?

这里我们就需要用到一个很巧妙的工具了:与运算符 &&

我们都知道,与运算符正常的打开方式是这样子的:

条件 1 && 条件 2

只有两个条件全为 True ,整个表达式才为 True如果条件 1 为 True ,则不会判断条件 2。

我们稍微思考一下,** 如果条件 2 恒为 True ,那么整个表达式的值完全取决于条件 1。** 而 && 运算符两边是可以塞下一个赋值表达式的!

这样,我们就可以把剩下的三条赋值表达式全部用连续的 && 运算符塞进一个括号里面去!

赋值表达式本身的值等于最终被赋值的值,我们只需要通过取反运算符 ! 或者直接 +1 让表达式的值恒为 True 就好了。

所以就变成了这样:

(jump += !a[++i %= n]) == m && (a[i] = true) && (count++)+1 && !(jump = 0)

与上面的 printf 函数合并一下,变成:

printf((jump += !a[++i %= n]) == m && (a[i] = true) && (count++)+1 && !(jump = 0) ? "%d " : "", i+1);

Perfect!

# Step 5

最后我们只需要将代码整理一下即可。

貌似改动的时候出了点小 bug, i 不能初始化为 -1 ,要初始化为 0 。我也不知道是什么原因。但也好,这就更简单了。

所有的变量和数组都定义为全局变量,直接默认初始化为 0 ,这样把初始化的赋值和 memset 都省了。

整理一下,大功告成:

#include<cstdio>
int n, m, i, count, jump;
bool a[100];
int main(){
    scanf("%d%d", &n, &m);
    while (count < n) printf((jump += !a[++i %= n]) == m && (a[i] = true) && (count++)+1 && !(jump = 0) ? "%d " : "", i+1);
    return 0;
}

# 尾声

还是没有大佬们厉害。

题目背景

约瑟夫是一个无聊的人!!

我也像是个无聊的人 <_<

Edited on

Give me a cup of [coffee]~( ̄▽ ̄)~*

玄云Fidel WeChat Pay

WeChat Pay

玄云Fidel Alipay

Alipay

玄云Fidel PayPal

PayPal

玄云Fidel afdian

afdian