Day15

第一题

第八届2017年蓝桥杯省赛

算式900

C++C组第3题

填空题

跟带分数那道题很类似，只需要更换一下判断公式即可，直接上全排列模板：

public class Main {

    static int[] num = new int[10];
    static boolean[] st = new boolean[10];

    public static void main(String[] args) {
        dfs(0);
    }

    private static void dfs(int u) {
        if (u == 10) {
            if (num[0] != 0 && num[4] != 0 && num[8] != 0) { // 首位不为0
                int a = calc(0, 3);
                int b = calc(4, 7);
                int c = calc(8, 9);
                if ((a - b) * c == 900 && a != 5012) System.out.printf("(%d-%d)*%d=900\n", a, b, c);
            }
        } else {
            for (int i = 0; i < 10; i++) {
                if (!st[i]) {
                    st[i] = true;
                    num[u] = i;
                    dfs(u + 1);
                    st[i] = false;
                }
            }
        }
    }

    // 计算某一段区间的值
    private static int calc(int l, int r) {
        int res = 0;
        for (int i = l; i <= r; i++) res = res * 10 + num[i];
        return res;
    }
}

第二题

2021年模拟赛

谈判

贪心

哈夫曼树

排序做法

对数组排序，优先取两个数值最小的合并，把合并后的值放进去，再取两个最小值合并。

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static final int N = 1010;
    static int[] a = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();

        Arrays.sort(a, 0, n);

        int sum = 0;
        for (int i = 0; i < n - 1; i++) {
            sum += a[i] + a[i + 1];
            a[i + 1] = a[i] + a[i + 1]; // 合并
        }
        System.out.print(sum);
    }
}

优先队列做法，更推荐这种做法，因为本题数据量小，所以用排序也可以过。

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Integer> q = new PriorityQueue<>(); // 优先队列
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            q.add(num);
        }

        int ans = 0;
        if (q.size() == 1) { // 只有一个值时，说明谈判完成
            System.out.println(q.poll());
        } else {
            while (q.size() != 1) {
                // 取出前两个值
                int a = q.poll();
                int b = q.poll();
                q.add(a + b);
                ans += a + b;
            }
            System.out.println(ans);
        }
    }
}

第三题

第四届2013年蓝桥杯省赛

幸运数

JavaB组第8题

模拟

import java.util.Scanner;

public class Main {	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt(), n = sc.nextInt();
		int[] a = new int[n + 1];
		for (int i = 2; i <= n; i++) {
			if (a[i] == 0) {
				int cnt = 0;
				for (int j = 1; j <= n; j++) {
					if (a[j] == 0) {
						cnt++;
						if (cnt % i == 0) a[j] = 1; // 表示被删除
					}
				}
			}
		}
		
		int ans = 0;
		for (int i = m + 1; i < n; i++) {
			if (a[i] == 0) ans++;
		}
		
		System.out.println(ans);
	}
}

第四题

第十二届2021年蓝桥杯国赛

123

C++B组第6题

二分+前缀和

import java.util.Scanner;

public class Main {
    
    static int N = (int) 2e6;
    static long[] a = new long[N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        pre();
        while (t-- > 0) {
            long l = sc.nextLong();
            long r = sc.nextLong();
            System.out.println(ans(r) - ans(l - 1));
        }
    }

    private static long f(long x) {
        long l = 1;
        long r = (long) 3e6;
        while (l < r) {
            long mid = (l + r + 1) >> 1;
            if ((mid + 1) * mid < x * 2) l = mid;
            else r = mid - 1;
        }
        return l;
    }
    
    private static long sum(long x) {
        return x * (x + 1) / 2;
    }
    
    private static long ans(long x) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        long y = f(x);
        return a[(int) y] + sum(x - sum(y));
    }
    
    private static void pre() {
        for (int i = 1; i < N; i++) {
            a[i] = a[i - 1] + sum(i);
        }
    }
}