2025寒假算法练习——Week 1

2025-01-19 · 10 分钟阅读 · 算法桶排序动态规划 dfs ·

复制链接:

文章目录

习题均来自 NEFU OJ

Problem 357 | 天下无双

Description

太极生两仪,两仪生四象,四象生八卦,八卦生万物。天地初开，万物皆欲成双成对；芸芸丛生，谁愿孤苦伶仃。知音难觅，阳春白雪绕梁何久，千古一绝，神雕侠女驰骋九洲。
天下岂无双？千古绝唱为知音。情寄雨丝丝，述相思之意；梦随风万里，寻同道之人。共聚一堂，为梦想而努力；携手共进，为程序而疯狂！
夜夜编程不漫长，只因与君共拼搏……
给定n个数，其数值范围在1到n-1中，已知其中必有两个数是相同的，要求你找出并输出。（2<=n<=1，000,000）

Input

多组数据输入. 每组输入第一行一个数n。第二行n个数，其数值范围为1..n-1。

Output

每组输出一行一个数，即出现过两次的数。

Sample Input

15
22 3 1 4 2
38
47 6 1 2 3 5 4 7

Sample Output

12
27

第一眼看到这道题的时候，我想到了力扣两数之和，因而选择使用哈希表来解决这一问题：

 1import java.util.Scanner;
 2import java.util.Map;
 3import java.util.HashMap;
 4
 5public class Main {
 6    public static void main(String[] args) {
 7        try (Scanner scanner = new Scanner(System.in)) {
 8            while (scanner.hasNextInt()) {
 9                Map<Integer, Integer> map = new HashMap<>();
10                int n = scanner.nextInt();
11                for (int i = 0; i < n; i++) {
12                    int num = scanner.nextInt();
13                    int count = map.getOrDefault(num, 0);
14                    if (count == 1) {
15                        System.out.println(num);
16                    }
17                    map.put(num, count + 1);
18                }
19            }
20        }
21    }
22}

不过超时了……
随后我想到，使用 Map<Integer, Integer> 不如使用 int[] ，故修改代码如下：

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        try (Scanner scanner = new Scanner(System.in)) {
 6            while (scanner.hasNextInt()) {
 7                int n = scanner.nextInt();
 8                int[] nums = new int[n];
 9                for (int i = 0; i < n; i++) {
10                    int value = scanner.nextInt();
11                    if (nums[value - 1] == 1) {
12                        System.out.println(value);
13                    }
14                    nums[value - 1]++;
15                }
16            }
17        }
18    }
19}

还是 TLE……
这次我怀疑是语言的问题，遂改 C++ 尝试：

 1#include <iostream>
 2#include <vector>
 3
 4int main() {
 5
 6    int n;
 7    while (std::cin >> n) {
 8        std::vector<int> nums(n, 0);
 9
10        for (int i = 0; i < n; i++) {
11            int value;
12            std::cin >> value;
13            if (nums[value - 1] == 1) {
14                std::cout << value << std::endl;
15            }
16            nums[value - 1]++;
17        }
18    }
19
20    return 0;
21}

AC！

Problem 1604 | QWQ和彩色石-map

Description

QWQ来到了一个神奇的地方，这个地方有很多颜色不同的彩色石，每个颜色都可以用一个数字来代替，QWQ收集了一堆石子，他想知道这堆石子中颜色相同的石子个数的最大值

Input

第1行输入一个数字n，代表这堆石子的个数
第二行输入n个数，代表n个石子的颜色
保证输入的所有数都不超过100

Output

输出一个数字，代表颜色相同的石子个数的最大值

Sample Input

110
21 3 5 7 9 1 2 3 5 5

Sample Output

又是一个桶排序。

 1#include <iostream>
 2
 3int main() {
 4
 5    unsigned char stones[101] = {0}; // 既然数字都不超过 100，不妨用 unsigned char
 6    int n, k;
 7    std::cin >> n;
 8    for (int i = 0; i < n; i++) {
 9        std::cin >> k;
10        stones[k]++;
11    }
12
13    int max = 0;
14    for (int i = 0; i < 101; i++) {
15        if (stones[i] > max) {
16            max = stones[i];
17        }
18    }
19
20    std::cout << max << std::endl;
21
22    return 0;
23}

