直线方程集合
• 分式消除误差
• 平面几何

暴力搜索
• 缩放质因子

搜索
• 深度优先搜索
• 记忆化搜索
• 枝剪广搜
• 双向搜索

Dijkstra
• Floyd
• A*

Java Win
• 不依赖 API 的实现

变种三进制

类比单调数列

去冗操作
• 树分裂&合并 (有点忙，待更)

待更

Placeholder

#A ASC

本题总分：5 分

问题描述

  已知大写字母AAA 的ASCIIASCIIASCII 码为656565，请问大写字母20000LLL 的ASCIIASCIIASCII 码是多少？

答案提交

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

76

calcCode：

public class Test {public static void main(String[] args) { new Test().run(); }void run() {// System.out.println(65 + 'L' - 'A');System.out.println((int)'L');}}

麻烦签到题写的认真一点，谢谢。

#B 卡片

本题总分：5 分

问题描述

  小蓝有很多数字卡片，每张卡片上都是数字000 到999。
  小蓝准备用这些卡片来拼一些数，他想从111 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
  小蓝想知道自己能从111 拼到多少。
  例如，当小蓝有303030 张卡片，其中000 到999 各333 张，则小蓝可以拼出111 到101010，但是拼111111 时卡片111 已经只有一张了，不够拼出111111。
  现在小蓝手里有000 到999 的卡片各202120212021 张，共202102021020210 张，请问小蓝可以从111 拼到多少？
  提示：建议使用计算机编程解决问题。

答案提交

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

3181

朴素解法

public class Test {public static void main(String[] args) { new Test().run(); }void run() { System.out.println(calc(2021)); }int calc(int upper) {int[] count = new int[10];for (int n = 1, k = 1; ; k = ++n)doif (++count[k % 10] > upper)return n - 1;while ((k /= 10) > 0);}}

  没什么好说的。

弯道超车

  观察[1,9][1,9][1,9] 这个区间中，[0,9][0,9][0,9] 的出现情况。

  在[1,9][1,9][1,9] 中，111 至999 各出现111 次。

  把观察的范围扩大到[1,99][1,99][1,99]，十位的111 出现[10,19][10,19][10,19] 共101010 次，十位的222 出现[20,29][20,29][20,29] 共101010 次，⋯\\cdots⋯ ，十位的999 出现[90,99][90,99][90,99] 共101010 次，低位[0,9][0,9][0,9] 重复出现101010 次，111 至999 各出现202020 次，000 出现999 次。

  将这个观察范围继续扩大，会发现111 的使用次数总是不小于000 、222 至999，也就是说统计000 、222 至999 是没有意义的。

public class Test {public static void main(String[] args) { new Test().run(); }void run() { System.out.println(calc(2021)); }int calc(int upper) {int count = 0;for (int n = 1, k = 1; ; k = ++n) {doif (k % 10 == 1) count++;while ((k /= 10) > 0);if (count >= upper)return count == upper ? n : n - 1;}}}

#C 直线

本题总分：10 分

问题描述

