Rank 44/3682. Solved 12/13.简单题太多坑，难题都有点眼熟
A. mutsumi的质数合数
题意
给定一个数组 \(a_i\)，求数组中质数和合数的数量之和。
思路
只有 \(1\) 既不是质数也不是合数，所以答案为 \(n - cnt_1\)。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
int cnt = 0;
for(int i=1;i<=n;i++) {
int x;
cin >> x;
if(x != 1) cnt ++;
}
cout << cnt << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}花了半分钟把线性筛板子拿出来，忍俊不禁
B. tomorin的字符串迷茫值
题意
给定一个字符串，在不删除连续字符的条件下，输出所有删除方案得到的字符串中包含连续子串 \(\mathtt{mygo}\) 的个数。
思路
首先，我们可以发现，两个不同位置的 \(\mathtt{mygo}\) 互不影响对方的计算。
从而，既然是要求所有方案中子串 \(\mathtt{mygo}\) 的数量，那么我们就可以固定每个 \(\mathtt{mygo}\)，统计 \(\mathtt{mygo}\) 左侧和右侧的删除方案总数，这样累加得到的结果是相同的。
而删除与否，对于 \(\mathtt{mygo}\) 子串来说，就是相邻字符间是否有多余的一个字符，也就是说，我们只需检查形为 \(\mathtt{m\_y\_g\_o}\) 的子串，其中下划线对应的字符可有可无。
那么剩下的问题就是，如果子串位于 \([l, r]\) 区间内，那么剩余的 \([1, l - 1], [r + 1, n]\) 如何处理呢？
不难发现的是，他们互不影响，所以答案一定是两者数量的乘积，所以我们来考虑单独的一个区间 \([1, x]\)。
我们可以找规律，得到一个斐波那契数列，此处就不证明了。
如上即可解决本题。
时间复杂度：\(O(n)\)
对应AC代码 (MInt)
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(int x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
int v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<>
int MInt<0LL>::Mod = (int)1E18 + 9;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 1e9 + 7;
using Z = MInt<P>;
void solve() {
string s;
cin >> s;
int n = s.size();
s = " " + s;
vector<Z> cnt(n + 1);
cnt[0] = 1, cnt[1] = 2;
for(int i=2;i<=n;i++) cnt[i] = cnt[i - 1] + cnt[i - 2];
Z ans = 0;
for(int i=1;i<=n;i++) {
if(s[i] == 'm') {
for(int j : {i + 1, i + 2}) {
if(j <= n && s[j] == 'y') {
for(int p : {j + 1, j + 2}) {
if(p <= n && s[p] == 'g') {
for(int q : {p + 1, p + 2}) {
if(q <= n && s[q] == 'o') {
ans = ans + cnt[i - 1] * cnt[n - q];
}
}
}
}
}
}
}
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) solve();
}直接 \(dp\) 也是可以的，只是在动工前突然想到可以这么做（
C. anon的私货
题意
给定一个正整数数组，定义 若数组中任意一个包含非 \(0\) 元素的连续子数组的平均值 \(\leq 1\)，那么这个数组就不合法。
若可以在数组中任意位置插入任意数量的 \(0\)，输出使数组依旧合法的最多插入数量。
思路
我们不妨考虑 \(0\) 尽可能多的数组，这样就能让平均值尽可能小。
那么，我们最起码，要让形如 \(p\ 0\ 0\ \ldots \ 0\) 的子数组平均值 \(\geq 1\)。
若需满足上述条件，我们只需在两个正数 \(p, q\) 之间插入 \(\min(p, q) - 1\) 个 \(0\)。
然而上面的条件是不够的，进一步地，我们还需要让形如 \(p\ 0\ 0\ \ldots\ 0\ q\ 0\ 0\ \ldots \ 0\) 的子数组平均值 \(\geq 1\)。
而有趣的是，如果我们是从左往右计算的，我们就可以把 \(q\) 左边的那份代价直接合并到 \(q\) 身上，这样就只需考虑一开始的那种情况了。
至于如何合并，我们在计算 \(p\ 0\ 0\ \ldots \ 0\) 后，令 \(q := q - (\min(p, q) - 1)\) 即可，这样在后续计算中，我们就把之前的 \(0\) 删掉了。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
if (i == 1) {
ans += a[1] - 1;
a[1] = 1;
} else {
int now = min(a[i], a[i - 1]) - 1;
ans += now;
a[i] -= now;
}
}
ans += a[n] - 1;
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}没错，我一开始只考虑了那个最简单的贪心
D. soyorin的树上剪切
待补充
E. soyorin的数组操作（easy）
和 \(F\) 相同，区别为本题不需要计算具体数量
F. soyorin的数组操作（hard）
题意
给定一个数组 \(a\)，定义一次操作为选定一个偶数 \(k\)，并将所有 \(a_i, i \in[1, k]\) 加上 \(i\)。
输出将数组变为非降序的最小操作次数，无解输出 \(-1\).
思路
首先，可以发现的是，既然我们加上的是一个递增的序列，那么假设我们对 \([1, x]\) 序列进行 \(p\) 次操作后整个序列合法了，我们对 \([1, n]\) 序列进行 \(p\) 次操作后依然能使其合法。
那么，这道题就很简单了...吗？并不是。
可以发现，只有当序列长度为偶数时，我们才能这么干，当序列长度为奇数的时候，由于 \(a[n]\) 无法改变，这限制了我们对 \(a[n - 1]\) 的操作次数。
我们先来看看 \(n\) 为偶数的时候，我们该如何计算操作次数。
我们记操作次数为 \(k\)，从而有 \(a[i] + k \cdot i \leq a[i + 1] + k \cdot (i + 1)\)，化简得到 \(k \geq a[i] - a[i + 1]\)。
也就是说，当 \(n\) 为偶数的时候，\(k = (a[i] - a[i + 1])_{\max}\)。
而当 \(n\) 为奇数的时候，我们就得一个一个考虑了。
可以发现的是，因为我们操作的起点固定，所以 \(a[x]\) 一定被加了至少 \((a[i] - a[i + 1])_{\max}, i \in [x, n-2]\) 次。
从而，我们考虑维护一个后缀数组，\(cnt[x]\) 为 \((a[i] - a[i + 1])_{\max}, i \in [x, n-2]\)。
答案已经可以确定，就是 \(cnt[1]\)，因为我们无所谓这 \(cnt[1]\) 次操作的右端点如何，第一个元素永远都会被加 \(cnt[1]\) 次。
剩下就是如何判断是否有解了。我们直接按照 \(cnt\) 数组，依次模拟计算即可，这样只要中间出现了无解，最后依然能检查到。我们检查 \(a[n - 1]\) 和 \(a[n]\) 的大小关系即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
if(n % 2 == 0) {
int cnt = 0;
for(int i=2;i<=n;i++) cnt = max(cnt, a[i - 1] - a[i]);
cout << cnt << '\n';
return;
}
vector<int> cnt(n + 1);
for(int i=n-1;i>=1;i--) {
cnt[i] = max(cnt[i + 1], a[i - 1] - a[i]);
}
int pre = -inf;
for(int i=1;i<n;i++) {
if(i % 2 == 0) cnt[i] = cnt[i - 1];
int now = a[i] + i * cnt[i];
if(pre > now) cnt[i] += (pre - now + (i - 1)) / i;
pre = a[i] + i * cnt[i];
}
if(pre > a[n]) cout << -1 << '\n';
else cout << cnt[1] << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) solve();
}其实有点写复杂了，倒着直接推也行
G. sakiko的排列构造（easy）
和 \(H\) 相同，区别为数据范围
H. sakiko的排列构造（hard）
题意
给定一个整数 \(n\)，构造一个长为 \(n\) 的排列 \(p\)，满足 \(p_i + i\) 为质数。
思路
首先，我们可以发现的是，\(10^6\) 范围内，相邻质数的差值比较小，打表可以发现最大差值为 \(132\)。
那么，如果我们能找到质数 \(n + k\)，\([k, n]\) 区间内就可以填 \(\{n, n - 1, \ldots, k\}\)。
此时，剩余的 \([1, k - 1]\) 区间就变得很小了。
同样的，相邻质数的最大差值来到 \(14\)，我们继续重复上述操作。
此时，相邻质数的最大差值来到个位数，可以发现，最后我们要么相差 \(1\)，要么相差 \(2\)，要么一点不差，从而一定有解。
综上，没有无解的情况，循环上述操作几次即可得到答案。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
bool not_pri[N];
int pr[N], cnt;
//线性筛求积性函数
static void sieve_mul_func(const int n, bool not_pri[], int pr[], int &cnt, const auto &&new_pri, const auto &&stop, const auto &&on) {
for (int i = 2; i <= n; i ++) {
if (!not_pri[i]) pr[cnt++] = i, new_pri(i);
for (int j = 0; j < cnt && i * pr[j] <= n; j ++) {
not_pri[i * pr[j]] = true;
if (i % pr[j] == 0) {
stop(i, pr[j]);
break;
}
on(i, pr[j]);
}
}
}
//线性筛: pr[] 所有素数
static void get_prime(const int n, bool not_pri[], int pr[], int &cnt) {
sieve_mul_func(n, not_pri, pr, cnt, [&](const int i) {}, [&](const int i, const int pr_) {}, [&](const int i, const int pr_) {});
}
void init() {
get_prime(2e6, not_pri, pr, cnt);
}
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=n;i>=1;){
int ind = 1;
while(not_pri[ind + i]) ind ++;
for(int j=ind;j<=i;j++) a[j] = i + ind - j;
i = ind - 1;
}
for(int i=1;i<=n;i++) cout << a[i] << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) solve();
}打表看出的唯一规律估计就是答案由连续的几段递减的序列构成
I. rikki的最短路
题意
在一条数轴上，\(A\) 位于点 \(a\)，\(T\) 位于点 \(t\)。
\(R\) 需要从 \(0\) 出发，来到 \(A\) 所在位置，将其带到 \(T\) 所在位置。
\(R\) 具有大小为 \(k\) 的视野，如果位于位置 \(u\)，那么可以看到 \([u - k, u + k]\) 内的东西。
\(R\) 只知道 \(T\) 的位置，对于 \(A\) 的位置，它可以询问 \(T\)，也可以在前往 \(T\) 的路上通过视野看到。
输出最小移动距离。
思路
直接分类讨论。
首先，在前往 \(T\) 的路上，\(R\) 能看到的范围为 \([\min(0, t) - k, \max(0, t) + k]\)，如果 \(A\) 不在区间内，那么 \(R\) 只能去问 \(T\)，答案为 \(\text{abs}(t) + 2 \times \text{abs}(a - t)\)。
否则，我们需要根据 \(A, T\) 位置的正负来分讨。
如果 \(A, T\) 在数轴同侧，那么如果 \(T\) 在前往 \(A\) 的路上，我们就需要折返，答案为 \(\text{abs}(a) + \text{abs}(a - t)\)，否则，我们直走到 \(T\) 即可，答案为 \(\text{abs}(t)\)。
如果位于异侧，那么我们就需先走到 \(A\)，再折回来，答案为 \(2 \times \text{abs}(a) + \text{abs}(t)\)。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int t, a, k;
cin >> t >> a >> k;
if(a >= min(0ll, t) - k && a <= max(0ll, t) + k) {
if(a * t >= 0) {
if(abs(a) > abs(t)) cout << abs(a) + abs(a - t) << '\n';
else cout << abs(t) << '\n';
}else {
cout << 2 * abs(a) + abs(t) << '\n';
}
}else cout << abs(t) + abs(a - t) * 2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) solve();
}有人没看到 \(a, t\) 可以是负数然后挂了 \(2\) 发，我不说是谁
J. rikki的数组陡峭值
题意
构造一个长为 \(n\) 的数组 \(a\)，满足给定区间限制 \(a_i \in [l_i, r_i]\)。
输出 \(\sum_{i=1}^{n-1} |a_i - a_{i + 1}|\) 的最小值。
思路
我们不妨维护区间左端点的最大值 \(lm\) 和右端点的最小值 \(rm\)，如果 \(lm \leq rm\) 一直成立，我们就可以选择区间内的任意一个数，从而差值和为 \(0\)。
否则，我们会遇到冲突，对于新区间 \([l_i, r_i]\)，如果 \(l_i > rm\)，那么前面的所有元素都选 \(rm\)，而后续的选择将退化为一个点，当前点的值不妨选 \(l_i\)。同样地，如果 \(r_i < lm\)，那么前面的所有元素都选 \(lm\)，当前点的值不妨选 \(r_i\)。
然后我们只需按照后续的区间更新点即可，如果点在区间内，那么值不变，否则更改为最近的区间端点即可。
至于证明，不妨考虑后续值变化的时候，我们计算差值时，去掉绝对值后，中间的点因为正负号抵消而变为 \(0\)，从而中间的选择是任意的。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> l(n + 1), r(n + 1);
for(int i=1;i<=n;i++) cin >> l[i] >> r[i];
int lm = -inf, rm = inf;
int pre = -1, ans = 0, i = 1;
for(;i<=n;i++) {
lm = max(lm, l[i]), rm = min(rm, r[i]);
if(lm <= rm) continue;
if(l[i] == lm) pre = lm;
else pre = rm;
ans += lm - rm;
i ++;
break;
}
for(;i<=n;i++) {
if(l[i] > pre) {
ans += l[i] - pre;
pre = l[i];
}
if(r[i] < pre) {
ans += pre - r[i];
pre = r[i];
}
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) solve();
}很眼熟，绝对做过 x1
K. soyorin的通知
题意
对于一则消息，需要传递给 \(n\) 个人，一开始没有人知道。
有两种方式传递：
花费 \(p\) 代价，选择一个未被传递的人，传递给他；
选择一个已经被传递的人 \(i\)，花费 \(a_i\) 代价，将消息传递给最多 \(b_i\) 个人
输出让所有人都被传递到消息的最小代价。
思路
我们记 \(a_0 = p, b_0 = 1\)，然后直接套完全背包板子即可。
注意第一个人一定要使用第一种方法，从而我们直接将背包容量视为 \(n- 1\)，然后最后加上即可。
注意 \(dp\) 数组一开始需要为 \(inf\)，标记其未被传递。
时间复杂度：\(O(n^2)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, p;
cin >> n >> p;
vector<int> dp(n + 1, inf);
dp[0] = 0;
for(int i=0;i<=n;i++) {
int a, b;
if(i == 0) a = p, b = 1;
else cin >> a >> b;
for(int j=0;j<n;j++) {
dp[min(n - 1, j + b)] = min(dp[min(n - 1, j + b)], dp[j] + a);
}
}
cout << dp[n - 1] + p << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) solve();
}L. anon的星星
题意
对于一个游戏，赢则得到一个星星，输则失去一个星星。
现在，给定游戏总局数，以及星星个数，输出赢和输的局数。
思路
设未知数然后列方程组即可，最后答案为 \(\frac{n+x}{2}, \frac{n-x}{2}\)。
当然，如果 \(n, x\) 奇偶性不同，就是无解了。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, x;
cin >> n >> x;
if(abs(n % 2) != abs(x % 2)) {
cout << -1 << '\n';
return;
}
cout << (n + x) / 2 << ' ' << (n - x) / 2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}判奇偶的时候，注意可能会出现正数 \(1\) 和负数 \(-1\) 比较的情况，需要取绝对值
M. mutsumi的排列连通
题意
对于一个 \(2 \times n\) 的矩阵，每行都由长度为 \(n\) 的排列组成。
定义一次操作为选择一个数字，并将矩阵中该数字对应的方格删去。
定义对于两个方格 \(x, y\)，如果双方都能以上下左右移动的方式到达对方，那么这两个方格位于同个连通块中。
输出使矩阵变为两个连通块的最小操作数，无解输出 \(-1\)。
思路
首先，我们先对 \(n = 1, 2\) 单独考虑，前者一定无解，后者如果上下刚好不一致，那么答案为 \(1\)，否则无解。
其次，我们考虑矩阵中是否存在 \(i, j\)，满足 \(\text{abs}(i - j) \leq 1\)，且第一行的第 \(i\) 个元素和第二行的第 \(j\) 个元素相等。
如果满足上述条件，我们就可以删一次达到目的，否则我们就需要删两次。
当然上面需要对 \(i = j\) 特判，因为如果我们删掉了两头，还是只有一个联通块。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
for(int i=1;i<=n;i++) {
cin >> a[i];
}
for(int i=1;i<=n;i++) {
cin >> b[i];
}
if(n == 1) {
cout << -1 << '\n';
return;
}else if(n == 2) {
if(a[1] == 1 && b[1] == 1) {
cout << -1 << '\n';
}else cout << 1 << '\n';
return;
}
for(int i=1;i<=n;i++) {
if(i > 1 && i < n && a[i] == b[i]) {
cout << 1 << '\n';
return;
}else if(i > 1 && a[i - 1] == b[i]) {
cout << 1 << '\n';
return;
}else if(i < n && a[i + 1] == b[i]) {
cout << 1 << '\n';
return;
}
}
cout << 2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) solve();
}如果没看到是排列那就尴尬了（