2个小时：15道单选 加 5道不定项选择 加 3道编程题

第一题：数学分析

题目描述

整数 1～n，计算选择 k 个数最多能获得多少积分。 计分规则：初始积分为 0，对于被选取的整数 i，如果 i+1 没选，则积分加 1 。

输入模式： 每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1<=T<=10^5)$ 代表数据组数，每组测试数据描述如下： 在一行上输入两个整数 $n, k (1<=n, k<=10^12)$，含义和题面描述一致。

输出描述： 对于每一组测试数据，在一行上输出一个整数，代表最多能获得的积分

示例： 输入：

2
1 1
4 2

输出：

1
2

说明：

第一个样例选择 1，积分为 1。

第二个样例一种可行方案为 1, 3，积分为 2。

解题思路

问题分析：

• 目标：从整数 1 到 n 中选择 k 个数，最大化积分。
• 积分规则：初始积分为 0，对于被选取的整数 i，如果 i+1 没选，则积分加 1。

思考如何最大化积分：

• 关键点：我们需要最大化被选取的整数中，其后继（i+1）未被选取的数量。
• 策略：为了最大化积分，我们需要避免选取连续的数。也就是说，尽可能让每个被选取的数的下一个数未被选取。

推导最大积分公式：

• 最大可能的积分数 = 选取的数中，其后继未被选取的数的数量。
• 如果我们能完全避免选取连续的数，那么最大积分就是 k。
• 但是，当 k 比 n 一半还大时，就无法避免选取连续的数。

计算最大积分的方法：

• 最大积分 = min(k, n - k + 1)

  • 解释：
    • 当 k ≤ n/2 时，可以完全避免选取连续的数，最大积分为 k。
    • 当 k > n/2 时，不可避免地要选取一些连续的数，此时最大积分会减少。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            long n = sc.nextLong();
            long k = sc.nextLong();
            long maxScore = n - k + 1;
            if(maxScore < 0) maxScore = 0;
            long ans = Math.min(k, maxScore);
            System.out.println(ans);
        }
    }
}

第二题：字符串

题目描述

长度为 n 只包含小写字母的字符串 S，下标 1 开始。进行 n 次操作，第 i 次操作将 $S_i$ 移动到字符串末尾。输出 n 次操作后的字符串。

例如字符串 "abqde" ，第一步 "bqdea" ，第二步 "bdeaq" ，第三步 "bdaqe"，第四步 "bdaeq" ，第五步 "bdaeq"

输入描述： 在一行上输入一个由小写字母构成的字符串，长度记为 $n(1<=n<=10^6)$

输出描述： 在一行上输出一个字符串，表示操作后的字符串。

示例： 输入：

paectc

输出：

accept

解题思路

由于字符串长度可能达到 10610^6106，直接模拟操作会导致时间复杂度过高。为了高效地模拟每次从中间删除一个字符并移动到末尾的操作，我们采用了平衡树（如Treap） 来实现。

在这个程序中，我们使用了Treap（树堆）来支持以下操作：

• Split（拆分）： 根据位置将树分成两部分。
• Merge（合并）： 将两棵树合并成一棵。

操作步骤：

1. 构建初始Treap： 将字符串中的每个字符构造成一个Treap的节点，按照顺序合并形成初始的Treap。

2. 模拟操作： 对于每次操作，我们将位置iii之前的部分和之后的部分进行拆分，然后将位置iii的字符（单独的节点）移动到Treap的末尾。

   • 拆分操作： 将Treap按照位置i−1i-1i−1进行拆分，得到左子树和右子树。
   • 再次拆分： 对右子树按照位置1进行拆分，得到待移动的节点和剩余的右子树。
   • 合并操作： 按照新的顺序合并左子树、右子树和待移动的节点，完成字符的移动。

3. 输出结果： 通过中序遍历Treap，得到最终的字符串。

注意事项：

• 随机优先级： 为了保证Treap的平衡性，每个节点都被赋予了一个随机的优先级。
• 维护子树大小： 在每次操作后，及时更新节点的子树大小，以保证Split和Merge操作的正确性。

代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

public class Main {

    static class TreapNode {
        char c;
        int size;
        long priority;
        TreapNode left, right;

        TreapNode(char c) {
            this.c = c;
            size = 1;
            priority = random.nextLong();
        }
    }

    static Random random = new Random();

