A
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int p[507];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> p[i];
int pos1 = 0, pos2 = 0;
for (int i = 1;i <= n;i++) {
if (p[i] != i) {
pos1 = i;
break;
}
}
for (int i = pos1 + 1;i <= n;i++) {
if (pos1 == p[i]) {
pos2 = i;
break;
}
}
reverse(p + pos1, p + pos2 + 1);
for (int i = 1;i <= n;i++) cout << p[i] << " \n"[i == n];
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[100007];
bool solve() {
int n;
cin >> n;
int mx0 = 0, mx1 = 0;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n;i++) {
if (a[i] & 1) {
if (a[i] < mx1) return false;
mx1 = a[i];
}
else {
if (a[i] < mx0) return false;
mx0 = a[i];
}
}
cout << "YES" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
C
题意
给定一个长为 \(n\) 的排列，将数字看作点，其中的逆序对当作一条边，问这个图有多少个连通块。
题解
知识点：贪心，单调栈。
从左到右遍历，考虑用一个单调递增栈保存之前连通块，用连通块最大数字代表它所在连通块。
之后每加入一个数字，需要和栈顶连通块比较。若小于连通块最大数字，则连通块可以与这个数字连通。随后将这个连通块弹出栈顶，继续比较下一个。
直到没有比这个数字更大的连通块，即不存在逆序对，就将之前与这个数字连通的连通块中取最大值放入栈中，表示这一整个连通块。
若不存在连通块能和这个数字连通，那么就将这个数字放入栈中。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int p[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> p[i];
vector<int> v;
for (int i = 1;i <= n;i++) {
int mx = 0;
while (v.size() && v.back() > p[i]) {
mx = max(mx, v.back());
v.pop_back();
}
v.push_back(mx ? mx : p[i]);
}
cout << v.size() << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题意
有一个 \(n\times m\) 的空白矩阵和一个目标矩阵，可以用一个 \(2\times 2\) 的刷子对其染色（覆盖原来的颜色）。
问能否在若干次染色后，使得空白矩阵变成目标矩阵，并给出染色方案。
题解
知识点：BFS，贪心，构造。
考虑逆推。
我们用每个 \(2 \times 2\) 的区域的左上角坐标，代表这个区域。
一开始，确定若干个 \(2 \times 2\) 的纯色区域，这些一定是可以最后一步染色的。将这些区域规定为最后一步后，这些区域之前是什么颜色并不重要，因为最后总会被覆盖的，因此这些区域的格子可以是任意颜色，作为一个通配符存在。随后，以这些区域为起点，继续往外染色即可。
按照这个规律，问题等价于在一个 \((n-1) \times (m-1)\) 地图上完成遍历连通块的问题。若整张图都被遍历了，那么染色方案是存在，方案倒序即是答案，否则无解。
时间复杂度 \(O(nm)\)
空间复杂度 \(O(nm)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int dt[1007][1007];
int check(int x, int y) {
int color = 0;
for (auto xx : { x,x + 1 }) {
for (auto yy : { y,y + 1 }) {
if (!dt[xx][yy]) continue;
if (!color) color = dt[xx][yy];
if (color != dt[xx][yy]) return -1;
}
}
return color;
}
void deal(int x, int y) {
for (auto xx : { x,x + 1 })
for (auto yy : { y,y + 1 })
dt[xx][yy] = 0;
}
struct node {
int x, y, c;
};
queue<node> q;
bool vis[1007][1007];
vector<node> ans;
void bfs() {
for (int i = 1;i < n;i++)
for (int j = 1;j < m;j++)
if (check(i, j) != -1) q.push({ i,j,check(i,j) });
while (q.size()) {
auto [x, y, c] = q.front();
q.pop();
if (vis[x][y]) continue;
vis[x][y] = 1;
deal(x, y);
if (c) ans.push_back({ x,y,c });
for (auto xx : { x - 1,x,x + 1 }) {
for (auto yy : { y - 1,y,y + 1 }) {
if (xx < 1 || xx >= n || yy < 1 || yy >= m || vis[xx][yy] || check(xx, yy) == -1) continue;
q.push({ xx,yy,check(xx,yy) });
}
}
}
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
cin >> dt[i][j];
bfs();
bool ok = 1;
for (int i = 1;i < n;i++)
for (int j = 1;j < m;j++)
ok &= vis[i][j];
if (ok) {
reverse(ans.begin(), ans.end());
cout << ans.size() << '\n';
for (auto [x, y, c] : ans) cout << x << ' ' << y << ' ' << c << '\n';
}
else cout << -1 << '\n';
return 0;
}
E
题意
给定一个长为 \(n\) 的整数数组 \(a\) ，其中每个数字都有一个颜色。
初始时，所有数字都为 \(0\) ，颜色都为 \(1\) 。
现在完成 \(q\) 个操作，有如下种类：
- 将 \([l,r]\) 的数字染色成 \(c\) 。
- 给所有颜色为 \(c\) 的数字加上 \(x\)。
- 输出 \(a_i\) 。
题解
知识点：珂朵莉树，树状数组，枚举。
我们先考虑操作1都是单点操作的情景。
对于操作2，因为是对所有颜色 \(c\) 的数字加，所以我们没必要枚举每个满足条件的数字，考虑用 \(col_c\) 记录当前对颜色 \(c\) 加了多少，之后遇到操作3询问的数字颜色为 \(c\) 时，输出 \(a_i + col_c\) 即可。
对于操作1，若原来的颜色是 \(c\) ，新的颜色是 \(c'\) ，我们只需要将 \(a_i\) 改为 \(a_i + col_c - col_{c'}\) ，即等价替换了颜色。
对于原题区间操作的操作1，考虑用珂朵莉树维护颜色段一致的区间，随后暴力修改每个相同颜色段区间的数字，用树状数组维护区间修改即可。
虽然这题并没有保证数据随机，但考虑势能分析区间数。每次操作最多新增 \(2\) 段区间，而一次区间减少段数最多为区间新增的段数，因此区间数的变化量绝对值的总和是 \(O(q)\) 的，因此区间修改的复杂度是 \(O(q \log n)\) 的。
时间复杂度 \(O(n + q\log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T>
class ODT {
map<int, T> tree;
public:
ODT(int n = 0, T val = T()) { init(n, val); }
ODT(const vector<T> &src) { init(src); }
void init(int n, T val) {
tree.clear();
tree[1] = val;
tree[n + 1] = T();
}
void init(const vector<T> &src) {
int n = src.size() - 1;
init(n);
for (int i = 1;i <= n;i++) tree[i] = src[i];
}
auto split(int x) {
auto it = prev(tree.upper_bound(x));
return tree.insert({ x,it->second }).first;
}
void assign(int l, int r, T val) {
auto L = split(l), R = split(r + 1);
tree.erase(L, R);
tree[l] = val;
}
};
template <class T>
class Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
node.assign(n + 1, T());
}
void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }
T query(int x) {
T ans = T();
for (int i = x;i >= 1;i -= i & -i) ans += node[i];
return ans;
}
T query(int l, int r) {
T ans = T();
ans += query(r);
ans -= query(l - 1);
return ans;
}
int lower_bound(T val) {
int pos = 0;
for (int i = 1 << __lg(n); i; i >>= 1) {
if (pos + i <= n && node[pos + i] < val) {
pos += i;
val -= node[pos];
}
}
return pos + 1;
}
int upper_bound(T val) {
int pos = 0;
for (int i = 1 << __lg(n); i; i >>= 1) {
if (pos + i <= n && node[pos + i] <= val) {
pos += i;
val -= node[pos];
}
}
return pos + 1;
}
};
ll col[1000007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
ODT<int> odt(n, 1);
Fenwick<ll> fw(n);
auto color = [&](int l, int r, int c) {
auto L = odt.split(l), R = odt.split(r + 1);
for (auto it = L;it != R;it++) {
fw.update(it->first, col[it->second] - col[c]);
fw.update(next(it)->first, -col[it->second] + col[c]);
}
odt.assign(l, r, c);
};
while (q--) {
string op;
cin >> op;
if (op == "Color") {
int l, r, c;
cin >> l >> r >> c;
color(l, r, c);
}
else if (op == "Add") {
int c, x;
cin >> c >> x;
col[c] += x;
}
else {
int x;
cin >> x;
cout << fw.query(1, x) + col[odt.split(x)->second] << '\n';
}
}
return 0;
}