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

偏执的太偏执、 2023-09-24 15:29 31阅读 0赞

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

题目链接：[题目链接][Link 1]

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题面： ###

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

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

小王从兜里拿出 `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 递推运算  
    ![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 初始代码 ###

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));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 样例说明 ###

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

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

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

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题解 ###

考察**第二斯特林数**（贝尔数）的理解，也是一道**动态规划**递推题，需要**打表**处理。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));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 总结 ###

要 AC 本题，必须学会 java 中 **二位数组**的基本用法，另外还要对动态规划和**DP**的算法有一定的了解，从而去递推第二斯特林数，最终通过本题。

![在这里插入图片描述][3a01dc60e62c415b812015851343f1c0.png_pic_center]

[Designer]: https://blog.csdn.net/qq_41464123
[Link 1]: https://www.lanqiao.cn/contests/lqENT05/challenges/
[d20811fc24154b148e6372d8bd803dab.png_pic_center]: https://img-blog.csdnimg.cn/d20811fc24154b148e6372d8bd803dab.png#pic_center
[3a01dc60e62c415b812015851343f1c0.png_pic_center]: https://img-blog.csdnimg.cn/3a01dc60e62c415b812015851343f1c0.png#pic_center