链接：https://qoj.ac/contest/1290
A
表达式板子。
\(O(|s|)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<array<i64, 3>> info;
vector<char> o;
auto work = [&]() {
char op = o.back();
o.pop_back();
auto [r, r1, r2] = info.back();
info.pop_back();
auto [l, l1, l2] = info.back();
info.pop_back();
if (op == '-') {
info.push_back({l - r, l1 + r2, l2 + r1});
} else {
info.push_back({l + r, l1 + r1, l2 + r2});
}
};
auto run = [&](string &s) {
for (int i = 0; i < n; ) {
if (s[i] == '?') {
info.push_back({0, 1, 0});
i++;
} else if (isdigit(s[i])) {
i64 res = 0;
for ( ; i < n && isdigit(s[i]); i++) {
res *= 10;
res += s[i] - '0';
}
info.push_back({res, 0, 0});
} else {
if (s[i] == '(') {
o.push_back('(');
} else if (s[i] == ')') {
while (o.back() != '(') {
work();
}
o.pop_back();
} else {
while (!o.empty() && o.back() != '(') {
work();
}
o.push_back(s[i]);
}
i++;
}
}
while (!o.empty()) {
work();
}
auto [res, add, del] = info.back();
info.pop_back();
return res + 9 * add;
};
cout << run(s) << '\n';
return 0;
}
E
每次选两个数减 \(1\)，问能操作几次。
\(O(n)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
i64 sum = 0;
int mx = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
mx = max(mx, a[i]);
}
if (mx * 2LL <= sum) {
cout << sum / 2 << '\n';
} else {
cout << sum - mx << '\n';
}
return 0;
}
G
对顶堆快速中位数。
\(O(n\log n)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, a0;
cin >> n >> a0;
vector<int> a(n + 1);
a[0] = a0;
for (int i = 1; i <= n; i++) {
a[i] = (998244353LL * a[i - 1] + 1000000007) % 1000000009;
}
vector<int> p(n + 1);
iota(p.begin(), p.end(), 0);
for (int i = 1; i <= n; i++) {
swap(p[i], p[(a[i] % i) + 1]);
}
i64 pw = 19;
i64 ans = 0;
priority_queue<int> q1;
priority_queue<int, vector<int>, greater<>> q2;
for (int i = 1; i <= n; i++) {
q1.push(p[i]);
while ((int) q1.size() > (int) q2.size() + 1) {
auto cur = q1.top();
q1.pop();
q2.push(cur);
}
while (!q1.empty() && !q2.empty()) {
auto cur1 = q1.top();
auto cur2 = q2.top();
q1.pop();
q2.pop();
if (cur1 > cur2) {
q1.push(cur2);
q2.push(cur1);
} else {
q1.push(cur1);
q2.push(cur2);
break;
}
}
ans = (ans + 1LL * q1.top() * pw % 998244353) % 998244353;
pw = (pw * 19) % 998244353;
}
cout << ans << '\n';
return 0;
}
I
模拟。
\(O(n\cdot q)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<array<int, 2>> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1];
}
while (q--) {
int o;
cin >> o;
if (o == 1) {
int x, y;
cin >> x >> y;
x--;
a[x][1] = y;
} else {
int x;
cin >> x;
x--;
int ok = 0;
int mx = 0;
for (int i = 0; i < n; i++) {
if (a[i][1] == 1) {
ok = 1;
mx = max(mx, a[i][0]);
}
}
if (a[x][0] == mx && a[x][1] == 1) {
cout << "1\n";
} else {
int tm = m;
if (ok) {
tm = m - 1;
}
for (int i = 0; i < n; i++) {
if (ok && a[i][0] == mx && a[i][1] == 1) {
continue;
}
if (i != x) {
if (a[i][0] > a[x][0]) {
tm--;
}
}
}
cout << (tm >= 1 ? 1 : 0) << '\n';
}
}
}
return 0;
}
J
\(\text{bfs}\)。
复杂度不会算。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int sx = 0, sy = 0, tx = n - 1, ty = n - 1;
queue<array<int, 3>> q;
q.push({0, sx, sy});
int dx[] = {+1, -1, +0, +0};
int dy[] = {+0, +0, +1, -1};
vector<vector<int>> vis(n, vector<int>(n));
vis[sx][sy] = 1;
while (!q.empty()) {
auto [res, x, y] = q.front();
if (x == tx && y == ty) {
cout << res << '\n';
return 0;
}
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
continue;
}
if (vis[nx][ny]) {
continue;
}
if (a[nx][ny] == '*') {
continue;
}
vis[nx][ny] = 1;
q.push({res + 1, nx, ny});
}
int X = x, Y = y;
for (int i = 0; i <= k; i++) {
int nx = X;
int ny = Y;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
break;
}
if (vis[nx][ny]) {
int tmp = X;
X = Y + 1;
Y = tmp;
continue;
}
if (a[nx][ny] == '*') {
int tmp = X;
X = Y + 1;
Y = tmp;
continue;
}
vis[nx][ny] = 1;
q.push({res + 1, nx, ny});
int tmp = X;
X = Y + 1;
Y = tmp;
}
}
cout << "-1\n";
return 0;
}
K
签到。
\(O(n\cdot m)\)。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < min(m, n); i++) {
a[i][i] = 1;
}
if (n < m) {
for (int i = m - 1; i >= min(m, n); i -= 2) {
a[n - 1][i] = 1;
}
} else {
for (int i = n - 1; i >= min(n, m); i -= 2) {
a[i][m - 1] = 1;
}
}
cout << min(n, m) + (abs(n - m) + 1) / 2 << '\n';
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << a[i][j] << " \n"[j == m - 1];
}
}
return 0;
}