比赛链接
A
题意
给一个字符串 \(s\) ，对其加倍，即每个字符后面追加一个相同字符。
加倍后可以重排列，要求构造一个回文串。
题解
知识点：构造。
既然可以重排列了，那顺序是随意的了，直接翻转加在原来的后面。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
string s;
cin >> s;
cout << s;
reverse(s.begin(), s.end());
cout << s << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
题意
构造有 \(n\) 个数的序列 \(a(1\leq a_i \leq 10^9)\) ，满足：
\[a_1 \oplus a_2 \oplus \cdots \oplus a_n = \frac{1}{n} \sum_{i=1}^{n} a_i
\]
题解
知识点：构造。
方法一
\(n\) 为奇数，显然构造一样的 \(n\) 个数就行。
\(n\) 为偶数，仿造奇数情况，尝试在 \(n-1\) 个数 \(a\) 后加一个数 \(b\) ，于是我们只要找到满足 \(n(a \oplus b) = (n-1)a + b\) 的 \(a\) 和 \(b\) 即可。
假设 \(a>b\) ，根据需要满足的条件可以得到 \(a \oplus b < a\) ，因此我们需要用 \(b\) 通过异或缩小 \(a\) 。
我们假设 \(b\) 只会消去一些 \(a\) 的二进制位，而不会增加，那么 \(a \oplus b = a-b\) ，从而原方程变为 \(n(a-b) = (n-1)a + b\) ，解得 \(a = (n+1)b\) 。
我们取 \(b = 1\) ，那么 \(a = n+1\) ，刚好满足两条假设 \(a>b\) 和 \(a \oplus b = a-b\) ，因此是合法的。
方法二
- \(n\) 为奇数，构造 \(n\) 个 \(2\) 。
\(n\) 为偶数，构造 \(n-2\) 个 \(2\) ，随后 \(1\) 和 \(3\) 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码
方法一
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n - 1;i++) cout << n + 1 << ' ';
if (n & 1) cout << n + 1 << '\n';
else cout << 1 << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
方法二
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
if (n == 1) {
cout << 2 << '\n';
return true;
}
for (int i = 1;i <= n - 2;i++) cout << 2 << ' ';
if (n & 1) cout << 2 << ' ' << 2 << '\n';
else cout << 1 << ' ' << 3 << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
题意
给出 \(n,x\) ，构造一个长为 \(n\) 的排列 \(p\) ，满足 \(p_1 = x,p_n = 1\) ，且 \(p_i\) 是 \(i\) 的倍数，其中 \(2\leq i \leq n-1\) ，多个答案输出字典序最小的。
题解
方法一
知识点：构造，数论，质因子分解。
注意到 \(n \mod x \neq 0\) 时，一定不存在方案。因为 \(x\) 不是合法的位置，那么假设 \(n\) 放在任意合法的位置，那个位置的数一定会替换在他前面合法位置的数。但这些数一定是 \(n\) 的因子，那么一定不是 \(x\) 的倍数，替换到最后一定会有一个素数没地方放，因此无解。
如果有解，我们要让字典序最小。因为 \(x\) 空出来了，我们可以每次往前提最小的合法的数字，这样字典序最小。
我们可以分解 \(d = \frac {n}{x}\) 的质因子，得到 \(d = a_1^{k_1}a_2^{k_2}\cdots a_n^{k_n}\) ，每次让当前位置下标乘上目前最小质因子的数填到当前位置，即 $p_x = a_1x,p_{a_1x} = a_12x,\cdots,p_{a_1{k_1-1}} = a_1^{k_1}x, p_{a_1^{k_1}} = a_1{k_1}a_2x,\cdots,p_{a_1{k_1}a_2^{k_2}\cdots a_n^{k_n-1}} = dx = n $ 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(\sqrt n)\)
方法二
知识点：构造，数论。
\(n \mod x \neq 0\) 无解。
如果有解，我们先令排列 \(x,2,\cdots,x-1,n,x+1,\cdots,n-1,1\) ，然后把 \(n\) 往后移。设当前 \(p_{cur} = n\) ，如果一个位置 \(i\) 满足 $n \mod i = i \mod cur = 0 $ 那么可以把 \(p_i\) 和 \(p_{cur}\) 交换，这样就将小的数字往前提了。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
方法一
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n, x;
cin >> n >> x;
if (n % x) return false;
int d = n / x;
vector<int> ft;
for (int i = 2;i <= d / i;i++) {
while (d % i == 0) ft.push_back(i), d /= i;
}
if (d > 1) ft.push_back(d);
reverse(ft.begin(), ft.end());
cout << x << ' ';
int mul = 1;
for (int i = 2;i <= n - 1;i++) {
if (i == mul * x) cout << ((mul *= ft.back()) * x) << ' ', ft.pop_back();
else cout << i << ' ';
}
cout << 1 << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
方法二
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n, x;
cin >> n >> x;
if (n % x) return false;
vector<int> v(n + 1);
for (int i = 2;i <= n - 1;i++) v[i] = i;
v[1] = x;
v[x] = n;
v[n] = 1;
int cur = x;
for (int i = x + 1;i <= n - 1;i++) {
if (i % cur == 0 && n % i == 0) swap(v[cur], v[i]), cur = i;
}
for (int i = 1;i <= n;i++) cout << v[i] << ' ';
cout << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题意
构造含有 \(n\) 个数的序列 \(a(1\leq a_i\leq 10^9)\) ，满足：
\[\max(a_1,a_2,\cdots,a_n) - \min(a_1,a_2,\cdots,a_n) = \sqrt{\sum_{i=1}^n a_i}
\]
题解
知识点：构造。
\(n\) 为偶数时，容易构造等式结果为 \(n\) 的序列 \(n - \frac{n}{2},\cdots ,n-1,n+1,\cdots ,n - \frac{n}{2}\) 。
\(n\) 为奇数时，可以仿造 \(n\) 为偶数的操作，但发现构造等式结果为 \(n\) 的序列是不可能的，原因是数字之间的间隔太小，数字大小上没有操作空间，因此尝试构造等式结果为 \(2n\) 的序列。
同样对称操作，\(3n,3n+\lfloor \frac{2n}{n-1} \rfloor,\cdots ,3n+(\lfloor \frac{n}{2} \rfloor-1) \lfloor \frac{2n}{n-1} \rfloor, 4n,5n-(\lfloor \frac{n}{2} \rfloor-1) \lfloor \frac{2n}{n-1} \rfloor,\cdots ,5n-\lfloor \frac{2n}{n-1} \rfloor,5n\) 即可。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
if (n & 1) {
int d = 2 * n / (n - 1);
for (int i = 1;i <= n / 2;i++) cout << 3 * n + (i - 1) * d << ' ';
cout << 4 * n << ' ';
for (int i = n / 2;i >= 1;i--) cout << 5 * n - (i - 1) * d << ' ';
}
else {
for (int i = n - n / 2;i <= n + n / 2;i++) if (i != n) cout << i << ' ';
}
cout << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
