A. 整数范围

思路：

签到题。答案：$255$

B. 纯质数

思路：

先用筛法筛出所有的质数，再根据题意判断，模板参考AcWing 数学知识。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static final int N = 20211000;static int[] p = new int[N];static boolean[] st = new boolean[N];static int cnt;static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer in = new StreamTokenizer(br);public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}public static boolean check(int x) {if (st[x]) return false;while (x != 0) {if (st[x % 10]) return false;x /= 10;}return true;}public static void main(String[] args) {// TODO Auto-generated method stubst[0] = st[1] = true;for (int i = 2; i <= 20210605; i++) {if (!st[i]) p[cnt++] = i;for (int j = 0; p[j] * i <= 20210605; j++) {st[p[j] * i] = true;if (i % p[j] == 0) break;}}int ans = 0;for (int i = 1; i <= 20210605; i++) {if (check(i)) ans++;}out.println(ans);out.flush();}
}

C. 完全日期

思路：

使用Java自带的 LocalDate 类，简化日期计算。

代码：

import java.time.LocalDate;public class Main {static LocalDate start = LocalDate.of(2001, 1, 1);static LocalDate end = LocalDate.of(2021, 12, 31);public static boolean check(LocalDate date) {String dt = date.toString();int res = 0;for (int i = 0; i < dt.length(); i++) {if (Character.isDigit(dt.charAt(i))) {res += dt.charAt(i) - '0';}}int a = (int) Math.sqrt(res);return a * a == res;}public static void main(String[] args) {// TODO Auto-generated method stubint ans = 0;while (start.compareTo(end) <= 0) {if (check(start)) ans++;start = start.plusDays(1);}System.out.println(ans);}}

D. 最小权值

思路：
这个题现在看起来就是一个动态规划的题目，但是当时做的时候没意识到，最后错了。可以用记忆化搜索或者动态规划求。

记忆化搜索：

注意空子树权值为0，所以初始化为0；

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static final int N = 2030;static long[] dp = new long[N];static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer in = new StreamTokenizer(br);public static long dfs(int size) {if (dp[size] != 0 || size == 0) return dp[size];long res = 0x3f3f3f3f3f3f3fl;for (int i = 0; i < size; i++) {int j = size - 1 - i;res = Math.min(res, 1 + 2 * dfs(i) + 3 * dfs(j) + (long)i * i * j);}return dp[size] = res;}public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(dfs(2021));}
}