  在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。
  给定平面上2×32 × 32×3 个整点{(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z}\\{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z\\}{(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z}，即横坐标是000 到111 (包含000 和111) 之间的整数、纵坐标是000 到222 (包含000 和222) 之间的整数的点。这些点一共确定了111111 条不同的直线。
  给定平面上20×2120 × 2120×21 个整点{(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z}\\{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z\\}{(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z}，即横坐标是000 到191919 (包含000 和191919) 之间的整数、纵坐标是000 到202020 (包含000 和202020) 之间的整数的点。请问这些点一共确定了多少条不同的直线。

答案提交

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

40257

直线方程集合

  一种朴素的想法，是将所有点连接起来，去掉重复的线，然后统计。

  为了方便表示，这里采用斜截式方程y=kx+by=kx+by=kx+b 来表示每一条直线，其中kkk 为直线斜率，bbb 为直线在yyy 轴上的截距，并统一不处理斜率不存在的线，将结果加上一个202020。

  注意！ 这段程序的结果是不准确的。

import java.util.HashSet;import java.util.Set;public class Test {public static void main(String[] args) { new Test().run(); }int X = 20, Y = 21;void run() {Set<Line> set = new HashSet();for (int x1 = 0; x1 < X; x1++)for (int y1 = 0; y1 < Y; y1++)for (int x2 = x1; x2 < X; x2++)for (double y2 = 0; y2 < Y; y2++)if (x1 != x2){double k = (y2 - y1) / (x2 - x1);double b = -x1 * k + y1;set.add(new Line(k, b));}System.out.println(set.size() + X);}class Line {double k, b;Line(double b, double k) {this.k = k;this.b = b;}@Overridepublic boolean equals(Object obj) {return k == ((Line)obj).k && b == ((Line)obj).b;}@Overridepublic int hashCode() {return (int)k ^ (int)b;}}}

分式消除误差

  斜率在浮点数表示下，精度那是参差不齐，诚然可以将误差限制在一个范围内，当绝对差落入当中时，我们就将其视为值相同。

  但是对于这种需要可表示的范围小的时候，我们可以定义分式来做到无误差，而不是控制精度。

import java.util.HashSet;import java.util.Set;public class Test {public static void main(String[] args) { new Test().run(); }int X = 20, Y = 21;void run() {Set<Line> set = new HashSet();for (int x1 = 0; x1 < X; x1++)for (int y1 = 0; y1 < Y; y1++)for (int x2 = x1; x2 < X; x2++)for (int y2 = 0; y2 < Y; y2++)if (x1 != x2){Fraction k = new Fraction(y2 - y1, x2 - x1);Fraction b = new Fraction(y1 * (x2 - x1) - x1 * (y2 - y1),x2 - x1);set.add(new Line(k, b));}System.out.println(set.size() + X);}class Fraction {int numerator, denominator;Fraction(int numerator, int denominator) {int gcd = gcd(numerator, denominator);this.denominator = denominator /gcd;this.numerator = numerator / gcd;}int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }@Overridepublic boolean equals(Object obj) {return this.numerator == ((Fraction)obj).numerator && this.denominator == ((Fraction)obj).denominator;}}class Line {Fraction k, b;Line(Fraction b, Fraction k) {this.k = k;this.b = b;}@Overridepublic boolean equals(Object obj) {return this.k.equals(((Line)obj).k) && this.b.equals(((Line)obj).b);}@Overridepublic int hashCode() {return k.denominator;}}}

平面几何

  这是一个平面直角坐标系，原点与(1,2)(1,2)(1,2) 连成一条线段。

  我们将经过这两点的直线，以及这条直线经过的点与该点于横竖轴的垂线标记出来。

  显然，若直线经过(x1,y1)(x_{1},y_{1})(x1​,y1​)、(x2,y2)(x_{2},y_{2})(x2​,y2​) 两点，那么它必然也经过(x1+k(x1−x2),y1+k(y1−y2))(x_{1} +k(x_{1} – x_{2}),y_{1} + k(y_{1} – y_{2}))(x1​+k(x1​−x2​),y1​+k(y1​−y2​))，k∈Zk \\in Zk∈Z。

  若在连接一条直线时，将所有直线经过的点标记起来，在下次遇到已经标记过的两点，我们便可直接跳过。

public class Test {public static void main(String[] args) { new Test().run(); }int X = 20, Y = 21;void run() {int count = 0;boolean[][][][] marked = new boolean[X][Y][X][Y];for (int x1 = 0; x1 < X; x1++)for (int y1 = 0; y1 < Y; y1++) {marked[x1][y1][x1][y1] = true;for (int x2 = 0; x2 < X; x2++)for (int y2 = 0; y2 < Y; y2++) {if (marked[x1][y1][x2][y2]) continue;int x = x1, y = y1, xOffset = x - x2, yOffset = y - y2;while (x >= 0 && x < X && y >= 0 && y < Y) {x += xOffset;y += yOffset;}x -= xOffset;y -= yOffset;while (x >= 0 && x < X && y >= 0 && y < Y) {for (int i = x - xOffset, j = y - yOffset; i >= 0 && i < X && j >= 0 && j < Y; i -= xOffset, j -= yOffset) {marked[x][y][i][j] = marked[i][j][x][y] = true;}x -= xOffset;y -= yOffset;}count++;}}System.out.println(count);}}

  我觉得可能会再考个差不多的，这里给大伙一个推论。

  平面直角坐标系上有n×nn × nn×n，n≥2n \\ge 2n≥2 个点{(x,y)∣0≤x<n,0≤y<n,x∈Z,y∈Z}\\{(x, y)|0 ≤ x < n, 0 ≤ y < n, x ∈ Z, y ∈ Z\\}{(x,y)∣0≤x<n,0≤y<n,x∈Z,y∈Z}，从原点出发可连接的不同直线为1≤x,y<n1 \\leq x,y <n1≤x,y<n，x≠yx \\ne yx​=y 中gcd(x,y)=1gcd(x,y) = 1gcd(x,y)=1 的次数加333。

  感兴趣的读者可以自行证明。

  同时在1≤x<y<n1 \\leq x < y < n1≤x<y<n 时，gcd(x,y)=1gcd(x,y) = 1gcd(x,y)=1 的出现次数恰好等于∑y=2n−1φ(y)\\displaystyle\\sum_{y = 2}^{n-1}\\varphi(y)y=2∑n−1​φ(y)，其中φ\\varphiφ 为欧拉函数。

  能力有限，这里便不再继续讨论。

#D 货物摆放

本题总分：10 分

问题描述

  小蓝有一个超大的仓库，可以摆放很多货物。
  现在，小蓝有nnn 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
  小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆L、W、HL、W、HL、W、H 的货物，满足n=L×W×Hn = L × W × Hn=L×W×H。
  给定nnn，请问有多少种堆放货物的方案满足要求。
  例如，当n=4n = 4n=4 时，有以下666 种方案：1×1×41×1×41×1×4、1×2×21×2×21×2×2、1×4×11×4×11×4×1、2×1×22×1×22×1×2、2×2×12 × 2 × 12×2×1、4×1×14 × 1 × 14×1×1。
  请问，当n=2021041820210418n = 2021041820210418n=2021041820210418 （注意有161616 位数字）时，总共有多少种方案？
  提示：建议使用计算机编程解决问题。

答案提交

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

2430

暴力搜索

  每届必考的基本算术定理。

import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;public class Test {public static void main(String[] args) { new Test().run(); }long n = 2021041820210418L;void run() {List<Integer> exps0 = new ArrayList();ArrayDeque<Integer> exps1 = new ArrayDeque();for (int k = 2; k <= n; k++)if (n % k == 0) {int e = 0;while (n % k == 0) {n /= k;e++;}exps0.add(e);}System.out.println(dfs(exps0, exps1, 0));}int dfs(List<Integer> exps0, ArrayDeque<Integer> exps1, int cur) {if (cur == exps0.size()) {int comb = 1;for (int exp : exps1)comb *= exp + 1;return comb;}int ans = 0;for (int i = exps0.get(cur); i >= 0; i--) {exps1.push(i);ans += dfs(exps0, exps1, cur + 1);exps1.pop();}return ans;}}

  直接套两 for 也不是不行，但这么写出来的程序，通常到比赛结束都跑不完。

  因此我们要避免无效因子的判断，

  这里统计的为质因子分成三份，可能的组合个数，它与原命题等价。

  没什么好讲的。

  只用套两 for 是因为一个数的因子只能成对出现，

  扫一下数盲。

缩放质因子

  举个例子，

  当n=9n = 9n=9  时，有666 种方案：1×1×91×1×91×1×9、1×3×31×3×31×3×3、1×9×11×9×11×9×1、3×1×33×1×33×1×3、3×3×13 × 3 × 13×3×1、9×1×19 × 1 × 19×1×1;

  当n=25n = 25n=25 时，有666 种方案：1×1×251×1×251×1×25、1×5×51×5×51×5×5、⋯\\cdots⋯ ;

  当n=p2n =p^{2^{}}n=p2 时，有666 种方案：1×1×p21×1×p^{2}1×1×p2、1×p×p1×p×p1×p×p、⋯\\cdots⋯ ;

  其中ppp 为质数。

  其实上例解法当中，我们就能发现，组合的个数与其具体的值无关，它只与质因数指数挂钩。

  2021041820210418=2×33×17×131×2857×58823532021041820210418 = 2 × 3^3 × 17 × 131 × 2857 × 58823532021041820210418=2×33×17×131×2857×5882353

  如果我们找最小的几个质数来代替它们，得到的新数字23×3×5×7×11×13=1201202^3 × 3 × 5 × 7 × 11 × 13 = 12012023×3×5×7×11×13=120120 与202104182021041820210418202104182021041820210418 在这个命题下等价。

  而120120120120120120 的大小就足够我们真暴搜把它的全部因数组合找到了。

import java.util.ArrayList;import java.util.List;public class Test {public static void main(String[] args) { new Test().run(); }long N = 2021041820210418L;void run() {List<Integer> exps = new ArrayList();for (int k = 2; k <= N; k++)if (N % k == 0) {int e = 0;while (N % k == 0) {N /= k;e++;}exps.add(e);}exps.sort((a, b) -> (b - a));int n = 1, p = 2, ans = 0;for (int exp : exps) {for (int i = 2; i * i <= p; i++)if (p % i == 0) {i = 1;p++;}while (exp-- > 0) n *= p;p++;}for (int a = 1; a <= n; a++)if (n % a == 0)for (int b = 1; b <= n; b++)if (n / a % b == 0) ans++;System.out.println(ans);}}

#E 路径

本题总分：15 分

问题描述

  小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
  小蓝的图由202120212021 个结点组成，依次编号111 至202120212021。对于两个不同的结点a,ba, ba,b，如果aaa 和bbb 的差的绝对值大于212121，则两个结点之间没有边相连；如果aaa 和bbb 的差的绝对值小于等于212121，则两个点之间有一条长度为aaa 和bbb 的最小公倍数的无向边相连。
  例如：结点111 和结点232323 之间没有边相连；结点333 和结点242424 之间有一条无向边，长度为242424；结点151515 和结点252525 之间有一条无向边，长度为757575。
  请计算，结点111 和结点202120212021 之间的最短路径长度是多少。
  提示：建议使用计算机编程解决问题。

答案提交

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

10266837

  题目已经说的够清楚了，

  建一个有202120212021 个顶点21×2000+21(21+1)221 × 2000 + \\cfrac{21(21 + 1)}{2}21×2000+221(21+1)​ 条边的无向图，跑图上的算法就完事了。

  还有的细节就是整形是否会溢出，我们取(1,2021](1,2021](1,2021] 中最大的质数201720172017 与202122021^220212 相乘，得到的结果还是有点夸张的，虽然经过测试，可能的线路权值合至多不会超过231−12^{31} – 1231−1，但毕竟是面向竞赛，考虑甄别的时间成本，直接使用长整形更为划算。

搜索

深度优先搜索

  202120212021 个顶点，绝大多数顶点都连有2×212 × 212×21 条边，

  别深搜了，一搜就是

  compilaition completed successfully in 500ms(4 hour ago)

  就，电脑跟选手对着坐牢。

记忆化搜索

  深度优先搜索，在搜索最优结果时，通常需要完整的枚举全部可能的问题状态。

  但在这个问题状态的集合中，所有可选方案的 “后缀” 都是相同，也就是所有可选的分支，它们都是以同一个节点结尾。

  如果我们将已经搜索到的节点到目标节点间的最短路径保存下来，在再次搜索到这个 “后缀” 的分支时直接返回。

  那么问题就可能在一个较短的时间内解决。

  这也是所谓的记忆化搜索。

import java.util.ArrayList;import java.util.List;public class Test {public static void main(String[] args) { new Test().run(); }int N = 2021;int[] weight = new int[N + 1];List<Edge>[] graph = new List[N + 1];boolean[] visited = new boolean[N + 1];void run() {for (int i = 1; i <= N; i++)graph[i] = new ArrayList();for (int v = 1; v <  N; v++)for (int w = v + 1; w <= min(v + 21, N);  w++) {graph[v].add(new Edge(w, lcm(v, w)));graph[w].add(new Edge(v, lcm(v, w)));}visited[1] = true;System.out.println(dfs(1));}int dfs(int v) {if (v == N) return 0;if (weight[v] != 0) return weight[v];int min = 0x7FFFFFFF;for (Edge edge : graph[v]) {if (visited[edge.w]) continue;visited[edge.w] = true;min = min(min, dfs(edge.w) + edge.weight);visited[edge.w] = false;}return weight[v] = min;}int min(int a, int b) { return a < b ? a : b; }int lcm(int a, int b) { return a * b / gcd(a, b); }int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }class Edge {int w, weight;Edge(int w, int weight) {this.weight = weight;this.w = w;}}}

枝剪广搜

  其实朴素的去搜索，不论深搜还是广搜，在竞赛里都是很冒进的行为，

  影响这两个算法执行效率的因素太多。

  当然要是没有其他的思路，也只能死马当活马医了。

  幸运的是，只需简单的枝剪，就能在很短的时间计算出结果

import java.util.PriorityQueue;import java.util.ArrayList;import java.util.Arrays;import java.util.Queue;import java.util.List;public class Test {public static void main(String[] args) { new Test().run(); }int N = 2021;void run() {List<Edge>[] graph = new List[N + 1];long[] visited = new long[N + 1];for (int i = 1; i <= N; i++)graph[i] = new ArrayList();for (int v = 1; v <  N; v++)for (int w = v + 1; w <= min(v + 21, N);  w++) {graph[v].add(new Edge(w, lcm(v, w)));graph[w].add(new Edge(v, lcm(v, w)));}Queue<Vertex> queue = new PriorityQueue();Arrays.fill(visited, Long.MAX_VALUE);queue.offer(new Vertex(1, 0));Vertex V = null;while (queue.size() > 0) {V = queue.poll();if (V.v == N) break;if (V.weight >= visited[V.v]) continue;visited[V.v] = V.weight;for (Edge edge : graph[V.v])queue.offer(new Vertex(edge.w, edge.weight + V.weight));}System.out.println(V.weight);}int min(int a, int b) { return a < b ? a : b; }int lcm(int a, int b) { return a * b / gcd(a, b); }int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }class Edge {int w, weight;Edge(int w, int weight) {this.weight = weight;this.w = w;}}class Vertex implements Comparable<Vertex> {int v;long weight;Vertex(int v, long weight) {this.weight = weight;this.v = v;}@Overridepublic int compareTo(Vertex V) { return Long.compare(this.weight, V.weight); }}}

双向搜索

  很容易就能发现，越是编号大的节点，连接着它的边的权重可能越大。

  也就是在最短路径的这条分支中，越是靠近目标节点，就越可能进入无效的分支。

  通常，在这个数据规模下，不带策略的去广搜是致命的。

  一种常见的优化方法是从源点和终点双向开始搜索，当两条分支相遇时，即视为找到了最短路径。

  由于这种问题可选择的解法有很多，这里便不做展开。

import java.util.PriorityQueue;import java.util.ArrayList;import java.util.Queue;import java.util.List;public class Test {public static void main(String[] args) { new Test().run(); }int N = 2021;void run() {List<Edge>[] graph = new List[N + 1];long[] visited0 = new long[N + 1];long[] visited1 = new long[N + 1];for (int i = 1; i <= N; i++) {graph[i] = new ArrayList();visited0[i] = visited1[i] = Long.MAX_VALUE;}for (int v = 1; v <  N; v++)for (int w = v + 1; w <= min(v + 21, N);  w++) {graph[v].add(new Edge(w, lcm(v, w)));graph[w].add(new Edge(v, lcm(v, w)));}Queue<Vertex> queue = new PriorityQueue();queue.offer(new Vertex(N, 0, false));queue.offer(new Vertex(1, 0));Vertex V = null;while (true) {V = queue.poll();if (V.fromHead) {if (visited1[V.v] != Long.MAX_VALUE) break;if (V.weight >= visited0[V.v]) continue;visited0[V.v] = V.weight;} else {if (visited0[V.v] != Long.MAX_VALUE) break;if (V.weight >= visited1[V.v]) continue;visited1[V.v] = V.weight;}for (Edge edge : graph[V.v])queue.add(new Vertex(edge.w, edge.weight + V.weight, V.fromHead));}System.out.println(V.weight + (V.fromHead ? visited1[V.v] : visited0[V.v]));}int min(int a, int b) { return a < b ? a : b; }int lcm(int a, int b) { return a * b / gcd(a, b); }int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }class Edge {int w, weight;Edge(int w, int weight) {this.weight = weight;this.w = w;}}class Vertex implements Comparable<Vertex> {int v;long weight;boolean fromHead;Vertex(int v, long weight) { this(v, weight, true); }Vertex(int v, long weight, boolean fromHead) {this.fromHead = fromHead;this.weight = weight;this.v = v;}@Overridepublic int compareTo(Vertex V) { return Long.compare(this.weight, V.weight); }}}

单源最短路径

Dijkstra

