XX Russia Team Open, High School Programming Contest St Petersburg, Barnaul, Tbilisi, Almaty, Kremenchug, November 30, 2019

• easy: AFI
• medium-easy: BDH
• medium: CGKL
• ???: EJ

A. Attractive Flowers

签到。

B. Blocking the View

C. Fermat’s Last Theorem

题意 将有序四元组 \((a,b,c,n)\) 按 max 为第一关键字，字典序为第二关键字排序，求第 l 位到第 r 位，并判断 \(a^n+b^n\) 与 \(c^n\) 大小关系。

做法 先确定 max，后逐位考虑，可以求出 rank 为 \(x\) 的四元组是谁。如果 \((\frac{a}{c})^n+(\frac{b}{c})^n\) 和 1 的距离大于 eps，直接得出大小关系，否则高精度计算 \(a^n+b^n\) 与 \(c^n\) 大小关系。

D. Guess the Path

题意 交互，\(n*m\)，每次可以输出一条 \((1,1)\) 到 \((n,m)\) 的路径（只能往右走或往下走），返回与既定路径 \(p\) 的交。

做法 如果 \((x_1,y_1), (x_2,y_2)(x_1 \leq x_2, y_1 \leq y_2)\) 在答案中，我们可以递归地构造 \((x_1,y_1)\) 到 \((x_2, y_2)\) 的路径。先右走到 \((x_1, (y_1+y_2)/2)\) 再下走到 \((x_2,(y_1+y_2)/2)\) 再右走，下走的过程和路径 \(p\) 必定有交。这样递归的层数是 log 级别的。

E. Hide-and-Seek for Robots

F. Isosceles triangles

做法

枚举等腰三角形顶点，正三角形会被算多次，减去。

G. Too Many Hyphens

题意 给一个 +- 组成的序列，现在需要插入一个极短的合法括号序列，使得任意两个 - 不相邻。求所有方案中字典序 \(k\) 小。

做法

• 如果有 \(x\) 对 - 相邻，那么最短的括号序列，左括号个数是 \(\lceil \frac{x}{2} \rceil\)
• \(f[i][j][k]\) 表示考虑第 \(0\) 个到第 \(i-1\) 个空隙中填入了 \(j\) 个 {, \(j\) 个 }，接下来有几种填写方式能够填出最优解。
• 决策的时候，枚举在当前空隙填啥，注意到填入的字符不超过 2 个。

H. Planet Nine

题意 两种操作，加 \(9x\)，扔掉长度为 \(y\) 的全是 1 的前缀。把 \(a\) 变成 \(b\)

做法

• 因为 \(9|10^k-1\) 所以每次可以让一个低位减一，让一个高位加一。
• 先把 \(a\) 变成 0，再把 \(0\) 变成 \(b\)

I. Dates

J. Factory

K. RotationAlmostSort

L. Time Travel

XX Russia Team Open, High School Programming Contest St Petersburg, Barnaul, Tbilisi, Almaty, Kremenchug, November 30, 2019

原文：https://www.cnblogs.com/FST-stay-night/p/11979435.html