Day8

第一题

第五届2014年蓝桥杯省赛

神奇算式

JavaA组第3题

填空题

利用Set集合去重，并判断set的大小是否为4。

import java.util.Arrays;import java.util.HashSet;import java.util.Set;public class Main {    public static void main(String[] args) { int cnt = 0; for (int i = 1; i <= 987; i++) {     for (int j = i; j <= 987; j++) {  int res = i * j;  if (res >= 10000) continue;  String s1 = i + "" + j;  String s2 = res + "";  char[] c1 = s1.toCharArray();  char[] c2 = s2.toCharArray();  if (check(c1, c2)) cnt++;     } } System.out.println(cnt);    }    private static boolean check(char[] c1, char[] c2) { Arrays.sort(c1); Arrays.sort(c2); String s1 = String.valueOf(c1); String s2 = String.valueOf(c2); if (s1.equals(s2) && check_reduplicate(s2)) {     return true; } return false;    } // 判重    private static boolean check_reduplicate(String s) { Set<String> set = new HashSet<>(); for (int i = 0; i < s.length(); i++) { set.add(s.charAt(i) + ""); } if (set.size() == 4) {     return true; } return false;    }}

第二题

第九届2018年蓝桥杯省赛

缩位求和

JavaC组第6题

简单的字符串处理问题。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String a = sc.next();while (a.length() > 1) {int sum = 0;for (int i = 0; i < a.length(); i++) {sum += a.charAt(i) - '0'; // 转为int类型}String b = sum + ""; // 转为String类型a = b; // 重新赋值 再次拆分}System.out.println(a); // 此时a只剩一位}}

第三题

NOIP2013提高组

积木大赛

贪心+差分

给定一个区间$[L,R]$，每次操作可以使这个区间所有积木数+1，现在就是给我们一个大厦的宽度n以及每1个宽度需要的积木数，让我们求最少操作多少次可以建成大厦，不难看出是一道贪心题目，使我们的区间尽量大。

我们可以把过程逆过来，因为我们已经知道了每堆积木的高度，所以我们可以将某一段区间所有高度-1，求我们操作多少次可以把所有高度变为0。

看第一个样例：

操作所有数，全部-1

再操作前3个数：

再操作第2、3个数：

然后再分别操作第3个数和第5个数，总操作数为5。

我们试着用差分来解决这道题，将原数组 h i h_i hi​ 变为差分数组 b i b_i bi​ = > b i = h i − hi−1 => b_i = h_i - h_{i - 1} =>bi​=hi​−hi−1​

原数组： h 1 , h 2 . . . h 3 h_1, h_2 ... h_3 h1​,h2​...h3​

差分数组：

b 1 = h 1 b_1 = h_1 b1​=h1​

b 2 = h 2 − h 1 b_2 = h_2 - h_1 b2​=h2​−h1​

​ $...$

b n = h n − hn−1 b_n = h_n - h_{n-1} bn​=hn​−hn−1​

bn+1 = − h n b_{n+1} = -h_n bn+1​=−hn​

当我们想让区间$[L,R]$的所有数 h L , hL+1 . . . h R h_L,h_{L+1}...h_R hL​,hL+1​...hR​ 全部-1，我们只需要改差分数组的两个值就可以， b L = h L − hL−1 b_L = h_L-h_{L-1} bL​=hL​−hL−1​， hL−1 h_{L-1} hL−1​不变， h L h_{L} hL​ 减了1，所以 b L b_{L} bL​ 减了1； bL+1 = hL+1 − h L b_{L+1} = h_{L+1}-h_{L} bL+1​=hL+1​−hL​， hL+1 h_{L+1} hL+1​ 和 h L h_{L} hL​ 都减了1，差值不变，所以 bL+1 b_{L+1} bL+1​ 不变，以此类推剩下的都不变，但当 bR+1 = hR+1 − h R b_{R + 1} = h_{R + 1} - h_R bR+1​=hR+1​−hR​ 时， hR+1 h_{R + 1} hR+1​ 不变， h R h_R hR​ 减了1，所以是让 bR+1 b_{R + 1} bR+1​ 加了1。

综上，如果对原数组的区间$[L.R]$所有值全部减1，那么对应到差分数组我们只改变了两个值：一个是 b L b_L bL​ 减1，另一个是 bR+1 b_{R + 1} bR+1​ 加1。

原数组任意的区间操作都可以对应到差分数组两个数的操作，而且是一一对应的。

我们要使原数组所有数变成0，那么差分数组也全部变成0，相当于我们每次要从差分数组 b 1 , b 2 . . . bn+1 b_1, b_2 ... b_{n + 1} b1​,b2​...bn+1​ 挑两个数，前一个减1，后一个加1，求最少操作多少次可以将所有数变成0。

我们每一次从前往后看，找到第一个大于0的 b i b_i bi​，我们从后面任意找一个负数 b j b_j bj​ 和 b i b_i bi​ 配对，然后让 b i b_i bi​ 减1， b j b_j bj​ 加1即可。

我们如何确定我们一定能在 b i b_i bi​ 后面找到一个负数呢？

把所有 b i b_i bi​ 拆分成原数组，所有项全部都消掉了，只剩下了 − hi−1 -h_{i - 1} −hi−1​ 。

我们发现：因为所有 h i ⩾ 0 h_i \geqslant 0 hi​⩾0，所以 b i + . . . + bn+1 b_i+ ...+b_{n + 1} bi​+...+bn+1​ 一定是小于等于0的，所以当 b i > 0 b_i > 0 bi​>0 时， bi+1 + . . . + bn+1 b_{i+1}+ ...+b_{n + 1} bi+1​+...+bn+1​ 一定是严格小于0的，所以 b i b_i bi​ 后面必然存在一个负数。

综上，证明完毕。

求出差分数组并扫描一遍即可。

时间复杂度 $O(N)$

import java.util.Scanner;public class Main { static final int N = 100010;    static int[] h = new int[N]; // 原数组    static int[] b = new int[N]; // 差分数组    public static void main(String[] args) {Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 1; i <= n; i++) h[i] = sc.nextInt();  for (int i = 1; i <= n + 1; i++) b[i] = h[i] - h[i - 1]; // 差分数组 i要取到n + 1  int res = 0; for (int i = 1; i <= n + 1; i++) {     if (b[i] > 0) res += b[i]; // 只要b[i] > 0 我们就至少需要操作一次 } System.out.println(res);}}

简化版代码：如果当前数大于前一个数，则 res += 当前数 - 前一个数

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int res = 0, last = 0; // 记录上一次的积木数 while (n-- > 0) {     int h = sc.nextInt();     if (h > last) res += h - last; // 如果h较大，则证明h搭积木的时候可以带着前一个last一起搭     last = h; } System.out.println(res);}}