前言
今天晚上因为打了一场 vp 导致我没来得及写总结，好可惜。但是如果今天不写的话以后更不可能写得完。所以就简单地写一写吧。比较简略请见谅。谢谢。
但是就算这么说，我也想说点什么，似乎又没有什么好说的。你说得对，我又在水字数了哈哈。但是一转眼又一周要过去了……今天是疯狂星期四！可是疯狂后又是什么呢？什么都没有了。还是希望淡淡的、莫名其妙地就把这几年过去了。（装Xing，不要理我哇酷哇酷）。
早上
今天早上就是练习赛而已。emm，三道题，USACO 的。大概可能是 noip T1 的难度吧？或许是这样的。link 。就是这个。不是很难。也不想讲太多。就贴一下代码，以彰显我的 blog 很认真（误）。
T1 Milk Sum
排一个序，插一插，减一减就行。贪心显然。
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
| #include <bits/stdc++.h>
#define N 150010
using namespace std;
using ll = long long;
int n;
ll a[N], b[N];
int q;
int x;
ll y;
ll sum, hz[N];
int main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", a + i);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
for (ll i = 1; i <= n; ++i) sum += b[i] * i;
for (int i = n; i; --i) hz[i] = hz[i + 1] + b[i];
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
scanf("%d%lld", &x, &y);
ll tmp = sum;
ll ps = lower_bound(b + 1, b + n + 1, a[x]) - b;
tmp -= hz[ps + 1] + a[x] * ps;
ll jr = upper_bound(b + 1, b + n + 1, y) - b;
tmp += hz[jr];
if (jr <= ps) tmp -= b[ps];
else --jr;
tmp += y * jr;
printf("%lld\n", tmp);
}
return 0;
}
|
这里写的很复杂（颩脸(T_T)），其实改变的只是两个数之间的那部分罢了。
T2 Field Day
这道题没有做出来。但是看样子我们 oj 上的数据比较水。我写得45 pts 的暴力拿了 80 pts，神奇。正解大致有两种。第一种是把数拆成前一半和后一半。类似题目请参照 CSP-S 2020 初赛最后一道题。（应该是吧）。还有一种就是相当于是取反的汉明距离最近，搞一搞就行。很好写，就这样。
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
| #include <bits/stdc++.h>
#define N 150010
using namespace std;
int n, c;
char s[20];
vector<int> a;
int f[262200];
int getv() {
int ans = 0;
for (int i = 0; i < c; ++i) {
ans = (ans << 1) | (s[i] == 'G');
}
return ans;
}
int main() {
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d%d", &c, &n);
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; ++i) {
scanf("%s", s);
auto tmp = getv();
f[tmp] = 0;
a.emplace_back(tmp);
}
for (int i = 0; i < c; ++i) {
for (int j = 0; j < (1 << c); ++j) {
f[j ^ (1 << i)] = min(f[j ^ (1 << i)], f[j] + 1);
}
}
for (auto i : a) {
printf("%d\n", c - f[((1 << c) - 1) ^ i]);
}
return 0;
}
|
T3 Pareidolia
就是个字符串 dp？每一位找到第一个能够匹配第一个 Bessie 的位置，然后就是那个位置后一个的 f 加上这后面的距离。（f 就是以这一位开头的贡献）。比较显然，就不想说了，看看代码画一画就行。
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
| #include <bits/stdc++.h>
#define N 300010
using namespace std;
char s[N];
using ll = long long;
ll ans;
const char pp[8] = "bessie";
#define pre(x) (x + 5) % 6
ll f[N];
int p[N][7];
int n;
int main() {
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 0; i < 6; ++i) p[n + 1][i] = n + 1;
for (int i = n; i; --i) {
for (int j = 0; j < 6; ++j) {
p[i][j] = p[i + 1][j];
if (s[i] == pp[j]) {
if (j < 5) p[i][j] = p[i + 1][j + 1];
else p[i][j] = i;
}
}
f[i] = f[p[i][0] + 1] + n + 1 - p[i][0];
ans += f[i];
}
printf("%lld", ans);
return 0;
}
|
下午
看懂了有一年 noip 那个树的重心那道题。xht 的方法还是非常巧妙的，%%%。还有就是呢，我还没有写出来那道题（,,ԾㅂԾ,,），嘻嘻，但肯定会写出来的。我现在都还为我写出了喵了个喵而感到高兴，喵~。
然后就没啥事了。
真的吗？？？
(￣ε(#￣)，你不觉得换这么多行不丑吗……好了不开玩笑了，我们进入下一个标题。
晚上
打完今日模板后就去打 vp 了，导致没有写总结，呜呜呜。可怜。其实不是立刻，中间还是隔了亿点点时间的……都怪我，┭┮﹏┭┮。那场 vp 就看我 [[题解/Codeforces/Codeforces 作题记录1|Codeforces 作题记录1]] 里面的记录了吧，这里就不记载了。
