C2Ladder之旅-1300

4FGR2025-12-152026-06-09

C2Ladder之旅-1300

1

You are given an array $a$ of $n$ integers. Find the number of pairs $(i, j)$ ($1 \le i < j \le n$) where the sum of $a_i + a_j$ is greater than or equal to $l$ and less than or equal to $r$ (that is, $l \le a_i + a_j \le r$).

For example, if $n = 3$, $a = [5, 1, 2]$, $l = 4$ and $r = 7$, then two pairs are suitable:

$i=1$ and $j=2$ ($4 \le 5 + 1 \le 7$);
$i=1$ and $j=3$ ($4 \le 5 + 2 \le 7$).

原 Tutorial 的解法是排序后二分查找，本人的做法是排序后用三指针，设置三指针 $i,j,k$ ，意表示有效的 $(i,x)$ ，其中 $x \in(k,j]$ ， $j$ 表示 $a_i+a_j \leq r$ 的最大编号 $(j>i)$，$k$ 表示 $a_i+a_k<l$ 的最大编号 $(k\geq i)$ ，显然，这样的 $x$ 共有 $j-k$ 个，当 $j<k$ 时显然应该退出，但不能在 $j=k$ 时退出。注意到，可能存在找到的 $j$ 有 $a_i+a_j< l \leq r$ ，这种情况下，$j=k$ 但后续是可能有解的，不应该提前退出。

