- C20250021's blog
Day 3
-
C20250021
LV 10
@
2024-1-31 11:34:46
7:30楼下等车，等了30min到8点车没到，发现车追尾了，走路走了一个小时，路程3.5km，走到1/3路程的时候下雨了:(，到机房的时候寂静浑身湿了。
简要题解：
A
水
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a, c, e;
char b, d;
signed main() {
int res;
scanf("%d %c %d %c %d", &a, &b, &c, &d, &e);
if (b == '+') {
if (d == '+')
cout << (a + c + e);
if (d == '-')
cout << (a + c - e);
if (d == '*')
cout << (a + c * e);
if (d == '/')
cout << (a + c / e);
if (d == '%')
cout << (a + c % e);
}
if (b == '-') {
if (d == '+')
cout << (a - c + e);
if (d == '-')
cout << (a - c - e);
if (d == '*')
cout << (a - c * e);
if (d == '/')
cout << (a - c / e);
if (d == '%')
cout << (a - c % e);
}
if (b == '*') {
if (d == '+')
cout << (a * c + e);
if (d == '-')
cout << (a * c - e);
if (d == '*')
cout << (a * c * e);
if (d == '/')
cout << (a * c / e);
if (d == '%')
cout << (a * c % e);
}
if (b == '/') {
if (d == '+')
cout << (a / c + e);
if (d == '-')
cout << (a / c - e);
if (d == '*')
cout << (a / c * e);
if (d == '/')
cout << (a / c / e);
if (d == '%')
cout << (a / c % e);
}
if (b == '%') {
if (d == '+')
cout << (a % c + e);
if (d == '-')
cout << (a % c - e);
if (d == '*')
cout << (a % c * e);
if (d == '/')
cout << (a % c / e);
if (d == '%')
cout << (a % c % e);
}
}
B
easy
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
int n, m, p;
int cnt = 0, ans = 0;
signed main() {
cin >> n >> m >> p;
for (int i = 1, x; i <= n; i++) {
cin >> x;
if (x < p) {
if (cnt >= m) {
ans += (cnt - m + 1);
}
cnt = 0;
} else
cnt++;
}
cout << ans + (cnt >= m ? (cnt - m + 1) : 0) << endl;
}
C
预处理出一些空间，0~w-1为空地，w~n+w-1为积木，n+w~n+2*w为空地。
然后记录大于 h 和小于 h 的个数取 min
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
int n, w, h;
int a[MAXN];
bool check() {
int res = 0;
for (int i = w; i < n + w; i++) res += a[i];
return (res >= w * h);
}
signed main() {
cin >> n >> w >> h;
for (int i = 0; i < w; i++) a[i] = 0;
for (int i = w; i < n + w; i++) cin >> a[i];
for (int i = n + w; i < n + 2 * w; i++) a[i] = 0;
if (!check()) {
puts("-1");
exit(0);
}
int pos = 0, neg = 0, minn;
for (int i = 0; i < w; i++) {
if (a[i] > h)
pos += (a[i] - h);
else
neg += (h - a[i]);
}
minn = max(pos, neg);
for (int i = w; i < n + 2 * w; i++) {
if (a[i] > h)
pos += (a[i] - h);
else
neg += (h - a[i]);
if (a[i - w] > h)
pos -= (a[i - w] - h);
else
neg -= (h - a[i - w]);
minn = min(minn, max(pos, neg));
}
cout << minn << endl;
}
D
首先暴力，喜得 20pts。
考虑 优化，用set枚举，如果有多个区间包含，优先选择最小的区间。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
int n, m;
int now = 0, ans = 0;
pair<int, int> a[MAXN];
int b[MAXN];
multiset<int> st;
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
for (int i = 1; i <= m; i++) cin >> b[i];
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);
for (int i = 1; i <= m; i++) {
for (; now < n && a[now + 1].first <= b[i]; now++) st.insert(a[now + 1].second);
while (!st.empty() && *st.begin() < b[i]) st.erase(st.begin());
if (!st.empty()) {
st.erase(st.begin());
ans++;
}
}
cout << ans << endl;
return 0;
}
E
很容易能想到4维dp。
优化一下能得到三维dp。
发现会超时，我们将第一维滚动就可以了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 10;
const int MR = 2e2 + 10;
const int INF = 0x3f3f3f3f;
int n, l;
int c[MR][MR], p[MAXN];
int dp[2][MR][MR];
int now = 0;
signed main() {
freopen("server.in", "r", stdin);
freopen("server.out", "w", stdout);
memset(dp[0], INF, sizeof dp[0]);
dp[0][1][2] = 0;
p[0] = 3;
cin >> l >> n;
for (int i = 1; i <= l; i++) {
for (int j = 1; j <= l; j++) {
cin >> c[i][j];
}
}
for (int i = 1; i <= n; i++) cin >> p[i];
int ans = INF;
for (int i = 1; i <= n; i++) {
now ^= 1;
memset(dp[now], INF, sizeof dp[now]);
for (int j = 1; j <= l; j++) {
if (j != p[i - 1]) {
for (int k = 1; k <= l; k++) {
// cout << i <<' ' << j << ' ' << k << endl;
if (j != k && k != p[i - 1]) {
if (j != p[i] && k != p[i])
dp[now][j][k] = min(dp[now][j][k], dp[now ^ 1][j][k] + c[p[i - 1]][p[i]]);
if (j != p[i])
dp[now][j][p[i - 1]] = min(dp[now][j][p[i - 1]], dp[now ^ 1][j][k] + c[k][p[i]]);
if (k != p[i])
dp[now][p[i - 1]][k] = min(dp[now][p[i - 1]][k], dp[now ^ 1][j][k] + c[j][p[i]]);
}
}
}
}
}
for (int i = 1; i <= l; i++) {
for (int j = 1; j <= l; j++) {
if (i == j && i == p[n] && j == p[n])
continue;
ans = min(ans, dp[now][i][j]);
}
}
cout << ans << endl;
return 0;
}
F
善用人类思维。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
int n;
char s[MAXN];
int lt[MAXN], rt[MAXN];
int cnt, pos[MAXN];
int dp[MAXN];
void init() {
int now = n + 1;
for (int i = cnt; i >= 1; i--) {
if (s[pos[i]] != '.') {
rt[i] = now - 1;
if (s[pos[i]] == 'L')
now = pos[i];
}
}
now = 0;
for (int i = 1; i <= cnt; i++) {
if (s[pos[i]] != '.') {
lt[i] = now + 1;
if (s[pos[i]] == 'R')
now = pos[i];
}
}
for (int i = 1; i <= cnt; i++) {
if (s[pos[i]] == 'L')
rt[i] = pos[i];
if (s[pos[i]] == 'R')
lt[i] = pos[i];
}
}
signed main() {
cin >> (s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++)
if (s[i] != '.')
pos[++cnt] = i;
init();
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = cnt; j >= 1; j--) {
if (lt[j] <= i && i <= rt[j]) {
dp[j] = (dp[j] + dp[j - 1]) % MOD;
}
}
}
cout << dp[cnt];
}
G
写了个线段树+数剖的东东。
有一个简单的方法用倍增+记忆化，没调出来。
#include <bits/stdc++.h>
using namespace std;
#define N 400001
#define ll long long
inline int read() {
int x = 0, s = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-')
s = -1;
c = getchar();
}
while (isdigit(c)) {
x = x * 10 + (c ^ '0');
c = getchar();
}
return x * s;
}
struct node {
int v, next;
} t[N << 1];
int f[N];
int n, m;
ll dp[N];
int bian = 0;
inline void add(int u, int v) {
t[++bian] = (node){ v, f[u] }, f[u] = bian;
return;
}
struct piao {
int x, k, cost;
inline void insert() {
x = read(), k = read(), cost = read();
return;
}
} g[N];
int top[N], fa[N], son[N], siz[N], deth[N];
int dfn[N], rev[N], id = 0;
#define v t[i].v
void dfs1(int now, int father) {
fa[now] = father;
siz[now] = 1;
deth[now] = deth[father] + 1;
for (int i = f[now]; i; i = t[i].next) {
if (v != father) {
dfs1(v, now);
siz[now] += siz[v];
if (siz[v] > siz[son[now]])
son[now] = v;
}
}
return;
}
void dfs2(int now, int tp) {
top[now] = tp;
dfn[now] = ++id;
rev[id] = now;
if (!son[now])
return;
dfs2(son[now], tp);
for (int i = f[now]; i; i = t[i].next) {
if (v != fa[now] && v != son[now])
dfs2(v, v);
}
return;
}
struct tree {
ll minn;
} e[N << 2];
inline void pushup(int o) {
e[o].minn = min(e[o << 1].minn, e[o << 1 | 1].minn);
return;
}
void build(int o, int l, int r) {
if (l == r) {
e[o].minn = (ll)1e18;
return;
}
int mid = l + r >> 1;
build(o << 1, l, mid);
build(o << 1 | 1, mid + 1, r);
pushup(o);
return;
}
void update(int o, int l, int r, int x, ll k) {
if (l > x || r < x)
return;
if (l == r && l == x) {
e[o].minn = min(e[o].minn, (ll)k);
return;
}
int mid = l + r >> 1;
update(o << 1, l, mid, x, k);
update(o << 1 | 1, mid + 1, r, x, k);
pushup(o);
return;
}
ll query(int o, int l, int r, int in, int end) {
if (l > end || r < in) {
return (ll)1e18;
}
if (l >= in && r <= end) {
return e[o].minn;
}
int mid = l + r >> 1;
return min(query(o << 1, l, mid, in, end), query(o << 1 | 1, mid + 1, r, in, end));
}
ll ask_min(int x, int len) {
ll now = x, temp = (ll)1e18;
while (deth[x] - deth[top[now]] <= len && now) {
temp = min(temp, query(1, 1, n, dfn[top[now]], dfn[now]));
now = fa[top[now]];
}
if (now == 1 || deth[x] - deth[now] > len)
return temp;
ll l = dfn[top[now]], r = dfn[now], pos = r;
ll mid = l + r >> 1;
while (l <= r) {
int mid = l + r >> 1;
if (deth[x] - deth[rev[mid]] <= len)
pos = mid, r = mid - 1;
else
l = mid + 1;
}
temp = min(temp, query(1, 1, n, pos, dfn[now]));
return temp;
}
bool cmp(piao a, piao b) { return dfn[a.x] < dfn[b.x]; }
int main() {
freopen("match.in", "r", stdin);
freopen("match.out", "w", stdout);
n = read(), m = read();
int Q = read();
for (int i = 1; i < n; i++) {
int x = read(), y = read();
add(x, y);
add(y, x);
}
dfs1(1, 0);
dfs2(1, 1);
for (int i = 1; i <= m; i++) g[i].insert();
sort(g + 1, g + m + 1, cmp);
memset(dp, 37, sizeof(dp));
dp[1] = 0;
build(1, 1, n);
update(1, 1, n, 1, 0);
for (int i = 1; i <= m; i++) {
int x = g[i].x, k = g[i].k, cost = g[i].cost;
if (x == 1)
continue;
ll temp = ask_min(x, k) + cost;
if (temp < dp[x]) {
dp[x] = min(dp[x], temp);
update(1, 1, n, dfn[x], dp[x]);
}
}
while (Q--) {
int x = read();
printf("%lld\n", dp[x]);
}
return 0;
}
H
赛时没想出来。
以后有时间再补吧。
中午回家又吃了一个菌菇牛肉饭，好吃:)
下午写了一个抽象的东西，尝试启动⚪但是失败了（悲
晚上看了一讲回放，10点左右就睡了。