赛码网,三道编程题。提前二十多分钟交的卷,,第二题通过率36%想了半天想不出来哪出问题了,裂开。
第一题:目录命令
【时间限制】: 3000MS 内存限制: 589824KB 【题目描述】: 你需要编写一个程序来模拟目录的操作,一开始,你在根目录"\",一共有两种命令: ● cd s: s为一个目录名,表示从当前工作目录的路径进入名为s的目录。 特别地,"cd .."(即s=="..")表示返回上一级目录,若当前已为根目录,则无视该次操作。数据保证若s不为"..",则一定为小写字母组成的长度不超过10的字符串。 ● pwd: 表示查看当前工作目录的路径,你需要输出这个路径。 【输入描述】 第一个行是一个整数n,表示一共会有n个操作。 接下来每行是一条命令,命令的种类为问题描述中的二种之一。 注意,测试用例中cd s的操作,中间有空格。 输出描述 对于每个"pwd"命令,你需要单行输出当前的工作路径。 【样例输入】 7 cd a cd b pwd cd .. pwd cd .. pwd 【样例输出】 \a\b \a \ (提示 1<=n<=300)通过率100%:
public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Scanner sc = new Scanner(System.in); List<String> list = new ArrayList<>(); int n = Integer.parseInt(br.readLine()); for (int i = 0; i < n; i++) { String line = sc.nextLine(); String[] strs = line.split(" "); if ("cd".equals(strs[0])) { if ("..".equals(strs[1])) { if (!list.isEmpty()) { list.remove(list.size() - 1); } } else { list.add("\\" + strs[1]); } } else if ("pwd".equals(strs[0])) { if (list.isEmpty()) { System.out.println('\\'); } else { StringBuilder sb = new StringBuilder(); for (String s : list) { sb.append(s); } System.out.println(sb); } } } } }
第二题:分段
时间限制: 3000MS 内存限制: 589824KB 【题目描述】 有一个长度为n的序列A,序列中的第i个数为A[i] (1<=i<=n),现在你可以将序列分成至多连续的k段。 对于每一段,我们定义这一段的不平衡度为段内的最大值减去段内的最小值。显然,对于长度为1的段,其不平衡度为0。 对于一种合法的分段方式(即每一段连续且不超过k段),我们定义这种分段方式的不平衡度为每一段的不平衡度的最大值。 现在你需要找到不平衡度最小的分段方式,输出这种分段方式的不平衡度即可。 【输入描述】 第一行两个空格隔开的整数n,k,分别表示序列的长度和最多可分成的段数。 第二行是n个用空格隔开的整数,第i个数表示A[i]的值。 【输出描述】 一行一个整数,表示最小的不平衡度。 样例输入 5 3 3 5 5 2 5 样例输出 2 提示 数据范围:1<=n<=100000, 1<=A[i]<=100000 输入样例1 5 3 3 5 5 2 5 输出样例1 2 解释 最终分为[3 5 5] [2] [5],该种分段方式的不平衡度为2。这道题我只AC了36%
public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] s = br.readLine().split(" "); int m = Integer.parseInt(s[0]); //m个数 int n = Integer.parseInt(s[1]); //最多分成n段 String[] strs = br.readLine().split(" "); List<Integer> list = new ArrayList<>(); list.add(Integer.parseInt(strs[0])); for (int i = 1; i < m; i++) { if (strs[i].equals(strs[i - 1])) { continue; } list.add(Integer.parseInt(strs[i])); } System.out.println(minValue(list, n)); } public static int minValue(List<Integer> nums, int n) { if (n >= nums.size()) { return 0; } int[] dif = new int[nums.size() - 1]; for (int i = 1; i < nums.size(); i++) { dif[i - 1] = Math.abs(nums.get(i) - nums.get(i - 1)); } Arrays.sort(dif); return dif[dif.length - n]; // 输出第n大的即可 } }
第三题:消除连续的1
时间限制: 3000MS 内存限制: 589824KB 【题目描述】 现在给你一个长度为n的01序列,你可以通过消除连续的1的序列来获取一定的分数。 题目中将给你若干个长度和分数的对应关系,你需要正确求解出对应的答案。 例如:现在给你一个长度为12的01序列111111011111。 现在给你如下可以获取得分的消除方式: 消除三个连续的1,获取得分10 消除四个连续的1,获取得分15 对于前面的六个连续的1,你的消除方案有两种: 消除一次连续的四个1,获得得分15,或者进行两次连续的三个1消除,获取得分20. 对于后面的五个连续的1,你有两种消除方案: 消除一次连续的四个1,获得得分15,或者消除一次连续的三个1,获得得分10 上述方案中可以获得的最大分数是20 + 15 = 35. 你的任务就是设法获得最大的消除分数。 请注意:不一定需要把所有的1的消除完毕,我们的目标是最大化分数而不是最大化消除个数。 【输入描述】 第一行两个空格隔开的正整数n,m,分别表示01串的长度和消除规则的数量。 接下来一行字符串长度为n,每个字符只能是0或者1中的一种。 接下来m行,每行两个空格隔开的正整数k, x,为消除连续的k个1可以获得的分数x 输出描述 输出可以获得的最大分数。 样例输入 11 2 11111101111 3 10 4 15 样例输出 35 提示 n <= 100000, m <= 100 保证对于每个规则,k和x都在[1, 100]之间。这道题是完全背包的变种,通过率100%
public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String ss = br.readLine(); String[] sss = ss.split(" "); int line = Integer.parseInt(sss[1]); char[] nums = br.readLine().toCharArray(); // 01序列 int[][] wvs = new int[line + 1][2]; for (int i = 1; i <= line; i++) { String[] wv = br.readLine().split(" "); wvs[i][0] = Integer.parseInt(wv[0]); wvs[i][1] = Integer.parseInt(wv[1]); } List<Integer> list = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if (nums[i] == '0') { continue; } int W = 0; while (i < nums.length && nums[i] == '1') { W++; i++; } list.add(W); i--; } int res = 0; for (Integer W : list) { res += maxValue(W, wvs); } System.out.println(res); } public static int maxValue(int V, int[][] wv) { int N = wv.length - 1; int[] dp = new int[V + 1]; for (int i = 1; i <= N; i++) { for (int j = 0; j <= V; j++) { if (j >= wv[i][0]) { dp[j] = Math.max(dp[j - wv[i][0]] + wv[i][1], dp[j]); } } } return dp[V]; } }最后祝大家机会多多,offer多多!
喜欢的点个赞,谢谢,手残党码了半天字;
全部评论
(17) 回帖