A ICPC Problems
请输入文本
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cout << (char)('A' + i) << " ";
cout << "\n";
}B Chess
对于象，它可以移动到 $(\pm2,\pm2)$ 的位置，也就是说
- 如果 $n\leq 2$ 或 $m\leq 2$ ，必然一步都跳不了
- 移动不会改变它横坐标和纵坐标的奇偶性。
记 $a=\lceil\frac{n}{2}\rceil,b=\lfloor\frac{n}{2}\rfloor,c=\lceil\frac{m}{2}\rceil,d=\lfloor\frac{m}{2}\rfloor$ 我们可以把棋盘分为四个子块：
- 与 $(1,1)$ 奇偶性相同的点，数量为 $a\times c$ 。
- 与 $(1,2)$ 奇偶性相同的点，数量为 $a\times d$ 。
- 与 $(2,1)$ 奇偶性相同的点，数量为 $b\times c$ 。
- 与 $(2,2)$ 奇偶性相同的点，数量为 $b\times d$ 。
对角线移动又会保证 $(x+y)\mod 4$ 的值一定，在奇偶性相同的条件下，每块又会被分为两个连通块，最大连通块的大小为 $\lceil\frac{size}{2}\rceil$ 。
枚举四个起点取最大值就行。
void solve() {
ll n, m;
cin >> n >> m;
if (n <= 2 || m <= 2) cout << 1 << "\n";
else {
ll a1 = (n + 1) / 2, a2 = n / 2, b1 = (m + 1) / 2, b2 = m / 2;
cout << max({(a1 * b1 + 1) / 2, (a1 * b2 + 1) / 2, (a2 * b1 + 1) / 2, (a2 * b1 + 1) / 2}) << "\n";
}
}C Sequence Cost
记数组和为 $S$ ，不难猜到最终的答案为 $min(S,mx+n*mn)$ 。接下来给出证明：
如果不进行修改，代价为 $S$ ；
如果进行修改，记操作花费为 $C$ ，最终数组的和为 $F$ ：
- 整个数组的 $mx$ 被修改了，此时必然有 $C\geq mx$ ，$C+F\geq mx+n*mn$ 。
- 整个数组的 $mx$ 没有被修改，最终的数组的 $sum$ 至少为 $mx+(n-1)mn$ ，此时总费用为 $C+mx+(n-1)mn$ ：
- 如果 $S\geq mx+nmn$ ， $C+mx+(n-1)mn-(mx+nmn) = C-mn$ ，如果进行了有效的修改， $C$ 显然大于 $mn$ ，故 $C+mx+(n-1)mn\geq mx+n*mn$ 。
- 如果 $S< mx+nmn$ ，即 $mx>S-nmn$ ， $C+mx+(n-1)mn-S\geq C-mn$ ，如果进行了有效的修改， $C$ 显然大于 $mn$ ，$C+mx+(n-1)mn\geq mx+n*mn$ 。
综上，最小代价为 $min(S,mx+n*mn)$ 。
void solve() {
ll n, mn = INF, mx = 0, sum = 0;
cin >> n;
for (ll i = 0, x; i < n; ++i) cin >> x, sum += x, mn = min(mn, x), mx = max(mx, x);
cout << min(mx + mn * n, sum) << "\n";
}D Digital Deletion
如果当前的 $mex$ 为 $R+1$ ，即前面的数字可以组成 $1\sim R$ 的所有数字，如果引入一个新的数字 $x$ ， $R$ 就能被扩展到 $R+x$ ：
- 对于 $t\in [1,x]$ ，还是原来的组合方式
- 对于 $t\in[x+1,R]$ ，可以通过 $x+[t-x]$ 的组合得到。（此处 $[x]$ 为组成 $x$ 的一组方案）
用这种方式，我们就能把 $R$ 拓展到 $R+x$ ，此时要求 $x\leq R+1$ 。
这样从小到大模拟一遍就可以算出最大的 $R$ 了。
- 如果 $R$ 为 $0$ ，显然所有数字都能被删除。
- 对于其余情况：
- 如果 $x=0$ 或 $x>R$ ，它产生不了任何贡献，可以直接删。
- 对于剩余的情况，我们贪心地拿出 $\leq cur+1$ 的最大的数进行更新，直到 $cur=R$ ，剩下的数字就是能删的数字。
void solve() {
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(all(a));
ll R = 0;
for (int i = 0; i < n; ++i) {
if (a[i] <= R + 1) R += a[i];
else break;
}
if (R == 0) {
cout << n << "\n";
return;
}
multiset<ll> ms;
for (int i = 0; i < n; ++i) {
if (1 <= a[i] && a[i] <= R) ms.insert(a[i]);
}
ll cur = 0;
int keep = 0;
while (cur < R) {
auto it = ms.upper_bound(cur + 1);
if (it == ms.begin()) {
break;
}
--it;
cur += *it;
ms.erase(it);
++keep;
}
cout << n - keep << "\n";
}E Block Array
好数组就是连接的几个块，所以我们贪心地进行分割，若当前位置值为 $k$ ，则要求区间 $[i,i+k-1]$ 内所有值都等于 $k$ ，若满足则把这段当作一个块，下一起点变为 $i+k$ 。对每个 $i$ 记录能连续切出的块个数 $\text{cnt[i]}$ ，那么以 $i$ 为左端的好子数组个数就是 $\text{cnt[i]}$ ，总体答案就是 $\sum\limits_i cnt[i]$ 。
void solve() {
int n;
cin >> n;
vector<int> a(n + 2, 0);
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<int> R(n + 2, 0);
R[n + 1] = n + 1, R[n] = n;
for (int i = n; i >= 1; --i) {
if (i < n && a[i] == a[i + 1]) R[i] = R[i + 1];
else R[i] = i;
}
vector<int> cnt(n + 3, 0);
ll ans = 0;
for (int i = n; i >= 1; --i) {
int k = a[i], r = i + k - 1;
if (k <= 0 || r > n) {
cnt[i] = 0;
} else {
if (R[i] >= r) {
int j = i + k;
if (j <= n) cnt[i] = 1 + cnt[j];
else cnt[i] = 1;
} else {
cnt[i] = 0;
}
}
ans += cnt[i];
}
cout << ans << "\n";
}F Sequence Covering
我们需要构建一个字典序最大的序列。这意味着我们希望从左到右尽可能让每一个位置的数字最大。
在每一个位置 $i$（当前还没有确定的位置），我们有两个选择：
- 延续上一次操作的值：如果我们之前进行了一个操作，当前位置 $i$ 可以被包含在那个操作的延伸区间中（或者被一个新的与之前值相同的操作覆盖，代价为 $\text{1}$ ）。如果之前的“活跃值” $V$ 比我们在当前预算 $k$ 下能找到的新的最大值还要大，那么花费 1 的代价将 $V$ 延伸到 $i$ 是最优的。
- 开始一个新的区间操作：如果在当前位置 $i$ 和预算 $k$ 允许的范围 $[i,i+k]$ 内，能找到一个比 $V$ 更大的值（或者没有活跃值，或者 $V$ 不够大），我们就应该去获取这个最大值。假设最大值 $M$ 出现在下标 $p$ ，我们执行操作区间 $[i,p]$ 。这样 $a[i…p]$ 都会变成 $M$ ，花费是 $p−i$ 。为了给后面的操作保留尽可能多的预算，如果有多个相同的最大值 $M$ ，我们选择最左边的一个（下标 $p$ 最小）。
void solve() {
int n;
ll k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
ST<int> st(n);
st.init(a);
vector<int> ans(n + 1);
int i = 1;
int las = -1;
while (i <= n) {
ll lim = i + k;
int r = (lim > n) ? n : lim;
auto [mv, pos] = st.getMax(i, r);
pos = -pos;
if (las > mv && k >= 1) {
ans[i] = las;
k--;
i++;
} else {
int cost = pos - i;
for (int j = i; j <= pos; j++) {
ans[j] = mv;
}
k -= cost;
las = mv;
i = pos + 1;
}
}
for (int j = 1; j <= n; j++) cout << ans[j] << " ";
cout << "\n";
}头文件
//Another
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TLLL = tuple<ll, ll, ll>;
constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}
void init() {
}
void solve() {
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int t = 1;
cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}ST表
template<class Int>
struct ST {
const int n, k;
vector<vector<pair<Int, int>>> Max;
vector<vector<pair<Int, int>>> Min;
ST(int n) : n(n), k(__lg(n)) {
Max.resize(k + 1, vector<pair<Int, int>>(n + 1));
Min.resize(k + 1, vector<pair<Int, int>>(n + 1));
}
template<class Array>
void init(Array &a) {
for (int i = 1; i <= n; i++) {
Max[0][i] = {a[i], -i};
Min[0][i] = {a[i], -i};
}
for (int i = 0, t = 1; i < k; i++, t <<= 1) {
const int T = n - (t << 1) + 1;
for (int j = 1; j <= T; j++) {
Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
Min[i + 1][j] = min(Min[i][j], Min[i][j + t]);
}
}
}
pair<Int, int> getMax(int l, int r) {
if (l > r) {
swap(l, r);
}
int k = __lg(r - l + 1);
return max(Max[k][l], Max[k][r - (1 << k) + 1]);
}
pair<Int, int> getMin(int l, int r) {
if (l > r) {
swap(l, r);
}
int k = __lg(r - l + 1);
return min(Min[k][l], Min[k][r - (1 << k) + 1]);
}
};