Atcoder Beginner Contest 421
A
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
unordered_map<int, string> h;
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i ++) {
string s; cin >> s;
h[i] = s;
}
int x; cin >> x; string s; cin >> s;
if (h[x] != s) puts("No");
else puts("Yes");
return 0;
}
B
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
int a[15];
int f(int x) {
int b[20] = {0}, cnt = 0;
if (x < 0) x = -x;
while (x) b[++ cnt] = x % 10, x /= 10;
int t = 1;
while (!b[t] && t <= cnt) t ++;
int y = 0;
for (int i = t; i <= cnt; i ++) y = y * 10 + b[i];
return y;
}
signed main() {
cin >> a[1] >> a[2];
for (int i = 3; i <= 10; i ++)
a[i] = f(a[i - 1] + a[i - 2]);
printf("%lld\n", a[10]);
return 0;
}
C
简单贪心，注意到分为 \(ABABAB\) 和 \(BABABA\) 两种方案，分别从 \(n \to 1\) 计算一下距离即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
int n;
string s;
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n; cin >> s; string tmp = s;
if (s.size() == 1) {
cout << 0 << endl;
return 0;
}
int ans = 0, j = s.size() - 2;
for (int i = s.size() - 1; i >= 0; i --) {
if (s[i] == 'A') {
if (i != j) {
ans += abs(i - j);
}
j -= 2;
}
}
int ans2 = 0; j = s.size() - 1;
for (int i = s.size() - 1; i >= 0; i --) {
if (s[i] == 'A') {
if (i != j) ans2 += abs(i - j);
j -= 2;
}
}
cout << min(ans, ans2) << endl;
return 0;
}
D
魔怔题目。
首先可以根据题目给出的顺序每次跳当前 \(A_i, B_j\) 中较小的那一段距离然后让较大值减去较小值接着循环。
所以相当于要解一个方程：
\(\left\{\begin{matrix} a + dx_1 \times t = c + dx_2 \times t \\ b + dy_1 \times t = d + dy_2 \times t \end{matrix}\right.\)
然后要讨论 \(dx_1 - dx_2\) 和 \(dy_1 - dy_2\) 是否为 \(0\)，挺魔怔的。
好在样例挺强。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 100010;
int L, n, m;
int sx1, sy1, sx2, sy2;
struct Node { int s, dx, dy; } A[N], B[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> sx1 >> sy1 >> sx2 >> sy2;
cin >> L >> n >> m;
for (int i = 1; i <= n; i ++) {
string s; cin >> s; cin >> A[i].s;
int dx, dy;
if (s == "U") dx = -1, dy = 0;
else if (s == "R") dx = 0, dy = 1;
else if (s == "D") dx = 1, dy = 0;
else dx = 0, dy = -1;
A[i].dx = dx, A[i].dy = dy;
}
for (int i = 1; i <= m; i ++) {
string s; cin >> s; cin >> B[i].s;
int dx, dy;
if (s == "U") dx = -1, dy = 0;
else if (s == "R") dx = 0, dy = 1;
else if (s == "D") dx = 1, dy = 0;
else dx = 0, dy = -1;
B[i].dx = dx, B[i].dy = dy;
}
int ans = 0;
for (int i = 1, j = 1; i <= n && j <= m; ) {
int R = min(A[i].s, B[j].s);
if ((sx2 - sx1) * (A[i].dy - B[j].dy) == (sy2 - sy1) * (A[i].dx - B[j].dx)) {
if (A[i].dy - B[j].dy == 0 && A[i].dx - B[j].dx == 0) {
if (sx1 == sx2 && sy1 == sy2) ans += R;
} else if (A[i].dy - B[j].dy == 0) {
if (sy2 == sy1) {
if ((sx2 - sx1) % (A[i].dx - B[j].dx) == 0) {
int res = (sx2 - sx1) / (A[i].dx - B[j].dx);
if (res > 0 && res <= R) ans ++;
}
}
} else if (A[i].dx - B[j].dx == 0) {
if (sx2 == sx1) {
if ((sy2 - sy1) % (A[i].dy - B[j].dy) == 0) {
int res = (sy2 - sy1) / (A[i].dy - B[j].dy);
if (res > 0 && res <= R) ans ++;
}
}
} else {
if ((sy2 - sy1) % (A[i].dy - B[j].dy) == 0 && (sx2 - sx1) % (A[i].dx - B[j].dx) == 0) {
int res = (sy2 - sy1) / (A[i].dy - B[j].dy);
if (res > 0 && res <= R) ans ++;
}
}
}
if (A[i].s <= B[j].s) {
sx1 += A[i].s * A[i].dx, sy1 += A[i].s * A[i].dy;
sx2 += A[i].s * B[j].dx, sy2 += A[i].s * B[j].dy;
B[j].s -= A[i].s, i ++;
if (!B[j].s) j ++;
} else {
sx1 += B[j].s * A[i].dx, sy1 += B[j].s * A[i].dy;
sx2 += B[j].s * B[j].dx, sy2 += B[j].s * B[j].dy;
A[i].s -= B[j].s, j ++;
if (!A[i].s) i ++;
}
// cout << sx1 << ' ' << sy1 << ' ' << sx2 << ' ' << sy2 << endl;
// cout << ans << endl;
}
cout << ans << endl;
return 0;
}
F
显然要链表，但会发现直接做没办法判断给出的 \(x, y\) 的先后顺序。
考虑离线，只处理所有加入操作，由于不管怎么删除先后的顺序都是一定的所以就对了。
代码改了很久，巨丑。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 1000010;
int Q, idx, hh, tt = 1;
int ne[N], pre[N], p[N], a[N];
int ne2[N], b[N], p2[N], a2[N], idx2;
void init() {
ne[hh] = 2, ne[2] = tt, idx = 2;
pre[tt] = 2, pre[2] = hh;
ne2[0] = 1, ne2[1] = -1, idx2 = 1, p2[0] = 1, a2[1] = 0;
p[0] = 2, a[2] = 0;
}
void insert(int k, int x) {
a[++ idx] = x, p[x] = idx;
ne[idx] = ne[k], pre[idx] = k, pre[ne[k]] = idx, ne[k] = idx;
}
struct Query {
int op, x, y;
} q[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> Q;
init();
for (int i = 1; i <= Q; i ++) {
int op; cin >> op; q[i].op = op;
if (op == 1) {
int x; cin >> x;
p2[i] = ++ idx2, a2[idx2] = i;
ne2[idx2] = ne2[p2[x]], ne2[p2[x]] = idx2;
q[i].x = x;
} else {
int x, y; cin >> x >> y;
q[i].x = x, q[i].y = y;
}
}
int tot = 0;
for (int p = 1; ~p; p = ne2[p]) b[a2[p]] = ++ tot;
// for (int i = 0; i <= Q; i ++) cout << b[i] << ' ';
// cout << endl;
for (int i = 1; i <= Q; i ++) {
int op = q[i].op;
if (op == 1) {
int x = q[i].x;
insert(p[x], i);
} else {
int x = q[i].x, y = q[i].y;
int l = p[x], r = p[y], q, ans = 0;
if (b[x] > b[y]) swap(l, r);
if (l == r) {
cout << 0 << endl;
continue;
}
if (ne[l] == r) {
cout << 0 << endl;
continue;
}
l = ne[l], r = pre[r]; q = l;
for (; q != r; q = ne[q]) ans += a[q];
ans += a[r];
ne[pre[l]] = ne[r]; pre[ne[r]] = pre[l];
cout << ans << endl;
}
// for (int q = hh; q != tt; q = ne[q]) cout << a[q] << ' ';
// cout << endl;
}
return 0;
}
E
简单概率题。
骰子个数很少，所以不妨考虑状压。
令 \(f_{k, S}\) 表示当前倒数第 \(k\) 轮，集合 \(S\) 中的骰子已经被保留，最终的期望值。令 \(T = U \setminus S\)，则有转移：
- \(\sum_{I}P(I)\underset{J \subseteq T}{\max}f_{k - 1, S \cup J} \to f_{k, s} (k > 1)\)，其中 \(I\) 为 \(T\) 中数的一种掷骰后的变幻状态。
- \(\sum_{I}P(I)W(S \cup T) \to f_{k, s}(k = 1)\)。
于是就做完了，对于 \(I\) 的枚举考虑使用六进制状压，比较诡异。
G
序列不递减相当于差分序列大于等于 \(0\)。
所以考虑建差分序列 \(b\)，那么一个操作相当于差分序列一加一减。考虑网络流，进行一下连边：
- 若 \(b_i \geq 0\)，则连边 \(s \to i\)，容量为 \(b_i\)，费用为 \(0\)。
- 若 \(b_i < 0\)，则连边 \(i \to t\)，容量为 \(-b_i\)，费用为 \(0\)。
- 对于 \(b_l + 1, b_{r + 1} - 1\) 的操作，从 \(r + 1 \to l\) 连边，容量为 \(\infty\)，费用为 \(1\)。
- 特殊地连 \(s \to n + 1\)，容量为 \(\infty\)，费用为 \(0\)。
跑最小费用最大流即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 1e16
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 510, M = 2010;
int n, m, a[N], b[N];
int s, t;
int h[N], e[M], ne[M], w[M], cost[M], idx;
int d[N], incf[N], pre[N], vis[N], maxflow, ans;
queue<int> q;
void add(int a, int b, int c, int f) {
e[idx] = b, w[idx] = c, cost[idx] = f, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, w[idx] = 0, cost[idx] = -f, ne[idx] = h[b], h[b] = idx ++;
}
bool spfa() {
for (int i = s; i <= t; i ++) d[i] = INF;
memset(vis, 0, sizeof vis);
while (!q.empty()) q.pop();
d[s] = 0, vis[s] = 1, incf[s] = INF; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (!w[i]) continue;
if (d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i], pre[v] = i;
incf[v] = min(incf[u], w[i]);
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
if (d[t] == INF) return false;
return true;
}
void upd() {
int x = t;
while (x != s) {
int i = pre[x];
w[i] -= incf[t], w[i ^ 1] += incf[t];
x = e[i ^ 1];
}
maxflow += incf[t];
ans += incf[t] * d[t];
}
signed main() {
memset(h, -1, sizeof h);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m; s = 0, t = n + 2;
for (int i = 1; i <= n; i ++) cin >> a[i], b[i] = a[i] - a[i - 1];
int need = 0;
for (int i = 2; i <= n; i ++)
if (b[i] < 0) add(i, t, -b[i], 0), need += -b[i];
else if (b[i] > 0) add(s, i, b[i], 0);
add(s, n + 1, INF, 0);
while (m --) {
int a, b; cin >> a >> b;
add(b + 1, a, INF, 1);
}
while (spfa()) upd();
if (maxflow != need) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
浙公网安备 33010602011771号