C2Ladder之旅-1200

4FGR2025-12-042026-06-08

C2Ladder之旅-1200

1

You are given an array $a$ of $n$ integers. Count the number of pairs of indices $(i, j)$ such that $i < j$ and $a_j - a_i = j - i$.

注意到， $a_j-a_i=j-i \Rightarrow a_j-j = a_i-i$ ，用哈希记录值为 $a_i-i$ 的个数 $n_i$ ，假设共有 $m$ 组，则有： \[ ans = \sum\limits_{i=1}^m C_{n_i}^2 \]

2

Challenging Cliffs

You are a game designer and want to make an obstacle course. The player will walk from left to right. You have $n$ heights of mountains already selected and want to arrange them so that the absolute difference of the heights of the first and last mountains is as small as possible.

In addition, you want to make the game difficult, and since walking uphill or flat is harder than walking downhill, the difficulty of the level will be the number of mountains $i$ ($1 \leq i < n$) such that $h_i \leq h_{i+1}$ where $h_i$ is the height of the $i$-th mountain. You don’t want to waste any of the mountains you modelled, so you have to use all of them.

From all the arrangements that minimize $|h_1-h_n|$, find one that is the most difficult. If there are multiple orders that satisfy these requirements, you may find any.

显然，得先找到峰距最小的两座峰 $l,r$（若有多组，它们的高度也应该是最小的），小的放第一位，大的放第二位。想要让 difficulty 最大，就要尽量爬山，那么凡是高度大于峰 $r$ 先升序放，最后高度小于峰$l$ 再升序放。显然，一开始就升序排序，能轻松解决上述两个子问题。

3

Pleasant Pairs

You are given an array $a_1, a_2, \dots, a_n$ consisting of $n$ distinct integers. Count the number of pairs of indices $(i, j)$ such that $i < j$ and $a_i \cdot a_j = i + j$.

和 $1$ Same Differences 很像，但这道题是暴力，注意到对于 $x\times y \leq 2n$ ，对于正整数 $x$ ，可能的 $y$ 应该有多少种呢？应该为 $\frac{2n}{x}$ 种，由于元素互不相同，对于一组元素，最坏情况有 $\frac{2n}{1}+\frac{2n}{2}+\cdots+\frac{2n}{n}=2n*(1+\frac{1}{2}+\cdots+\frac{1}{n})$ ，由于调和级数 $\sum \frac{1}{n}$ 可近似为 $\ln n$ ，因此这个暴力也就 $O(nlogn)$ ，即每次直接找 $1\cdots \lfloor\frac{2n}{x} \rfloor$ 的数是否存在并且下标 $j>i$ 且满足题干条件。也可以排完序（其中一维存原始下标）后在 $a_i\times a_j\leq 2n$ ，暴力搜满足 $a_{i.v}\times a_{j.v} == a_{i.p}+a_{j.p}$ 的个数。

4

Palindrome Game (easy version)

A palindrome is a string that reads the same left to right and right to left. For example, “101101” is a palindrome, while “0101” is not.

Alice and Bob are playing a game on a string $s$ (which is initially a palindrome in this version) of length $n$ consisting of the characters ‘0’ and ‘1’. Both players take alternate turns with Alice going first.

In each turn, the player can perform one of the following operations:

Choose any $i$ ($1 \le i \le n$), where $s[i] =$ ‘0’ and change $s[i]$ to ‘1’. Pay 1 dollar.
Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse. That is, if Alice reverses the string, then Bob can’t reverse in the next move, and vice versa.

Reversing a string means reordering its letters from the last to the first. For example, “01001” becomes “10010” after reversing.

The game ends when every character of string becomes ‘1’. The player who spends minimum dollars till this point wins the game and it is a draw if both spend equal dollars. If both players play optimally, output whether Alice wins, Bob wins, or if it is a draw.

没有平局存在。

Alice唯一的赢面，当且仅当在 $0$ 的个数非 $1$ 的情况下，$s$ 的长度 $|s|$ 为奇数，且最中心位置上为 $0$ ，使得 Bob 不能之后进行反转操作（直至胜利，Alice总能使得字符串非回文）。

