A（水题）
题目链接
⭐
题目：
给出 \(a,b,c\) 三个数，保证均为正数，其中 \(a\) 权值为1， \(b\) 权值为\(2\)， \(c\) 权值为3，将 \(a,b,c\) 分成两堆，两堆的权值和的差最小是多少
解析：
考虑取若干个 \(2\) ，则能取到 \([0,2b]\) 间所有的偶数，再加上若干个 \(1\) ，则能取到 \([0,a+2b]\) 所有数，对于 \([a+2b+1,a+2b+3c]\) ，可以由 \([0,a+2b]\) 中的某些数加若干个 \(3\) 获得，因此若 \(2\mid a+2b+3c\)，则一定可以得到 \(\frac{a+2b+3c}{2}\)，反之一定会有最小差 \(1\)
#include <bits/stdc++.h>
int main() {
int T;
int a, b, c;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &a, &b, &c);
printf("%d\n", (1ll * a + 2 * b + 3 * c) & 1);
}
}
B（组合数学）
题目链接
⭐
题目：
给出数组 \(a\)，且 \(\sum_{i=1}^na_i=s\) ，找出有多少个子集满足 \(\sum_{i\in subset}a_i=s-1\)
解析：
子集必须不包含集合中任意一个 \(1\)，且可以包含任意个\(0\)，所以答案即为\(cnt_1\times2^{cnt_0}\)
#include <bits/stdc++.h>
int main() {
int T;
int n, one, zero;
std::vector<int> a;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
a.assign(n, 0);
for (int i = 0;i < n;++i)
scanf("%d", &a[i]);
one = std::count_if(a.begin(), a.end(), [](int x) {return x == 1;});
zero = std::count_if(a.begin(), a.end(), [](int x) {return x == 0;});
printf("%lld\n", 1ll * one * (1ll << zero));
}
}
C（双指针+搜索）
题目链接
⭐
题目：
一个字符串，可以指定删除某个特定字符任意次，求出删除字符最小的次数，使其构成一个回文串，如果无法得到则输出 \(-1\)
解析：
进行搜索，给出左右两个指针 \(l,r\)，如果\(str_l=str_r\)，则继续向中间搜索，否则考虑删除\(str_l\ or\ str_r\)，统计成功得到回文串结果的最小值
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::string str;
int T, n,ans;
std::cin >> T;
while (T--) {
std::cin >> n >> str;
ans = 0x3f3f3f3f;
std::function<void(int, int, char, int)> dfs = [&](int l, int r, char ch, int cur) {
if (l >= r) {
ans = std::min(ans, cur);
return;
}
if (str[l] == str[r]) dfs(l + 1, r - 1, ch, cur);
else {
if (ch) {
if (str[l] == ch) dfs(l + 1, r, ch, cur + 1);
else if (str[r] == ch) dfs(l, r - 1, ch, cur + 1);
else return;
}
else {
dfs(l + 1, r, str[l], 1);
dfs(l, r - 1, str[r], 1);
}
}
};
dfs(0, n - 1, 0, 0);
printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
}
}
D（构造）
题目链接
⭐⭐
题目：
给出一个无零数组\(a\)，找出另一个相同长度的无零数组\(b\)使得，\(\sum_{i=1}^na_ib_i=0\)，且要求\(\sum_{i=1}^nb_i<10^9\)
解析：
考虑\(n\)为偶数或者奇数
- 偶数时，求出\(lcm(a_i,a_{i+1})\)，指定好\(a_ib_i,a_{i+1}b_{i+1}\)的符号，对应\(|b_i|=\frac{lcm}{a_i},|b_{i+1}|=\frac{lcm}{a_{i+1}}\)
- 奇数时，则考虑将{\(a_1,a_2,a_3\)}单独拿出考虑，剩下部分仍按偶数情况处理，这时不能使用\(lcm\)，三个数的\(\frac{lcm}{a_i}\)可能大于\(1e9\)，考虑构造方式为\(b_1=a_2+a_3,b_2=a_1,b_3=a_1\)
另附 :
偶数时也可以使得 \(|b_i|=|a_{i+1}|,|b_{i+1}|=|a_i|\) 求\(lcm\)，可以让\(sum(b)\)更小一点，但会多花一些时间
#include <bits/stdc++.h>
using i64 = long long;
using std::abs;
int main() {
std::function<i64(i64, i64)> gcd = [&](i64 a, i64 b) {
return b ? gcd(b, a % b) : a;
};
int T, n;
std::vector<i64> a;
i64 lcm;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
a.assign(n, 0ll);
for (int i = 0;i < n;++i)
scanf("%lld", &a[i]);
if (n & 1) {
if (a[0] < 0) printf("-");
printf("%lld ", abs(a[1])+abs(a[2]));
if (a[1] > 0) printf("-");
printf("%lld ", abs(a[0]));
if (a[2] > 0) printf("-");
printf("%lld ", abs(a[0]));
for (int i = 3; i < n; i += 2) {
lcm = abs(a[i]) * abs(a[i + 1]) / gcd(abs(a[i]), abs(a[i + 1]));
if (a[i] < 0) printf("-");
printf("%lld ", lcm / abs(a[i]));
if (a[i + 1] > 0) printf("-");
printf("%lld ", lcm / abs(a[i + 1]));
}
}
else {
for (int i = 0; i < n; i += 2) {
lcm = abs(a[i]) * abs(a[i + 1]) / gcd(abs(a[i]), abs(a[i + 1]));
if (a[i] < 0) printf("-");
printf("%lld ", lcm / abs(a[i]));
if (a[i + 1] > 0) printf("-");
printf("%lld ", lcm / abs(a[i + 1]));
}
}
printf("\n");
}
}
E（dp）
题目链接
⭐⭐⭐
题目：
给出数组\(a\)，找出最小的\(k\)，使得在\(a\)中有\(k\)个互不相交的区间 \([l_1,r_1],[l_2,r_2]\dots [l_k,r_k]\)，并满足
- \(r_i-l_i+1=k-i+1\)
- \(r_i<l_{i+1}\)
- \(\sum_{j=l_i}^{r_i}a_j<\sum_{j=l_{i+1}}^{r_{i+1}}a_j\)
解析：
定义状态 \(dp(i,j)\) 代表从下标 \(i\) 开始选取区间时，第一个长度为\(j\)的区间和的最大值，考虑选取 \(a_i\) 作为第一个区间中的一个元素时，此时必须要求 \(sum(i,i+j-1)<dp(i+j,j-1)\) ，才可以有贡献 \(sum(i,i+j-1)\) ，或者不选取\(a_i\)时直接继承 \(dp(i+1,j)\) 即可
答案统计\(dp(1,j)\)中被更新状态过的 \(j\) 即可
#include <bits/stdc++.h>
using i64 = long long;
int main() {
int T;
int n, k;
std::vector<i64> a, sum;
std::vector<std::vector<i64>> dp;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
k = (-1 + std::sqrt(1 + 8 * n)) / 2;
dp.assign(n+2, std::vector<i64>(k + 1, 0));
for (int i = 2;i <= n + 1;++i)
dp[i][0] = 0x3f3f3f3f;
a.assign(n + 1, 0), sum.assign(n + 1, 0);
for (int i = 1;i <= n;++i)
scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i];
for (int i = n;i;--i)
for (int j = 1;j <= k;++j) {
dp[i][j] = dp[i + 1][j];
if (i + j - 1 <= n && sum[i + j - 1] - sum[i - 1] < dp[i + j][j - 1])
dp[i][j] = std::max(dp[i][j], sum[i + j - 1] - sum[i - 1]);
}
for (int i = k;i;--i)
if (dp[1][i]) {
printf("%d\n", i);
break;
}
}
}
F hard version（dp）
题目链接
⭐⭐⭐
题目：
给出数组\(a\)，找出其中严格递增的子序列，其中所有元素的异或和可能是多少
解析：
定义状态 \(dp(i,j)\) 是子序列最后一个数小于等于 \(i\) 时，异或和为 \(j\) ，子序列最后一个数下标的最小值
考虑 \(i\) 作为子序列中最后一个数，则可以从 \(dp(i-1,i\oplus j)\) 中继承，但需要保证值为\(i\)的下标中存在一个下标大于\(dp(i-1,i\oplus j)\)，这样才可以构成一个子序列
答案在 \(dp(\max(a_i),j)\) 找到所有状态被更新的\(j\)
#include <bits/stdc++.h>
int main() {
constexpr int maxx = 8192, maxa = 5000;
std::vector dp(maxa + 1, std::vector<int>(maxx, 0x3f3f3f3f));
std::vector pos(maxa + 1, std::vector<int>());
int n, t;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &t);
pos[t].push_back(i);
}
dp[0][0] = 0;
for (int i = 1; i <= maxa; ++i) {
for (int j = 0; j < maxx; ++j) {
dp[i][j] = dp[i - 1][j];
if (pos[i].empty()) continue;
auto t = std::lower_bound(pos[i].begin(), pos[i].end(), dp[i - 1][i ^ j]);
if (t != pos[i].end()) dp[i][j] = std::min(dp[i][j], *t);
}
}
printf("%d\n", std::count_if(dp[maxa].begin(), dp[maxa].end(), [](int x) {return x != 0x3f3f3f3f; }));
for (int i = 0; i < maxx; ++i) {
if (dp[maxa][i] != 0x3f3f3f3f)
printf("%d ", i);
}
}