大半夜被叫出去吃点宵夜，直接晕了两天，一定要好好睡觉，随便写点最近做的题。
F - Select Half
题目链接： F - Select Half
题意：
给定 $n$ 个数，选恰好 $\lfloor \frac{n}{2} \rfloor$ 个数，且不能同时选相邻的两个数，求和的最大值。
解题思路：
乍一看以为是线段树，但其实不太好控制选多少个数，其实直接用 DP 就可以了，数量也很好控制。
定义 $f[i]$ 为只从前 $i$ 个数中选恰好 $\lfloor \frac{i}{2} \rfloor$ 个数的所有方案，属性是最大值。
转移方面，假如 $i$ 之前有奇数个数，那么 $a_i$ 可以不选，可以直接从 $f[i-1]$ 转移过来；假如 $i$ 之前有偶数个数，有两种选择，选 $a_i$ 的话，要从 $f[i-2]$ 转移过来，否则必须要选 $pre[i-1]$ ，其中 $pre[i]$ 表示 $a_i+a_{i-2}+a_{i-4}+\dots$ 。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
vector<long long> pre(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
pre[i] = a[i];
if (i - 2 >= 0) {
pre[i] += pre[i - 2];
}
}
vector<long long> f(n);
for (int i = 1; i < n; i++) {
if (i & 1) {
f[i] = max(pre[i], pre[i - 1]);
if (i - 2 >= 0) {
f[i] = max(f[i], f[i - 2] + a[i]);
}
} else {
f[i] = max(f[i - 1], a[i] + f[i - 2]);
f[i] = max(f[i], pre[i - 1]);
}
}
cout << f.back() << '\n';
return 0;
}
F - Strivore
题目链接： F - Strivore
题意：
给定一个长度为 $n$ 的字符串，插入任意 $k$ 个字符，求可以形成多少种串。
解题思路：
这题本质上就是要避免重复计算字符串，因此主要考察的枚举顺序。
枚举一下原串第一个字符前面插入多少个字符，规定只有前面的字符才可以有连续多个字符相同，后面相邻的字符都是不同的。
假如前面有 $i$ 个字符，那么就会有 $26^i$ 种方案，后面剩下 $k-i$ 个字符需要插入，同时原串剩下 $n-1$ 个字符，问题就转化成了在 $n-1$ 个小球上有序地插入 $k-i$ 个新小球，也就是 $C_{k-i+n-1}^{n-1}$ ，因为后面的字符都不重复，因此方案数为 $25^{k-i}$ 。
代码如下：
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = (int) 1e9 + 7;
// assume -mod <= x < 2 * mod
int norm(int x) {
if (x < 0) {
x += mod;
}
if (x >= mod) {
x -= mod;
}
return x;
}
template<typename T, typename U>
T qp(const T &a, const U &b) {
assert(b >= 0);
T res = 1, x = a;
U p = b;
for (; p; p /= 2, x *= x) {
if (p % 2) {
res *= x;
}
}
return res;
}
class Mint {
public:
int x;
Mint(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Mint operator-() const {
return Mint(norm(mod - x));
}
Mint inv() const {
assert(x != 0);
return qp(*this, mod - 2);
}
Mint &operator*=(const Mint &rhs) {
x = (int) ((long long) x * rhs.x % mod);
return *this;
}
Mint &operator+=(const Mint &rhs) {
x = norm(x + rhs.x);
return *this;
}
Mint &operator-=(const Mint &rhs) {
x = norm(x - rhs.x);
return *this;
}
Mint &operator/=(const Mint &rhs) {
return *this *= rhs.inv();
}
friend Mint operator*(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res *= rhs;
return res;
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res += rhs;
return res;
}
friend Mint operator-(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res -= rhs;
return res;
}
friend Mint operator/(const Mint &lhs, const Mint &rhs) {
Mint res = lhs;
res /= rhs;
return res;
}
};
vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);
Mint C(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
while ((int) fact.size() < n + 1) {
fact.push_back(fact.back() * (int) fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n] * inv_fact[k] * inv_fact[n - k];
}
Mint Fact(int n) {
assert(n >= 0);
while ((int) fact.size() < n + 1) {
fact.push_back(fact.back() * (int) fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int k;
string s;
cin >> k >> s;
int n = (int) s.size();
Mint res = 0;
for (int i = 0; i <= k; i++) {
res += qp(Mint(26), i) * C(k - i + n - 1, n - 1) * qp(Mint(25), k - i);
}
cout << res.val() << '\n';
return 0;
}
C - Tricolor Pyramid
题目链接： C - Tricolor Pyramid
题意：
建议直接看原题。
解题思路：
思路有点抽象，但看了 题解 的示意图之后豁然开朗，很有意思的一道题，主要的难点是在计算模 $3$ 的组合数上。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
string s;
cin >> n >> s;
map<char, int> mp;
mp['B'] = 0;
mp['W'] = 1;
mp['R'] = 2;
vector<vector<int>> c(3, vector<int>(3));
for (int i = 0; i < 3; i++) {
for (int j = 0; j <= i; j++) {
if (!j) {
c[i][j] = 1;
} else {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
}
function<int(int, int)> C = [&](int a, int b) -> int {
if (a < b || b < 0) {
return 0;
}
int v = 1;
while (a > 0) {
int x = a % 3;
int y = b % 3;
a /= 3;
b /= 3;
v = (v * c[x][y]) % 3;
}
return v;
};
int res = 0;
for (int i = 0; i < n; i++) {
res = (res + C(n - 1, i) * mp[s[i]]) % 3;
}
if (n % 2 == 0) {
res = (-res % 3 + 3) % 3;
}
for (auto &[x, y] : mp) {
if (y == res) {
cout << x << '\n';
}
}
return 0;
}
D. Grime Zoo
题目链接： D. Grime Zoo
题意：
给定一个 $01$ 串，当中有一些位置是未知的，可以随意设置，设置完所有位置以后，每出现一次 $01$ 子序列则会扣 $x$ 分，出现 $10$ 子序列则会扣 $y$ 分，求扣分最小值。
解题思路：
直觉上觉得设置的方案应该是像 $000…111$ 或者 $111…000$ ，其实事实也确实如此，可以用邻值交换法证明。因为假如出现了 $101$ ，则会贡献 $10$ 和 $01$ ，那么一定可以设置成 $011$ ，贡献两个 $01$ ，或者设置成 $110$ ，贡献两个 $10$ ，这两种方案的其中之一一定会比 $101$ 更优。
因此就可以算一下这两种方案的最小值了，直接枚举分界点即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string s;
long long x, y;
cin >> s >> x >> y;
int n = (int) s.size();
vector<vector<int>> pre(n, vector<int>(2));
for (int i = 0; i < n; i++) {
if (i > 0) {
pre[i][0] = pre[i - 1][0];
pre[i][1] = pre[i - 1][1];
}
if (s[i] == '0') {
pre[i][0] += 1;
}
if (s[i] == '1') {
pre[i][1] += 1;
}
}
vector<vector<int>> suf(n, vector<int>(2));
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1) {
suf[i][0] = suf[i + 1][0];
suf[i][1] = suf[i + 1][1];
}
if (s[i] == '0') {
suf[i][0] += 1;
}
if (s[i] == '1') {
suf[i][1] += 1;
}
}
long long other = 0;
for (int i = 1; i < n; i++) {
if (s[i] == '0') {
other += pre[i - 1][1] * y;
}
if (s[i] == '1') {
other += pre[i - 1][0] * x;
}
}
int marks = (int) count(s.begin(), s.end(), '?');
// 111...000
long long res = (long long) 4e18;
{
// 000...000
long long cur = other;
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
if (i > 0) {
// 10
cur += pre[i - 1][1] * y;
}
if (i + 1 < n) {
// 01
cur += suf[i + 1][1] * x;
}
}
}
res = min(res, cur);
int one = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
if (i > 0) {
cur -= pre[i - 1][1] * y;
cur += pre[i - 1][0] * x;
}
if (i + 1 < n) {
cur -= suf[i + 1][1] * x;
cur += suf[i + 1][0] * y;
}
cur -= y * one;
++one;
cur += y * (marks - one);
res = min(res, cur);
}
}
}
// 000...111
{
long long cur = other;
// 111...111
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
if (i > 0) {
// 01
cur += pre[i - 1][0] * x;
}
if (i + 1 < n) {
cur += suf[i + 1][0] * y;
}
}
}
res = min(res, cur);
int zero = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
if (i > 0) {
cur -= pre[i - 1][0] * x;
cur += pre[i - 1][1] * y;
}
if (i + 1 < n) {
cur -= suf[i + 1][0] * y;
cur += suf[i + 1][1] * x;
}
cur -= x * zero;
++zero;
cur += x * (marks - zero);
res = min(res, cur);
}
}
}
cout << res << '\n';
return 0;
}
D. Segment Intersections
题目链接： D. Segment Intersections
题意：
给定 $n$ 对同样的线段的初始值 $[l,r]$ ，每花费 $1$ 可以将一个线段扩展一个单位长度，问至少花费多少可以使得每对线段的相交部分之和至少为 $k$ 。
解题思路：
本身不难，但需要观察出一些性质。
如果两个线段是不相交的，那么当前花费 $1$ 是不能产生贡献的，如果相交但不完全覆盖，那么花费 $1$ 则可以贡献 $1$ ，如果两线段完全覆盖，那么花费 $2$ 才会贡献 $1$ ，此外还要先加上初始时已经覆盖了的部分。
具体看代码注释，应该比较清楚。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n;
long long k;
cin >> n >> k;
vector<long long> l(2);
vector<long long> r(2);
for (int i = 0; i < 2; i++) {
cin >> l[i] >> r[i];
}
// 要使两线段相交需要的花费
long long gap = max(0LL, max(l[0], l[1]) - min(r[0], r[1]));
// 两线段已经相交的部分长度
long long cover = max(0LL, min(r[0], r[1]) - max(l[0], l[1]));
// 一对线段花费 1 所能产生的最大贡献
long long extend = max(r[0], r[1]) - min(l[0], l[1]) - cover;
long long res = 0;
// 先减去初始时就已经覆盖的部分
k = max(0LL, k - cover * n);
for (int i = 0; i < n; i++) {
if (i == 0) {
// 如果当前没有任何一对线段相交
// 则必须至少使一对相交再说
// 相交之后花费 1 贡献 1 肯定是划算的
res += gap;
long long take = min(k, extend);
k -= take;
res += take;
continue;
}
// 当前已经有相交了的线段了
// 要判断一下是否要付出 gap 的无意义花费
// 还是直接在已经相交的线段花费 2 贡献 1
long long take = min(k, extend);
if (2 * take > gap + take) {
res += gap + take;
k -= take;
}
}
res += 2 * k;
cout << res << '\n';
}
return 0;
}
F - Jealous Two
题目链接： F - Jealous Two
题意：
有 $n$ 种礼物，某种礼物在 $A$ 眼里的价值是 $x_i$ ，在 $B$ 眼里的价值是 $y_i$ ，要分别给两人一个礼物，两人可以得到同种礼物，问有多少种分配礼物的方案，使得 $A$ 得到的礼物，在 $A$ 眼里的价值不小于在 $B$ 眼里的价值，且 $B$ 得到的礼物，在 $B$ 眼里的价值不小于 $A$ 眼里的价值。
解题思路：
赛时做出来了，不过当时的代码不够优雅，再写一遍。
这是个比较典型的排序和树状数组的解决二维偏序问题的套路，首先肯定是要离散化的了。
然后按照题意，分别计算 $(x,y)$ 相同部分和不同部分的方案数即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class Fenwick {
public:
vector<T> fenw;
int n;
Fenwick(int _n) : n(_n) {
fenw.resize(n);
}
inline void add(int x, T v) {
assert(x >= 0 && x < n);
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
inline T get(int x) {
T res{};
while (x >= 0) {
res += fenw[x];
x = (x & (x + 1)) - 1;
}
return res;
}
inline T get(int l, int r) {
assert(l >= 0 && l < n && r >= 0 && r < n);
T res = get(r);
if (l - 1 >= 0) {
res -= get(l - 1);
}
return res;
}
};
// struct node {
// int a = ...; // don't forget to set default value
// inline void operator += (node &other) {
// ...
// }
// };
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<pair<int, int>> a(n);
vector<int> val;
for (int i = 0; i < n; i++) {
cin >> a[i].first;
val.emplace_back(a[i].first);
}
for (int i = 0; i < n; i++) {
cin >> a[i].second;
val.emplace_back(a[i].second);
}
sort(val.begin(), val.end());
for (int i = 0; i < n; i++) {
a[i].first = (int) (lower_bound(val.begin(), val.end(), a[i].first) - val.begin()) + 1;
a[i].second = -((int) (lower_bound(val.begin(), val.end(), a[i].second) - val.begin()) + 1);
}
sort(a.begin(), a.end());
for (int i = 0; i < n; i++) {
//cout << a[i].first << ' ' << -a[i].second << '\n';
}
int m = (int) val.size();
Fenwick<int> fen(m + 5);
long long res = 0;
for (int i = 0; i < n; i++) {
int j = i;
while (j < n && a[i] == a[j]) {
j++;
}
int cnt = j - i;
auto [x, y] = a[i];
y = -y;
res += (long long) cnt * cnt;
res += (long long) cnt * (i - fen.get(y - 1));
fen.add(y, cnt);
i = j - 1;
}
cout << res << '\n';
return 0;
}
E - Minimal payments
题目链接： E - Minimal payments
题意：
给定 $n$ 种纸币，第一种面额为 $1$ 元，后面的每种纸币的面额都是前一种的倍数，要买 $X$ 元的物品，要支付 $Y(Y\geq X)$ 元，找回 $Y-X$ 元，求至少用多少张纸币可以凑成这两个数。
解题思路：
要使得数量最少，直觉上会认为尽可能用大面额的纸币，由于本题要求每种纸币的面额都是前一种的倍数，因此可以用大面额的情况下，肯定可以用比它小的面额纸币凑出同样的金额，但是情况肯定会更坏，因此尽可能用大面额的纸币会更好，同时，由于有面额为 $1$ 的纸币，肯定有解，因此从大面额纸币开始考虑。
定义 $f[i,j]$ 为只考虑 $i$ 以及之后的纸币，凑出 $j$ 的所有方案，属性为最小值，那么其实只需要考虑两种情况：
- 用 $\lfloor \frac{j}{a_i} \rfloor$ 张当前的纸币，然后剩下 $j \mod a_i$ 由剩下的纸币来凑；
- 用 $\lceil \frac{j}{a_i} \rceil$ 张纸币，然后超出部分 $(a_i-j\mod a_i)\mod a_i$ 由对方找零。
由于 $j$ 很大，而且每个 $i$ 只需要考虑这两种情况，空间是线性的，可以用记忆化搜索。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
long long x;
cin >> n >> x;
vector<long long> a(n);
for (auto &u : a) {
cin >> u;
}
map<pair<int, long long>, long long> f;
function<long long(int, long long)> dp = [&](int i, long long j) -> long long {
if (i == 0 || j == 0) {
return j;
}
if (f.count(make_pair(i, j)) != 0) {
return f[make_pair(i, j)];
}
long long res = dp(i - 1, j % a[i]) + j / a[i];
res = min(res, dp(i - 1, (a[i] - j % a[i]) % a[i]) + (j + a[i] - 1) / a[i]);
return f[make_pair(i, j)] = res;
};
cout << dp(n - 1, x) << '\n';
return 0;
}
