链接：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;
}
}
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;
}
- Programming Provincial Contest Shaanxi Chinaprogramming provincial contest shaanxi programming collegiate provincial contest 2019 programming provincial contest programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong programming provincial collegiate shandong programming collegiate provincial counting programming provincial collegiate sponsored 2023 programming collegiate provincial