Codeforces Round 1075 (Div. 2)

原题链接

B. 青蛙的诅咒

每次测试的时间限制：1 秒

每次测试的内存限制：256 兆字节

在一条无限数轴上，点 $0$ 处坐着一只青蛙。经过多年的冥想，青蛙掌握了 $n$ 种独特类型的魔法跳跃。第 $i$ 种跳跃允许它向前跳跃不超过 $a_i$ 个单位。换句话说，如果它在整数点 $k$，跳跃后它可以落在从 $k$ 到 $k + a_i$ 的任意整数点。

但是魔法总是有代价的；它被诅咒了。在第 $i$ 种跳跃的每第 $b_i$ 次尝试之前（即在使用第 $i$ 种跳跃的第 $b_i$ 次、第 $2b_i$ 次、第 $3b_i$ 次等尝试中），青蛙会向后退 $c_i$ 个单位！换句话说，如果它在点 $k$，它首先会发现自己在点 $k - c_i$，跳跃之后，它可以落在从 $k - c_i$ 到 $k - c_i + a_i$ 的任意整数点。

青蛙的目标是到达数字为 $x$ 的点，同时使用跳跃并使回滚次数最少。帮助青蛙 —— 找到它在通往目标的路上必须忍受的最小回滚次数，或者确定它无法到达点 $x$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。测试用例的描述如下。

每个测试用例的第一行包含 2 个整数 $n$ 和 $x$ ($1 \le n \le 10^5, 1 \le x \le 10^{18}$) —— 青蛙可以进行的跳跃类型的数量及其最终目标。

接下来的 $n$ 行提供了跳跃类型的描述；第 $i$ 行包含 3 个整数 $a_i, b_i,$ 和 $c_i$ ($1 \le a_i, b_i, c_i \le 10^6$)。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出

对于每个测试用例，如果青蛙能到达点 $x$，找出它必须忍受的最小回滚次数。如果它不能到达点 $x$，输出 $-1$。

示例

input (输入)

6
1 1
3 3 3
1 7
4 2 5
2 4
1 2 3
2 2 4
5 8
12 1 11
10 1 4
1 1 3
1 2 5
2 1 7
1 1000000000000000000
1000000 4 654321
1 10
2 2 1

output (输出)

0
1
-1
2
298892990032
3

---

注

在第一个测试用例中，青蛙可以向前跳跃 $1$ 个单位并将在点 $1$ 结束。因此，答案是 $0$。

在第三个测试用例中，可以证明青蛙无法到达点 $4$。

在第四个测试用例中，青蛙可以到达点 $8$，例如，如下所示：使用第 $1$ 种类型跳跃 $12$，使用第 $4$ 种类型跳跃 $1$，使用第 $2$ 种类型跳跃 $10$。那么它将依次位于以下点 $0 \to (\textbf{rollback}) -11 \to 1 \to 2 \to (\textbf{rollback}) -2 \to 8$。

在第六个测试用例中，青蛙可以到达点 $10$，例如，如下所示：跳跃 $6$ 次使用类型 $2$ 和 $1$ 次使用类型 $1$。那么它将依次位于以下点 $0 \to 2 \to (\textbf{rollback})1 \to 3 \to 5 \to (\textbf{rollback})4 \to 6 \to 8 \to (\textbf{rollback})7 \to 9 \to 10$。

题面解读

题目链接

一只在数轴 $0$ 点的青蛙。跳到坐标 $\ge x$ 的位置。求最小的回滚次数。

解题思路

首先贪心的利用所有青蛙的安全跳跃距离$$\ \sum_{i=1}^{n} a_i \times (b_i - 1)$$如果这个总和 $\ge x$，那么回滚次数就是 0。

如果所有安全距离总和还不够，就必须开始回滚。贪心的挑选每次回滚距离最大的魔法$\max(-c_i + a_i + a_i(b_i - 1))$那么，需要回滚的次数就是$\lceil \frac{\text{还需要跳的距离}}{\text{最大回滚距离}} \rceil$。

题解代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
typedef long long ls;
int t;

ls cal(ls a, ls b, ls c){
	return (b-1)*a+a-c;
}

void solve(){
	ls n, x;
	ls a, b, c;
	ls maxn = -2e18;
	cin >> n >> x;
	ls sum = 0;
	for (int i = 1; i <= n; i++){
		cin >> a >> b >> c;
		sum += (b-1) * a;
		if (cal(a,b,c) > maxn)
			maxn = cal(a, b, c);
	}
	if (sum >= x){
		cout << 0 << endl;
		return;
	}
	if (maxn <= 0){
		cout << -1 << endl;
		return;
	}
	cout << (x - sum + maxn - 1) / maxn << endl;
}

