第八届传智杯-程序设计赛道初赛（第一场）
第八届传智杯程序设计赛道初赛第一场次补题链接：https://www.nowcoder.com/exam/oj/ta?tpId=405
带' * '的题目为复盘题目
A 蛇鸟
题目
蛇鸟是一种类似于蛇和鸟的可爱生物。 蛇鸟的主要食物是水果，每吃一个水果，它的长度就会增加1。水果离地面具有一定的高度，第i (1≤i≤N )个果实的高度为hi。 蛇鸟可以吃到小于等于其长度的水果。当蛇鸟的初始长度为L时，求它吃水果能达到的最大长度。
代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int L = in.nextInt();
int [] h = new int [N];
for(int i=0;i<N;i++) {
h[i] = in.nextInt();
}
Arrays.sort(h);
for(int j=0;j<N;j++) {
if (L>=h[j]) {
L++;
}
}
System.out.println(L);
in.close();
}
}
总结：
这道题目就是考察了一下数组排序，然后再遍历数组
B 小红的大小写字母*
题目：
小红拿到了一个仅由大小写字母构成的长度为 nn 的字符串，她每次操作可以将一个字符在大小写之间切换（例如将 ‘a’ 变为 ‘A’，或将 ‘Y’ 变为 ‘y’）。她希望经过恰好 k 次操作后，大写字母的数量尽可能多。请输出最终字符串中大写字母的数量。
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
String string = scanner.next();
int count = 0; //记录小写字母的个数
//转成数组
char c[] = new char[n];
c = string.toCharArray();
//遍历数组
for(int i=0;i<n;i++) {
if (c[i]>=97) {
count++;
}
}
//如果小写字母的数量小于操作数
if(count < k) {
//那么多出的次数就会对一个字母，反复转换
//如果为偶数次，那就没变化
if((k-count)%2==0) {
System.out.println(n);
}
//为奇数，那就一定会有一个不是大写
else {
System.out.println(n-1);
}
}
//如果操作数不够，那就是大写数量加上操作数
else {
System.out.println(n-count+k);
}
scanner.close();
}
}
总结：
这道题目没啥难度，就是考察遍历数组，硬说考点，那就是ascll码
C 字符串解密*
上次是ai，重写一遍
题目
给定一个由字符 ‘0’ 和 ‘1’ 构成的字符串 s。我们从字符串开头开始，按照长度依次取出以下子串并解析为十进制数：
- 长度 1 的子串
- 长度 2 的子串
- 长度 3 的子串
- ···
- 长度 10 的子串
然后循环回长度 1，依此类推；子串被取走后，视为删除，下一次从剩余的字符串中继续取子串，直到剩余字符不足以组成当前长度的子串
请输出解析得到的十进制数字序列
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.next();
int k = 1; //k的作用就是截断字符串的长度和2的指数
int len = string.length(); //输入字符串
int sum[] = new int [len]; //长度肯定只多不少
char c[] = string.toCharArray(); //转成数组，方便转换
int i = 0; //指针，遍历数组c
int j = 0; //指针，遍历数组sum
while(k <= len) {
int tem = 0; //临时解密结果
int e = k-1; //修正指数偏差
//转换
for(int n=0;n<k;n++) {
tem+= ((int)c[i++]-48)* Math.pow(2,e--);
}
//剩余长度修正
len-=k;
//记录转换结果
sum[j] = tem;
//截取长度自增，sum指针自增,而且k不能超过10
if (++k > 10) {
k=1;
}
j++;
}
//输出，转换成功的结果个数
System.out.println(j);
//输出每一个结果
for(int m = 0;m < j;m++) {
System.out.print(sum[m]+" ");
}
scanner.close();
}
}
总结：
这道题，有点意思，首先，需要数组截断，然后进行数制转变（二进制转成十进制）而且的话，这个截断长度还不是一直加，每10轮回，那就考查到了重置数值（也可以使用取余运算），而且k最小为1不是0
D 锁*
题目：
已知牛牛有 n 份资源，编号为 1 到 n，初始均处于未上锁状态。现在共有 m 次操作，每次给定一个编号 p：
- 若编号为 p 的资源未上锁，则为其上锁；
- 否则，解除锁，使其回到未上锁状态。
每次操作后，牛牛希望分别统计区间 [1,x] 与 [y,n] 中“可访问”资源的数量。这里规定，资源可访问当且仅当其处于未上锁状态。
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
int lm[] = new int [400000];
int rm[] = new int [400000];
int i=0;
for(int q=0;q<T;q++) {
boolean lock[] = new boolean [200000];
int n = scanner.nextInt();
int m = scanner.nextInt();
int x = scanner.nextInt();
int y = scanner.nextInt();
int tem[] = new int [m];
int left = x;
int right = n-y+1;
for(int k=0;k<m;k++) {
tem[k] = scanner.nextInt();
}
for(int j=0;j<m;j++) {
if (!lock[tem[j]]) {
lock[tem[j]]= true;
if (tem[j]<=x) {
left--;
}
if (tem[j]>=y) {
right--;
}
}
else {
lock[tem[j]]= false;
if (tem[j]<=x) {
left++;
}
if (tem[j]>=y) {
right++;
}
}
lm[i]=left;
rm[i]=right;
i++;
}
}
for (int l=0;l<i;l++) {
System.out.println(lm[l]+" "+rm[l]);
}
scanner.close();
}
}
总结：
这个题，主要是思路，首先考查第一个就是，多组数据输入用for循环，然后，把每组数据，分成两部分，然后这里怎么判断是否上锁呢？就是创建一个boolean类型的数组，每操作一次取反，并且对应的状态记录指针加减1，最后再按照每一步操作，记录一下上锁和未上锁的状态（创建数组记录结果）
E 牛牛的括号式*
题目：
牛牛给出了一个关于未知量 x 的多项式。这个多项式以字符串的形式表示，它由若干个形如 (x-d) 或 (x+d) 的括号表达式相乘构成。其中，d 是一个 1 到 9 之间的数字字符。牛牛想知道，当这个多项式完全展开后，x 的一次项（即 x1项）的系数是多少？请计算这个系数，由于答案可能很大，请将答案对 (10007) 取模后输出。
分析：
这道题目，有点难度，这里我根据ai提示，做一些分析
设多项式为：P(x) = (x-a₁)(x-a₂)...(x-aₙ)
其中：
- 若因子为 (x-d)，则 aᵢ = d
- 若因子为 (x+d)，则 aᵢ = -d
通过展开规律发现：
- 当 n=2 时：(x-a)(x-b) = x² - (a+b)x + ab，一次项系数为 -(a+b)
- 当 n=3 时：(x-a)(x-b)(x-c) = x³ - (a+b+c)x² + (ab+bc+ca)x - abc，一次项系数为 ab+bc+ca
- 一般地，coeff = (-1)n-1 × Sn-1
那么我们的思路就清晰了
设 P = a1a2a3...an，则：
这里求逆元，用到了费马小定理
Sn-1 = P/a1 + P/a2 + ... + P/an = P × (1/a1 + 1/a2 + ... + 1/an)
先计算所有数的乘积 P，再计算所有数的倒数之和，两者相乘得到 Sn-1
代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static final long MOD = 10007L;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//读入字符串
String string = scanner.nextLine();
//定义动态数组
List<Integer> aList = new ArrayList<>();
//循环遍历，填入动态数组
int i = 0;
while (i < string.length()) {
if (string.charAt(i) == '(') {
i++; // 跳过 '('
i++; // 跳过 'x'
char sign = string.charAt(i); i++; // 符号
int d = string.charAt(i) - '0'; i++; // 数字
i++; // 跳过 ')'
if (sign == '-') aList.add(d);
else aList.add(-d);
} else {
i++;
}
}
int n = aList.size();
if (n == 0) {
System.out.println(0);
return;
}
//计算P
long P = 1;
for (int a : aList) {
long aMod = (a % MOD + MOD) % MOD;
P = (P * aMod) % MOD;
}
// 计算逆元和
long sumInv = 0;
for (int a : aList) {
long aMod = (a % MOD + MOD) % MOD;
sumInv = (sumInv + powMod(aMod, MOD-2)) % MOD;
}
// 计算 S
long S = (P * sumInv) % MOD;
// 计算最终系数
long ans = (n % 2 == 1) ? S : (MOD - S) % MOD;
System.out.println(ans);
scanner.close();
}
// 求逆元
static long powMod(long a, long b) {
long res = 1;
a %= MOD;
while (b > 0) {
if ((b & 1) == 1) res = (res * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
}
总结：
这个题，不简单，最难的点还是找规律，其次就是如何计算P和S，这里求解S，是用到了费马小定理，最后还要进行取余，所以这道题，尽力理解就行
F 选药*
题目：
小红拿到了n 种药品，第i种药品的疼痛程度是ai，功效值是bi。小红希望选择一种药品，在疼痛值不超过x的情况下功效值尽可能大。你能帮帮她吗？共有q次询问
代码：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<Choice> lists = new ArrayList<>();
int n = scanner.nextInt();
for(int i=0;i<n;i++) {
int pain = scanner.nextInt();
int effect = scanner.nextInt();
lists.add(new Choice(pain, effect));
}
// 1. 只按pain从小到大排序
Collections.sort(lists, new Comparator<Choice>() {
@Override
public int compare(Choice c1, Choice c2) {
return Integer.compare(c1.pain, c2.pain);
}
});
// 2. 计算前缀最大值数组
int[] prefixMax = new int[n];
if (n > 0) {
prefixMax[0] = lists.get(0).effect;
for (int i = 1; i < n; i++) {
prefixMax[i] = Math.max(prefixMax[i - 1], lists.get(i).effect);
}
}
int ask = scanner.nextInt();
int output[] = new int [ask];
// 3. 处理每个查询
for (int j = 0; j < ask; j++) {
int endure = scanner.nextInt();
// 特判：如果列表为空
if (n == 0) {
System.out.println(-1);
continue;
}
// 特判：如果第一个药品的pain就大于endure
if (lists.get(0).pain > endure) {
output[j] = -1;
continue;
}
// 二分查找：找到最后一个 pain <= endure 的位置
int left = 0, right = n - 1;
int pos = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (lists.get(mid).pain <= endure) {
pos = mid; // 记录这个可能的位置
left = mid + 1; // 尝试往右找更大的
} else {
right = mid - 1; // 往左找
}
}
// 保存每一次查询的最大前缀值
output[j] = prefixMax[pos];
}
for(int k=0;k<ask;k++) {
System.out.println(output[k]);
}
scanner.close();
}
}
class Choice{
public int pain;
public int effect;
public Choice( int pain, int effect) {
this.pain = pain;
this.effect = effect;
}
public Choice() {}
}
总结：
这道题，出的挺好的，他考察了对象类型的创建，然后运用comparator进行排序，最后又创建了一个最大前缀值数组，那么怎么创建的呢？又怎么使用呢？创建的话，就是按pain排序好,先第一个对象的effect值作为初始值，后续跟每一个pain值对应对象的effect的值，二者选最大。使用的话，就是运用到了二分查找，先找到小于等于indure的最大pain值，然后锁定位置，在最大前缀值数组取出对应的值，就是结果
G 字符串字串*
题目：
给定一个仅包含小写字母的字符串 s。请计算这个字符串的所有非空子串中，不包含字符 ‘d’ 且同时包含字符 ‘r’ 与 ‘e’ 的子串数量。
【名词解释】子串：为从原字符串中，连续的选择一段字符（可以全选）得到的新字符串。
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
String s[] = string.split("d");
long totalCount = 0;
// 处理每一段
for (String seg : s) {
if (seg.length() == 0) continue; // 跳过空段
// 计算这一段中同时包含'r'和'e'的子串数
totalCount += countSegmentSubstrings(seg);
}
System.out.println(totalCount);
scanner.close();
}
// 计算一个字符串（不含'd'）中，同时包含'r'和'e'的子串数量
private static long countSegmentSubstrings(String s) {
int n = s.length();
// 先检查这一段是否同时包含'r'和'e'
boolean hasR = false, hasE = false;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == 'r') hasR = true;
if (c == 'e') hasE = true;
}
// 如果不包含'r'或不包含'e'，那么这一段没有合法子串
if (!hasR || !hasE) {
return 0;
}
long count = 0;
// 对每个左端点，找到最小的右端点使得子串同时包含r和e
for (int i = 0; i < n; i++) { // 左端点
boolean foundR = false, foundE = false;
for (int j = i; j < n; j++) { // 右端点
char c = s.charAt(j);
if (c == 'r') foundR = true;
if (c == 'e') foundE = true;
// 如果当前子串同时包含'r'和'e'
if (foundR && foundE) {
// 从当前位置j到末尾的所有子串都合法
count += (n - j);
break; // 提前结束内层循环
}
}
}
return count;
}
}
总结：
这道题，确实很难，难在了代码实现上面，思路还是很清晰的，就学习一下吧
思路：先读入一段字符串，以'd'分割开，然后存入新的字符串数组，对每一个字符串进行遍历，先判断这个字符串是否含有'r''e'，如果没有，直接返回0，否则，计算子字符串。那怎么计算呢？用双指针（两层循环），第一层是左端点，第二层是右端点，开始遍历这个字符串，找到最早出现r和e的位置，直接计算剩下长度，因为无论是什么都满足。如果你有疑问，可能是这些情况，rere，erer，erre等等，这些情况，都会在左端点的循环遍历时全覆盖，所以无需担心。也可以使用暴力枚举，但是既然是比赛，肯定会限制时间，所以这里就简化了，把count++，改成了运算
H 密码锁*
题目：
有一个密码锁，密码锁是由一个N×M的矩阵构成，该密码锁只有在每一列上，每个数均不同的情况下，才能被打开，此外，还可以对矩阵的任意一行上的数字进行翻转操作（每行最多只能翻转一次）；若此时仍然无法满打开密码锁的条件，则该密码锁将无法被打开。现在给出密码锁上的密码矩阵，请你编写一个程序判断是否可以打开该密码锁
代码：
import java.util.*;
import java.io.*;
public class Main {
// 2-SAT 图和 Tarjan 算法所需的全局变量
static List<Integer>[] adj;
static int[] dfn, low, sccId;
static Stack<Integer> tarjanStack;
static boolean[] inStack;
static int timestamp, sccCount;
static int n; // 行数
static int nextVarIndex; // 下一个可用的辅助变量节点索引
// 新的节点编号: 2*i (true), 2*i+1 (false)
// neg(u) is u ^ 1
static int neg(int u) {
return u ^ 1;
}
// 添加 2-SAT 子句 (a V b), 等价于 (!a -> b) AND (!b -> a)
static void addClause(int u, int v) {
// (u V v) <=> (!u => v) AND (!v => u)
adj[neg(u)].add(v);
adj[neg(v)].add(u);
}
// Tarjan 算法的迭代实现
static void tarjanIterative(int startNode, int numNodes) {
Stack<int[]> dfsStack = new Stack<>();
dfsStack.push(new int[]{startNode, 0});
while (!dfsStack.isEmpty()) {
int[] state = dfsStack.peek();
int u = state[0];
int neighborIdx = state[1];
if (dfn[u] == 0) {
timestamp++;
dfn[u] = low[u] = timestamp;
tarjanStack.push(u);
inStack[u] = true;
}
if (neighborIdx < adj[u].size()) {
int v = adj[u].get(neighborIdx);
state[1]++;
if (dfn[v] == 0) {
dfsStack.push(new int[]{v, 0});
} else if (inStack[v]) {
low[u] = Math.min(low[u], dfn[v]);
}
} else {
dfsStack.pop();
if (dfn[u] == low[u]) {
sccCount++;
int node;
do {
node = tarjanStack.pop();
inStack[node] = false;
sccId[node] = sccCount;
} while (node != u);
}
if (!dfsStack.isEmpty()) {
int parent = dfsStack.peek()[0];
low[parent] = Math.min(low[parent], low[u]);
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] matrix = new int[n][m];
int[][] reversedMatrix = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
for (int j = 0; j < m; j++) {
reversedMatrix[i][j] = matrix[i][m - 1 - j];
}
}
// 两阶段建图以优化内存
List<int[]> edgeList = new ArrayList<>();
int nextVarIndex = n;
int maxNode = 2 * n - 1;
Map<Integer, List<Integer>> valueToNodes = new HashMap<>(n * 2);
for (int j = 0; j < m; j++) {
valueToNodes.clear();
for (int i = 0; i < n; i++) {
valueToNodes.computeIfAbsent(matrix[i][j], k -> new ArrayList<>()).add(2 * i);
valueToNodes.computeIfAbsent(reversedMatrix[i][j], k -> new ArrayList<>()).add(2 * i + 1);
}
for (List<Integer> nodes : valueToNodes.values()) {
if (nodes.size() > 1) {
int k = nodes.size();
int[] s = new int[k - 1];
for (int i = 0; i < k - 1; i++) s[i] = nextVarIndex++;
maxNode = Math.max(maxNode, 2 * s[k-2] + 1);
// (!p1 V s1)
edgeList.add(new int[]{neg(nodes.get(0)), 2 * s[0]});
// (!pk V !s_{k-1})
edgeList.add(new int[]{neg(nodes.get(k - 1)), neg(2 * (s[k - 2]))});
for (int i = 1; i < k - 1; i++) {
edgeList.add(new int[]{neg(nodes.get(i)), 2 * s[i]});
edgeList.add(new int[]{neg(2 * s[i - 1]), 2 * s[i]});
edgeList.add(new int[]{neg(nodes.get(i)), neg(2 * s[i - 1])});
}
}
}
}
int numNodes = maxNode + 1;
adj = new ArrayList[numNodes];
for (int i = 0; i < numNodes; i++) adj[i] = new ArrayList<>();
for (int[] edge : edgeList) {
adj[neg(edge[0])].add(edge[1]);
adj[neg(edge[1])].add(edge[0]);
}
dfn = new int[numNodes];
low = new int[numNodes];
sccId = new int[numNodes];
tarjanStack = new Stack<>();
inStack = new boolean[numNodes];
for (int i = 0; i < numNodes; i++) {
if (dfn[i] == 0) tarjanIterative(i, numNodes);
}
for (int i = 0; i < n; i++) {
if (sccId[2 * i] == sccId[2 * i + 1] && sccId[2 * i] != 0) {
pw.println("No");
pw.flush();
return;
}
}
pw.println("Yes");
List<Integer> flippedRows = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (sccId[2 * i] < sccId[2 * i + 1]) {
flippedRows.add(i + 1);
}
}
pw.println(flippedRows.size());
if (!flippedRows.isEmpty()) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < flippedRows.size(); i++) {
sb.append(flippedRows.get(i));
if (i < flippedRows.size() - 1) sb.append(" ");
}
pw.println(sb.toString());
} else {
pw.println();
}
pw.flush();
}
}
总结：
这个题，超级超级难难难难难难难难难难难难难难难难难难难难难难难难，这里分享大佬的思路和代码，干不下去了，下课下课
https://blog.nowcoder.net/n/1b0a28b05dc6468685c5846b12f2e561
写不下去了，太难辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣辣
这是线
投递小天才等公司10个岗位