题解 | #哈尔滨华德学院第十五届程序设计竞赛#
A~I, J不会
A 签到了签到了
真签到题
print("Harbin Huade University")
B 裁决之时
n = int(input())
for i in range(n):
a = int(input())
if a >= 60:
print("AC")
else:
print("WA")
C 总成绩计算
总之就是 小数部分如果不为0 就可以向上取整(+1)
a * 0.4 + b * 0.6 小数只有1位, 所以只需要判断小数点后的第一位是否为0
n = int(input())
for _ in range(n):
a, b = map(int, input().split())
c = a * 0.4 + b * 0.6
s = str(c)
idx = s.index(".")
f = s[idx + 1:]
if f[0] == '0':
print(s[:idx])
else:
print(int(s[:idx]) + 1)
D WYL的善良之平均成绩
贪心
修改成绩优先修改最低的, 所以先排序
然后从低成绩开始依次修改, 当平均分够4.5(四舍五入为5)时break
n = int(input())
sc = list(map(int, input().split()))
s = sum(sc) # 总成绩
sc.sort()
cnt = 0
for i in sc:
if s / n >= 4.5: # 平均成绩足够, break
break
cnt += 1 # 记录操作次数
# 当前成绩改为5
s -= i
s += 5
print(cnt)
E 单表代换密码
模拟
(1) 输入Secretkey
(2) 去除特殊字符 + 转大写 + 去重
(3) 未出现的字母依次拼接在Secretkey后
(4) 现在有 编码映射Secretkey(小写字母 → 大写字母), 再构建映射map(大写字母 → 小写字母)以供解码
(5) 根据操作进行编码/解码
import java.io.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static String S() throws IOException {
return bf.readLine();
}
public static void main(String[] args) throws Exception {
char[] key = S().toCharArray(); // (1)输入
char[] Secretkey = getSecretkey(key);// (2)、(3)去除特殊字符 + 转大写 + 去重
// (4) 现在有 编码映射Secretkey(小写字母 → 大写字母), 再构建映射map(大写字母 → 小写字母)以供解码
char[] mapUpToLow = new char[26];
for (int i = 0; i < 26; i++) {
mapUpToLow[Secretkey[i] - 'A'] = (char) (i + 'a');
}
// (5) 根据操作进行编码/解码
while (true) {
String op = S();
if (op.equals("END")) {
pw.println("Thanks for using goodbye!");
break;
}
char[] text = S().toCharArray();
if (op.equals("encryption")) {// 小->大
print(text, Secretkey, 'a', 'z');
} else {// 大->小
print(text, mapUpToLow, 'A', 'Z');
}
pw.println();
}
pw.flush();
}
static void print(char[] text, char[] map, char a, char z) {
for (char ch : text) {
if (a <= ch && ch <= z) {
pw.print(map[ch - a]);
} else {
pw.print(ch);
}
}
}
private static char[] getSecretkey(char[] key) {
boolean[] have = new boolean[26];
StringBuilder res = new StringBuilder();
for (char ch : key) {
if ('a' <= ch && ch <= 'z') {
ch = (char) (ch - 'a' + 'A');
}
if ('A' <= ch && ch <= 'Z' && !have[ch - 'A']) {
res.append(ch);
have[ch - 'A'] = true;
}
}
for (int i = 0; i < 26; i++) {
if (!have[i]) {
res.append((char) (i + 'A'));
}
}
return res.toString().toCharArray();
}
}
F 考试排名
哈希映射设计
先看操作:
(1) 学号+课程编号 → 成绩
(2) 学号+课程编号 → 排名
(3) 课程编号 → 学号+排名(按排名输出)
(4) 学号 → 课程编号+排名(按课程编号输出)
其中最难搞的就是排名, 排名是与课程挂钩的, 所以它必然从 课程→成绩表中生成, 所以先看(3)
- 对于(3):
排名需要由成绩生成, 所以课程编号需要存储成绩, 排序后,自然得到排名
f(课程编号) = [学号,成绩,排名]
- 对于(1)(2):
学号与课程编号组成一个元组作为键, 映射到成绩与排名
f(学号+课程编号) = (成绩,排名)
对于排名, 在 f(课程编号) = [学号,成绩,排名]生成排名时,有学号和课程号信息, 可以对其做排名信息同步
- 对于(4):
需要 f(学号)=[课程编号] 和 f(学号+课程编号)=(排名)
前一个在读入时直接存即可, 后一个在生成排名时同步了信息
至此, 需要:
(1) f(学号)=[课程编号]
(2) f(课程编号) = [学号,成绩,排名]
(3) f(学号+课程编号)=(成绩,排名)
其中[学号,成绩,排名]可以抽成一个结构体
也就是:
HashMap<Long, List<Long>> sno_cno = new HashMap<>();//学生号 -> 选修的课程集合
HashMap<Long, List<Data>> cno_score = new HashMap<>();//课程号 -> 学号+成绩
HashMap<String, Data> scno_score = new HashMap<>();//学生号+课程号 -> 成绩+排名
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static Scanner sc = new Scanner(System.in);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static int I() throws IOException {
return sc.nextInt();
}
static long L() {
return sc.nextLong();
}
static String S() throws IOException {
return sc.nextLine();
}
static String split = "+";
static class Data {
Long sno;//学号
int score;//成绩
int rank;//排名
public Data(Long sno, int score) {
this.sno = sno;
this.score = score;
}
@Override
public String toString() {
return "Data{" +
"sno=" + sno +
", score=" + score +
", rank=" + rank +
'}';
}
}
static HashMap<Long, List<Long>> sno_cno = new HashMap<>();//学生号 -> 选修的课程集合
static HashMap<String, Data> scno_score = new HashMap<>();//学生号+课程号 -> 成绩+排名
static HashMap<Long, List<Data>> cno_score = new HashMap<>();//课程号 -> 学号+成绩
public static void main(String[] args) throws Exception {
in();//输入
deal();//处理排名等
while (select()) ;//处理查询请求
pw.flush();
}
private static void in() throws IOException {
int n = I();
for (int i = 0; i < n; i++) {
long sno = L(), cno = L();
int score = I();
scno_score.put(sno + split + cno, new Data(sno, score));
sno_cno.computeIfAbsent(sno, k -> new ArrayList<>()).add(cno);
cno_score.computeIfAbsent(cno, k -> new ArrayList<>()).add(new Data(sno, score));
}
S();//过滤换行符
}
private static void deal() {
for (List<Long> list : sno_cno.values()) {//按课程号升序
list.sort((a, b) -> a < b ? -1 : 1);
}
for (List<Data> list : cno_score.values()) {// 按成绩大到小排序
list.sort((a, b) -> {
if (a.score != b.score) return b.score - a.score;
return a.sno < b.sno ? -1 : 1;
});
}
for (Map.Entry<Long, List<Data>> e : cno_score.entrySet()) {// 记录排名
Long cno = e.getKey();
List<Data> list = e.getValue();
Data pre = list.get(0);
pre.rank = 1;
scno_score.get(pre.sno + split + cno).rank = 1;
for (int i = 1; i < list.size(); i++) {
Data data = list.get(i);
if (data.score == pre.score) {
data.rank = pre.rank;
} else {
data.rank = pre.rank + 1;
}
scno_score.get(data.sno + split + cno).rank = data.rank; //在scno_score中同步
pre = data;
}
}
}
private static boolean select() throws IOException {
String op = S();
if (op.equals("END")) {
pw.println("OK");
return false;
}
String[] sp = op.split(" ");
String type = sp[0];
if (type.equals("query1")) {// 学号+课程编号 → 成绩
long sno = Long.parseLong(sp[1]);
long cno = Long.parseLong(sp[2]);
pw.println(scno_score.get(sno + split + cno).score);
} else if (type.equals("query2")) {// 学号+课程编号 → 排名
long sno = Long.parseLong(sp[1]);
long cno = Long.parseLong(sp[2]);
pw.println(scno_score.get(sno + split + cno).rank);
} else if (type.equals("query3")) {// 课程编号 → 学号+排名(按排名输出)
long cno = Long.parseLong(sp[1]);
List<Data> list = cno_score.get(cno);
for (int i = 0; i < list.size(); i++) {
Data data = list.get(i);
pw.println(data.sno + " " + data.score + " " + data.rank);
}
} else {// 学号 → 课程编号+排名(按课程编号输出)
long sno = Long.parseLong(sp[1]);
List<Long> cnos = sno_cno.get(sno);
for (Long cno : cnos) {
Data data = scno_score.get(sno + split + cno);
pw.println(cno + " " + data.score + " " + data.rank);
}
}
return true;
}
}
G 质数质数质数，到底有多少个质数？
前缀思想+素数筛+二分
[A,B]的质数个数 = [1,B]的质数个数 - [1,A)的质数个数
如何求[1,n]的素数个数:
素数筛预处理出素数表prime, 那么只要在prime上二分查找n的位置, 即可知道 ≤n的质数有多少个
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static int I() throws IOException {
st.nextToken();
return (int) st.nval;
}
static List<Integer> prime = new ArrayList<>();
static {// 欧拉筛处理素数表
int N = (int) 1e7;
boolean[] isCom = new boolean[N + 1];// 合数
for (int i = 2; i <= N; i++) {
if (!isCom[i]) prime.add(i);// i为质数
for (int j = 0; j < prime.size(); j++) {// 标记i的倍数为合数
int p = prime.get(j);
if (p * i > N) break;
isCom[p * i] = true;
if (i % p == 0) break;
}
}
}
public static void main(String[] args) throws Exception {
int n = I();
for (int i = 0; i < n; i++) {
int a = I(), b = I();
pw.println(get(b) - get(a - 1));//前缀
}
pw.flush();
}
static int get(int n) {
if (n < 2) return 0;// 防止没有,二分l下标错误,不满足prime[l]<=n
//二分查找<=n的质数个数
int l = 0, r = prime.size();//prime[l]<=n, prime[r]>n
while (l + 1 != r) {
int mid = (l + r) >>> 1;
if (prime.get(mid) <= n) {
l = mid;
} else {
r = mid;
}
}
return l + 1;// prime[l]<=n, prime[r]>n, 索引+1==个数
}
}
H 字符串呀，字符串。
(前缀)字典树
把这些字符串存入字典树, 记录end信息(以该字符结尾), 这样路径上的节点值之和即为数量
最后dfs遍历这颗树, 找到最大的路径和即可
import java.io.*;
import java.util.Scanner;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static int I() throws IOException {
st.nextToken();
return (int) st.nval;
}
static String S() throws IOException {
String res = bf.readLine();
while (res.isEmpty()) res = bf.readLine();
return res;
}
public static void main(String[] args) throws Exception {
int n = I();
Tree tree = new Tree();
for (int i = 0; i < n; i++) {
tree.add(S());
}
System.out.println(tree.findMax());
}
static class Tree {
static class Node {// 每个node代表一个字符
int endCnt = 0;//记录end信息(以该字符结尾)
Node[] children = new Node[26];
}
Node root = new Node();// 根节点,空字符
void add(String s) {
Node p = root;
for (char ch : s.toCharArray()) {
int idx = ch - 'a';
if (p.children[idx] == null) p.children[idx] = new Node();
p = p.children[idx];
}
p.endCnt++;
}
int max = 0;
int findMax() {//最大路径和
max = 0;
dfs(root, 0);
return max;
}
private void dfs(Node node, int sum) {
sum += node.endCnt;
boolean isEnd = true;//是否为叶子节点
for (Node child : node.children) {
if (child != null) {
isEnd = false;
dfs(child, sum);
}
}
if (isEnd) max = Math.max(max, sum);//叶子,更新最大数量
}
}
}
I WYL的善良之等差数列
分类讨论
(1) 题目限制, 一个数只能操作一次
(2) 确定一个等差数列只需要两项
由这两点: 枚举前两项的操作情况, 然后检查后面能否操作为等差数列,如果能,最少操作几次
import java.io.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static int I() throws IOException {
st.nextToken();
return (int) st.nval;
}
public static void main(String[] args) throws Exception {
System.out.println(solve());
}
static int n;
static int[] a = new int[n];
private static int solve() throws IOException {
n = I();
a = new int[n];
for (int i = 0; i < n; i++) a[i] = I();
if (n < 3) return 0;
int ans = Integer.MAX_VALUE;
for (int op1 = -1; op1 <= 1; op1++) {
for (int op2 = -1; op2 <= 1; op2++) {
a[0] += op1;
a[1] += op2;
int minChange = check();
minChange += Math.abs(op1) + Math.abs(op2);//前两项的操作次数也要加上
if (minChange >= 0) ans = Math.min(ans, minChange);
// 回退该步操作
a[0] -= op1;
a[1] -= op2;
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private static int check() {
//首项a[0], 均差d
int d = a[1] - a[0];
int change = 0;
for (int i = 1; i < n; i++) {
long cur = a[0] + (long) i * d;
if (Math.abs(cur - a[i]) > 1) return Integer.MIN_VALUE;// 无法操作1次得到
if (cur != a[i]) change++;// 是否要操作
}
return change;
}
}
J 奇妙的购物体验
点至少走一次, 好像是哈密顿回路最短路径长, 然后还要算点奇奇怪怪的东西, 不会
总结
A~I都没什么难度
J题防AK的吧, 把我防住了
