百度
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（合并）： 将两棵树合并成一棵。
操作步骤：
-
构建初始Treap： 将字符串中的每个字符构造成一个Treap的节点，按照顺序合并形成初始的Treap。
-
模拟操作： 对于每次操作，我们将位置iii之前的部分和之后的部分进行拆分，然后将位置iii的字符（单独的节点）移动到Treap的末尾。
- 拆分操作： 将Treap按照位置i−1i-1i−1进行拆分，得到左子树和右子树。
- 再次拆分： 对右子树按照位置1进行拆分，得到待移动的节点和剩余的右子树。
- 合并操作： 按照新的顺序合并左子树、右子树和待移动的节点，完成字符的移动。
- 输出结果： 通过中序遍历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个对子。
为了高效地解决这个问题，我们采取以下步骤：
-
生成所有可能的牌数组合：
- 使用递归函数
generateCounts，逐个确定每种牌的数量，确保总和为14。 - 由于每种牌的数量在0到4之间，我们可以在递归中限制每种牌的数量，并在总和超过14时剪枝。
-
判断牌型是否能胡牌：
-
对于每一种生成的牌数组合，使用函数
isWinningHand判断是否能胡牌。 isWinningHand函数尝试为每种可能的对子（数量不少于2的牌）减去2张牌作为对子，然后调用isMeld函数判断剩余的牌是否能组成面子。-
判断剩余的牌是否能组成面子：
-
使用递归函数
isMeld，尝试将剩余的牌划分为面子。 - 在每一步中，尝试：
- 刻子： 如果某张牌数量不少于3，则减去3张牌继续递归。
- 顺子： 如果连续的三张牌数量都不少于1，则各减去1张牌继续递归。
-
使用记忆化搜索优化：
-
为了避免重复计算，我们使用
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;
}
}