    static int size(TreapNode node) {
        return node == null ? 0 : node.size;
    }

    static void updateSize(TreapNode node) {
        if (node != null) {
            node.size = size(node.left) + size(node.right) + 1;
        }
    }

    static TreapNode merge(TreapNode left, TreapNode right) {
        if (left == null) return right;
        if (right == null) return left;
        if (left.priority > right.priority) {
            left.right = merge(left.right, right);
            updateSize(left);
            return left;
        } else {
            right.left = merge(left, right.left);
            updateSize(right);
            return right;
        }
    }

    static void split(TreapNode node, int k, TreapNode[] result) {
        if (node == null) {
            result[0] = result[1] = null;
            return;
        }
        if (size(node.left) < k) {
            split(node.right, k - size(node.left) - 1, result);
            node.right = result[0];
            updateSize(node);
            result[0] = node;
        } else {
            split(node.left, k, result);
            node.left = result[1];
            updateSize(node);
            result[1] = node;
        }
    }

    static TreapNode root = null;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] initialString = br.readLine().toCharArray();

        // Build initial treap
        for (char c : initialString) {
            TreapNode node = new TreapNode(c);
            root = merge(root, node);
        }

        int n = initialString.length;

        for (int i = 1; i <= n; i++) {
            TreapNode[] split1 = new TreapNode[2];
            split(root, i - 1, split1);
            TreapNode left = split1[0];
            TreapNode right = split1[1];

            TreapNode[] split2 = new TreapNode[2];
            split(right, 1, split2);
            TreapNode middle = split2[0];
            TreapNode right2 = split2[1];

            // Merge left, right2, middle
            TreapNode temp = merge(left, right2);
            root = merge(temp, middle);
        }

        // In-order traversal to get the final string
        StringBuilder sb = new StringBuilder();
        inorder(root, sb);
        System.out.println(sb.toString());
    }

    static void inorder(TreapNode node, StringBuilder sb) {
        if (node == null) return;
        inorder(node.left, sb);
        sb.append(node.c);
        inorder(node.right, sb);
    }
}

第三题

题目描述

Ame9最近沉迷麻将。Ame9喜欢万字清一色（只包含万字牌的胡牌），他决定只胡万字清一色。

普通的麻将游戏中，万子牌有以下9种，每种牌有4张，我们用数字1~9表示。1表示一万,2表示二万，以此类推。 但是注意：本题中一共有n 种万字牌，使用数字 1～n 表示。

胡牌，是麻将中的胜利条件。要达成这个条件，手中14张牌必须组成四个面子+一个对子的形式（不考虑七对子） 对子即两张相同的牌。 面子又分为顺子和刻子两种。

• 顺子：三张连续的牌，如123或567
• 刻字：三张相同的牌，如333或999

无论是顺子还是刻子，都可以构成胡牌所需的面子。 举例：

• 11223355577999是胡牌
• 11223344467899是胡牌
• 11223344467999不是胡牌

现在给出一个正整数 $n (1<=n<=13)$，假设Ame9只能使用1至 n 之间的万字牌胡牌，请问他有几种不同的胡牌牌型？两种牌型是不同的，当且仅当存在一种牌在两种牌型中的枚数不同。

输入描述：

一行一个正整数 n (1<=n<=13)

输出描述：

一行一个整数，代表胡牌牌型的种数。

示例1： 输入：

4

输出：

10

说明：

合法的胡牌牌型：
11222233334444
11122233334444
11122223334444
11122223333444
11112233334444
11112223334444
11112223333444
11112222334444
11112222333444
11112222333344

示例2： 输入：

1

输出：

0

说明：

4张一万凑不齐14张牌，当然没有胡牌牌型

解题思路

由于每种牌的张数有限（每种牌最多有4张），并且总共需要14张牌，因此我们需要生成所有可能的牌数组合，使得：

• 每种牌的数量在0到4之间。
• 所有牌的总数为14。
• 该组合能被划分为4个面子（顺子或刻子）和1个对子。

为了高效地解决这个问题，我们采取以下步骤：

1. 生成所有可能的牌数组合：

   • 使用递归函数generateCounts，逐个确定每种牌的数量，确保总和为14。
   • 由于每种牌的数量在0到4之间，我们可以在递归中限制每种牌的数量，并在总和超过14时剪枝。

