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)。具体步骤如下：

1. 初始化矩阵：

   • 创建一个 f 矩阵，其中 f[u][v] 表示用户 u 对用户 v 的直接点赞次数。
   • 对于每个点赞记录 (u, v)，将 f[u][v] 增加 1。

2. 应用 Floyd-Warshall 算法：

   • 对于每一个中间用户 k，检查是否通过 k 可以增加 f[u][v]。
   • 更新规则：f[u][v] = max(f[u][v], min(f[u][k], f[k][v]))。

3. 处理查询：

   • 对于每个查询 (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();
    }
}

版权所有

版权归属：cloudinwind

本文链接：/review/ounjlb4e/

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