2023.7月初模拟赛总结
前言：
近期（约）3天比了3场模拟赛，都源于USACO。但是这3场我的成绩都很低，赛后一看题解被自己的智商哭死，实在看不下去了，决定要写一篇总结
Day 1
T1
P3132 [USACO16JAN] Angry Cows G
正解
DP，设 $f_i$ 为使第 $i$ 个干草堆左边的所有干草堆爆炸的最小力度。
考虑转移方程。
找一个 $j$，满足：
会有很多个 $j$，我们需要最后一个，即最靠近 $i$ 的那一个。
易得：
$$
f_i=min(a_i-a_j,f_{j+1}+1)
$$
其中 $f_1=0$
类似的，我们可得使右边的爆炸的 $g[]$ 的状态转移方程。
最后我们枚举爆炸点，显然：
$$
ans=min\{max(\frac{a_j-a_i}{2},max(f_i,g_j)+1) \}
$$
其中，$i$ 和 $j$ 的互相推进用到了贪心策略。
还有一点，因为最优情况爆炸点只可能在整点或两个整点中间，所以为了避免double精度问题，我们可以都乘以一个 $2$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
const ll MAXN = 5e4 + 5, INF = 0x3f3f3f3f;
ll n;
ll f[MAXN], g[MAXN];
ll a[MAXN];
int main() {
scanf("%lld", &n);
rp(i, 1, n) scanf("%lld", &a[i]), a[i] *= 2;
sort(a + 1, a + n + 1);
memset(f, 0x3f, sizeof(f));
memset(g, 0x3f, sizeof(g));
ll t = 1;
f[1] = 0;
rp(i, 2, n) {
while (t + 1 < i && a[i] - a[t + 1] > f[t + 1] + 2) ++t;
f[i] = min(a[i] - a[t], f[t + 1] + 2);
}
t = n;
g[n] = 0;
pr(i, n - 1, 1) {
while (t - 1 > i && a[t - 1] - a[i] > g[t - 1] + 2) --t;
g[i] = min(a[t] - a[i], g[t - 1] + 2);
}
ll ans = INF;
for (ll i = 1, j = n; i < j;) {
ans = min(ans, max((a[j] - a[i]) / 2, max(f[i], g[j]) + 2));
if (f[i + 1] < g[j - 1])
++i;
else
--j;
}
printf("%.1lf", (double)ans / 2);
return 0;
}
|
T2
P3133 [USACO16JAN] Radio Contact G
正解
dp,设 $f_{i,j}$ 为在 $(i,j)$ 时最小代价。对于他们的行动串，分别用两个递推数组储存他们的横坐标与纵坐标。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
#define po(x) ((x) * (x))
const ll MAXN = 1e3 + 5;
ll n, m;
ll fx, fy, cx, cy;
ll f[MAXN][MAXN];
ll ax[MAXN], bx[MAXN], ay[MAXN], by[MAXN];
ll d(ll i, ll j) { return po(fx + ax[i] - (cx + bx[j])) + po(fy + ay[i] - (cy + by[j])); }
int main() {
scanf("%lld%lld", &n, &m);
scanf("%lld%lld%lld%lld", &fx, &fy, &cx, &cy);
rp(i, 1, n) {
char ch;
cin >> ch;
ax[i] = ax[i - 1], ay[i] = ay[i - 1];
if (ch == 'N')
ay[i]++;
if (ch == 'S')
ay[i]--;
if (ch == 'W')
ax[i]--;
if (ch == 'E')
ax[i]++;
}
rp(i, 1, m) {
char ch;
cin >> ch;
bx[i] = bx[i - 1], by[i] = by[i - 1];
if (ch == 'N')
by[i]++;
if (ch == 'S')
by[i]--;
if (ch == 'W')
bx[i]--;
if (ch == 'E')
bx[i]++;
}
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
rp(i, 0, n) {
rp(j, 0, m) {
if (i != 0)
f[i][j] = min(f[i][j], f[i - 1][j] + d(i, j));
if (j != 0)
f[i][j] = min(f[i][j], f[i][j - 1] + d(i, j));
if (i != 0 && j != 0)
f[i][j] = min(f[i][j], f[i - 1][j - 1] + d(i, j));
}
}
printf("%lld\n", f[n][m]);
return 0;
}
|
T3
P3134 [USACO16JAN] Lights Out G
正解
按照题意所说，枚举每个点出发的情况。再把路径记录下来，看看这条路径是否唯一。若唯一，则“觉醒”。
我们可以用map储存，路径可以压成 string。
其中对于路径储存问题，我们需要知道这条边的长度与这个角的角度。由于这里的角度不是 270° 就是 90°，所以判断旋转方向即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
const ll MAXN = 200 + 5;
ll n;
struct node {
ll x, y;
} a[MAXN];
map<string, ll> ma;
ll ans;
ll len[MAXN], dis[MAXN];
string ang[MAXN], ls[MAXN];
bool got(ll i, ll j, ll k) {
bool op;
if (a[i].x == a[j].x) {
if (a[j].y > a[i].y) {
if (a[k].x > a[j].x)
op = 1;
else
op = 0;
} else {
if (a[k].x > a[j].x)
op = 0;
else
op = 1;
}
} else {
if (a[j].x > a[i].x) {
if (a[k].y > a[j].y)
op = 0;
else
op = 1;
} else {
if (a[k].y > a[j].y)
op = 1;
else
op = 0;
}
}
return op;
}
inline string work(ll x) {
string s;
ll a[10], hd = 0;
while (x) {
a[++hd] = x % 10;
x /= 10;
}
pr(i, hd, 1) s += a[i] + 48;
return s;
}
int main() {
scanf("%lld", &n);
rp(i, 1, n) scanf("%lld%lld", &a[i].x, &a[i].y);
rp(i, 1, n) {
ll i0 = i - 1, i1 = i + 1;
if (i0 < 1)
i0 = n - i0;
if (i1 > n)
i1 = i1 - n;
ang[i] = got(i0, i, i1) ? "A" : "B";
len[i] = abs(a[i0].x - a[i].x) + abs(a[i0].y - a[i].y);
}
rp(i, 1, n) {
ls[i] = work(len[i]);
ll t1 = len[1], t2 = len[2];
if (i == 1)
continue;
rp(j, i + 1, n) t1 += len[j];
pr(j, i - 1, 2) t2 += len[j + 1];
dis[i] = min(t1, t2);
}
rp(i, 2, n) {
string s;
s += ang[i];
ma[s]++;
rp(j, i + 1, n) {
s = s + ls[j] + ang[j];
ma[s]++;
}
}
rp(i, 2, n) {
ll now = -1;
string s;
s += ang[i];
if (ma[s] == 1)
continue;
ll sum = 0;
rp(j, i + 1, n) {
s = s + ls[j] + ang[j];
sum += len[j];
if (ma[s] == 1) {
now = j;
break;
}
}
if (now == -1)
ans = max(ans, sum + len[1] - dis[i]);
else
ans = max(ans, dis[now] + sum - dis[i]);
}
printf("%lld\n", ans);
return 0;
}
|
总结
同年级rk12，倒数第一……
其实题都不难，可能是脑子抽了……
Day 2
T1
P8901 [USACO22DEC] Circular Barn S
正解
这是巴什博奕。
上来先筛一遍质数，欧拉筛 $O(n)$ 搞定。
经过打表找规律会发现一个房间内只要是对于 $4$ 的倍数，则先手必输。（可以证明，但这里不展开了）
对于先手而言，肯定自己占优时希望能快则快、占劣时能拖则拖。
所以我们记录一下轮数（两人都进行一次操作称为一轮）。
如果是 $4$ 的倍数，两人最优策略都只能不停出 $2$，所以我们这一个房间结束时，经历了 $i/4+1$ 轮。
如果不是，那先手可以取走一个数使得剩下的数右边为 $4$ 的倍数。记录一下 $i \mod 4$ 最大数 $i$。
那么怎么知道答案呢？记录先手获胜时最小轮数 $min_1$ 与这个房间号 $pos_1$，后手同理。
然后比较 $min_1$ 与 $min_2$ 的大小，谁更小，意味着谁更快赢得游戏。
想等的话比较谁的房间号更小。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <cstdio>
using namespace std;
#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
const ll MAXN = 2e5 + 5, MAXM = 5e6 + 5, INF = 0x7f7f7f7f;
ll T, n;
ll a[MAXN], pri[MAXM], pinum;
bool ispr[MAXM];
ll s[4];
ll ans[MAXM];
inline ll read() {
ll 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 << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x * f;
}
inline void write(ll x) {
if (x < 0) {
putchar('-'), write(-x);
return;
}
if (x > 9)
write(x / 10), putchar(x % 10 + 48);
else
putchar(x + 48);
}
void getprime(ll n) {
ans[1] = 1;
s[1] = 1;
for (ll i = 2; i <= n; ++i) {
if (!ispr[i]) {
pri[++pinum] = i;
if (i % 4)
s[i % 4] = i;
}
for (ll j = 1; j <= pinum; ++j) {
if (i * pri[j] > n)
break;
ispr[i * pri[j]] = 1;
if (i % pri[j] == 0)
break;
}
if (i % 4 == 0)
ans[i] = i / 4 + 1;
else
ans[i] = (i - s[i % 4]) / 4 + 1;
}
}
int main() {
getprime(MAXM - 5);
T = read();
while (T--) {
n = read();
ll min1 = INF, pos1, min2 = INF, pos2;
rp(i, 1, n) {
a[i] = read();
if (a[i] % 4 == 0) {
if (min2 > ans[a[i]]) {
min2 = ans[a[i]];
pos2 = i;
}
} else {
if (min1 > ans[a[i]]) {
min1 = ans[a[i]];
pos1 = i;
}
}
}
if (min1 < min2)
puts("Farmer John");
else if (min1 > min2)
puts("Farmer Nhoj");
else {
if (pos1 < pos2)
puts("Farmer John");
else
puts("Farmer Nhoj");
}
}
return 0;
}
|
T2
P8903 [USACO22DEC] Bribing Friends G
正解
dp，但是需要优化。
$O(n^3)$ 的朴素dp这里不说了，直接说正解。
设 $f_{i,j}$ 为遍历了前 $i$ 个人，花了 $j$ 个雪糕可以得到的最大利润。
设 $g_{i,j}$ 为花了 $j$ 元的最大利润。
然后我们枚举在哪一个人身上既花雪糕又花钱。
这显然可以证明只会有一个人既花雪糕又花钱，那他前面的就都用雪糕、后面的就都用钱来支付。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
const ll MAXN = 2e3 + 5;
ll n, A, B;
ll f[MAXN][MAXN];
ll g[MAXN][MAXN];
struct node {
ll p, c, x, xc;
bool operator<(const node &t) const { return x < t.x; }
} a[MAXN];
int main() {
scanf("%lld%lld%lld", &n, &A, &B);
rp(i, 1, n) {
ll x, y, z;
scanf("%lld%lld%lld", &x, &y, &z);
a[i] = { x, y, z, y * z };
}
sort(a + 1, a + n + 1);
rp(i, 1, n) {
rp(j, 0, B) f[i][j] = f[i - 1][j];
pr(j, B, a[i].xc) f[i][j] = max(f[i][j], f[i - 1][j - a[i].xc] + a[i].p);
}
pr(i, n, 1) {
rp(j, 0, A) g[i][j] = g[i + 1][j];
pr(j, A, a[i].c) g[i][j] = max(g[i][j], g[i + 1][j - a[i].c] + a[i].p);
}
ll ans = 0;
rp(i, 1, n) {
ans = max(ans, max(f[i - 1][B] + g[i][A], f[i][B] + g[i + 1][A]));
for (ll j = 0; j <= min(A, a[i].c); ++j) {
if (B < (a[i].c - j) * a[i].x)
continue;
ans = max(ans, f[i - 1][B - (a[i].c - j) * a[i].x] + g[i + 1][A - j] + a[i].p);
}
}
printf("%lld\n", ans);
return 0;
}
|
T3
P8904 [USACO22DEC] Mountains G
正解
暴力膜你模拟。
我们每个山峰都建一个set，记录他右边能看到的山有哪些。
在修改一座山 $x$ 的数据后，判断山 $x$ 会不会挡住山 $i$ 本来能看见的一些山。若挡住，则将山 $x$ 右边的山从 $s_i$ 中删掉。
对于山 $x$ 本身，重构就好了。
能互相看到的山的对数在这个过程中也可以统计出来。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <cstdio>
#include <set>
using namespace std;
#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
#define ins insert
#define era erase
#define upp upper_bound
#define low lower_bound
const ll MAXN = 2e3 + 5;
ll n, ans;
ll a[MAXN];
set<ll> s[MAXN];
double gotk(ll i, ll j) { return 1.0 * (a[j] - a[i]) / (j - i); }
int main() {
scanf("%lld", &n);
rp(i, 1, n) scanf("%lld", &a[i]);
rp(i, 1, n) {
s[i].ins(0), s[i].ins(n + 1);
double k = -1e9;
rp(j, i + 1, n) {
if (gotk(i, j) >= k) {
k = gotk(i, j);
s[i].ins(j);
++ans;
}
}
}
ll Q;
scanf("%lld", &Q);
while (Q--) {
ll ix, h;
scanf("%lld%lld", &ix, &h);
a[ix] += h;
rp(i, 1, ix - 1) {
auto it = s[i].low(ix);
it--;
ll y = *it;
if (y && gotk(i, y) > gotk(i, ix))
continue;
if (s[i].find(ix) == s[i].end())
s[i].ins(ix), ++ans;
for (y = *s[i].upp(ix); y <= n; y = *(s[i].upp(y))) {
if (gotk(i, y) >= gotk(i, ix))
break;
s[i].era(y), --ans;
}
}
ans -= s[ix].size() - 2;
s[ix].ins(0), s[ix].ins(n + 1);
double k = -1e9;
rp(i, ix + 1, n) {
if (gotk(ix, i) >= k) {
k = gotk(ix, i);
s[ix].ins(i);
++ans;
}
}
printf("%lld\n", ans);
}
return 0;
}
|
总结
同级rk5，但是大家都没打好，太难了，没有人A。
可能是我这次比较走运。
Day 3
补题去了。
顺便一提，一道绿题做了一天……
其实还是很简单的，但是我的脑细胞却死了不少。。
罪魁祸首：
Day 4
T1
P3090 [USACO13NOV] Empty Stalls G
正解
签到题，但是我没做出来。
赛后看了题解，只要扫一遍就好了，注意要再扫一轮，以免一些特殊情况。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <set>
#include <cstdio>
using namespace std;
#define int long long
#define rp(i, o, p) for (int i = o; i <= p; ++i)
#define pr(i, o, p) for (int i = o; i >= p; --i)
const int MAXN = 3e6 + 5, MAXK = 1e4 + 5;
int n, k;
int num[MAXN];
signed main() {
scanf("%lld%lld", &n, &k);
rp(i, 1, k) {
int x, y, a, b;
scanf("%lld%lld%lld%lld", &x, &y, &a, &b);
rp(j, 1, y) {
int t = a * j % n + b % n;
t %= n;
num[t] += x;
}
}
rp(i, 0, n - 1) {
if (num[i]) {
num[(i + 1) % n] += num[i] - 1;
num[i] = 1;
}
}
if (num[0])
for (int i = 0; i < n; ++i) {
if (num[i]) {
num[(i + 1) % n] += num[i] - 1;
num[i] = 1;
}
}
rp(i, 0, n - 1) if (!num[i]) {
printf("%lld\n", i);
break;
}
return 0;
}
|
T2
P3088 [USACO13NOV] Crowded Cows S
正解
又是签到题，可是我又傻了。
单调队列维护最大值，然后判断即可。
注意正反都做一遍，可以做到 $O(n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
#define rp(i, o, p) for (int i = o; i <= p; ++i)
#define pr(i, o, p) for (int i = o; i >= p; --i)
const int MAXN = 1e5 + 5;
int n, d;
struct node {
int x, h;
bool operator<(const node &t) const { return x < t.x; }
} a[MAXN], q[MAXN];
bool l[MAXN], r[MAXN];
signed main() {
scanf("%lld%lld", &n, &d);
rp(i, 1, n) scanf("%lld%lld", &a[i].x, &a[i].h);
sort(a + 1, a + n + 1);
int lf = 1, rg = 0;
rp(i, 1, n) {
while (lf <= rg && q[rg].h < a[i].h) --rg;
q[++rg] = a[i];
while (lf <= rg && q[lf].x < a[i].x - d) ++lf;
if (q[lf].h >= a[i].h * 2)
l[i] = 1;
}
memset(q, 0, sizeof(q));
lf = 1, rg = 0;
pr(i, n, 1) {
while (lf <= rg && q[rg].h < a[i].h) --rg;
q[++rg] = a[i];
while (lf <= rg && q[lf].x > a[i].x + d) ++lf;
if (q[lf].h >= a[i].h * 2)
r[i] = 1;
}
int ans = 0;
rp(i, 1, n) if (l[i] && r[i])++ ans;
printf("%lld\n", ans);
return 0;
}
|
T3
P3089 [USACO13NOV] Pogo-Cow S
正解
dp，容易想到设 $f_{i,j}$ 为第 $i$ 点，从第 $j$ 点跳过来的最大分值。
可得
$$
f_{i,j}=f_{j,k}+p_i
$$
但是会爆。
若 $i\to i-1$
得
$$
f_{i-1,j}=f_{j,k}+p_{i-1}
$$
结合一下，得
$$
f_{i,j}=f_{i-1,j}-p_{i-1}+p_i
$$
好像没 $k$ 什么事了。
我们思考一下，如果固定 $j$ 点，$i$ 点与 $k$ 点的变换类似于共同进行，所以我们可以在同一个循环中搞定。
时间复杂度 $O(n^2)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
struct node {
int x, p;
bool operator<(const node &t) const { return x < t.x; }
} a[MAXN];
int ans;
int f[MAXN][MAXN];
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].x, &a[i].p);
sort(a + 1, a + n + 1);
for (int j = 1; j <= n; ++j) {
f[j][j] = a[j].p;
int k = j + 1;
for (int i = j + 1; i <= n; ++i) {
f[i][j] = f[i - 1][j] - a[i - 1].p;
while (k > 1 && a[j].x - a[k - 1].x <= a[i].x - a[j].x) f[i][j] = max(f[i][j], f[j][--k]);
f[i][j] += a[i].p;
ans = max(ans, f[i][j]);
}
ans = max(ans, f[j][j]);
}
for (int j = n; j >= 1; --j) {
f[j][j] = a[j].p;
int k = j - 1;
for (int i = j - 1; i >= 1; --i) {
f[i][j] = f[i + 1][j] - a[i + 1].p;
while (k < n && a[k + 1].x - a[j].x <= a[j].x - a[i].x) f[i][j] = max(f[i][j], f[j][++k]);
f[i][j] += a[i].p;
ans = max(f[i][j], ans);
}
ans = max(ans, f[j][j]);
}
printf("%d\n", ans);
return 0;
}
|
总结
同级倒数第一，有两个人AK……
总总结
“开动脑筋。”这是教练常说的话。
确实，这个暑假如果不改变不勤思考的习惯，只会被淘汰。