07.12&07.14模拟赛总结
前言：
这是最戏剧性的一集，两场都是同级第一，只不过一场正数、一场倒数。
07.12——Day 1
T1
P8093 [USACO22JAN] Searching for Soulmates S
正解
以下除以 $2$ 操作、加 $1$ 操作、乘以 $2$ 操作分别为操作 1、2、3。
思考发现，如果我们先前一直进行操作 1 和操作 2，那等到我们再进行操作 3 时，就不会再进行操作 1，（因为不会更优）。
换句话说，我们操作的步骤大约分为两个部分：
- 前半段：进行操作 1、2
- 后半段：进行操作 2、3
容易想到处理出前后半段中间的一个中间值 $t$。
由于后半段的操作不是乘以 $2$ 就是加 $1$，所以这个 $t$ 一定是 $b$ 的前缀（二进制中）。
那就很清晰了，直接枚举 $t$，在记录步数即可。
代码
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
int d(int x) {
for (int i = 63; i >= 0; --i)
if (x >> i)
return i + 1;
return 0;
}
int get(int num, int x, int len) { return num >> (len - x); }
void solve() {
int a, b;
scanf("%lld%lld", &a, &b);
if (a == b) {
puts("0");
return;
}
int len = d(b);
int ans = 0x3f3f3f3f;
for (int i = 1; i <= len; i++) {
int cnt = 0;
int t = get(b, i, len);
int ta = a;
while (ta != t) {
if (ta > t) {
if (ta & 1)
++ta;
else
ta /= 2;
++cnt;
} else {
cnt += t - ta;
ta = t;
}
}
for (int j = i + 1; j <= len; j++) {
t = get(b, j, len);
ta <<= 1;
++cnt;
if (t != ta)
++ta, ++cnt;
}
ans = min(ans, cnt);
}
printf("%lld\n", ans);
}
signed main() {
int n;
scanf("%lld", &n);
while (n--) solve();
return 0;
}
|
T2
P8094 [USACO22JAN] Cow Frisbee S
正解
直接枚举、用栈维护即可。
代码
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e5 + 5;
int n, ans;
int h[MAXN], x[MAXN];
stack<int> s;
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &h[i]), x[h[i]] = i;
for (int i = 1; i <= n; i++) {
while (!s.empty()) {
int t = s.top();
ans += abs(x[h[i]] - x[t]) + 1;
if (h[i] <= t)
break;
s.pop();
}
s.push(h[i]);
}
printf("%lld\n", ans);
return 0;
}
|
T3
P8095 [USACO22JAN] Cereal 2 S
正解
对于这道题，一眼二分图最大匹配，直接匈牙利带走。
结果发现 $\Omicron(nm)$ 把匈牙利带走。
但是没有关系！直接建超级源点和超级汇点，dinic 网络流直接 $\Omicron(\sqrt{n}m)$ 带走。
但是，这样非常难打，而且在输出排队顺序是也异常繁琐，可以说是拿考场时间换代码运行时间了……
怎么办呢？还好这场比赛这道题最难，所以应该没有人会 A，打点部分分也是不错的选择【大拇指d(￣▽￣)b】。
实际上这道题数据很水，匈牙利+卡常+优秀的代码逻辑是可以 A 的。
至于输出方案，这个想想就出来了，这里不做过多赘述。
代码
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int MAXN = 2e6 + 5;
int n, m;
int a[MAXN];
int f[MAXN], s[MAXN];
int lk[MAXN], ilk[MAXN];
bool vis[MAXN];
vector<int> v[MAXN], vec[MAXN];
bool dfs(int x) {
for (auto i : v[x]) {
if (!vis[i]) {
vis[i] = 1;
if (!lk[i] || dfs(lk[i])) {
lk[i] = x, ilk[x] = i;
vis[i] = 0;
return 1;
}
}
}
return 0;
}
int MXMC() {
int re = 0;
for (int i = 1; i <= n; i++) re += dfs(i);
return re;
}
signed main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &f[i], &s[i]);
v[i].pb(f[i]), v[i].pb(s[i]);
vec[f[i]].pb(i);
}
int ans = MXMC();
printf("%lld\n", n - ans);
queue<int> q;
for (int i = 1; i <= n; i++) {
if (ilk[i] != f[i])
continue;
printf("%lld\n", i);
for (auto j : vec[f[i]]) {
if (ilk[j] == s[j])
q.push(j);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
printf("%lld\n", u);
for (int j : vec[s[u]]) {
if (ilk[j] == s[j])
q.push(j);
}
}
for (int i = 1; i <= n; i++)
if (!ilk[i])
printf("%lld\n", i);
return 0;
}
|
总结
$8+27+7=42/rk12$
同级倒一、直接趋势。
总结发现是答题时心态没有调整好，导致陷入思维怪圈，进一步导致简单题做不对、难题不会做的情况。
07.13——Day 2
原题检测，没打比赛。
一早上复习，复习了上一周打过的模拟赛。幸好我都写了总结、方便复习。
结果：
我：（开始啦开始啦！）咦？这个“旅行商简化版”是个什么东西？
隔壁的新初一：好像是我们作业里的一道题。
隔壁同级：教练，这个我们要做吗？
教练：新初三的也要做，注意一下啊。
新初三的我们：……
顺提，我们原题检测里的题，一题没A跑2圈……
但成绩挺可观的：
$100+100+52+100+71+0=423/rk2$
好吧，跑6圈。遗憾的是期望得到 $500$ 分，可惜有两题打挂了……
07.14——Day 3
T1
P9186 [USACO23OPEN] Milk Sum S
正解
容易想到肯定先排序嘛，那么就会得到新数组。
发现用二分找到查询数据在新数组位置时，答案的增加与减少可以用一个后缀和来搞定。（当然，前缀和应该没问题，可是赛时我先想到了后缀和）。
那就很容易做了，二分可以写 lower_bound，减少码量。因为近期用 set 用得比较多，所以我就干脆丢进了 set 里进行 lower_bound 操作。
代码
好不容易第一次赛时切绿，这里放一下我的赛时代码（无格式化、码风为本人码风）
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
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2e5+5,INF=1e9;
int n,ans;
struct node
{
int x,id;
bool operator<(const node &T)const
{
if(x!=T.x)
return x<T.x;
return id<T.id;
}
}a[MAXN],b[MAXN];
int sum[MAXN];
multiset<node> s;
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].x);
b[i].x=a[i].x;
b[i].id=i;
}
sort(a+1,a+n+1);
for(int i=n;i>=1;i--)
{
ans+=a[i].x*i;
sum[i]=sum[i+1]+a[i].x;
a[i].id=i;
s.insert(a[i]);
}
s.insert({-1,0}),s.insert({INF,0});
int tmp=ans,Q;
scanf("%lld",&Q);
while(Q--)
{
ans=tmp;
int x,y;
scanf("%lld%lld",&x,&y);
auto it=s.lower_bound({b[x].x,0});
node t=*it;
ans-=t.x*t.id;
auto it2=s.upper_bound({y,0});
node t2=*it2;
if(t2.x==INF)
{
ans-=sum[t.id+1];
ans+=y*n;
printf("%lld\n",ans);
continue;
}
if(t2.id==t.id)
{
ans+=y*t.id;
printf("%lld\n",ans);
continue;
}
if(t2.id<t.id)
{
ans+=sum[t2.id]-sum[t.id];
ans+=y*t2.id;
}
else
{
ans+=y*(t2.id-1);
ans-=sum[t.id+1]-sum[t2.id];
}
printf("%lld\n",ans);
}
return 0;
}
|
T2
P9187 [USACO23OPEN] Field Day S
正解
这个一看就是可以转成二进制，比较就是异或操作了。
这是个很好的思路，如果赛时没想到的话那就是能力问题了。
因为他要求找最大不同，那脑海中可以有这样的思路：
$$
最大不同\to 最小相同\to 可以对其一取反\to 最小不同
$$
那就很容易了，我们可以用一个非常简单的dp实现：
设 $f_i$ 为得到 $i$ 的最小不同，最后输出答案时就是
$$
c-f_{(2^c-1) \oplus a_i}
$$
怎么转移呢？预处理一下就好了
代码
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 5;
int n, c;
int a[MAXN];
int f[MAXN];
signed main() {
scanf("%lld%lld", &c, &n);
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= c; j++) {
char ch;
cin >> ch;
a[i] <<= 1;
a[i] += (ch == 'G');
}
f[a[i]] = 0;
}
for (int j = 1; j <= c; j++) {
for (int i = 1; i <= (1 << c) - 1; i++) f[(1 << (j - 1)) ^ i] = min(f[(1 << (j - 1)) ^ i], f[i] + 1);
}
for (int i = 1; i <= n; i++) {
int ans = c - f[((1 << c) - 1) ^ a[i]];
printf("%lld\n", ans);
}
return 0;
}
|
T3
P9188 [USACO23OPEN] Pareidolia S
正解
考虑DP。
设 $f_i$ 为这样一个 $[1,i]$ 的区间出现 bessie 的个数。
怎么转移呢？可以利用一下辅助数组 $lst_i$，其中 $i\in [1,6]$。
这是什么？
如果出现了一个序列 bessie，那第 $i$ 位前面的 bessie 的起始位（b 的位置）
例如 bessie，那么 $lst_i=1 ; (1\leq i\leq 6)$
那么考虑转移 $f$：
提供贡献的只有：
- 前面的转移过来
- 当前贡献了多少
1 情况怎么处理呢？显然是 $f_{lst_6-1}$
2 情况呢？因为当前 bessie 的出现，所以对于 $[l,lst_6] ; (l\in [1,lst_6])$ 这些区间，答案都会 +1，所以转移量就是 $lst_6$
综上，
$$
f_i=f_{lst_6-1}+lst_6
$$
因为答案是所有区间，所以答案就为:
$$
\sum_{i=1}^n f_i
$$
代码
有些许改动：
（$dp_i \to f_i$）
（$f_i \to lst_i$）
括号里左边为代码变量，右边为思路变量
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
|
#include <cstring>
#include <cstdio>
using namespace std;
#define int long long
const int MAXN = 3e5 + 5;
char s[MAXN];
int f[10],dp[MAXN];
signed main() {
scanf("%s",s+1);
int n=strlen(s+1);
// bessie
for(int i=1;i<=n;i++)
{
if(s[i]=='b')
f[1]=i;
if(s[i]=='e')
f[6]=f[5],f[2]=f[1];
if(s[i]=='s')
f[4]=f[3],f[3]=f[2];
if(s[i]=='i')
f[5]=f[4];
dp[i]=dp[f[6]-1]+f[6];
}
int ans=0;
for(int i=1;i<=n;i++)
ans+=dp[i];
printf("%lld\n",ans);
return 0;
}
|
总结
$100+25+17=142/rk1$
这次 $rk1$ 不只是同级，还是同机房。
再接再厉。