显然随着 $i$ 增加，$a_i$ 也增加，对于原先的 $j,k$ ， $a_{i'}+a_{j/k}$ 显然更大，因此，$j$ 和 $k$ 都可能右移。注意到，可能 $k$ 会出现比 $i'$ 小的情况，此时相当于转化为了双指针（肯定满足 $a_i+a_j \geq l$ ，$j>i$ ），应该让 $k=i'$ 。

2

Coin Rows

Alice and Bob are playing a game on a matrix, consisting of $2$ rows and $m$ columns. The cell in the $i$\-th row in the $j$\-th column contains $a_{i, j}$ coins in it.

Initially, both Alice and Bob are standing in a cell $(1, 1)$. They are going to perform a sequence of moves to reach a cell $(2, m)$.

The possible moves are:

Move right — from some cell $(x, y)$ to $(x, y + 1)$;
Move down — from some cell $(x, y)$ to $(x + 1, y)$.

First, Alice makes all her moves until she reaches $(2, m)$. She collects the coins in all cells she visit (including the starting cell).

When Alice finishes, Bob starts his journey. He also performs the moves to reach $(2, m)$ and collects the coins in all cells that he visited, but Alice didn’t.

The score of the game is the total number of coins Bob collects.

Alice wants to minimize the score. Bob wants to maximize the score. What will the score of the game be if both players play optimally?

哎哟我去，这个爱丽丝怎么这么坏？

问题的关键在于，在这个宽 $2$ ，长 $m$ 的格子中，二人只能向右或者向下走。不难发现，爱丽丝一旦往下走，就不能往上走，也不能往左走。那么，以这个列 $i$ 为 $y$ 轴，两行之间为 $x$ 轴，爱丽丝捡了 $y$ 轴、第一象限、第四象限的硬币，由于行走限制，Bob 要么捡第二象限的硬币，要么捡第三象限的硬币。Bob 一定选择硬币价值最大的那个象限，捡到： \[ \max(\sum\limits_{i+1}^m a_{(1,j)}+\sum\limits_{1}^{i-1}a_{(2,j)}) \] 既然 Alice 想让 Bob 找到的硬币价值最小，就是找到这么一个当她向下走的列 $i$ 使得这个最大值最小。

代码层面上，不妨初始化 $t1$ 为行 $1$ 的硬币总价值，$t2$ 为 $0$ ，然后如此迭代

1
2
3

t1 -= a[0][i]; //得到行1的[i+1,m]
t2 += a[1][i-1]; //得到行2的[1,i-1]
ans = min(ans,max(t1,t2));

3

Nastia and a Good Array

*Nastia has received an array of $n$ positive integers as a gift.*

She calls such an array $a$ good that for all $i$ ($2 \le i \le n$) takes place $\gcd(a_{i - 1}, a_{i}) = 1$, where $\gcd(u, v)$ denotes the greatest common divisor (GCD) of integers $u$ and $v$.

You can perform the operation: select two different indices $i, j$ ($1 \le i, j \le n$, $i \neq j$) and two integers $x, y$ ($1 \le x, y \le 2 \cdot 10^9$) so that $\min{(a_i, a_j)} = \min{(x, y)}$. Then change $a_i$ to $x$ and $a_j$ to $y$.

The girl asks you to make the array good using at most $n$ operations.

It can be proven that this is always possible.

Output:

For each of t test cases print a single integer k (0≤k≤n) — the number of operations. You don’t need to minimize this number.

什么？！，题目居然不要求有最优解，那 4FGR 是时候搞魔法了！

显然，数值相差 $1$ 的数一定互质，贪心地，从 $i=2$ 开始，我们每次只考虑设法让 $a_i$ 和 $a_{i-1}$ 互质，那么：

如果 $a_i \geq a_{i-1}$ ，$a_{i-1}$ 是最小值， $(a_{i-1},a_i)$ 变为 $(a_{i-1},a_{i-1}+1)$ 。
如果 $a_i < a_{i-1}$ ，我们不想思考改变 $a_{i-1}$ （这会影响 $a_{i-2}$ 和 $a_{i-1}$ 的公约数关系），考虑把值推给 $a_{i+1}$ ，让 $a_{i+1}$ 为 $\min(a_i,a_{i+1})$ ，$a_i$ 为 $a_{i-1}+1$ 。

特别的，如果 $i$ 到了最后一位，如果陷入了第二种情况，我们要让 $a_{i-1}$ 和 $a_{i-2}$ 、$a_i$ 都互质。简单的想法是，只要让 $a_{i-1}$ 是足够大的质数即可，$a_i$ 不变。笔者写的是 $10^9+7$ ，虽然通过了，但从数据上看可能 wa ，最好是大于 $10^9 +10^5$ 的素数。

显然，操作次数是 $n-1$ 次，满足要求。

4

D. Array and Operations

You are given an array $a$ of $n$ integers, and another integer $k$ such that $2k \le n$.

You have to perform exactly $k$ operations with this array. In one operation, you have to choose two elements of the array (let them be $a_i$ and $a_j$; they can be equal or different, but their positions in the array must not be the same), remove them from the array, and add $\lfloor \frac{a_i}{a_j} \rfloor$ to your score, where $\lfloor \frac{x}{y} \rfloor$ is the maximum integer not exceeding $\frac{x}{y}$.

Initially, your score is $0$. After you perform exactly $k$ operations, you add all the remaining elements of the array to the score.

Calculate the minimum possible score you can get.

注意，我们要求最小值，一个很自然的想法就是让大的数 “自相残杀” ，保留小的数。注意到，$\lfloor \frac{x}{y} \rfloor = 0 \, ,y>x$ 。但有时会出现相等情况。无论无何，首先降序排序，然后为尽量避免相等情况，我们让 $\lfloor \frac{a_{i+k} }{a_i}\rfloor$ 。如果这样也能产生 $1$ 的贡献，那么这个贡献是必须的（有一半以上相等的数）。

5

Make a Power of Two

You are given an integer $n$. In $1$ move, you can do one of the following actions:

erase any digit of the number (it’s acceptable that the number before the operation has exactly one digit and after the operation, it is “empty”);
add one digit to the right.

The actions may be performed in any order any number of times.

Note that if, after deleting some digit from a number, it will contain leading zeroes, they will not be deleted. E.g. if you delete from the number $301$ the digit $3$, the result is the number $01$ (not $1$).

You need to perform the minimum number of actions to make the number any power of $2$ (i.e. there’s an integer $k$ ($k \ge 0$) such that the resulting number is equal to $2^k$). The resulting number must not have leading zeroes.

E.g. consider $n=1052$. The answer is equal to $2$. First, let’s add to the right one digit $4$ (the result will be $10524$). Then let’s erase the digit $5$, so the result will be $1024$ which is a power of $2$.

E.g. consider $n=8888$. The answer is equal to $3$. Let’s erase any of the digits $8$ three times. The result will be $8$ which is a power of $2$.

设数 $s$ ，其 $|s|$ 为其十进制长度。

如果全删，操作数应该为 $|n|$ + $|2^k|$ ，显然至少的操作数最多为 $|n|+1$ 次。

如果保留 $a$ 个，就节省了 $2a$ 次操作（删与增）

至于，保留顺序应该从双方的最高位开始，例如 $23$ 想变成 $32$ ，必须删去最高位 $2$ 。

如果 $n$ 可全部保留，这么一个比他大的二进制数 $k$ 其 $|k|\leq|n|+1$ ，否则其不会对答案有贡献。也可以直接取 ll 范围内的大值。

6

Not Seitting

Rahul and Tina are looking forward to starting their new year at college. As they enter their new classroom, they observe the seats of students are arranged in a $n \times m$ grid. The seat in row $r$ and column $c$ is denoted by $(r, c)$, and the distance between two seats $(a,b)$ and $(c,d)$ is $|a-c| + |b-d|$.

As the class president, Tina has access to exactly $k$ buckets of pink paint. The following process occurs.

First, Tina chooses exactly $k$ seats in the classroom to paint with pink paint. One bucket of paint can paint exactly one seat.
After Tina has painted $k$ seats in the previous step, Rahul chooses where he sits. He will not choose a seat that has been painted pink due to his hatred of the colour pink.
After Rahul has chosen his seat, Tina chooses a seat for herself. She can choose any of the seats, painted or not, other than the one chosen by Rahul.

Rahul wants to choose a seat such that he sits as close to Tina as possible. However, Tina wants to sit as far away from Rahul as possible due to some complicated relationship history that we couldn’t fit into the statement!

Now, Rahul wonders for $k = 0, 1, \dots, n \cdot m - 1$, if Tina has $k$ buckets of paint, how close can Rahul sit to Tina, if both Rahul and Tina are aware of each other’s intentions and they both act as strategically as possible? Please help satisfy Rahul’s curiosity!

注意 $n\times m$ 的数据不大。

Rahul 知道 Tina 知道他想离 Tina 的座位更近，那么 $k=0$ 的情况下，Rahul 显然选择最中间的位置，使得 Tina 即便在四个角落也使得距离更近。事实是，Tina 的最优选择一定会是在某个角落的位置（这很容易证明），那么，只要找出每个格子离四个角落的最大距离，并且按照升序排列并输出即可。

7

And It's Non-Zero

You are given an array consisting of all integers from $[l, r]$ inclusive. For example, if $l = 2$ and $r = 5$, the array would be $[2, 3, 4, 5]$. What’s the minimum number of elements you can delete to make the bitwise AND of the array non-zero?

A bitwise AND is a binary operation that takes two equal-length binary representations and performs the AND operation on each pair of the corresponding bits.

显然，关键在于得知 $[l,r]$ 区间内的第几位 $1$ 的个数最多，只要保留这些在该位有 $1$ 的数，用区间总数减去该个数就能得到最小的删除个数。

显然，直接处理 $[l,r]$ 区间的每个位置 $1$ 的个数是会超时的，我们利用前缀和的思想，预处理前 $i$ 个数其二进制位的 $1$ 的数量，这样预处理时间复杂度是 $O(n\log n)$ ，而对每次查询的时间复杂度来到了 $O(\log n)$ 。

8

D. Co-growing Sequence

A sequence of non-negative integers $a_1, a_2, \dots, a_n$ is called growing if for all $i$ from $1$ to $n - 1$ all ones (of binary representation) in $a_i$ are in the places of ones (of binary representation) in $a_{i + 1}$ (in other words, $a_i \:\&\: a_{i + 1} = a_i$, where $\&$ denotes bitwise AND). If $n = 1$ then the sequence is considered growing as well.

For example, the following four sequences are growing:

$[2, 3, 15, 175]$ — in binary it’s $[10_2, 11_2, 1111_2, 10101111_2]$;
$[5]$ — in binary it’s $[101_2]$;
$[1, 3, 7, 15]$ — in binary it’s $[1_2, 11_2, 111_2, 1111_2]$;
$[0, 0, 0]$ — in binary it’s $[0_2, 0_2, 0_2]$.

The following three sequences are non-growing:

$[3, 4, 5]$ — in binary it’s $[11_2, 100_2, 101_2]$;
$[5, 4, 3]$ — in binary it’s $[101_2, 100_2, 011_2]$;
$[1, 2, 4, 8]$ — in binary it’s $[0001_2, 0010_2, 0100_2, 1000_2]$.

Consider two sequences of non-negative integers $x_1, x_2, \dots, x_n$ and $y_1, y_2, \dots, y_n$. Let’s call this pair of sequences co-growing if the sequence $x_1 \oplus y_1, x_2 \oplus y_2, \dots, x_n \oplus y_n$ is growing where $\oplus$ denotes bitwise XOR.

You are given a sequence of integers $x_1, x_2, \dots, x_n$. Find the lexicographically minimal sequence $y_1, y_2, \dots, y_n$ such that sequences $x_i$ and $y_i$ are co-growing.

The sequence $a_1, a_2, \dots, a_n$ is lexicographically smaller than the sequence $b_1, b_2, \dots, b_n$ if there exists $1 \le k \le n$ such that $a_i = b_i$ for any $1 \le i \lt k$ but $a_k \lt b_k$.

显然，为了使字典序最低，第一个 $y_0$ 肯定是 $0$ ，那么使 $x_{i+1}\oplus y_{i+1}=x_{i}\oplus y_i$ ，对于 $y_{i+1}$ ，其最小的值应该是什么呢？

注意异或性质，我们设 $c=x_{i}\oplus y_i$ ，有 $c'$ 满足 $c\&c'=c$，则 $y_{i+1} =x_{i+1}\oplus c'$ 中，$c'=c$ 总能使得序列是 growing ，但这并不是最小的，由于我们想让 $c'\&c=c$ ，只要让 $c$ 二进制位的 $1$ 在 $c'$ 有即可，由于非 $1$ 的地方需要异或 $1$ ，会使 $c'$ 增大，因此仅需要最低限度的让 $c'$ 有 $1$ ，这显然以 $x_i$ 为基础，如果二进制对应的为 $0$ ，显然 $y_i$ 此二进制位为 $1$ .

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5+10;
int x[N],y[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i=0;i<n;i++) cin >> x[i];
        y[0] = 0;
        for(int i=1;i<n;i++){
            y[i] = 0;
            int c = x[i-1]^y[i-1];
            if((c&x[i])==c) continue;
            else{
                for(int j=1;j<=c;j<<=1){
                    if((c&j)&&!(x[i]&j)){
                        y[i] |= j;
                    }
                }
            }
        }
        for(int i=0;i<n;i++){
            cout << y[i] << " "; 
        }
        cout << '\n';
    }
}