2. 判断牌型是否能胡牌：

   • 对于每一种生成的牌数组合，使用函数isWinningHand判断是否能胡牌。
   • isWinningHand函数尝试为每种可能的对子（数量不少于2的牌）减去2张牌作为对子，然后调用isMeld函数判断剩余的牌是否能组成面子。

3. 判断剩余的牌是否能组成面子：

   • 使用递归函数isMeld，尝试将剩余的牌划分为面子。
   • 在每一步中，尝试：
     • 刻子： 如果某张牌数量不少于3，则减去3张牌继续递归。
     • 顺子： 如果连续的三张牌数量都不少于1，则各减去1张牌继续递归。

4. 使用记忆化搜索优化：

   • 为了避免重复计算，我们使用HashMap记录已经计算过的牌数组合的结果。
   • 我们将牌数组合编码为一个唯一的long类型的键值，以便在哈希表中存储和检索。

注意事项：

• 剪枝优化： 在生成牌数组合和递归判断时，及时剪枝可以大大减少计算量。
• 边界条件： 如果总牌数不足14张（即n * 4 < 14），则无法胡牌，直接输出0。
• 记忆化搜索的键值生成： 由于每种牌的数量在0到4之间，我们使用5进制编码牌数组合，以生成唯一的键值。

运行时间分析：

• 由于n的最大值为13，且每种牌的数量有限，生成的牌数组合总数是可控的。
• 通过剪枝和记忆化搜索，可以在合理的时间内完成计算。

算法复杂度：

• 时间复杂度： O(总牌数组合数 × 递归深度)
• 空间复杂度： O(记忆化搜索的哈希表大小)

代码实现

import java.util.*;

public class Main {
    static int n;
    static int[] counts;
    static int totalCount = 0;
    static Map<Long, Boolean> memoMeld = new HashMap<>();
    static Map<Long, Boolean> memoWin = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        counts = new int[n + 1]; // counts[1..n]

        if (n * 4 < 14) {
            System.out.println(0);
            return;
        }

        generateCounts(1, 0);
        System.out.println(totalCount);
    }

    static void generateCounts(int index, int sum) {
        if (index == n + 1) {
            if (sum == 14) {
                if (isWinningHand()) {
                    totalCount++;
                }
            }
            return;
        }
        for (int cnt = 0; cnt <= 4; cnt++) {
            if (sum + cnt > 14) break;
            counts[index] = cnt;
            generateCounts(index + 1, sum + cnt);
            counts[index] = 0;
        }
    }

    static boolean isWinningHand() {
        long key = getKey(counts);
        if (memoWin.containsKey(key)) {
            return memoWin.get(key);
        }
        for (int i = 1; i <= n; i++) {
            if (counts[i] >= 2) {
                counts[i] -= 2;
                if (isMeld()) {
                    counts[i] += 2;
                    memoWin.put(key, true);
                    return true;
                }
                counts[i] += 2;
            }
        }
        memoWin.put(key, false);
        return false;
    }

    static boolean isMeld() {
        long key = getKey(counts);
        if (memoMeld.containsKey(key)) {
            return memoMeld.get(key);
        }
        // Check if counts are all zero
        boolean empty = true;
        for (int i = 1; i <= n; i++) {
            if (counts[i] > 0) {
                empty = false;
                break;
            }
        }
        if (empty) {
            memoMeld.put(key, true);
            return true;
        }
        for (int i = 1; i <= n; i++) {
            if (counts[i] >= 3) {
                counts[i] -= 3;
                if (isMeld()) {
                    counts[i] += 3;
                    memoMeld.put(key, true);
                    return true;
                }
                counts[i] += 3;
            }
            if (i + 2 <= n && counts[i] >= 1 && counts[i + 1] >= 1 && counts[i + 2] >= 1) {
                counts[i]--;
                counts[i + 1]--;
                counts[i + 2]--;
                if (isMeld()) {
                    counts[i]++;
                    counts[i + 1]++;
                    counts[i + 2]++;
                    memoMeld.put(key, true);
                    return true;
                }
                counts[i]++;
                counts[i + 1]++;
                counts[i + 2]++;
            }
        }
        memoMeld.put(key, false);
        return false;
    }

    static long getKey(int[] counts) {
        long key = 0;
        for (int i = 1; i <= n; i++) {
            key = key * 5 + counts[i];
        }
        return key;
    }
}

版权所有

版权归属：cloudinwind

本文链接：/review/n88ryxsz/

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)