  题目给出的图显然是个边加权，权重非负的无向图，跑遍DijkstraDijkstraDijkstra 就完事了。

import java.util.PriorityQueue;import java.util.ArrayList;import java.util.Queue;import java.util.List;public class Test {public static void main(String[] args) { new Test().run(); }int N = 2021;void run() {boolean[] marked = new boolean[N + 1];List<Edge>[] graph = new List[N + 1];long[] distTo = new long[N + 1];for (int i = 1; i <= N; i++) {graph[i] = new ArrayList();distTo[i] = Long.MAX_VALUE;}for (int v = 1; v <  N; v++)for (int w = v + 1; w <= min(v + 21, N);  w++) {graph[v].add(new Edge(w, lcm(v, w)));graph[w].add(new Edge(v, lcm(v, w)));}Queue<Vertex> queue = new PriorityQueue();queue.offer(new Vertex(1, distTo[1] = 0));while (queue.size() > 0) {Vertex V = queue.poll();if (marked[V.v])continue;marked[V.v] = true;for (Edge edge : graph[V.v])if (distTo[edge.w] > distTo[V.v] + edge.weight)queue.offer(new Vertex(edge.w, distTo[edge.w] = distTo[V.v] + edge.weight));}System.out.println(distTo[N]);}int min(int a, int b) { return a < b ? a : b; }int lcm(int a, int b) { return a * b / gcd(a, b); }int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }class Edge {int w, weight;Edge(int w, int weight) {this.weight = weight;this.w = w;}}class Vertex implements Comparable<Vertex> {int v;long dist;Vertex(int v, long dist) {this.dist = dist;this.v = v;}@Overridepublic int compareTo(Vertex V) { return Long.compare(this.dist, V.dist); }}}

Floyd