9

B. Two Tables

You have an axis-aligned rectangle room with width $W$ and height $H$, so the lower left corner is in point $(0, 0)$ and the upper right corner is in $(W, H)$.

There is a rectangular table standing in this room. The sides of the table are parallel to the walls, the lower left corner is in $(x_1, y_1)$, and the upper right corner in $(x_2, y_2)$.

You want to place another rectangular table in this room with width $w$ and height $h$ with the width of the table parallel to the width of the room.

The problem is that sometimes there is not enough space to place the second table without intersecting with the first one (there are no problems with tables touching, though).

You can’t rotate any of the tables, but you can move the first table inside the room.

Example of how you may move the first table.

What is the minimum distance you should move the first table to free enough space for the second one?

对于这个问题，我们的做法是贪心的，桌子 $t_1$ 要么横向移动，要么竖向移动。$t_1$ 与 $t_2$ 有重叠，说明 $t1$ 至少有一个顶点在 $t2$ 内，单从顶点来看，他想要逃离的最短距离就是往 $t2$ 的水平线（长）或垂直线（高）做垂线的两个垂线段中取最短的。于是问题变成了，横向挪动 $t_1$ ，使得最大空余长 $\max(W-x2,x)$ 大于 $w$ ，竖向挪动也是同理。但显然，由于有 $W$ 和 $H$ 的设置，可能会发生无法横向（竖向）移动的情况（$w>W-(x2-x)$），需要另外判断。