否则，由于 $s$ 初始为回文串，Alice 不得不执行操作 $1$，随后 Bob 只要在对应方放置，使得 $s$ 仍为回文串，Alice 就不得不一直执行操作 $1$ ，而 Bob 总能找到恰当的时机反转，比如当轮到 Bob 操作时，若 $0$ 的个数为 $1$ ，就反转。此时，轮到 Bob 操作时，$0$ 的个数不可能为偶数，否则说明一开始有奇数个 $0$ 。由于对称性，$0$ 只能在中间，为上述情况。

5

Stable Groups

There are $n$ students numerated from $1$ to $n$. The level of the $i$-th student is $a_i$. You need to split the students into stable groups. A group of students is called stable, if in the sorted array of their levels no two neighboring elements differ by more than $x$.

For example, if $x = 4$, then the group with levels $[1, 10, 8, 4, 4]$ is stable (because $4 - 1 \le x$, $4 - 4 \le x$, $8 - 4 \le x$, $10 - 8 \le x$), while the group with levels $[2, 10, 10, 7]$ is not stable ($7 - 2 = 5 > x$).

Apart from the $n$ given students, teachers can invite at most $k$ additional students with arbitrary levels (at teachers’ choice). Find the minimum number of stable groups teachers can form from all students (including the newly invited).

For example, if there are two students with levels $1$ and $5$; $x = 2$; and $k \ge 1$, then you can invite a new student with level $3$ and put all the students in one stable group.

显然，先排序，保证每对相邻元素的间距为原排列最小。若每个间距大于 $x$ 就不得不为 ans 贡献 $1$ ，用 $map$ 记录若填充这个间距需要的最少人员数 $t$ ，可证明 $t$ 为间距差 $\lfloor \frac{d-1}{x} \rfloor$ 。最后因此遍历 $map$ ，在 $k$ 充足的情况下优先补足小间距，直至 $k$ 用尽或遍历结束。

由于对于间距 $d$ ，邀请 $k$ 个学生，能产生 $k+1$ 个间隔，每个间隔最大为 $x$ ，因此 $d\leq (k+1)\times x$ ,因此 $k = \lceil \frac{d}{x} \rceil -1$ ，考虑精度问题，$\lceil \frac{a}{b} \rceil$ 等价于 $\lfloor \frac{a + b - 1}{b}\rfloor$ ，用整数运算转换为 $k = \lfloor \frac{d-1}{x} \rfloor$

6

Mocha and Hiking

The city where Mocha lives in is called Zhijiang. There are $n+1$ villages and $2n-1$ directed roads in this city.

There are two kinds of roads:

$n-1$ roads are from village $i$ to village $i+1$, for all $1\leq i \leq n-1$.
$n$ roads can be described by a sequence $a_1,\ldots,a_n$. If $a_i=0$, the $i$-th of these roads goes from village $i$ to village $n+1$, otherwise it goes from village $n+1$ to village $i$, for all $1\leq i\leq n$.

Mocha plans to go hiking with Taki this weekend. To avoid the trip being boring, they plan to go through every village exactly once. They can start and finish at any villages. Can you help them to draw up a plan?

很简单，想要判断是否仅一次遍历完所有村庄，只用判断三个条件:

$1$ 号村庄能被 $n+1$ 号村庄到达（存在路 $a[0]=1$ ）
$n$ 号村庄能到达 $n+1$ 号村庄
存在相邻的村庄 $i、i+1$ ，前者能到 $n+1$ ，而 $n+1$ 号村庄能到 $i+1$

若任一条件成立，根据条件输出即可。否则，输出 $-1$ 。

7

Penalty

Consider a simplified penalty phase at the end of a football match.

A penalty phase consists of at most $10$ kicks, the first team takes the first kick, the second team takes the second kick, then the first team takes the third kick, and so on. The team that scores more goals wins; if both teams score the same number of goals, the game results in a tie (note that it goes against the usual football rules). The penalty phase is stopped if one team has scored more goals than the other team could reach with all of its remaining kicks. For example, if after the $7$-th kick the first team has scored $1$ goal, and the second team has scored $3$ goals, the penalty phase ends — the first team cannot reach $3$ goals.

You know which player will be taking each kick, so you have your predictions for each of the $10$ kicks. These predictions are represented by a string $s$ consisting of $10$ characters. Each character can either be 1, 0, or ?. This string represents your predictions in the following way:

