F、天干地支
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分
问题描述
古代中国使用天干地支来记录当前的年份。
天干一共有十个，分别为：甲（jiǎ）、乙（yǐ）、丙（bǐng）、丁（dīng）、戊（wù）、己（jǐ）、庚（gēng）、辛（xīn）、壬（rén）、癸（guǐ）。
地支一共有十二个，分别为：子（zǐ）、丑（chǒu）、寅（yín）、卯（mǎo）、辰（chén）、巳（sì）、午（wǔ）、未（wèi）、申（shēn）、酉（yǒu）、戌（xū）、亥（hài）。
将天干和地支连起来，就组成了一个天干地支的年份，例如：甲子。
2020 年是庚子年。
每过一年，天干和地支都会移动到下一个。例如 2021 年是辛丑年。
每过 60 年，天干会循环 6 轮，地支会循环 5 轮，所以天干地支纪年每 60 年轮回一次。例如 1900 年，1960 年，2020 年都是庚子年。
给定一个公元纪年的年份，请输出这一年的天干地支年份。
输入格式
输入一行包含一个正整数，表示公元年份。
输出格式
输出一个拼音，表示天干地支的年份，天干和地支都用小写拼音表示（不表示声调），之间不要加入任何多余的字符。
测试样例1
Input：
2020
Output：
gengzi
评测用例规模与约定
对于所有评测用例,输入的公元年份为不超过 9999 的正整数。
package action; public class demo { public static void main(String[] args) { int x = 1960; String s1[] = { "jia", "yi", "bing", "ding", "wu", "ji", "geng", "xin", "ren", "gui" }; String s2[] = { "zi", "chou", "yin", "mao", "chen", "si", "wu", "wei", "shen", "you", "xu", "hai" }; int x1 = x % 10 + 6; int x2 = x % 12 - 4; System.out.println(s1[x1] + s2[x2]); } }
G、皮亚诺曲线距离
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
问题描述
皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3×3 的方格中的每一个格子，最终到达右上角的一条曲线。
（图8-1）
下图给出了皮亚诺曲线的 2 阶情形，它是经过一个 3^2 × 3^2 （3的2次方乘以3的2次方）的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。
（图8-2）
下图给出了皮亚诺曲线的 3 33 阶情形，它是经过一个3^3 × 3^3 （3的3次方乘以3的3次方）的方格中的每一个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。
（图8-3）
皮亚诺曲线总是从左下角开始出发，最终到达右上角。
我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是(0,0)，右上角坐标是 (3^k−1, 3^k−1)，右下角坐标是 (3^k−1,0)，左上角坐标是(0, 3^k−1)。
给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮亚诺曲线走，距离是到少？
输入格式
输入的第一行包含一个正整数 k ，皮亚诺曲线的阶数。
第二行包含两个整数x1,y1，表示第一个点的坐标。
第三行包含两个整数x2,y2，表示第二个点的坐标。
输出格式
输出一个整数，表示给定的两个点之间的距离。
测试样例1
Input：
1
0 0
2 2
Output：
8
测试样例2
Input：
2
0 2
0 3
Output：
13
评测用例规模与约定
对于 30 3030% 的评测用例，0≤k≤10。
对于 50 5050% 的评测用例，0≤k≤20。
对于所有评测用例，0 ≤ k ≤ 100 , 0 ≤ x1 , y1 , x2 , y2 < 3^k , x1 , y1 , x2 , y2 ≤ 1 0^18 。
数据保证答案不超过 10^18。
package action; import java.util.Scanner; public class demo { public static void main(String[] args) { run(); } static long N = 450283905890997363L, ans = 0; static int[][] idx = { { 0, 1, 2 }, { 5, 4, 3 }, { 6, 7, 8 } }; public static void run() { Scanner sc = new Scanner(System.in); sc.next(); long x1 = sc.nextLong(); long y1 = sc.nextLong(); long x2 = sc.nextLong(); long y2 = sc.nextLong(); sc.close(); boolean sign1 = true, sign2 = true, turn1, turn2; int offset1, offset2; for (int i = 38; i > 0; i--) { offset1 = idx[(int) (x1 / N)][(int) (y1 / N)]; offset2 = idx[(int) (x2 / N)][(int) (y2 / N)]; turn1 = (offset1 & 1) == 1; turn2 = (offset2 & 1) == 1; if (x1 / N == 1) { offset1++; if (sign1) ans--; else ans++; } if (x2 / N == 1) { offset2++; if (sign2) ans++; else ans--; } ans += ((sign1 ? offset1 : -offset1) - (sign2 ? offset2 : -offset2)) * N * N; if (x1 / N == 1) sign1 = !sign1; if (x2 / N == 1) sign2 = !sign2; if (turn1) x1 = N - x1 % N - 1; else x1 %= N; if (turn2) x2 = N - x2 % N - 1; else x2 %= N; y1 %= N; y2 %= N; N /= 3; } System.out.println(ans > 0 ? ans : -ans); } }
H、蓝肽子序列
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分
问题描述
L 星球上的生物由蛋蓝质组成，每一种蛋蓝质由一类称为蓝肽的物资首尾连接成一条长链后折叠而成。
生物学家小乔正在研究 L 星球上的蛋蓝质。她拿到两个蛋蓝质的蓝肽序列，想通过这两条蓝肽序列的共同特点来分析两种蛋蓝质的相似性。
具体的，一个蓝肽可以使用 1 至 5 个英文字母表示，其中第一个字母大写，后面的字母小写。一个蛋蓝质的蓝肽序列可以用蓝肽的表示顺序拼接而成。
在一条蓝肽序列中，如果选取其中的一些位置，把这些位置的蓝肽取出，并按照它们在原序列中的位置摆放，则称为这条蓝肽的一个子序列。蓝肽的子序列不一定在原序列中是连续的，中间可能间隔着一些未被取出的蓝肽。
如果第一条蓝肽序列可以取出一个子序列与第二条蓝肽序列中取出的某个子序列相等，则称为一个公共蓝肽子序列。
给定两条蓝肽序列，找出他们最长的那个公共蓝肽子序列的长度。
输入格式
输入两行，每行包含一个字符串，表示一个蓝肽序列。字符串中间没有空格等分隔字符。
输出格式
输出一个整数，表示最长的那个公共蓝肽子序列的长度。
测试样例1
Input：
LanQiaoBei
LanTaiXiaoQiao
Output：
2
Explanation：
最长的公共蓝肽子序列为 LanQiao，共两个蓝肽。
评测用例规模与约定
对于 20% 的评测用例，两个字符串的长度均不超过 20。
对于 50% 的评测用例，两个字符串的长度均不超过 100。
对于所有评测用例，两个字符串的长度均不超过 1000。
package action; import java.util.HashSet; import java.util.Scanner; public class demo { public static void main(String[] args) { HashSet<String> set = new HashSet<>(); Scanner sc = new Scanner(System.in); String s1 = sc.next(); String s2 = sc.next(); sc.close(); int l1 = len(s1); int l2 = len(s2); sz(s1, l1, set); sz(s2, l2, set); System.out.println(l1 + l2 - set.size()); } private static void sz(String s1, int l1, HashSet set) { String s = ""; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) < 90 && i != 0 || i == s1.length() - 1) { if (i == s1.length() - 1) { s = s + s1.charAt(i); } set.add(s); s = "" + s1.charAt(i); } else { s = s + s1.charAt(i); } } } private static int len(String s) { int x = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) < 90) { x++; } } return x; } }
I、画廊
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
小蓝办了一个画展，在一个画廊左右两边陈列了他自己的作品。为了使画展更有意思，小蓝没有等距陈列自己的作品，而是按照更有艺术感的方式陈列。
在画廊的左边陈列了 L 幅作品，在画廊的右边陈列了 R 幅作品，左边的作品距离画廊的起点依次为 u1, u2, · · · , uL，右边的作品距离画廊起点依次为 v1, v2, · · · , vR。
每周，小蓝要整理一遍自己的每一幅作品。整理一幅作品的时间是固定的，但是要带着沉重的工具。从一幅作品到另一幅作品之间的距离为直线段的长度。
小蓝从画廊的起点的正中央（左右两边的中点）出发，整理好每一幅画，最终到达画廊的终点的正中央。已知画廊的宽为 w。
请问小蓝最少带着工具走多长的距离？
输入格式
输入的第一行包含四个整数 L , R , d , w，表示画廊左边和右边的作品数量，以及画廊的长度和宽度。
第二行包含 L 个正整数 u1, u2, · · · , uL，表示画廊左边的作品的位置。
第三行包含 R 个正整数 v1, v2, · · · , vR，表示画廊右边的作品的位置。
输出格式
输出一个实数，四舍五入保留两位小数，表示小蓝最少带着工具走的距离。
测试样例1
Input：
3 3 10 2
1 3 8
2 4 6
Output：
14.71
Explanation：
小蓝从起点开始，首先到达左边第一幅作品（走动距离 √2），然后到达左
边第二幅作品（走动距离 2），然后到达右边第一幅作品（走动距离 √5），然后
到达右边第二幅和第三幅作品（走动距离 2 和 2），然后到达左边第三幅作品（走动距离 2√2），最后到达画廊终点（走动距离 √5）。
总共距离为 √2 + 2 + √5 + 2 + 2 + 2 √2 + √5 ≈ 14.71。
评测用例规模与约定
对于 40% 的评测用例，1≤L,R≤10,1≤d≤100,1≤w≤100。
对于 70% 的评测用例，1≤L,R≤100,1≤d≤1000,1≤w≤1000。
对于所有评测用例，1≤L,R≤500,1≤d≤100000,1≤w≤100000,0≤ u1 < u2 < ⋅ ⋅ ⋅ < uL ≤ d , 0 ≤ v1 <v2 <··· <vR ≤ d。
package action; import java.util.Scanner; public class demo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int L = sc.nextInt(); int R = sc.nextInt(); double d = sc.nextDouble(); double w = sc.nextDouble(); double l[] = new double[L]; double r[] = new double[R]; for (int i = 0; i < l.length; i++) { l[i] = sc.nextDouble(); } for (int i = 0; i < r.length; i++) { r[i] = sc.nextDouble(); } double dp[][][] = new double[L + 1][R + 1][2]; for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[0].length; j++) { dp[i][j][0] = dp[i][j][1] = Integer.MAX_VALUE; } } dp[1][0][0] = Math.sqrt((w / 2 * w / 2) + (l[0] * l[0])); for (int i = 2; i <= L; i++) { dp[i][0][0] = dp[i - 1][0][0] + l[i - 1] - l[i - 2]; } for (int i = 2; i <= R; i++) { dp[0][i][1] = dp[0][i - 1][1] + r[i - 1] - r[i - 2]; } dp[0][1][1] = Math.sqrt((w / 2 * w / 2) + (r[0] * r[0])); for (int i = 1; i <= L; i++) { for (int j = 1; j <= R; j++) { double t = Math.sqrt(w * w + Math.abs(l[i - 1] - r[j - 1]) * Math.abs(l[i - 1] - r[j - 1])); if (i - 2 < 0) { dp[i][j][0] = dp[i - 1][j][1] + t; } else { dp[i][j][0] = Math.min(dp[i - 1][j][0] + l[i - 1] - l[i - 2], dp[i - 1][j][1] + t); } if (j - 2 < 0) { dp[i][j][1] = dp[i][j - 1][0] + t; } else { dp[i][j][1] = Math.min(dp[i][j - 1][1] + r[j - 1] - r[j - 2], dp[i][j - 1][0] + t); } } } System.out.printf("%.2f", Math.min(dp[L][R][0] + Math.sqrt(w / 2 * w / 2 + (d - l[l.length - 1]) * (d - l[l.length - 1])), dp[L][R][1] + Math.sqrt(w / 2 * w / 2 + (d - r[r.length - 1]) * (d - r[r.length - 1])))); } }
E、答疑
时间限制: 3.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。
一位同学答疑的过程如下：
1. 首先进入办公室，编号为 i 的同学需要 si 毫秒的时间。
2. 然后同学问问题老师解答，编号为 i 的同学需要 ai 毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。
4. 最后同学收拾东西离开办公室，需要 ei 毫秒的时间。一般需要 10 秒、20 秒或 30 秒，即 ei 取值为 10000，20000 或 30000。
一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。
答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群里面发消息的时刻之和最小。
输入格式
输入第一行包含一个整数 n ，表示同学的数量。
接下来 n 行，描述每位同学的时间。其中第 i ii 行包含三个整数si,ai,ei，意义如上所述。
输出格式
输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。
测试样例1
Input：
3
10000 10000 10000
20000 50000 20000
30000 20000 30000
Output：
280000
Explanation：
按照 1, 3, 2 的顺序答疑，发消息的时间分别是 20000, 80000, 180000。
评测用例规模与约定
对于 30 3030% 的评测用例，1 ≤ n ≤ 20。
对于 60 6060% 的评测用例，1 ≤ n ≤ 200。
对于所有评测用例，1 ≤ n ≤ 1000 ，1 ≤ s i ≤ 60000 ，1 ≤ a i ≤ 1000000 ，e i ∈ { 10000 , 20000 , 30000 } ，即 e i 一定是 10000 、 20000 、 30000 之一。
package action; import java.util.Arrays; import java.util.Scanner; public class demo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long num[][] = new long[n][3]; for (int i = 0; i < n; i++) { num[i][0] = sc.nextLong(); num[i][1] = sc.nextLong(); num[i][2] = sc.nextLong(); } long num3[] = new long[n]; long num2[] = new long[n]; for (int i = 0; i < n; i++) { num3[i] = num[i][0] + num[i][1] + num[i][2]; num2[i] = num[i][0] + num[i][1]; } Arrays.sort(num2); Arrays.sort(num3); long count = 0; for (int i = 0; i < n; i++) { count += num2[i]; } for (int i = 0, j = n - 1; i < n; i++, j--) { count += num3[i] * j; } System.out.println(count); } }
