目录
- Day1 T1
- Day1 T4
Day1 T1
简单的模拟： 题目内容大概是给一个字符串a，a的子串拼成字符串b。
例如abcd -> abbccd 给你b字符串，要求给出a字符串。
思路：b字符串中除了第一个字符和最后一个字符串外，其他的都是重复字符，隔一个选一个就好。
点击查看代码
import java.util.*;public class Main {/*** 根据解码规则，从字符串 b 反推出原始字符串 a* @param b 编码后的字符串* @return 解码后的原始字符串 a*/public static String decode(String b) {// a的长度至少为2，所以b的长度也至少为2，不需要特殊处理空字符串或长度为1的字符串if (b == null || b.length() < 2) {// 根据题意，这种情况不会发生，但作为代码健壮性可以保留return ""; }StringBuilder aBuilder = new StringBuilder();// 1. a的第一个字符就是b的第一个字符aBuilder.append(b.charAt(0));// 2. a的后续字符是b中所有奇数索引上的字符for (int i = 1; i < b.length(); i++) {if (i % 2 != 0) { // 判断索引是否为奇数aBuilder.append(b.charAt(i));}}return aBuilder.toString();}/*** 程序主入口，负责处理标准输入和输出*/public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取一行输入，即编码后的字符串 bString b = scanner.nextLine();// 调用解码函数String a = decode(b);// 打印最终结果到标准输出System.out.println(a);}
}Day1 T4
题目内容： 给一个数组，q次查询，每次给一个x，y。你可以随意重新排序数组（其实暗示了不用关心数组顺序），以x倍数为下标是数组元素集合记为xSet，集合数值总和记为xSum，以y为下标的数组元素集合记为ySet,它们的总和为ySum，输出重排后xSum-ySum的最大值。
思路：其实x和y是有公倍数的，数组中下标为x和y公倍数的元素在xSet和ySet中都会存在(记为x^ySet 为 xSet 和ySet的公共部分 )，所以对xSum-ySum无影响。那么需要关注的就是不重合的部分元素，即只需关注 集合xSet-x^ySet 和集合ySet-x^ySet。
这两部分不重合，所以只需要把元素值大的元素放在xSet中，把元素小的放在ySet中即可。
因此，对于每个x，y， xSum-ySum的最大值是 最大的n/x-n/(x * y)个元素的和 减去最小的n/y-n/(x * y)个元素的和。
对数组元素排序，维护一个前缀和和后缀和 每次查询作差即可（当天拉肚子没写完去厕所了。。。）
点击查看代码
package cn.CL;import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();//数组长度int q = in.nextInt();//q次查询int[] a = new int[n];//数组值for (int i = 0; i <n; i++) {a[i] = in.nextInt();}//对数组先进行排序Arrays.sort(a);while (q-- > 0) {long ans =0;int x = in.nextInt();int y = in.nextInt();//下标为x的倍数的数int nx = n / x;//下标为y的倍数的数int ny = n / y;//下标为xy的倍数的数int nxy = n / (x * y);nx = nx-nxy;ny = ny-nxy;//然后最大的一些的值减去最小的一些数的值for(int i=n-1;i>=n-nx;i--){ans += a[i];}for(int i=0;i < ny;i++){ans -= a[i];}System.out.println(ans);}}
}