链接：https://ac.nowcoder.com/acm/contest/125083
A – ICPC Problems
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i)
cout << char('A' + i) << ' ';
cout << endl;
}B – Chess
算法：
思维。
思路：
默认 \(n < m\)，不难发现在 \((1, 1)\) 放置象是最优的。
当 \(n < 3\) 时，答案是 \(1\)。
否则，一个 \(n\) 行的棋盘有 \(\lceil \frac{n}{2} \rceil\) 行可到达，连续可到达的两行棋盘存在 \(\lceil \frac{m}{2} \rceil\) 个位置可到达。
那么当棋盘上有偶数行可到达时，有 \(\lceil \frac{n}{4} \rceil * \lceil \frac{m}{2} \rceil\) 个点可到达。
存在奇数行时，有 \(\lceil \frac{n}{4} \rceil * \lceil \frac{m}{2} \rceil – \lceil \frac{m}{4} \rceil\) 个点可到达。
关键代码：
void miyan()
{
ll n, m;
cin >> n >> m;
if (n > m)
swap(n, m);
if (n < 3)
cout << 1 << endl;
else
{
ll row = (n + 1) / 2;
ll col = (m + 1) / 2;
if (row & 1)
cout << ((row + 1) / 2) * col - col / 2 << endl;
else
cout << row / 2 * col << endl;
}
}C – Sequence Cost
算法：
贪心。
思路：
答案只有两种情况：
- 数组不进行操作。
- 对整个数组全部元素做一次操作。
- 答案取最小即可。
关键代码：
void miyan()
{
int n;
cin >> n;
vector<ll> a(n);
for (auto &x : a)
cin >> x;
ll ans1 = accumulate(all(a), 0ll);
ll ans2 = ranges::max(a) + ranges::min(a) * n;
cout << min(ans1, ans2) << endl;
}D – Digital Deletion
算法：
贪心。
思路：
先对数组进行排序。
设 \(sum\) 为当前的 \(mex\)，即前面的数字已经可以拼出来 \([0, sum]\) 所有的数字，此时准备加入一个数字 \(x\)：
- 如果 \(x \in [0, sum + 1]\)，在选择数字 \(x\) 后，可拼出的数字区间就为 \([0, sum + x]\)。
- 如果 \(x \in [sum + 2, \infty)\)，在选择数字 \(x\) 后，可拼出的数字区间就为 \([0, sum] \cup [sum + 2, infty)\)。
对于上述加数字的情况，不难发现从小到大选是最优的。
当选择的数字 \(x\) 大于 \(sum + 1\) 时，可拼出的数字区间就会断掉，那么后续所有的数字及其 \(x\) 都不会对区间产生实质性贡献，直接删掉即可。
关键代码：
void miyan()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
ranges::sort(a);
int cnt = ranges::count(a, 0);
ll sum = 0;
for (int i = 0; i < n; ++i)
{
if (a[i] <= sum + 1)
sum += a[i];
else
{
cout << n - i + cnt << endl;
return;
}
}
cout << cnt << endl;
}E – Block Array
算法：
\(dp\)。
思路：
经典计数\(dp\)。
定义 \(dp[i]\) 为严格以 \(i\) 作为结尾的好数组的数量。
维护当前连续相同元素的长度 \(cnt\)。
- 若 \(cnt >= a[i]\)，说明以 \(i\) 结尾的长度为 \(a[i]\) 的子数组是一个合法块，此时 \(dp[i] = dp[i – a[i]] + 1\)，表示在前面好数组基础上接一个块；
- 否则 \(dp[i] = 0\)。
答案为所有 \(dp[i]\) 之和。
关键代码：
void miyan()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<ll> dp(n + 1, 0);
ll ans = 0;
for (int i = 1, cnt = 1; i <= n; ++i)
{
if (i > 1 && a[i] == a[i - 1])
++cnt;
else
cnt = 1;
if (cnt >= a[i])
dp[i] = dp[i - a[i]] + 1;
ans += dp[i];
}
cout << ans << endl;
}F – Sequence Covering
算法：
贪心，\(ST\)表。
思路：
贪心策略：
在位置 \(i\)，我们向后看 \(k\) 步（即 \([i, \min(n, i+k)]\)），找到这个范围内的最大值 \(val\)。
- \(last > val\) 之前选择的数字比当前的最大值大，花 \(1\) 代价把 \(last\) 延续到当前位置 \(i\)。
- 注：如果 \(k=0\)，没法延续，进入情况 \(B\)。
- \(val \ge last\) 在范围内找到了一个比 \(last\) 更大（或相等）的数 \(val\)。既然能变大，我们肯定选 \(val\)。
由于需要寻找区间最大值，可以使用 \(ST\)表维护，并多维护最大值位置。
关键代码：
struct ST
{
int n;
vector<int> arr;
vector<int> log2;
vector<vector<pii>> st_max, st_min;
ST(int _n, const vector<int> &_arr)
{
n = _n;
arr = _arr;
log2.resize(n + 1, 0);
for (int i = 2; i <= n; ++i)
log2[i] = log2[i >> 1] + 1;
st_max.resize(n + 1, vector<pii>(log2[n] + 1));
st_min.resize(n + 1, vector<pii>(log2[n] + 1));
init();
}
void init()
{
for (int i = 1; i <= n; ++i)
st_max[i][0] = st_min[i][0] = {arr[i], -i};
for (int j = 1; j <= log2[n]; ++j)
{
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
{
st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1 << (j - 1))][j - 1]);
}
}
}
pii query_max(int l, int r)
{
int len = log2[r - l + 1];
return max(st_max[l][len], st_max[r - (1 << len) + 1][len]);
}
pii query_min(int l, int r)
{
int len = log2[r - l + 1];
return min(st_min[l][len], st_min[r - (1 << len) + 1][len]);
}
};
void miyan()
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
ST st(n, a);
vector<int> ans(n + 1);
int last = INT_MIN;
for (int i = 1; i <= n;)
{
int r = i + k;
r = max(n, r);
auto [val, pos] = st.query_max(i, r);
pos = -pos;
if (val < last && k)
{
--k;
ans[i] = last;
++i;
}
else
{
for (int j = i; j <= pos; ++j)
ans[j] = val;
k -= pos - i;
i = pos + 1;
last = val;
}
}
for (int i = 1; i <= n; ++i)
cout << ans[i] << ' ';
cout << endl;
}