  如果是一道最短路径的结果题。

  竞赛时限内能运行完O(n3)O(n^{3})O(n3) 的程序。

  那其实无脑套FloydFloydFloyd 就行。

public class Test {public static void main(String[] args) { new Test().run(); }int N = 2021;void run() {long[][] floyd = new long[N + 1][N + 1];for (int v = 1; v < N; v++)for (int w = v + 1; w <= min(N, v + 21); w++)floyd[v][w] = floyd[w][v] = lcm(v, w);for (int k = 1; k <= N; k++)for (int v = 1; v <= N; v++)if (floyd[v][k] == 0) continue;else for (int w = 1; w <= N; w++)if (floyd[k][w] == 0) continue;else if (floyd[v][w] == 0 || floyd[v][k] + floyd[k][w] < floyd[v][w])floyd[v][w] = floyd[v][k] + floyd[k][w];System.out.println(floyd[1][N]);}long min(int a, int b) { return a < b ? a : b; }int lcm(int a, int b) { return a * b / gcd(a, b); }int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}

  半分钟就出来了，还行。

A*

  隐隐觉得能找到一些有启发性的性质。

  推了一下午狗屁没推出来，就当在这开个坑把。

在这里4d393插入代码片

动态规划

  受不同的图性质影响，通常最短路径问题难以在线性时间内用动态规划解决。