AC！

Problem 1605 | QWQ和翻译机

Description

QWQ拥有一台破烂的翻译机，作为他在星际旅行时候的必备物品，某日，他来的一颗名为倒置星的星球，这个星球上的所有东西都是倒置的，就连说话也要倒过来说，比如，translate在这颗星球上就是etalsnart，QWQ想依靠这台破烂的翻译机完成语言交流，然而，这台翻译机每次翻译的结果并不一定是正确的，你能告诉QWQ每次翻译的结果是否正确么？如果争取就输出’YES‘，否则输出’NO‘。

Input

每组输入占2行
第一行位QWQ想说的话
第二行位翻译机翻译的结果
每句话的长度不超过100个字符

Output

每组输出占一行
YES或者NO

Sample Input

1样例一：
2code
3edoc
4
5样例二：
6abb
7aba

Sample Output

1样例一：
2YES
3
4样例二：
5NO

简单的字符串倒置，语法题。

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        Scanner scanner = new Scanner(System.in);
 6        String raw = scanner.nextLine();
 7        String translated = scanner.nextLine();
 8        scanner.close();
 9
10        StringBuilder sb = new StringBuilder(raw);
11        System.out.println(sb.reverse().toString().equals(translated) ? "YES" : "NO");
12    }
13}

AC！

Problem 1606 | QWQ和棋局挑战

Description

众所周知QWQ的棋艺已经到了独孤求败的地步，某日一位来自泰坦星的勇士前来向QWQ发起挑战，不过挑战的项目却非常奇怪：这位勇士要求QWQ在一个n x n大小的棋盘上放置k个棋子，并要求放置后的棋盘上每一行和每一列最多有一个棋子，显然这个问题是如此的简单，所以这位勇士要求QWQ告诉他这样的棋局共有多少种？你能帮助QWQ解决这个问题么？

Input

每组输入占据一行
一行有两个数字分别表示棋盘的大小n和要求放置的棋子k
0<n<9 , 0<k<=n

Output

每组输入占据一行
输出这样的棋局的种类数目

Sample Input

1样例一：
22 1
3
4样例二：
52 2

Sample Output

1样例一：
24
3
4样例二：
52

这是一道简单的排列组合问题。首先在n行中无序选出k行，再在n列中有序选出k列，即。

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        Scanner scanner = new Scanner(System.in);
 6        int n = scanner.nextInt();
 7        int k = scanner.nextInt();
 8        scanner.close();
 9
10        System.out.println(combination(n, k) * arrangement(n, k));
11    }
12
13    public static int arrangement(int n, int k) {
14        if (k == 1) {
15            return n;
16        }
17        int result = 1;
18        for (int i = 1; i <= k; i++) {
19            result *= n - i + 1;
20        }
21        return result;
22    }
23
24    public static int combination(int n, int k) {
25        if (k > n / 2) {
26            k = n - k;
27        }
28        return arrangement(n, k) / arrangement(k, k);
29    }
30}

Problem 1607 | QWQ和神秘商人

Description

众所周知，QWQ热衷于星际探险和旅行，一天他来到了K星，在这里他遇到了一位神秘的商人，这位商人手中有n个宝物，每个宝物都有一定的价格和珍藏值。如果QWQ想从商人手中购买宝物，就只能花费宇宙中唯一的通货——永恒宝石，但是在K星上关于购买宝物有奇怪的规定:

购买者手中永恒宝石的数量必须大于或者等于想要购买宝物的价格；
每当完成一个交易，购买者手中永恒宝石的数量就会变成所购买的宝物的价格，不论购买者原来有多少个永恒宝石；

现在，QWQ手中有k个永恒宝石，如果他想换取最大的珍藏值，这个值是多少呢？

Input

