华硕编程竞赛11月JAVA专场 I题名片发放题解

Designer 小郑

发布于 2023-08-01 13:47:26

1420

发布于 2023-08-01 13:47:26

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

题目链接：题目链接

题面：

小王顺利通过天桥后，进入到了太空奖励关卡。在小王眼前出现了无数多个小仙女，正和小王打着招呼，还向小王索要联系方式！

小王闭上眼睛想了想，自己可是有花之主，还是算了，于是准备扭头就走，但是小王突然想起，自己的朋友还都是单身，这是帮助自己朋友们脱单的好机会！

小王从兜里拿出 N 张不同的朋友名片，名片上写着自己朋友的姓名和联系方式，这正是面前小仙女们想要的。

小王可以将任意多张名片给一位或多位小仙女，小王认为给每位小仙女同一张名片是同一种选择，即将名片 X 给小仙女 A 和给小仙女 B 视为同一种方式。

这时小王想到一个问题，如果小王只有一张名片，小王可以将名片 1 交给任意一名小仙女，也就是只有一种方式。

如果小王有两张名片，小王可以将两张一起交给同一位小仙女，或者分开交给两位小仙女，也就是有两种方式。

如果小王有三张名片：

【1】小王可以分别将三张名片交给三位小仙女。

【2】或者名片 A、B 给仙女 1，名片 C 给仙女 2。

【3】或者名片 B、C 给仙女 1，名片 A 给仙女 2。

【4】名片 A、C 给仙女 1，名片 B 给仙女 2。

【5】或者三张名称全部给仙女 1；总计有 5 种方式。

那么请问小王如果有 N（0 < N < 2500）张不同名片，有几种给予方式？

知识点

Java 二维数组基础使用
数组 DP 递推运算

初始代码

public class EMain {

    public static Long doWork(int n) {
        Long ans = 1L;
        //代码编辑区 开始

        //代码编辑区 结束
        return ans;
    }

    public static void main(String[] args) {
        //测试用例
        System.out.printf((Objects.equals(2L,doWork(2)) ? "【√正确】" : "【X错误】") + "不同名片数 %d,给予方式有%d种\n",2,doWork(2));
        System.out.printf((Objects.equals(5L,doWork(3)) ? "【√正确】" : "【X错误】") + "不同名片数 %d,给予方式有%d种\n",3,doWork(3));
    }

样例说明

输入不同名片数 N，输出给予方式有几种。

如不同名片数 N = 2，则输出 2。

如不同名片数 N = 3，则输出 5

题解

考察第二斯特林数（贝尔数）的理解，也是一道动态规划递推题，需要打表处理。DP 公式为 Fn(i , j) = Fn(i - 1, j - 1) + j * Fn(i - 1, j)，名片数为 N的发放情况种类数就等于 Fn(i , 0) + Fn(i , 1) + ... + Fn(i , i - 1) + Fn(i , i)。

参考代码如下：

import java.util.Objects;

public class EAns {

    public static boolean INIT_FLAG = false;

    public static Integer MAX_LENGTH = 2502;

    public static Long MOD = 1314520L;

    public static Long[][] ANS_TEMP;

    public static Long[] ANS_LIST;

    private static void init() {
        ANS_TEMP = new Long[MAX_LENGTH][MAX_LENGTH];
        ANS_LIST = new Long[MAX_LENGTH];
        for(int i = 0; i < MAX_LENGTH; i ++) {
            for(int j = 0; j < MAX_LENGTH; j ++) {
                ANS_TEMP[i][j] = 0L;
            }
            ANS_TEMP[i][1] = 1L;
            ANS_TEMP[i][i] = 1L;
            ANS_LIST[i] = 0L;
        }
        for(int i = 2; i < MAX_LENGTH; i ++) {
            for(int j = 2; j <= i; j ++) {
                ANS_TEMP[i][j] = (ANS_TEMP[i - 1][j - 1] + ANS_TEMP[i - 1][j] * j) % MOD;
            }
        }
        for (int i = 1; i < MAX_LENGTH; i++) {
            for (int j = 1; j <= i; j++) {
                ANS_LIST[i] = (ANS_LIST[i] + ANS_TEMP[i][j]) % MOD;
            }
        }
        INIT_FLAG = true;
    }

    public static Long doWork(int n) {
        Long ans = 1L;
        //代码编辑区 开始
        if(!INIT_FLAG) {
            init();
        }
        ans = ANS_LIST[n];
        //代码编辑区 结束
        return ans;
    }

    public static void main(String[] args) {
        //测试用例
        System.out.printf((Objects.equals(2L,doWork(2)) ? "【√正确】" : "【X错误】") + "不同名片数 %d,给予方式有%d种\n",2,doWork(2));
        System.out.printf((Objects.equals(5L,doWork(3)) ? "【√正确】" : "【X错误】") + "不同名片数 %d,给予方式有%d种\n",5,doWork(3));
    }
}