  但这里给定无向图，

  我们将最短路径上的节点按升序排列，对于任意vvv、www，1<v<w<n1 < v < w < n1<v<w<n 只存在以下两种情况：

  但只有序号的绝对差小于等于212121 时，两个节点之间才存在边，即二图情况的前提条件是1<v<w≤221 < v < w \\leq 221<v<w≤22，将其推广至1≤x<v<w<y≤n1 \\leq x < v < w < y \\leq n1≤x<v<w<y≤n 的情况，

  显然，从源点到任意点VVV 的最短路径只会从[V−21,V+21][V -21,V+21][V−21,V+21] 中产生，我们先顺序的求出每个W=V+21W = V + 21W=V+21 较优路径，再用每个WWW 对[W−21,W)[W – 21, W)[W−21,W) 间的节点进行松弛，松弛完毕时(1,V](1,V](1,V] 间的路径已是最优。

  综上有状态转移方程：

  dp(i)=min⁡{dp(j)+lcm(i,j)}dp(i) = \\min\\{dp(j) + lcm(i, j)\\}dp(i)=min{dp(j)+lcm(i,j)}，i>j≥i−21i > j \\ge i -21i>j≥i−21

public class Test {public static void main(String[] args) { new Test().run(); }int N = 2021;void run() {long[] dp = new long[N + 1];for (int w = 2; w <= N; w++) {dp[w] = Long.MAX_VALUE;for (int v = w - 1; v > 0 && v >= w - 21; v--)dp[w] = min(dp[w], dp[v] + lcm(v, w));}System.out.println(dp[N]);}long min(long a, long b) { return a < b ? a : b; }int lcm(int a, int b) { return a * b / gcd(a, b); }int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}

#F 时间显示

时间限制:1.01.01.0s 内存限制:512.0512.0512.0MB 本题总分：151515 分

问题描述