if $s_i$ is 1, then the $i$-th kick will definitely score a goal;
if $s_i$ is 0, then the $i$-th kick definitely won’t score a goal;
if $s_i$ is ?, then the $i$-th kick could go either way.

Based on your predictions, you have to calculate the minimum possible number of kicks there can be in the penalty phase (that means, the earliest moment when the penalty phase is stopped, considering all possible ways it could go). Note that the referee doesn’t take into account any predictions when deciding to stop the penalty phase — you may know that some kick will/won’t be scored, but the referee doesn’t.

显然，？应该选择使得发球结束最快的情况：两队相比较的情况下，把之前的其中一队的？全部认作进球（要比两次）。考虑到当 $|s|$ 为奇数的情况下（实际上不会发生，$|s|=10$），两队的初始剩余比赛有差异，要分别记录。实现上可用大小为2的数组，$1$ 表示第一队，$0$ 表示第二队，这样设置，就可以用模运算得到当前队下标（比较的时候由于都要比较一遍，直接用 $0/1$ 即可）。

for(auto i: s){
    cnt++; //当前轮次
    int p = cnt%2;
    remain[p]--;
    if(i=='1')
    num[p]++; //当前进球
    else if(i=='?'){
        posi[p]++; //可能的进球次数
    }
    if(num[p^1]+remain[p^1]<num[p]+posi[p]||num[p]+remain[p]<num[p^1]+posi[p^1]){
        return cnt;
    }  
}

8

C1. k-LCM (easy version)

It is the easy version of the problem. The only difference is that in this version $k = 3$.

You are given a positive integer $n$. Find $k$ positive integers $a_1, a_2, \ldots, a_k$, such that:

$a_1 + a_2 + \ldots + a_k = n$
$LCM(a_1, a_2, \ldots, a_k) \le \frac{n}{2}$

Here $LCM$ is the least common multiple of numbers $a_1, a_2, \ldots, a_k$.

We can show that for given constraints the answer always exists.

由于原题只要求 $k=3$ ，显然 $n$ 为 3 的倍数时时直接就能整除了。事实上，还可以这样解。

如果是奇数，减 $1$ 肯定是偶数，$1$ 不影响其与别的数的最大公倍数，偶数肯定能分成两半，最大公倍数即此。
如果是偶数，如果不能被 $4$ 整除，也就是余数为 $2$ ，可取一个 $2$ ，剩下的数既然能被 $4$ 整除，那么其一半也是偶数，由于 $2$ 是所有偶数的约数，这个偶数就是最大公倍数。如果能被 $4$ 整除，那么可以分成两个四分之一和一个二分之一。

9

B. Prinzessin der Verurteilung

I, Fischl, Prinzessin der Verurteilung, descend upon this land by the call of fate an — Oh, you are also a traveler from another world? Very well, I grant you permission to travel with me.

It is no surprise Fischl speaks with a strange choice of words. However, this time, not even Oz, her raven friend, can interpret her expressions! Maybe you can help us understand what this young princess is saying?

You are given a string of $n$ lowercase Latin letters, the word that Fischl just spoke. You think that the MEX of this string may help you find the meaning behind this message. The MEX of the string is defined as the shortest string that doesn’t appear as a contiguous substring in the input. If multiple strings exist, the lexicographically smallest one is considered the MEX. Note that the empty substring does NOT count as a valid MEX.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

$a$ is a prefix of $b$, but $a \ne b$;
in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Find out what the MEX of the string is!

显然，我们可以预处理出字典序，由于 $n$ 至多为 $1000$ ，不难发现，子串长度小于 $3$ 的情况有 $n+n-1+n-2=3n-3$ 种，而长度小于 $3$ 的字母串有 $26+26^2+26^3$ 种，只要预处理出长度小于 $3$ 的情况，一一比较即可。

给出哈希值计算公式，其中 $t$ 为长度，$s[t]$ 为当前字母

\[ hash(t) = 26(hash(t-1)+1)+s[t]-'a' \]

例如：字母串 “aa” 为 \[ 26\times(0+1)+0=26 \] 可以理解为，一般进制都存在 $0$ ，但一般前导 $0$ 可以取出，但对于 “a” ，其位置为 $0$ ，但并不等价于 “aa” 。由此，当字母 $k$ 作为非 “个位数” 时，应当视作从 $1$ 出发，作为 “个位数” 时，视作从 $0$ 出发。