华硕编程竞赛11月JAVA专场 J题再见天空题解

Designer 小郑

发布于 2023-08-01 13:48:00

1470

发布于 2023-08-01 13:48:00

作者主页：Designer 小郑 作者简介：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！ 主打方向：Vue、SpringBoot、微信小程序

题目链接：题目链接

题面：

小王不知不觉也在太空世界玩了一天了，突然想起来明天还要上学，这可把小王急坏了。

小张告诉小王，太空会客厅出口有一套 “超时空传唤座椅”，它可以帮助小王回到地球！

“超时空传唤座椅” 有着特殊的机制，这套座椅有两个驾驶位，主驾驶位必须由身高超过 170cm 的人乘坐，而副驾驶位必须由身高不超过 170cm 的人乘坐，只有两个驾驶位坐上了人， “超时空传唤座椅” 才能启动。

只有“超时空传唤座椅”的主驾驶坐上了人，副驾驶的门才会打开，小王时间紧迫，着急告别了小张，他必须赶紧前往太空会客厅。

太空会客厅早已聚集了大量着急返回地球的人，且前面已经有一部分比较固执的人，他们不接受自己被变更排队位置。

一旦排在最前面的人无法上座椅，这个人就会发泄情绪把队列堵住，让后面的人也无法返回地球。

那么，如果小王排在第 N（1 < N < 800000) 位，他可以顺利返回地球吗？如果可以，有多少种排队方案？

提示：小王后面的人不得排到小王前面，但小王前面的人（接受自己被变更排队位置的人，含小王）可任意调整顺序，以保证初始队伍中小王及前面的人可以顺利返回地球。

引用说明：以上图片来源自蓝桥云课。

知识点

卡特兰数
乘法逆元
快速幂取模

初始代码

public class JMain {

    private static final Long MOD = 1000000007L;

    public static Long doWork(int n,String str) {
        //代码编辑区 开始
        return 0L;
        //代码编辑区 结束
    }

    public static void main(String[] args) {
        //测试用例
        System.out.println((Objects.equals(2L,doWork(6,"HM")) ? "【√正确】 " : "【X错误】 ") + "样例一，答案：" + doWork(6,"HM"));
        System.out.println((Objects.equals(0L,doWork(6,"MH")) ? "【√正确】 " : "【X错误】 ") + "样例二，答案：" + doWork(6,"MH"));
    }
}

样例说明

输入数据分为两行，第一行是一个整数 N，代表小王排队的位数。

第二行是队伍不接受自己被变更排队位置的情况，从前往后排列，身高大于 170cm 的人记为 H，否则记为 M。

需要输出一个整数 X，代表允许小王成功回到地球的不同队伍排列数量。

因排队方案数会很大，对较大素数取模依旧可以保持答案的正确性（原理如下），所以请你将顺序数对 1000000007 取模。

一个数对7取余，那么1、8、15都是一类答案，如果正确答案是8，您求出来是15，那么也会被认为是对的。
对91取余，那么1、92、183都是一类答案，如果正确答案是183，您求出来是92，那么也会被认为是对的。
以此类推，只要取余素数越大，答案正确性就越高。
如果要保证完全正确，则要用字符串去模拟大数运算，这样没有必要，也不是题目主要考察的点，所以请您对 1000000007 取模。

样例一：

6
HM

代表小王前面（含小王）共计 6 个人，前两个人为高、矮且不可更换位置，可能的情况为高矮高矮高矮、高矮高高矮矮两种，所以输出 2。

提示：因为前两个人不能变更，所以不会出现高高高矮矮矮的情况。

样例二：

6
MH

代表小王前面（含小王）共计 6 个人，前两个人为矮、高且不可更换位置，第 1 个人会把队列堵死，所以小王无法返回地球，输出 0。

题解

考察对卡特兰数的理解，此题的原型如下：

电影院门票五块钱，有 N 个人拿五块纸币，有 M 个人拿十块纸笔，售票口初始无零钱，问保证全部人进去，有几种方案？

题解很简单，每个拿五块纸币的人后面必须有一个拿十块纸币的人跟他对应入场，这就是卡特兰数的裸题。

此题对卡特兰数进行了改编，如果是合法的情况，将 H 看为左括号，把 M 看做右括号，已知前面的括号情况，求剩下括号情况种类数使得左括号和右括号相等。

根据组合数学的推理，解题公式为：C(n-a,n-a+n-b) - C(n-a-1,n-a+n-b)。

因为结果可能很大，所以需要用费马小定理和快速幂进行取模计算。

参考代码如下：

import java.util.Objects;

public class JAns {

    private static Long[] f = new Long[1000006];

    private static final Long MOD = 1000000007L;

    private static Boolean INIT_FLAG = false;

    public static Long doWork(int n,String str) {
        if(!INIT_FLAG) {
            INIT_FLAG = true;
            init();
        }
        int a = 0;
        int b = 0;
        for(int i = 0; i < str.length(); i ++) {
            if(Objects.equals('H',str.charAt(i))) {
                a ++;
            } else if(Objects.equals('M',str.charAt(i))) {
                b ++;
                if(b > a) {
                    return 0L;
                }
            }
        }
        if( (n & 1) > 0 || b > a || n-b-(a-b) < 0){
            return 0L;
        }
        a = n / 2 - a;
        b = n / 2 - b;
        if( a < 0 || b < 0){
            return 0L;
        }
        return (((f[a + b] * (b + 1 - a)) % MOD) * cal((f[a] * f[b + 1]) % MOD, MOD - 2L, MOD)) % MOD;
    }

    private static Long cal(Long a, Long b, Long p){
        Long ans = 1L;
        while(b > 0){
            if((b & 1) > 0){
                ans = (ans * a) % p;
            }
            b >>= 1;
            a = (a * a) % p;
        }
        return ans;
    }

    private static void init() {
        f[0] = 1L;
        for(int i = 1; i < 1000006; i ++) {
            f[i] = ((f[i - 1] % MOD) * (i % MOD)) % MOD;
        }
    }

    public static void main(String[] args) {
        //测试用例
        System.out.println((Objects.equals(2L,doWork(6,"HM")) ? "【√正确】 " : "【X错误】 ") + "样例一，答案：" + doWork(6,"HM"));
        System.out.println((Objects.equals(0L,doWork(6,"MH")) ? "【√正确】 " : "【X错误】 ") + "样例二，答案：" + doWork(6,"MH"));
    }
}