1746 Codeforces Global Round 23
FallenGemini

碎碎念

前些天和一位博导教授聊了一个多小时,了解到游戏制作也挺看重算法的,跌跌撞撞又回到了算法竞赛。
不过这一年还是以专业必修课和英语六级为主,算法竞赛相对花的时间更少。

比赛

A.Maxmina (0:06)

题意

数组 01 组成,有两种操作:

  • 相邻两个数字替换为这两个数字中较小的那个
  • 连续 个数字替换为这 个数字中最大的那个

求能否通过一定的操作,让数组 只有一个数字 1

分析

  • 考虑数组大小 :也就是只有操作一。这种情况下只要存在 0 就没有解。
  • 考虑数组大小 :显然,使用操作二一定不劣于使用 次操作一。这种情况下只要存在 1 就有解。
  • 考虑数组大小 :尝试让 ,不断使用操作一,尽可能保留 1。又因为只要存在 1就可以,那可以随便取一个长度为 的区间,这个区间包含至少一个 1,区间外的全用操作一去掉就可以了。

综合考虑,只需要判断 的大小关系即可。

Code

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
void solve()
{
int n,k;
bool flag;
std::cin >> n >> k;
if(n >= k)
{
flag = false;
for(int i = 1; i <= n; i++)
{
int x;
std::cin >> x;
if(x) flag = true;
}
}
else
{
flag = true;
for(int i = 1; i <= n; i++)
{
int x;
std::cin >> x;
if(!x) flag = false;
}
}
std::cout << (flag ? "YES\n" : "NO\n");
}

B. Rebellion (0:12)

题意

数组 01 组成,进行若干次操作:

  1. 选择两个下标
  2. 删去

要求最终的数组单调不下降,求最少操作次数。

分析

不难发现,最终的数组形式一定是若干个 0 + 若干个 1。若出现某个数字 ,一定能证明出有更优的解法。

于是可以使用两个指针,分别从前往后和从后往前。当找到一对 时,交换这两个数字

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve()
{
int n;
std::cin >> n;
std::vector<int> a(n);
for(int i = 0; i < n; i++)
std::cin >> a[i];
int l = 0, r = n - 1, ans = 0;
while(l < r)
{
while(l < r && a[l] != 1) l++;
while(l < r && a[r] != 0) r--;
if(l < r)
{
ans++;
l++;
r--;
}
}
std::cout << ans << '\n';
}

C. Permutation Operations (0:25)

题意

数组 是一个 的排列,进行 次操作,第 次操作:

  1. 选择一个下标
  2. 将区间 上的数字都加上

要求进行 次操作后,排列中的逆序对数最少,输出每一次操作的下标 (多种方案时任意输出一种)

分析

看到题的第一反应是,有没有一种通用的算法,能够让逆序对数变成0
然后手画了几个图,发现对于某一个较大的数字 ,如果要减少关于这个数字的逆序对(以这个数字为数对的第一个),那么就要让后边的数字增加一个值
不难发现,当 时,以 为第一变量的逆序对数一定会变成 0
再从 考虑,那么 是这合理的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve()
{
int n;
std::cin >> n;
std::vector<int> a(n);
for(int i = 0; i < n; i++)
std::cin >> a[i];
int l = 0, r = n - 1, ans = 0;
while(l < r)
{
while(l < r && a[l] != 1) l++;
while(l < r && a[r] != 0) r--;
if(l < r)
{
ans++;
l++;
r--;
}
}
std::cout << ans << '\n';
}

D. Paths on the Tree (1:25)

题意

给一棵有根数树,节点有权值
条从根开始的简单路径,令 表示经过点 的路径数量,要求对于所有兄弟节点
的最大值。

分析

首先考虑恰好均分的情况。
表示有 条路径经过了 表示节点 个子节点。
不是叶子节点时,有 成立,此时路径方案是唯一确定的。

再考虑对于多的路径如何分配。
对于 ,令 ,因为兄弟节点,那么对于这 条边必须分给 个儿子,问题转化为如何找到最优子节点。

从叶子节点的父亲那一层开始考虑:对于这个父亲节点 ,其最优的 个方案就是其子节点 的前 个值。
那么对于父亲节点的父亲节点,也就是叶子节点的祖先节点那一层,对于祖先节点 ,其最优的 个方案是【其子节点 + 那个子节点的第 个最优子节点 】的前 个值

依次从叶子结点向上传递信息。

Code

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
std::vector<int> f,s;
std::vector<std::vector<int>> To;
long long ans;
void dfs(int u,int time)
{
ans += 1ll * time * s[u];
if(To[u].size() == 0)
{
f[u] = s[u];
return;
}
int Mod = time % To[u].size();
int cnt = time / To[u].size();
std::priority_queue<int> q;
for(int v : To[u])
{
dfs(v, cnt);
q.push(f[v]);
}
while(Mod--)
{
ans += q.top();
q.pop();
}
f[u] = s[u] + q.top();
}
void solve()
{
int n,k;
std::cin >> n >> k;
To.clear();To.resize(n + 1);
for(int i = 2; i <= n; i++)
{
int fa;
std::cin >> fa;
To[fa].push_back(i);
}
s.clear();s.resize(n + 1);
for(int i = 1; i <= n; i++)
std::cin >> s[i];
f.clear();f.resize(n + 1);
ans = 0;
dfs(1, k);
std::cout << ans << '\n';
}

E1. Joking (Easy Version) (TLE)

题意

交互题。在 中猜一个数字。
每次提问时,给一个集合,返回 YES/NO
存在一些回答是假信息,保证相邻两个回答至少有一个回答是真信息。
有两次机会确定答案。

分析

对于这道题的简单模型,最多只需要 次提问。

考虑如何判断假消息,尝试从两次确定答案的机会入手。
开始直接确定答案是否为1,得到一个确定的信息,即答案不是1。
之后不停提问,给出集合{1},当回答为 YES 时,我们可以判断这是一条假消息,那么下一条消息为真,回归简单模型。

问题在于,假消息的出现频率是任意的,当假消息出现频率极低时,我们可能不停询问集合{1}。

总结

最近打 Codeforces 的次数真的很低,当时是不太想搞竞赛,打算去一次 ICPC 就退役的。

不过也还好,大二这一年把专业课学好,尽量多读点黑皮书,实现一下书里提到的内容。
无论是竞赛、大创还是美赛,都等到大三去好了。

目前计划一周打一次 CF VP,周六有 CF 就加一场比赛。
坚持一下咯,和博导聊天真的感觉到就业危机感了。