每组输入有三行
第一行宝物数量n，初始宝石数量k
第二行每一个宝物的价格
第三行每个宝物的珍藏值

1 <= n <= 100000
其余输入均不大于100

Output

输出最大的珍藏值

Sample Input

15 6
22 4 6 8 10
31 50 10 2 50

Sample Output

乍一看像是一个背包问题，但是拼尽全力无法写出状态转移方程，随后灵光乍现，这道题还是要用桶排序来解。

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        int n, k;
 6        int[] price = new int[100001];
 7        int[] value = new int[101];
 8
 9        Scanner scanner = new Scanner(System.in);
10        n = scanner.nextInt();
11        k = scanner.nextInt();
12        for (int i = 0; i < n; i++) {
13            price[i] = scanner.nextInt();
14        }
15        for (int i = 0; i < n; i++) {
16            value[price[i]] += scanner.nextInt();
17        }
18        scanner.close();
19
20        int maxValue = 0;
21        for (int i = 1; i <= k; i++) {
22            maxValue += value[i];
23        }
24        System.out.println(maxValue);
25    }
26}

AC!

Problem 1608 | QWQ和神奇的传送器

Description

《无敌破坏王2》上映啦！QWQ作为Disney的忠实粉丝当然去贡献票房了。电影里的无敌破坏王和云妮洛普来到了互联网的世界，在这里，每个上网的人都是一个个虚拟的相同的小人物，当他们点击到某个网站时，虚拟的人物会乘坐一个神奇的传送器前往目的网站。
QWQ看到这个细节认为一个神奇的传送器只搭载一个人传输效率太低了，所以他觉得如果每个传送器能够搭载无数个人就好了，那么如果此时只有m个神奇的传送器，但有n个人等着被传送，不允许传送器有空载并且每个人看作是相同的，有多少种安排方式呢？

Input

先输入一个t，代表数据的组数
每组数据只有一行有两个数字，之间用一个空格作为间隔，分表代表m、n
保证1<=m<=n<=12

Output

对于每组数据，输出一个数字，代表安排方式的种数

Sample Input

11
21 2

Sample Output

题目描述讲的不明不白，给的测试用例也莫名其妙。做出来后知道这个排列组合问题的设定是，m 个传送器互不相同，n 个人相同。

尝试使用动态规划解决问题。用 dp[i][j] 表示有 j 个人分配给 i 个传送器，想要处理这种情况，有两种可能的前置情况：

前 j-1 个人已经分配给了 i 个传送器，此时新添一个人坐到任意一个传送器上；
前 j-1 个人分配给 i-1 个传送器，新来的一个人单独坐一个传送器。

因此得到状态转移方程 dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]。

另一个问题是 dp 初始化问题。有以下几部分需要考虑：

当只有一个传送器时，即 i=1 时，所有人只能坐一个传送器，因此无论 j 为多少，dp[i][j] 均为 1；
当人数和传送器数量相等时，即 i=j 时，一人一个传送器，dp[i][j] 均为 1；
当传送器数量大于人数时，即 j>i 时，有些传送器空载，状态无效。

根据得到的信息写程序：

 1import java.util.Scanner;
 2
 3public class Main {
 4
 5    public static void main(String[] args) {
 6        Scanner scanner = new Scanner(System.in);
 7        int t = scanner.nextInt();
 8
 9        while (t-- > 0) {
10            int m = scanner.nextInt();
11            int n = scanner.nextInt();
12            System.out.println(countWays(m, n));
13        }
14
15        scanner.close();
16    }
17
18    private static int countWays(int m, int n) {
19        int[][] dp = new int[m + 1][n + 1];
20
21        for (int i = 1; i <= m; i++) {
22            dp[i][i] = 1;
23        }
24        for (int i = 1; i <= n; i++) {
25            dp[1][i] = 1;
26        }
27
28        for (int i = 2; i <= m; i++) {
29            for (int j = i + 1; j <= n; j++) {
30                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
31            }
32        }
33
34        return dp[m][n];
35    }
36}

AC！

