廊坊网站推广外包,网站搜索优化,多语言建站系统,公共服务平台登录目录 A - Binary ImbalanceB - Getting PointsC - Insert and Equalize A - Binary Imbalance
原题链接 题目描述 给你一个只包含字符 0或 1的字符串 s s s。在每次操作中#xff0c;你可以从任意两个字符间插入一个字符#xff1a;如果两个相邻的字符相等#xff0c;那么… 目录 A - Binary ImbalanceB - Getting PointsC - Insert and Equalize A - Binary Imbalance
原题链接 题目描述 给你一个只包含字符 0或 1的字符串 s s s。在每次操作中你可以从任意两个字符间插入一个字符如果两个相邻的字符相等那么你只可以插入1否则你只可以插入0。是否有可能使用任意数量的运算使 s s s中0的个数严格大于1的个数 思路观察 只要存在两个相邻的字符不相等那么可以在中间无限插入0使得其数量大于1的数量。 public static void solve() throws IOException {int n readInt();String s readString();int z 0, o 0;if (!s.contains(0)) {printWriter.println(NO);} else {printWriter.println(YES);}
}B - Getting Points
原题链接 题目描述 一个学期有N天为了不被开除你需要在这N天内至少拿到P学分。你每完成一项实践任务就能获得t分每上一堂课他就能获得l分其中实践任务每周一会解锁一个而课程每天都有。每天你都可以选择是学习还是休息一整天。当你决定学习时你可以上一堂课并完成不超过2个已解锁但未完成的实践任务。如果你选择休息一整天那么你将什么也不做。现在你希望休息的天数最大化问最多可以休息多少天。 思路二分分类讨论 最大化休息的天数那么可以理解为最小化学习的天数。二分枚举学习的天数分类讨论是否可以学完所有实践任务。可以根据week的大小进行分类讨论如果 m i d ≥ w e e k mid \geq week mid≥week那么可以学完所有实践任务,无论是一天完成一节还是两节实践任务否则最多只可以学习mid * 2个学习任务。 def solve():n, s, b, a map(int, input().split())week n // 7 (0 if n % 7 0 else 1) # n天内总共有多少周l 0r int(1e9) 10while l 1 r:mid (l r) 1tot mid * bif mid week // 2 week % 2: # 可以分批次学完所有实践任务tot week * aelse:tot mid * 2 * a # mid天内每天学习 2个实践任务if tot s:r midelse:l midprint(n - r)C - Insert and Equalize
原题链接 题目描述 给定一个长度为n且不含重复元素的数组arr你需要往数组中插入一个数组中不包含的元素然后再选择一个数x在每次操作中你可以为数组中的一个数加上x求使得数组中所有元素相等的最小操作数。 思路排序gcd 要使得操作数最小那么x的最优解为排序好的数组的所有相邻元素的差的最大公约数。insert的值为小于arr[n]的最大的且不在数组中且与arr[n]的差为gcd的倍数的值通过枚举数组可以得到。 public static void solve() throws IOException {int n readInt();long[] arr utils.nextLongArray(n);Arrays.sort(arr, 1, n 1);if (n 1) {// 数组只有一个元素printWriter.println(1);return;}ListLong list new ArrayList();for (int i 2; i n; i) {list.add(arr[i] - arr[i - 1]);// 存下相邻数的差}long gcd getGcd(0, list);// 获取所有数的 gcdlong insert Long.MAX_VALUE;// 要插入的元素for (int i n; i 2; i--) {if (arr[i] - arr[i - 1] ! gcd) {insert arr[i] - gcd;break;}}if (insert Long.MAX_VALUE) {// 无法插入那么插入一个最小的数 arr[1] - gcdinsert arr[1] - gcd;}long sum 0;for (int i 1; i n; i) {sum (arr[n] - arr[i]) / gcd;}sum (arr[n] - insert) / gcd;printWriter.println(sum);
}public static long getGcd(int u, ListLong list) {if (u list.size() - 1) {return list.get(u);}long v getGcd(u 1, list);return gcd(list.get(u), v);
}public static long gcd(long a, long b) {return b 0 ? a : gcd(b, a % b);
}
