CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
签到五分钟，发呆两小时…
Stock Arbitraging
#include <bits/stdc++.h>
using namespace std;
int n, m, r, s = 1e9, b;
int main()
{
scanf("%d%d%d", &n, &m, &r);
for (int i = 0, t; i < n; ++i)
scanf("%d", &t), s = min(s, t);
for (int j = 0, t; j < m; ++j)
scanf("%d", &t), b = max(b, t);
if (b > s)
r += r / s * (b - s);
printf("%d", r);
}
Tiling Challenge
#include <bits/stdc++.h>
using namespace std;
const int N = 63;
char s[N][N];
int n;
bool check(int x, int y)
{
if (x < 0 || x >= n || y < 0 || y >= n || s[x][y] == '#')
return 1;
return s[x][y] = '#', 0;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%s", s[i]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (s[i][j] != '#')
if (check(i, j) || check(i + 1, j - 1) || check(i + 1, j) || check(i + 1, j + 1) || check(i + 2, j))
return printf("NO"), 0;
printf("YES");
}
Prefix Sum Primes
尽量凑 2 和奇数即可。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
scanf("%d", &n);
for (int i = 0, t; i < n; ++i)
scanf("%d", &t), m += t & 1;
if (n -= m)
printf("2 "), --n;
if (m)
printf("1 "), --m;
for (int i = 0; i < n; ++i)
printf("2 ");
for (int i = 0; i < m; ++i)
printf("1 ");
}
Three Religions
现场想到 DP，无奈还是不会敲…
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9, M = 255;
char s[N], d[5][M];
int n, q, len[5], f[M][M][M], nxt[N][31];
int main()
{
scanf("%d%d%s", &n, &q, s + 1);
fill(nxt[n + 1], nxt[n + 1] + 26, n + 1);
fill(nxt[n], nxt[n] + 26, n + 1);
for (int i = n; i; --i)
{
copy(nxt[i], nxt[i] + 26, nxt[i - 1]);
nxt[i - 1][s[i] - 'a'] = i;
}
for (int x; q--; printf(f[len[1]][len[2]][len[3]] <= n ? "YES\n" : "NO\n"))
{
scanf("%s%d", s, &x);
if (s[0] == '-')
{
--len[x];
continue;
}
scanf("%s", &d[x][++len[x]]);
for (int i = x == 1 ? len[x] : 0; i <= len[1]; ++i)
for (int j = x == 2 ? len[x] : 0; j <= len[2]; ++j)
for (int k = x == 3 ? len[x] : 0; k <= len[3]; ++k)
{
f[i][j][k] = n + 1;
if (i)
f[i][j][k] = min(f[i][j][k], nxt[f[i - 1][j][k]][d[1][i] - 'a']);
if (j)
f[i][j][k] = min(f[i][j][k], nxt[f[i][j - 1][k]][d[2][j] - 'a']);
if (k)
f[i][j][k] = min(f[i][j][k], nxt[f[i][j][k - 1]][d[3][k] - 'a']);
}
}
}
Tree Generator™
线段树来维护答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
char s[N];
struct Node
{
int sum, pmx, lmx, mi, ma, d;
friend Node operator+(const Node &l, const Node &r)
{
return {l.sum + r.sum,
max(l.pmx, max(r.ma - 2 * l.mi + l.sum, r.pmx - l.sum)),
max(l.lmx, max(r.lmx - l.sum, l.ma - 2 * r.mi - 2 * l.sum)),
min(l.mi, r.mi + l.sum),
max(l.ma, r.ma + l.sum),
max(max(l.d, r.d), max(l.ma + r.pmx - l.sum, l.lmx + l.sum + r.ma))};
}
} v[N * 4];
void build(int l, int r, int x = 1)
{
if (l == r)
{
r = s[l] == '(' ? 1 : -1, v[x] = {r, -r, -r, r, r, 0};
return;
}
int m = l + r >> 1;
build(l, m, x << 1);
build(m + 1, r, x << 1 | 1);
v[x] = v[x << 1] + v[x << 1 | 1];
}
void update(int l, int r, int p, int x = 1)
{
if (l == r)
return build(l, r, x);
int m = l + r >> 1;
if (p <= m)
update(l, m, p, x << 1);
else
update(m + 1, r, p, x << 1 | 1);
v[x] = v[x << 1] + v[x << 1 | 1];
}
int main()
{
int n, m, x, y;
scanf("%d%d%s", &n, &m, s + 1);
build(1, n = n * 2 - 2);
for (printf("%d\n", v[1].d); m--; printf("%d\n", v[1].d))
scanf("%d%d", &x, &y),
swap(s[x], s[y]),
update(1, n, x),
update(1, n, y);
}