等等！这里的 dp 数组似乎是一个杨辉三角，而杨辉三角又可以表示为二项式系数，二项式系数又可以表示为组合数，难道说……

用隔板法也可以解决这道题！

 1import java.util.Scanner;
 2
 3public class Main {
 4
 5    public static void main(String[] args) {
 6        Scanner scanner = new Scanner(System.in);
 7        int t = scanner.nextInt();
 8
 9        while (t-- > 0) {
10            int m = scanner.nextInt();
11            int n = scanner.nextInt();
12            System.out.println(combination(m - 1, n - 1));
13        }
14
15        scanner.close();
16    }
17
18    private static int combination(int m, int n) {
19        if (m > n / 2) {
20            m = n - m;
21        }
22        return arrangement(m, n) / arrangement(m, m);
23    }
24
25    private static int arrangement(int m, int n) {
26        if (m == 1) {
27            return n;
28        }
29        int res = 1;
30        for (int i = n; i > n - m; i--) {
31            res *= i;
32        }
33        return res;
34    }
35}

还是 AC！

而且这里的 combination 函数还能继续优化，从而把 arrangement 函数抛弃掉：

 1import java.util.Scanner;
 2
 3public class Main {
 4
 5    public static void main(String[] args) {
 6        Scanner scanner = new Scanner(System.in);
 7        int t = scanner.nextInt();
 8
 9        while (t-- > 0) {
10            int m = scanner.nextInt();
11            int n = scanner.nextInt();
12            System.out.println(combination(m - 1, n - 1));
13        }
14
15        scanner.close();
16    }
17
18    private static int combination(int m, int n) {
19        if (m == 1) {
20            return n;
21        }
22        if (m == n) {
23            return 1;
24        }
25        if (m > n / 2) {
26            m = n - m;
27        }
28        int res = 1;
29        for (int i = 1; i <= m; i++) {
30            res = res * (n - m + i) / i;
31        }
32        return res;
33    }
34}

AC！

Problem 1609 | QWQ和QAQ

Description

QWQ的朋友QAQ开了一个A工厂，但QAQ不是一个很精明的老板，A工厂只生产三种产品，需要三种原材料，第一种产品分别消耗第一种原材料a1、第二种原材料b1、第三种原材料c1，第二种产品分别是a2、b2、c2，第三种产品分别是a3、b3、c3，但原材料总量是有限制的，分别是a、b、c，第一种产品可以盈利d1元，第二种产品可以盈利d2元，第三种原材料可以盈利d3元，由于每个产品都不可以分解，所以所有产品的生产量一定是整数。QAQ不知道怎么合理安排生产让他的盈利最大，于是他求助QWQ，QWQ更不知道了，但你一定知道

Input

先输入一个数字t（t<20），代表数组的组数
每组数据包括五行
第一行三个数字a1、b1、c1
第二行三个数字a2、b2、c2
第三行三个数字a3、b3、c3
第四行三个数字a、b、c
第五行三个数字d1、d2、d3
保证所有输入都是非负整数，并且不大于200

Output

输出最大的总盈利

Sample Input

Sample Output

一道三维完全背包问题：有三件物品，每件物品有三个维度的重量，而且每件物品都可以无限获取。
物品数量较低，考虑使用深搜：

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        Scanner sc = new Scanner(System.in);
 6        int t = sc.nextInt();
 7        while (--t >= 0) {
 8            int[] a = new int[4];
 9            int[] b = new int[4];
10            int[] c = new int[4];
11            int[] d = new int[4];
12
13            for (int i = 1; i <= 4; i++) {
14                a[i % 4] = sc.nextInt();
15                b[i % 4] = sc.nextInt();
16                c[i % 4] = sc.nextInt();
17            }
18            d[1] = sc.nextInt();
19            d[2] = sc.nextInt();
20            d[3] = sc.nextInt();
21
22            int s1 = 0, s2 = 0, s3 = 0;
23            System.out.println(dfs(a, b, c, d, s1, s2, s3));
24        }
25        sc.close();
26    }
27
28    public static int dfs(int[] a, int[] b, int[] c, int[] d, int s1, int s2, int s3) {
29        int usedA = a[1] * s1 + a[2] * s2 + a[3] * s3;
30        int usedB = b[1] * s1 + b[2] * s2 + b[3] * s3;
31        int usedC = c[1] * s1 + c[2] * s2 + c[3] * s3;
32        if (usedA > a[0] || usedB > b[0] || usedC > c[0]) {
33            return 0;
34        }
35
36        int currentProfit = d[1] * s1 + d[2] * s2 + d[3] * s3;
37        int profit1 = dfs(a, b, c, d, s1 + 1, s2, s3);
38        int profit2 = dfs(a, b, c, d, s1, s2 + 1, s3);
39        int profit3 = dfs(a, b, c, d, s1, s2, s3 + 1);
40        int maxProfit = Math.max(Math.max(currentProfit, profit1), Math.max(profit2, profit3));
41        return maxProfit;
42    }
43}

