2A
题意:给定一个01串,每次可以循环移动一个子串,求多少次操作使整串有序(升序)。
每次操作至多使极大全1段个数减一:111100001111
\(\to\) 000011111111
。
数一下一开始有多少全1段,判断一下最后一个元素是否是1即可。submission
A
题意:给定 \(n, m, a, b, k\),求满足 \(ax + by = k,\ x, y \ge 0\) 的 \(n + m - (x + y) \times \min(\lfloor\frac{n}{x}\rfloor,\ \lfloor\frac{m}{y}\rfloor)\) 最小值。
数据范围:\(1 \le n, m, a, b, k \le 10^9\)。
exgcd 求出一组 \((X, Y)\),其他可用 \((X + k\Delta x,\ Y - k\Delta y)\) 表示。
枚举 \(O(\sqrt n)\) 种不同的 \(\min(\lfloor\frac{n}{x}\rfloor,\ \lfloor\frac{m}{y}\rfloor)\),容易求出 \(\max(x + y) = X + Y + k(\Delta x - \Delta y)\)。submission
B
题意:
C
题意:定义一个序列的权值为每个数依次拼接后数的大小。
构造一个 \(a_i \in [0, 9]\) 的序列,使得他所有最长严格上升子序列的权值和等于 \(c\),\(0 \le c \le 10^{13}, \ \vert a\vert \le 500\)。
如果 \(c\) 足够大,可以用 \(56789a + 01234b\) 表示(两数互质),令 \(b < 56789\)。
构造形如 [5...9][0...4]
的数列,使得 LIS 为 \(5\),且只存在 \(56789\) 和 \(01234\) 两种形式。
两部分显然是独立的,只讨论前一部分,用 \(0 \sim 4\) 对应 \(5 \sim 9\)。
在 \(k\) 进制下进行构造,满足 \(k^5\) 足够大。
设最大的 \(i\) 满足 \(\sum_{j = 0}^{i - 1}k^{j} \le a\),则剩下的 \(a - \sum_{j = 0}^{i - 1}k^{j}\) 可被 \(k\) 进制表示为 \(\sum_{j = 1}^i x_jk^{i - j}\),保证 \(i \le 5\)。
构造:\(\bigg\vert 012\cdots i\bigg\vert + \bigg\vert i^{x_i} + (i -1)^{x_{i - 1}} + \cdots + 1^{x1}\bigg\vert + \bigg\vert 2^k + \cdots + i^{k}\bigg\vert + \bigg\vert(i + 1) + (i + 2) + \cdots + 4\bigg\vert\)。
上标表示这个串重复出现次数,加法表示拼接。
\([i + 1, 4]\) 的部分唯一确定,对前三段进行计数。
假设选了 \(\text{I}\) 的一个前缀 \([0, j]\),若 \(j + 1\) 出现在 \(\text{II}\),则方案数为 \(x_{j + 1} \times k^{i - j - 1}\);否则方案数为 \(k^{i - j}\)。
那么总方案为:
\[\sum_{j = 0}^{i - 1} x_{j + 1}\times k^{i - j - 1} + \sum_{j = 1}^i k^{i - j} = a \]上述构造最坏情况下(\(i = 5,\ x_j = k - 1\))有长度 \(9k\)。
满足 \(56789a \le 10^{13}\land \sum_{i = 0}^5 k^i > a\) 的最小 \(k\) 为 \(45\);满足 \(b < 56789\land \sum_{i = 0}^5 k^i > b\) 的最小 \(k\) 为 \(9\)。
\(9 \times (45 + 9) < 500\),满足限制。
哪些数一定存在一组非负整数解 \((a, b)\) 呢?
考虑 \(56789k \equiv i \pmod {1234}\),对于每个 \(i\) 求出最小 \(k\),所有与 \(i\) 同余的数都能在这基础上累加 \(1234\) 得到。
即 \(c \ge 56788 k_i\) 一定有解。
\(k\) 有最大值 \(1233\),因此 \(c \ge 700208374\) 一定能用上述方式构造。
否则令 \(c = 789a + 256b\),满足两数互质。
沿用类似的方式,可以每部分构造出上界为 \(4k\) 的序列。
满足 \(789a \le 700208374\land \sum_{i = 0}^3 k^i > a\) 的最小 \(k\) 为 \(96\);满足 \(b < 789\land \sum_{i = 0}^3 k^i > b\) 的最小 \(k\) 为 \(9\)。
最坏长度 \(4 \times(96 + 9) < 500\),满足限制。
同理对于 \(c\ge 201195\) 都能找到 \((a, b)\)。
令 \(c = 347a + 012b\),对应 \(k\) 为 \(8\) 和 \(7\),管辖 \(c \ge 3817\) 的范围。
构造序列 \(9^{\lfloor \frac{c}{9}\rfloor} + (c \bmod 9)\),长度不大于 \(425\)。