  小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从197019701970 年111 月 1 日00:00:0000:00:0000:00:00 到当前时刻经过的毫秒数。
  现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需显示出时分秒即可，毫秒也不用显示，直接舍去即可。
  给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

输入格式

  输入一行包含一个整数，表示时间。

输出格式

  输出时分秒表示的当前时间，格式形如HHHHHH:MMMMMM:SSSSSS，其中HHHHHH 表示时，值为000 到232323，MMMMMM 表示分，值为000 到595959，SSSSSS 表示秒，值为000 到595959。时、分、秒不足两位时补前导000。

测试样例1

Input：46800999Output：13:00:00

测试样例2

Input：1618708103123Output：01:08:23

评测用例规模与约定

  对于所有评测用例，给定的时间为不超过101810^{18}1018 的正整数。

Java Win

import java.util.Scanner;import java.time.LocalTime;import java.time.format.DateTimeFormatter;public class Main {public static void main(String[] args) { new Main().run(); }void run() {System.out.println(LocalTime.MIDNIGHT.plusSeconds(new Scanner(System.in).nextLong() / 1000).format(DateTimeFormatter.ISO_LOCAL_TIME));}}

不依赖 API 的实现

import java.util.Scanner;public class Test {public static void main(String[] args) { new Test().run(); }void run() {long t = new Scanner(System.in).nextLong();System.out.printf("%02d:%02d:%02d",t / 3600000 % 24, t / 60000 % 60, t / 1000 % 60);}}

  送分。

#G 最少砝码

时间限制:1.01.01.0s 内存限制:512.0512.0512.0MB 本题总分：202020 分

问题描述

  你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于NNN 的正整数重量。
  那么这套砝码最少需要包含多少个砝码？
  注意砝码可以放在天平两边。

输入格式

  输入包含一个正整数NNN。

输出格式

  输出一个整数代表答案。

测试样例1

Input：7Output：3Explanation：3 个砝码重量是 1、4、6，可以称出 1 至 7 的所有重量。1 = 1；2 = 6 − 4 (天平一边放 6，另一边放 4)；3 = 4 − 1；4 = 4；5 = 6 − 1；6 = 6；7 = 1 + 6；少于 3 个砝码不可能称出 1 至 7 的所有重量。

评测用例规模与约定

  对于所有评测用例，1≤N≤10000000001 ≤ N ≤ 10000000001≤N≤1000000000。

变种三进制

  不知道怎么取标题，也算是个规律题，

  这不是纯纯的恶心人吗。

  一个集合中包含nnn 个数，任取若干数可以加减出任意小于等于NNN 的正整数。

  首先要考虑怎么去满足题目要求的性质，

  设第iii 个砝码的重量为wiw_{i}wi​，原集合AN={w1,w2,⋯ ,wn}A_{N} = \\{w_{1},w_{2},\\cdots,w_{n}\\}AN​={w1​,w2​,⋯,wn​}。

  要满足题意首先要有sum(A)≥Nsum(A) \\ge Nsum(A)≥N，

  设我们知道了A⌊N/3⌋A_{\\lfloor N/3 \\rfloor}A⌊N/3⌋​ 的方案，那么我们就能在这个方案里加入一个2⌊N/3⌋+12\\lfloor N/3 \\rfloor + 12⌊N/3⌋+1，就能用2⌊N/3⌋+12\\lfloor N/3 \\rfloor + 12⌊N/3⌋+1 对A⌊N/3⌋A_{\\lfloor N/3 \\rfloor}A⌊N/3⌋​ 中个若干元素做差表示出(⌊N/3⌋,2⌊N/3⌋+1)(\\lfloor N/3 \\rfloor, 2\\lfloor N/3 \\rfloor + 1)(⌊N/3⌋,2⌊N/3⌋+1)，对若干元素求和表示出(2⌊N/3⌋+1,N](2\\lfloor N/3 \\rfloor + 1, N](2⌊N/3⌋+1,N]，并入A⌊N/3⌋A_{\\lfloor N/3 \\rfloor}A⌊N/3⌋​ 本身能表示的范围，即能表示出任意小于等于NNN 的正整数。

  如果A⌊N/3⌋A_{\\lfloor N/3 \\rfloor}A⌊N/3⌋​ 本身是最优的，那么往里面加入K=2⌊N/3⌋+1K = 2\\lfloor N/3 \\rfloor + 1K=2⌊N/3⌋+1 的ANA_NAN​ 也一定是最优的，因为要使得K+sum(A⌊N/3⌋)≥NK + sum(A_{\\lfloor N/3 \\rfloor}) \\ge NK+sum(A⌊N/3⌋​)≥N，KKK 必须大于等于2⌊N/3⌋+12\\lfloor N/3 \\rfloor + 12⌊N/3⌋+1，而当K>2⌊N/3⌋+1K > 2\\lfloor N/3 \\rfloor + 1K>2⌊N/3⌋+1 时，就无法表示出⌊N/3⌋+1\\lfloor N/3 \\rfloor + 1⌊N/3⌋+1，