动态规划：
易知状态转移方程为：
$$dp(i)=\{\begin{array}{ll}0& i=0\\ 1+2\ast dp(l)+3\ast dp(r)+l\ast l\ast r& 1+l+r=i,0\le l,0\le r\end{array}$$

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static final int N = 2030;static long[] dp = new long[N];static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer in = new StreamTokenizer(br);public static void main(String[] args) {// TODO Auto-generated method stubfor (int i = 1; i <= 2021; i++) {dp[i] = 0x3f3f3f3f3f3f3f3fl;for (int j = 0; j < i; j++) {int k = i - 1 - j;dp[i] = Math.min(dp[i], 1 + 2 * dp[j] + 3 * dp[k] + (long) j * j * k);}}System.out.println(dp[2021]);}}

E. 大写

思路：
模拟题，String.toUpperCase()

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException {// TODO Auto-generated method stubString s = br.readLine();out.println(s.toUpperCase());out.flush();}
}

F. 123

思路：

找规律，我们将数段分割为若干段单调递增的序列，第 $i$ 段序列的长度为 $i$，则前 $i$ 段序列的总长为 $i\ast (i+1)/2$，先用二分处理出询问的 $l$ ，$r$ 的前面一段序列（也可能就是当前的序列）。

数据范围为 $10^{12}$，根据前面的分析知二分的区间范围不会超过 $\sqrt{2\times 10^{12}}$，这里取右边界 $r=1500000$，二分求法如下：

int l = 0, r = 1500000;
while (l < r) {int mid = l + r + 1 >> 1;if ((long)mid * (mid + 1) / 2 <= left) l = mid;else r = mid - 1;
}

由于我们二分的是的 $l$ ，$r$ 的前面一段序列（也可能就是当前的序列），如果 $l$ 和 $r$ 在二分的序列之后，就要算下在当前序列的和，姑且称作 $l$ 和 $r$ 的余项和。方法是找到 $l$ ，$r$ 在当前元素的位置：

int lrem = (int) (left - (long)l * (l + 1) / 2);
int rrem = (int) (right - (long)l * (l + 1) / 2);

接着算 $l$ 和 $r$ 的余项和，

long lsum = (long)lrem * (lrem + 1) / 2;
long rsum = (long)rrem * (rrem + 1) / 2;

因为要求 $l$ ，$r$ 之间一段序列的和， $l$ 也包括在其中，所以要算出当前值，如果当前元素在第0号位置，也就相当于他在这一段序列的末尾，值为序列的长度

long lval = lrem == 0 ? l : lrem;

接着我们用二分好的答案算出两端序列之间的和，可以先预处理前缀和：

for (int i = 1; i < N; i++) {sum[i] = (long)i * (i + 1) / 2+ sum[i - 1];
}

两端序列之间的和加上 $r$ 的余项和，减去 $l$ 的余项和，再减去位置为 $l$ 的元素值，即为所求。

res += sum[rr] - sum[ll] - lsum + rsum + lval;

时间复杂度分析，预处理的时间复杂度为 $O(\sqrt{2\ast 10^{12}})$，有 $T$ 次询问，每次询问的时间复杂度为 $O(log(\sqrt{2\ast 10^{12}}))$，一个很小的常数，大概 $20$ 左右，所以总的时间复杂度数量级为 $10^6$，完全够用。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static final int N = 1414214;static long[] sum = new long[N];static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer in = new StreamTokenizer(br);public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}public static long nextLong() throws IOException {in.nextToken();return (long) in.nval;}public static void main(String[] args) throws IOException {// TODO Auto-generated method stubfor (int i = 1; i < N; i++) {sum[i] = (long)i * (i + 1) / 2 + sum[i - 1];}int t = nextInt();while (t-- != 0) {long l = nextLong();long r = nextLong();out.println(figure(l, r));}out.flush();}public static long figure(long left, long right) {long res = 0;int ll = 0, rr = 0;int l = 0, r = 1500000;while (l < r) {int mid = l + r + 1 >> 1;if ((long)mid * (mid + 1) / 2 <= left) l = mid;else r = mid - 1;}ll = l;int lrem = (int) (left - (long)l * (l + 1) / 2);long lsum = (long)lrem * (lrem + 1) / 2;long lval = lrem == 0 ? l : lrem;l = 0;r = 1500000;while (l < r) {int mid = l + r + 1 >> 1;if ((long)mid * (mid + 1) / 2 <= right) l = mid;else r = mid - 1;}rr = l;int rrem = (int) (right - (long)l * (l + 1) / 2);long rsum = (long)rrem * (rrem + 1) / 2;res += sum[rr] - sum[ll] - lsum + rsum + lval; return res;}}

G. 和与乘积

思路：
要求一段区间和和与乘积相等的话，$1$ 在里面 是很重要的，所以我们通过一些列的关于1的处理来解决这个问题。

首先我们只存储非 $1$ 的数，统计每一个非 $1$ 的数前连续的1的个数，以及前缀和。

num[i] 表示第i个非1的数
onecnt[i] 第i个非1的数前连续的1的个数
s[i] 包含第i个非1元素的前缀和

进行处理后，上述三个数组的有效长度都是$n-1$，随后求出所有数字的和。然后从第一个非 $1$ 的数开始枚举，计算当前数字和它后面非 $1$ 的数的乘积，在计算的过程中，每乘一个数都要判断是否可以构成一组解：

如果说当前的乘积已经大于所有数的和，那一定找不到对应的一组累加和，直接退出即可。

对于乘积小于所有数的和的情况，首先计算出乘积与和的差值 $d$，如果 $d=0$，则构成一组解，如果说乘积大于差值 ，并且差值小于等于当前区间左右两边相邻的连续的 $1$ 的和，那此时通过加上左右两边的1也可以构成解。

最后的解就是原序列的长度+符合上述分析的解的个数。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;public class Main {static final int N = 200010;static long[] s = new long[N];static int[] num = new int[N], onecnt = new int[N];static int n = 1, k;static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) {// TODO Auto-generated method stubReader reader = new Reader(System.in);k = reader.nextInt();for (int i = 1; i <= k; i++) {int tmp = reader.nextInt();if (tmp == 1) {s[n]++;onecnt[n]++;} else {s[n] += s[n - 1] + tmp;num[n] = tmp;n++;}}// 最后一个非1的数后面可能还有一串1long res = s[n - 1] + onecnt[n];long ans = k;for (int i = 1; i < n; i++) {long p = num[i];for (int j = i + 1; j < n; j++) {p *= num[j];if (p > res) break;/***  s[j]为包含第j个非1元素的前缀和*  s[i - 1]为包含第i - 1个非1元素的前缀和*  第i个非1元素前1的个数为onecnt[i]*  则从第i个非1元素和第j个非1元素的和为s[j] - s[i - 1] - onecnt[i]*/long d = p - s[j] + s[i - 1] + onecnt[i];if (d == 0) ans++;else if (onecnt[i] + onecnt[j + 1] >= d && d > 0) {long left = Math.min(d, onecnt[i]);long right = Math.min(d, onecnt[j + 1]);ans += left + right - d + 1;}}}out.println(ans);out.flush();}static class Reader {//自定义快读 Readpublic BufferedReader reader;public StringTokenizer tokenizer;public Reader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}

H. 巧克力

思路：

贪心问题的难点就在于如何选择贪心策略，如果按照正常思路，从第一天开始就选择能吃的巧克力，前面几天选择的范围比较大，到了后面几天就相对比较难选了，而且前面的选择会直接影响最后是否会有解以及解的大小，但是前面在选的时候根本无法对其造成的影响进行估计，举个例子：如果从前面开始选，一开始会面临很多种选择，通常会选择最优策略，也就是说保质期能满足当前这一天，并且价格最便宜，但如果存在这样一种巧克力，保质期最长，价格也是最低的，在一开始就把它给用了，到了后面就不能用了，也就是说它原本可以在很多天之后吃就行，现在却在前几天就吃了，吃的时候保质期还有很长的一段事件，到了后面可供选择的巧克力保质期就会越来越短，很可能会出现得不到一个可行方案的情况，对于这种情况，其实把前后选择的巧克力对调一下就能解决，把前面选的保质期长，价格低的巧克力放在后面吃，把后面价格高，保质期短的放在前面吃，通过这样一通分析，我们可以惊奇地发现，正着来不行，我们从后面来貌似就比较合理，这也就引申出了我们的正确的策略：

将所有种类的巧克力按保质期从长到短排序，然后我们从后面几天开始选择吃哪块巧克力，对于第 $i$ 天，将所有保质期满足能在第 $i$ 天吃的巧克力都找出来，然后对它们按价格从小到大排序，选择价格最低的在第 $i$ 天吃，并记录一下这种巧克力已经用掉了几块，如果全部都用掉了，那就不能再用了，这里用到了优先队列来动态维护当天能吃的各种巧克力，当前巧克力吃完就弹出。

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.PriorityQueue;public class Main {static final int N = 100010;static int[] cnt = new int[N];static Node[] chos = new Node[N];static int n, x;static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer in = new StreamTokenizer(br);static class Node implements Comparable<Node> {int a, b, c;public Node(int a, int b, int c) {this.a = a;this.b = b;this.c = c;}@Overridepublic int compareTo(Node o) {// TODO Auto-generated method stubreturn o.b - this.b;}}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}public static void main(String[] args) throws IOException {// TODO Auto-generated method stubx = nextInt();n = nextInt();for (int i = 1; i <= n; i++) {int a = nextInt();int b = nextInt();int c = nextInt();chos[i] = new Node(a, b, c);}Arrays.sort(chos, 1, n + 1);PriorityQueue<Node> heap = new PriorityQueue<Node>((o1, o2) -> {return o1.a - o2.a;});int t = 1;long cost = 0;boolean flag = true;for (int i = x; i >= 1; i--) {while(t <= n && chos[t].b >= i) {heap.add(chos[t]);t++;}if (heap.isEmpty()) {flag = false;break;}Node peek = heap.peek();peek.c--;cost += peek.a;if (peek.c == 0) heap.poll();}if (!flag) cost = -1;out.println(cost);out.flush();}}