10

Paprika and Permutation

Paprika loves permutations. She has an array $a_1, a_2, \dots, a_n$. She wants to make the array a **permutation** of integers $1$ to $n$.

In order to achieve this goal, she can perform operations on the array. In each operation she can choose two integers $i$ ($1 \le i \le n$) and $x$ ($x \gt 0$), then perform $a_i := a_i \bmod x$ (that is, replace $a_i$ by the remainder of $a_i$ divided by $x$). In different operations, the chosen $i$ and $x$ can be different.

Determine the minimum number of operations needed to make the array a permutation of integers $1$ to $n$. If it is impossible, output $-1$.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

显然，当对于一个数 $k$ ，我们希望通过模运算变成 $t$ 的话，如果可能，那么最优的一个操作是 $k:=k \mod x$ 中，$x=k-t$ ，但是，虽然 $k = t \pmod{k-t}$ 成立， $t$ 却可能大于模数 $k-t$ 而不在模数范围内（这也是为什么我们希望 $x$ 尽可能大），也就是说，若 $k\leq 2t$ ，则我们应当不做操作（特殊情况， $k=t$ 时，显然不用操作，但完成目的）。

我们希望让数组 $a$ 变成一个全排列，那么，如果 $a$ 中元素 $a_i$ 本就是全排列的一个元素，我们应当保留一个值为这个元素的元素（为了节省操作次数），我们能证明如果需要改变这个元素为 $k$ ，也能有全排列成立的话，保留这个元素，全排列仍成立，因为： \[ 2k<a\leq p \\ 其中, p 是利用操作变成 a 的那个数或者是值为a_i的另一个元素(保证排列成立) \\ 则一定存在模数 x ，使得\\ p\mod x = k \] 之后，就是补全剩余全排列中的元素，由于大的数通过操作能变的范围更大，我们需要进行升序排序，尽可能让数组中的小元素为或者变为全排列中的最小需满足元素 $cnt$ ，操控指针 $cnt$ 增加，利用哈希数组判断 $a_i$ 是否存在，在结束后，若 $cnt\leq n$ 说明失败，否则成功。