  当然这一切还有个前提条件，那就是sum(A⌊N/3⌋)=⌊N/3⌋sum(A_{\\lfloor N/3 \\rfloor}) = \\lfloor N/3 \\rfloorsum(A⌊N/3⌋​)=⌊N/3⌋。’

  不过到这里已经足够启发我们去顺推了，

  因为这个问题的边界是显然的，

  当N=1N = 1N=1 时，A1={1}A_{1} = \\{1\\}A1​={1}，

  我们往A1A_{1}A1​ 中加入2×sum(A1)+12 × sum(A_{1}) + 12×sum(A1​)+1，得到A4A_{4}A4​，即

  当N=4N = 4N=4 时，A4={1,3}A_{4} = \\{1,3\\}A4​={1,3}，

  当N=13N = 13N=13 时，A13={1,3,9}A_{13} = \\{1,3,9\\}A13​={1,3,9}，

  ⋯⋯\\cdots \\cdots⋯⋯

  当然还存在NNN 不在我们找到的最优规律中。

  我们设N=5N = 5N=5，

  因为A4={1,3}A_{4} = \\{1,3\\}A4​={1,3} 的最优性，222 个元素至多组成任意小于等于444 的正整数，

  因为A13={1,3,9}A_{13} = \\{1,3,9\\}A13​={1,3,9} 的最优性，333 个元素可以表示任意小于等于131313 的正整数。

  即对N=5N = 5N=5 给出的答案，必须大于222 小于等于333。

  对于给出任意NNN 我们都可以按照这个性质求出答案。

  同时在三进制下来看这个规律：

  {N}={(1)3,(11)3,(11)3,⋯ }\\{N\\} = \\{(1)_{3},(11)_{3},(11)_{3},\\cdots\\}{N}={(1)3​,(11)3​,(11)3​,⋯}

  可以二分，但没有必要。

import java.util.Scanner;public class Main {public static void main(String[] args) { new Main().run(); }void run() {long N = new Scanner(System.in).nextLong(), ans = 1;for (long pow3 = 1; pow3 < N; pow3 = pow3 * 3 + 1, ans++);System.out.println(ans);}}

  写的稀烂，主要这题目出的就恶心人。

#H 杨辉三角形

时间限制:5.05.05.0s 内存限制:512.0512.0512.0MB 本题总分：202020 分

  下面的图形是著名的杨辉三角形：
  如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

  1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \\cdots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯
  给定一个正整数NNN，请你输出数列中第一次出现NNN 是在第几个数？

输入格式

  输入一个整数NNN。

输出格式

  输出一个整数代表答案。

测试样例1

Input：6Output：13

评测用例规模与约定

  对于202020% 的评测用例，1≤N≤101 ≤ N ≤ 101≤N≤10；
  对于所有评测用例，1≤N≤10000000001 ≤ N ≤ 10000000001≤N≤1000000000。

  图片高清重置

类比单调数列

  杨辉三角最外层全部是111。

  第二层则是自然数序列。

  因为杨辉三角是左右对称的，因此我们可以忽略右边(左边的数字总是比右边先出现)，并将数字按层分成若干序列。

  由于序列都是从上置下单调递增的，我们可以在每一个这种序列上，二分查找NNN 的位置，特别的，N=1N = 1N=1 时直接输出111。

  此外，杨辉三角第nnn 行 m列列列

  =Cn−1m−1=(n−1)!(m−1)!(n−m)!=C_{n-1}^{m-1} = \\cfrac{(n-1)!}{(m-1)!(n – m)!}=Cn−1m−1​=(m−1)!(n−m)!(n−1)!​

  这个数字增长的非常快C3216=1166803110>1e9C_{32}^{16} = 1166803110 > 1e9C3216​=1166803110>1e9。

  也就至多在141414 条(除去最外两层)这样的序列中查找NNN 的位置，因为序列的单调性不允许NNN 的出现。

import java.util.Scanner;public class Main {public static void main(String[] args) { new Main().run(); }int N;void run() {N = new Scanner(System.in).nextInt();if (N == 1) System.out.println(1);else {long ans = (N + 1L) * N / 2 + 2;for (int m = 2; m < 16; m++) {int start = m * 2, end = N;while (start <= end) {int mid = start + end >> 1;if (C(mid, m) == N) {ans = min(ans, (mid + 1L) * mid / 2 + m + 1);break;} if (C(mid, m) > N) end = mid - 1;else start = mid + 1;}}System.out.println(ans);}}long min(long a, long b) { return a < b ? a : b; }long C(int n, int m) {long num = 1;for (int nm = 1; nm <= m; n--, nm++)if ((num = num * n / nm) > N) return num;return num;}}

#I 双向排序

时间限制:5.05.05.0s 内存限制:512.0512.0512.0MB 本题总分：252525 分

问题描述

  给定序列(a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n)(a_{1}, a_{2}, · · · , a_{n}) = (1, 2, · · · , n)(a1​,a2​,⋅⋅⋅,an​)=(1,2,⋅⋅⋅,n)，即ai=ia_{i} = iai​=i。
  小蓝将对这个序列进行mmm 次操作，每次可能是将a1,a2,⋅⋅⋅,aqia_{1}, a_{2}, · · · , a_{q_{i}}a1​,a2​,⋅⋅⋅,aqi​​ 降序排列，或者将aqi,aqi+1,⋅⋅⋅,ana_{q_{i}}, a_{q_{i+1}}, · · · , a_{n}aqi​​,aqi+1​​,⋅⋅⋅,an​ 升序排列。
  请求出操作完成后的序列。

输入格式

