科大讯飞
2个小时： 必做题：12道选择，3道编程 选做题：7道Java基础, 3道数据库，3道linux（都是选择）
第一题¶
题目描述：¶
小红拿到了一个仅包含小写字母的字符串。
对于每个下标 \(p\)，如果 \(p\) 的二进制表示有奇数个1，那么将 \(s_p\) 修改为对应的大写字母。（下标从1开始）
例如，字符串"abcdefg"，其中下标1、2、4、7在二进制表示下都有奇数个1，因此字符串变为"ABcDefG"。
小红想知道她拿到的字符串修改是什么，你能帮帮她吗？
输入描述：
第一行为T，表示有T组输入。
接下来T行，每行一个仅包含小写字母的字符串。
输出描述：
输出T行，每行一个字符串，表示修改后的字符串。
代码实现¶
import java.util.Scanner;
public class StrTran {
public static int countOnes(int n) {
int count = 0;
while(n != 0) {
if ((n & 1) == 1) count++;
n >>= 1;
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
scanner.nextLine(); // 读取整数后的换行符
for(int t = 0; t < T; t++) {
String s = scanner.nextLine();
StringBuilder result = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
int position = i + 1; // 下标从1开始
int ones = countOnes(position);
char c = s.charAt(i);
if(ones % 2 == 1) {
c = Character.toUpperCase(c);
}
result.append(c);
}
System.out.println(result.toString());
}
scanner.close();
}
}
第二题¶
题目描述¶
给出一个长度为 n 的整数数组 ，下标从 1 开始。q 次询问，每次询问给出两个区间 \([l_1, r_1] , [l_2, r_2]\) ，先让下标在 \([l_1, r_1]\) 里的元素乘以 2，再让下标在 \([l_2, r_2]\) 里的元素乘以2 ，输出每次询问操作后数组总和是多少？询问是相互独立的，每次询问后都把数组还原为初始状态。
输入描述：
第一行包含两个整数 \(n, q(1<=n, q <=2*10^5)\)，表示数组大小和询问个数。 第二行包含 n 个整数 \(a_i (-1*10^5 <= a_i <= 10^5)\)，表示数组 a。 接下来 q 行，每行四个整数 \(l_1, r_1, l_2, r_2\) (1<= l_1 <= r_1 <= n ) ，表示操作区间。
输出描述： 输出包含 q 行，每行一个整数，表示每次询问操作后的数组总和。
示例： 输入： 3 2 1 2 1 1 2 2 3 1 1 2 2 输出： 12 7
说明： 第一次询问： [1, 2]内元素乘 2， a=[2, 4, 1]， [2,3]内元素乘 2， a=[2, 8, 2]，数组总和是 12。 询问后数组a还原为初始状态 a=[1, 2, 1] 第二次询问：[1, 1]内元素乘 2， a=[2, 2, 1]， [2,2]内元素乘 2， a=[2, 4, 1]，数组总和是 7。
思路分析¶
-
计算前缀和：
- 首先计算数组的前缀和，这样可以在常数时间内求出任意区间的元素之和。
-
处理每个询问：
-
对于每个询问，给定两个区间
[l1, r1]和[l2, r2]。 - 计算区间
[l1, r1]内的元素之和S1。 - 计算区间
[l2, r2]内的元素之和S2。 - 计算两个区间的交集
[max(l1, l2), min(r1, r2)]，如果有交集，则计算交集区间内的元素之和S12，否则S12为 0。 - 根据题意，最终的数组总和可以表示为
S + S1 + S2 + S12，其中S是数组的初始总和。 - 输出结果：
- 对于每个询问，计算上述表达式并输出结果。
代码实现¶
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取 n 和 q
int n = sc.nextInt();
int q = sc.nextInt();
// 读取数组 a（1-based indexing）
long[] a = new long[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextLong();
}
// 计算前缀和
long[] prefix = new long[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + a[i];
}
long S = prefix[n]; // 初始总和
StringBuilder sb = new StringBuilder();
// 处理每个询问
for (int i = 0; i < q; i++) {
int l1 = sc.nextInt();
int r1 = sc.nextInt();
int l2 = sc.nextInt();
int r2 = sc.nextInt();
// 计算 S1 和 S2
long S1 = prefix[r1] - prefix[l1 - 1];
long S2 = prefix[r2] - prefix[l2 - 1];
// 计算交集 S12
int interL = Math.max(l1, l2);
int interR = Math.min(r1, r2);
long S12 = 0;
if (interL <= interR) {
S12 = prefix[interR] - prefix[interL - 1];
}
// 计算最终总和
long total = S + S1 + S2 + S12;
sb.append(total).append('\n');
}
// 输出所有结果
System.out.print(sb.toString());
sc.close();
}
}
过了67%
第三题¶
题目描述¶
现在发的动态都有点赞功能。如果A发的动态。B点赞了 x 次。那么B对A的赞同度为x， 记为 f(B, A), 并且f(B, A) 和 f(A, B)不一定相等。并且赞同度具有传递性。 f(A, B) = max(f(A, B), min(f(A, C), f(C, B)) ),可以多次传递。现在有 n 个人(以1～n的整数代指)，他们之间有 m 条点赞记录。现在有Q次询问，每次询问输入 u, v (空格隔开)，询问f(u, v)的值。
输入描述： 第一行输入三个整数 n, m , Q (1<=n<=100, 1<=m<=10^5, 1<=Q<=10^3) 接下来 m 行，每行输入u,v（代表u给v点了一次赞, 1<=u, v<=n ） 接下来 Q 行，每行输入u, v。
输出描述： 对于每个询问输出一个整数表示答案。
示例： 输入： 2 7 4 1 1 1 2 1 2 2 1 2 1 2 1 2 2 1 1 1 2 2 1 2 2 输出： 2 2 3 2
思路分析¶
要高效地计算社交网络中用户之间的“赞同度” f(u, v)。这个问题可以被建模为一个图论问题，其中每个用户是图中的一个节点，每次点赞操作是一个有向边，权重代表点赞次数。赞同度的定义类似于路径中边权的最小值的最大化。
由于 n 最大为 100，我们可以使用 Floyd-Warshall 算法来预处理所有用户对之间的最大赞同度 f(u, v)。具体步骤如下：
-
初始化矩阵：
- 创建一个
f矩阵，其中f[u][v]表示用户u对用户v的直接点赞次数。 - 对于每个点赞记录
(u, v)，将f[u][v]增加 1。 -
应用 Floyd-Warshall 算法：
-
对于每一个中间用户
k，检查是否通过k可以增加f[u][v]。 - 更新规则：
f[u][v] = max(f[u][v], min(f[u][k], f[k][v]))。 -
处理查询：
-
对于每个查询
(u, v)，直接输出f[u][v]。
- 创建一个
代码实现¶
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取 n, m, Q
int n = sc.nextInt();
int m = sc.nextInt();
int Q = sc.nextInt();
// 初始化 f 矩阵，使用 1-based 索引
int[][] f = new int[n + 1][n + 1];
// 读取 m 条点赞记录
for(int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
f[u][v]++;
}
// 应用 Floyd-Warshall 算法，计算所有 f(u, v)
for(int k = 1; k <= n; k++) {
for(int u = 1; u <= n; u++) {
int f_u_k = f[u][k];
if(f_u_k == 0) continue; // 如果 u 到 k 没有路径，跳过
for(int v = 1; v <= n; v++) {
if(f[k][v] == 0) continue; // 如果 k 到 v 没有路径，跳过
int temp = f_u_k < f[k][v] ? f_u_k : f[k][v];
if(temp > f[u][v]) {
f[u][v] = temp;
}
}
}
}
// 处理 Q 个查询
StringBuilder sb = new StringBuilder();
for(int i = 0; i < Q; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
sb.append(f[u][v]).append('\n');
}
// 输出结果
System.out.print(sb.toString());
sc.close();
}
}