AtCoder Beginner Contest 237题解
AtCoder Beginner Contest 237
A - Not Overflow
题目描述：给你一个在long long范围的整数，判断其是否在int范围内。
思路：根据题意模拟即可
时间复杂度：\(O(1)\)
参考代码：
void solve() {
long long n;
cin >> n;
if (n >= INT_MIN && n <= INT_MAX) cout << "Yes" << '\n';
else cout << "No" << '\n';
return;
}
B - Matrix Transposition
题目描述：给你一个\(n \times m\)的矩阵\(A\)，输出\(A^T\)。
思路：根据题意模拟即可。
时间复杂度：\(O(nm)\)
参考代码：
void solve() {
int n, m;
cin >> n >> m;
vector>a(n + 1, vector(m + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) cin >> a[i][j];
}
for (int j = 1; j <= m; ++j) {
for (int i = 1; i <= n; ++i) cout << a[i][j] << ' ';
cout << '\n';
}
return;
}
C - kasaka
题目描述：给你一个字符串\(s\)，问是否可以通过在\(s\)的前面增加字符a，使得字符串变成回文串。
思路：在字符串\(s\)两边删除相同数量的字符a，然后将右边多余的字符a也删去，判断剩下的字符串是否是回文即可。
时间复杂度：\(O(n)\)
参考代码：
void solve() {
string s;
cin >> s;
int n = s.size();
string t = s;
reverse(t.begin(), t.end());
if (s == t) {
cout << "Yes" << '\n';
return;
}
int lr = 0, rs = n - 1;
while (lr < rs && s[lr] == s[rs] && s[rs] == 'a') ++lr, --rs;
while (lr < rs && s[rs] == 'a') --rs;
t = s.substr(lr, rs - lr + 1);
s = t;
reverse(t.begin(), t.end());
if (s == t) {
cout << "Yes" << '\n';
return;
}
cout << "No" << '\n';
return;
}
D - LR insertion
题目描述：有一个集合\(S\)，初始时只有元素\(0\)，现在你需要依次放入\(1 \sim n\)，放入第\(i\)个数时会告诉你一个命令，表示将第\(i\)个数字放在第\(i - 1\)个数字的左边还是右边，让你输出最终序列。
思路：比较明显的链表操作，可以使用数组模拟链表即可。当然注意到第\(i\)个数字只与第\(i - 1\)个数字有关，且要么放在其左边要么放在其右边，抽象成树形结构就是二叉树，故该序列就等价于该二叉树的中序遍历。
时间复杂度：\(O(n)\)
数组模拟链表：
void solve() {
int n;
cin >> n;
string s;
cin >> s;
s = ' ' + s;
vector>res(n + 1, vector(2, -1));
for (int i = 1; i <= n; ++i) {
if (s[i] == 'L') {
int dx = res[i - 1][0];
if (dx != -1) {
res[dx][1] = i;
res[i][0] = dx;
}
res[i][1] = i - 1;
res[i - 1][0] = i;
}
else {
int dx = res[i - 1][1];
if (dx != -1) {
res[dx][0] = i;
res[i][1] = dx;
}
res[i][0] = i - 1;
res[i - 1][1] = i;
}
}
int head = 0;
for (int i = 0; i <= n; ++i) {
if (res[i][0] != -1) continue;
head = i;
break;
}
while (head != -1) {
cout << head << ' ';
head = res[head][1];
}
cout << '\n';
return;
}
中序遍历：
void solve() {
int n;
cin >> n;
vector>a(n + 2, vector(2, 0));
string s;
cin >> s;
for (int i = 1; i <= n; ++i) {
if (s[i - 1] == 'L') a[i][0] = i + 1;
else a[i][1] = i + 1;
}
auto dfs = [&](auto dfs, int u)->void {
if (a[u][0] != 0) dfs(dfs, a[u][0]);
cout << u - 1 << ' ';
if (a[u][1] != 0) dfs(dfs, a[u][1]);
return;
};
dfs(dfs, 1);
cout << '\n';
return;
}
E - Skiing
题目描述：有\(n\)座山编号\(1 \sim n\)，第\(i\)座山有一个高度\(h_i\)。有\(m\)个索桥连接一些山，这些索桥是双向的。若从高度高的山到高度低的山，假设这两座山编号为\(x , y\)，则可获得价值\(h_x - h_y\)；若从高度低的山到高度高的山，则获得价值为\(2(h_x - h_y) (h_x < h_y)\)。你有初始价值\(0\)，然后从\(1\)号山出发，你可以在任意山结束，问你最终能获得的最大价值。
思路：我们可以假设正向边是正权，反向边是负权，我们可以使用BFS，然后保证每一座山至少访问一次，再在之后的广搜中使用更大的价值更新当前点。最终遍历所有点取其价值的最大值。
时间复杂度：\(O(n + m)\)
参考代码：
void solve() {
int n, m;
cin >> n >> m;
vector>graph(n + 1);
vectorH(n + 1, 0);
for (int i = 1; i <= n; ++i) cin >> H[i];
int u, v;
vectordis(n + 1, 0);
vectorvis(n + 1, 0);
for (int i = 1; i <= m; ++i) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
queueq;
q.push(1);
vis[1] = true;
while (!q.empty()) {
u = q.front();
q.pop();
for (auto v : graph[u]) {
long long dx = dis[u] + (H[u] >= H[v] ? H[u] - H[v] : 2ll * (H[u] - H[v]));
if (vis[v] == false) dis[v] = dx, vis[v] = true, q.push(v);
if (dis[v] < dx) {
dis[v] = dx;
q.push(v);
}
}
}
long long res = 0;
for (int i = 1; i <= n; ++i) res = max(res, dis[i]);
cout << res << '\n';
return;
}
F - |LIS| = 3
题目描述：你需要构造一个LIS = 3的长度为\(n\)的数组\(a\)，且对于任意的\(a_i\)满足\(1 \leq a_i \leq m\)。问这样的\(a\)的方案数。对998244353取模。
数据范围：\(3 \leq n \leq 1000 , 3 \leq m \leq 10\)。
思路：比较明显的dp，定义状态\(f_{i , j ,k , r}\)表示对于前\(i\)个数字，LIS为子集(j , k , r)的方案数。转移方程为：
初始条件\(f_{0 , m , m , m} = 1\)。
最终答案为：
\[\sum\limits_{i = 0}^{m - 1}\sum\limits_{j = 0}^{m - 1}\sum\limits_{k = 0}^{m - 1} f_{n , i , j , k} \]时间复杂度：\(O(nm^4)\)
参考代码：
const int mod = 998244353;
void solve() {
int n, m;
cin >> n >> m;
vector>>>f(n + 1, vector>>(m + 1, vector>(m + 1, vector(m + 1, 0))));
f[0][m][m][m] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= m; ++k) {
for (int r = 0; r <= m; ++r) {
int dx = f[i][j][k][r];
if (dx == 0) continue;
for (int x = 0; x < m; ++x) {
if (x <= j) f[i + 1][x][k][r] = (f[i + 1][x][k][r] + dx) % mod;
else if (x <= k) f[i + 1][j][x][r] = (f[i + 1][j][x][r] + dx) % mod;
else if (x <= r)f[i + 1][j][k][x] = (f[i + 1][j][k][x] + dx) % mod;
}
}
}
}
}
int res = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j)
for (int k = 0; k < m; ++k)
res = (res + f[n][i][j][k]) % mod;
cout << res << '\n';
return;
}
G - Range Sort Query
题目描述：给你一个长度为\(n\)的排列\(P\)，有\(m\)次操作，每次操作给你三个数字op lr rs。含义如下：
op = 1表示将区间[lr , rs]内的元素按照升序排列op = 2表示将区间[lr , rs]内的元素按照降序排列
最后问元素\(x\)所在的位置的下标。（下标从\(1\)开始编号）。
思路：此题与P2824 [HEOI2016/TJOI2016]排序 的题目描述无不同考虑到这题的询问，需要寻求一种在线的解法，赛时找了博客 中的代码进行了魔改。涉及线段树合并和分裂的相关知识，可以找寻相关博客学习。
时间复杂度：\(O((n + m)logn + nlogn)\) 后一个\(nlogn\)是求解答案时需要的最坏复杂度
参考代码：
#include
using ll = long long;
const int maxn = 300010;
struct Tree {
Tree* ls, * rs;
int l, r, v;
Tree() {
ls = rs = NULL;
l = r = v = 0;
}
inline void pushup() { if (this->l != this->r) this->v = (this->ls ? this->ls->v : 0) + (this->rs ? this->rs->v : 0); else this->v = 1; }
};
struct OP {
int l, r;
bool up;
Tree* rot;
inline bool operator<(const OP& _others) const {
return this->r < _others.r;
}
OP(int _l = 0, int _r = 0, bool _up = 0, Tree* _rot = 0) {
l = _l; r = _r; up = _up; rot = _rot;
}
};
OP temp;
std::sets;
int n, m;
int MU[maxn];
void split(int, bool);
void insert(Tree*, int, int, int);
void split(Tree*, Tree*, Tree*, int);
Tree* merge(Tree*, Tree*);
int query(Tree*, int);
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
using std::cin;
using std::cout;
int x;
cin >> n >> m >> x;
for (int i = 1; i <= n; ++i) {
auto _rot = new Tree;
cin >> MU[i];
insert(_rot, 1, n, MU[i]); s.insert(OP(i, i, true, _rot));
}
for (int j = 1, a, b, c; j <= m; ++j) {
cin >> a >> b >> c;
--a;
split(b, true); split(c + 1, false);
auto l = s.lower_bound({ 0, b, true, NULL }), r = s.lower_bound({ 0, c + 1, true, NULL });
auto _tmp = *l;
for (auto i = s.erase(l); i != r; i = s.erase(i)) {
_tmp.rot = merge(_tmp.rot, (*i).rot);
}
_tmp.l = b; _tmp.r = c; _tmp.up = !a;
s.insert(_tmp);
}
for (int i = 1; i <= n; ++i) {
int q = i;
auto _ans = s.lower_bound({ 0, q, true, NULL }); auto ans = *_ans;
int k = ans.up ? q - ans.l + 1 : ans.r - q + 1;
q = query(ans.rot, k);
if (q == x) {
cout << i << '\n';
return 0;
}
}
return 0;
}
int query(Tree* u, int k) {
if (u->l == u->r) return u->l;
if (!u->ls) return query(u->rs, k);
if (u->ls->v >= k) return query(u->ls, k);
return query(u->rs, k - u->ls->v);
}
Tree* merge(Tree* u, Tree* v) {
if (!u) return v; else if (!v) return u;
u->v += v->v;
u->ls = merge(u->ls, v->ls);
u->rs = merge(u->rs, v->rs);
return u;
}
void insert(Tree* u, int l, int r, int v) {
++u->v;
if ((u->l = l) == (u->r = r)) return;
int mid = (l + r) >> 1;
if (v <= mid) insert(u->ls = new Tree, l, mid, v);
else insert(u->rs = new Tree, mid + 1, r, v);
}
void split(int x, bool isfront) {
auto k = s.lower_bound({ 0, x, true, NULL }); if (k == s.end()) return; auto t = *k;
if (t.l == x) return;
s.erase(k);
int _k = (isfront ? t.r - x + 1 : x - t.l), len = t.r - t.l + 1;
if (t.up == isfront) {
Tree* _rot = new Tree;
_k = len - _k;
if (!_k) {
s.insert(t); return;
}
split(t.rot, t.rot, _rot, _k);
if (!t.up) {
_k = len - _k; std::swap(_rot, t.rot);
}
s.insert({ t.l, t.l + _k - 1, t.up, t.rot });
s.insert({ t.l + _k, t.r, t.up, _rot });
}
else {
Tree* _rot = new Tree;
if (!_k) {
s.insert(t); return;
}
split(t.rot, t.rot, _rot, _k);
if (!t.up) {
std::swap(t.rot, _rot); _k = len - _k;
}
s.insert({ t.l, t.l + _k - 1, t.up, t.rot });
s.insert({ t.l + _k, t.r, t.up, _rot });
}
}
void split(Tree* u, Tree* l, Tree* r, int k) {
l->l = r->l = u->l; r->r = l->r = u->r;
if (!u->ls) split(u->rs, l->rs ? l->rs : l->rs = new Tree, r->rs ? r->rs : r->rs = new Tree, k);
else if (k == u->ls->v) {
l->ls = u->ls; r->rs = u->rs; l->rs = NULL; r->ls = NULL;
}
else if (k < u->ls->v) {
split(u->ls, l->ls ? l->ls : l->ls = new Tree, r->ls ? r->ls : r->ls = new Tree, k);
r->rs = u->rs; l->rs = NULL;
}
else {
split(u->rs, l->rs ? l->rs : l->rs = new Tree, r->rs ? r->rs : r->rs = new Tree, k - u->ls->v);
l->ls = u->ls; r->ls = NULL;
}
l->pushup(); r->pushup();
}