  输入的第一行包含两个整数n,mn, mn,m，分别表示序列的长度和操作次数。
  接下来mmm 行描述对序列的操作，其中第iii 行包含两个整数pi,qip_{i}, q_{i}pi​,qi​ 表示操作类型和参数。当pi=0p_{i} = 0pi​=0 时，表示将a1,a2,⋅⋅⋅,aqia_{1}, a_{2}, · · · , a_{q_{i}}a1​,a2​,⋅⋅⋅,aqi​​ 降序排列；当pi=1p_{i} = 1pi​=1 时，表示将aqi,aqi+1,⋅⋅⋅,ana_{q_{i}}, a_{q_{i+1}}, · · · , a_{n}aqi​​,aqi+1​​,⋅⋅⋅,an​ 升序排列。

输出格式

  输出一行，包含nnn 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

测试样例1

Input：3 30 31 20 2Output：3 1 2Explanation：原数列为 (1, 2, 3)。第 1 步后为 (3, 2, 1)。第 2 步后为 (3, 1, 2)。第 3 步后为 (3, 1, 2)。与第 2 步操作后相同，因为前两个数已经是降序了。

评测用例规模与约定

  对于303030% 的评测用例，n,m≤1000n, m ≤ 1000n,m≤1000；
  对于606060% 的评测用例，n,m≤5000n, m ≤ 5000n,m≤5000；
  对于所有评测用例，1≤n,m≤1000001 ≤ n, m ≤ 1000001≤n,m≤100000，0≤pi≤10 ≤ p_{i} ≤ 10≤pi​≤1，1≤qi≤n1 ≤ q_{i} ≤ n1≤qi​≤n；

去冗操作

  其实看到这个数据规模，五分钟写完 Brute Force，就可以下一道了，O(mnlog⁡n)O(mn \\log n)O(mnlogn) 就能过606060% 的用例，

  多的时间去证明其他程序的正确性可能收益会高点。

  不过，骗分就多骗两个吧。

  对于连续且pip_{i}pi​ 相同操作，在pi=0p_{i} = 0pi​=0 时只需要做qiq_{i}qi​ 最大的操作，在pi=1p_{i} = 1pi​=1 时只需要做qiq_{i}qi​ 最小的操作，如图：

  显然去掉冗余操作后，还是和原操作是等价的，只需要建立一个栈就能在线性时间内完成去冗，并且代码量较少。

  特别的，我可以先将(p:1,q:1)(p:1,q:1)(p:1,q:1) 压入栈底。

import java.io.*;import java.util.*;public class Main {public static void main(String[] args) { new Main().run(); }void run() {InputReader in = new InputReader(System.in);PrintWriter out = new PrintWriter(System.out);int n = in.readInt(), m = in.readInt();Deque<Step> deque = new ArrayDeque();deque.push(new Step(1, 1));while (m-- > 0) {int p = in.readInt();int q = in.readInt();while (deque.size() > 0 && deque.peek().p == p)if (p == 0)q = max(q, deque.pop().q);elseq = min(q, deque.pop().q);deque.push(new Step(p, q));}Integer[] ans = new Integer[n];for (int i = 0; i < n; i++)ans[i] = i + 1;deque.pollLast();while (deque.size() > 0) {Step step = deque.pollLast();if (step.p == 0)Arrays.sort(ans, 0, step.q, (a, b)->(b - a));elseArrays.sort(ans, step.q - 1, n);}for (int i = 0; i < n; i++) {out.print(ans[i]);out.print(' ');}out.flush();}int max(int a, int b) { return a > b ? a : b; }int min(int a, int b) { return a < b ? a : b; }class Step {int p, q;Step(int p, int q) {this.p = p;this.q = q;}}class InputReader {BufferedReader reader;StringTokenizer token;InputReader(InputStream in) {this.reader = new BufferedReader(new InputStreamReader(in));}String read() {while (token == null || !token.hasMoreTokens()) {try {token = new StringTokenizer(reader.readLine());} catch (IOException e) {e.printStackTrace();}}return token.nextToken();}int readInt() { return Integer.parseInt(read()); }}}

树分裂&合并 (有点忙，待更)

#J 括号序列

时间限制:5.05.05.0s 内存限制:512.0512.0512.0MB 本题总分：252525 分

问题描述

  给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
  两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
  例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。

输入格式

  输入一行包含一个字符串sss，表示给定的括号序列，序列中只有左括号和右括号。

输出格式

  输出一个整数表示答案，答案可能很大，请输出答案除以100000000710000000071000000007 (即109+710^{9} + 7109+7) 的余数。

测试样例1

Input：((()Output：5

评测用例规模与约定

  对于404040% 的评测用例，∣s∣≤200|s| ≤ 200∣s∣≤200。
  对于所有评测用例，1≤∣s∣≤50001 ≤ |s| ≤ 50001≤∣s∣≤5000。

待更