int main(){
	cin >> t;
	while (t--)	solve();
}

注：算法竞赛中向上取整ceil(a,b)更喜欢用(a + b - 1) / b来代替

C1. 异或便利 (简单版)

每次测试的时间限制：2 秒

每次测试的内存限制：256 兆字节

这是问题的简单版本。两个版本之间的区别在于，在此版本中，$2 \le i \le n - 1$。请注意，困难版本的正确解决方案不一定是简单版本的正确解决方案。

给定一个自然数 $n$。找到一个长度为 $n$ 的排列* $p$，使得对于每个 $i$ ($2 \le i \le n - 1$)，存在一个 $j$ ($i \le j \le n$) 满足 $p_i = p_j \oplus i$ $^{\dagger}$。

可以证明，在问题的约束下，至少存在一个合适的排列 $p$。

---

* 长度为 $n$ 的排列是一个包含从 $1$ 到 $n$ 的 $n$ 个不同整数的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列 ($2$ 在数组中出现两次)，$[1,3,4]$ 也不是一个排列 ($n=3$ 但数组中有 $4$)。

$\dagger \oplus$ 表示按位异或运算。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。测试用例的描述如下。

每个测试用例的唯一一行包含一个整数 $n$ ($3 \le n \le 2 \cdot 10^5$) —— 排列的长度。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出 $n$ 个整数 $p_1, p_2, \dots, p_n$ —— 即排列 $p$。

如果有多个解决方案，您可以输出其中任何一个。

示例

input (输入)

2
3
6

output (输出)

2 1 3
3 6 2 5 1 4

---

注

在第一个测试用例中，排列 $p = [2, 1, 3]$ 是合适的，因为 $p_2 = 1$ 且 $p_3 \oplus 2 = 1$。

在第二个测试用例中，排列 $p = [3, 6, 2, 5, 1, 4]$ 是合适的，因为：

• $p_2 = 6 = 4 \oplus 2 = p_6 \oplus 2$
• $p_3 = 2 = 1 \oplus 3 = p_5 \oplus 3$
• $p_4 = 5 = 1 \oplus 4 = p_5 \oplus 4$
• $p_5 = 1 = 4 \oplus 5 = p_6 \oplus 5$

题面解读

题目链接

构造一个长度为 $n$ 的排列 $p$（包含 $1$ 到 $n$ 不重复）。

对于中间的每一个位置 $i$ ($2 \le i \le n-1$)，必须在它右边（下标 $j \ge i$）找到一个搭档 $p_j$，满足：

$$p_i = p_j \oplus i \quad \iff \quad p_i \oplus p_j = i$$

解题思路

为了让回滚次数最少，逻辑非常直观：先把免费的用完，不够再付费。

假设我们把 $1$ 放在非常靠后的位置，比如 $p_{n} = 1$。 那么对于前面的所有 $i$（$2 \le i \le n-1$），我们只需要让 $p_i \oplus p_{n} = i$，即 $p_i \oplus 1 = i$。 这推导出：$p_i = i \oplus 1$。填完了 $p_2$ 到 $p_n$，剩下的那个没用过的数字就是 $p_1$，可以根据奇偶性来求出。

性质1： $A = B \oplus C \iff A \oplus B = C$

性质2：$x \oplus 1$ 的作用是翻转 $x$​ 二进制的最后一位。它的作用不是随机改变数字，而是成对交换相邻的偶数和奇数。

$2 \leftrightarrow 3$ （$2 \oplus 1 = 3$, $3 \oplus 1 = 2$）

$4 \leftrightarrow 5$

$6 \leftrightarrow 7$

…

$2k \leftrightarrow 2k+1$

题解代码

理解后代码其实非常好写

#include <bits/stdc++.h>
using namespace std;

int t;

void solve(){
	int n; cin >> n;
	vector<int> a(n+1);
	a[n] = 1;
	for (int i = 2; i <= n - 1; i++)
		a[i] = i ^ 1;
	a[1] = n % 2 == 1 ? n - 1 : n;
	for (int i = 1; i <= n; i++)
		cout << a[i] << ' ';
	cout << endl;
}

int main(){
	cin >> t;
	while (t--)	solve();
}

注：官方题解把1放在$p_{n-1}$其实是一种习惯，同时也方便下面一道困难题题解。