超时了……再一看这道题，每一个数据都不超过 200，也就是说，即使在最极端的情况下，也就是每个维度的背包都为 200 而每件物品各个维度的重量都为 1 时，一件物品最多有 200 件，所以试试枚举。

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        Scanner sc = new Scanner(System.in);
 6        int t = sc.nextInt();
 7        while (--t >= 0) {
 8            int[] a = new int[4];
 9            int[] b = new int[4];
10            int[] c = new int[4];
11            int[] d = new int[4];
12
13            for (int i = 1; i <= 4; i++) {
14                a[i % 4] = sc.nextInt();
15                b[i % 4] = sc.nextInt();
16                c[i % 4] = sc.nextInt();
17            }
18            d[1] = sc.nextInt();
19            d[2] = sc.nextInt();
20            d[3] = sc.nextInt();
21
22            System.out.println(enumerate(a, b, c, d));
23        }
24        sc.close();
25    }
26
27    public static int enumerate(int[] a, int[] b, int[] c, int[] d) {
28        int maxProfit = 0;
29        for (int s1 = 0; s1 <= 200; s1++) {
30            for (int s2 = 0; s2 <= 200; s2++) {
31                for (int s3 = 0; s3 <= 200; s3++) {
32                    int usedA = a[1] * s1 + a[2] * s2 + a[3] * s3;
33                    int usedB = b[1] * s1 + b[2] * s2 + b[3] * s3;
34                    int usedC = c[1] * s1 + c[2] * s2 + c[3] * s3;
35                    if (usedA > a[0] || usedB > b[0] || usedC > c[0]) {
36                        break;
37                    }
38                    int currentProfit = d[1] * s1 + d[2] * s2 + d[3] * s3;
39                    maxProfit = Math.max(maxProfit, currentProfit);
40                }
41            }
42        }
43        return maxProfit;
44    }
45}

AC！

Problem 1610 | 海贼的奖品赞助

Description

本次ACM校赛得到了海贼科技的小部分奖品的赞助（30个水杯），尽管赞助的奖品不多，但也是要感谢赞助商的！由于水杯是加急定制的，所以生产水杯的的过程和以往不同，从而导致了水杯的高度竟然是不一样的；规定水杯高度低于20.00CM 为不合格的产品，你能计算一下这批水杯的合格率吗？

Input

本题单组数据！
输入数据第一行为n，表示水杯的数量；接下来是这n个水杯的高度（实数）；

Output

输出这批水杯的合格率（保留2位小数）；合格率=合格数量/总数

Sample Input

15
219.23 18.00 21.00 22.00 20.00

Sample Output

10.60

简单题

 1import java.util.Scanner;
 2
 3public class Main {
 4    public static void main(String[] args) {
 5        Scanner sc = new Scanner(System.in);
 6        double n = sc.nextDouble();
 7        int qualified = 0;
 8        for (int i = 0; i < n; i++) {
 9            if (sc.nextDouble() >= 20.00) {
10                qualified++;
11            }
12        }
13        sc.close();
14        System.out.println(String.format("%.2f", qualified / n));
15    }
16}

AC！