2020-team11-C11

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team11 返回]
== 概述 ==
solved: 6/13  dirt: 46%
rank: 6
==  ==
== 总结 ==
开场发现A是个签到，结果因为Qza把>=写成了>而WA了一发。接下来Qza发觉B可以通过极其暴力的分类讨论过掉，而Zhw开出了M，因为M比较好写，所以Zhw先上去把M过了，然后Qza上去开始枚举B的情况。过掉B后，又去开H、I，发现H是个简单的dp后就把H过掉了。后来Qza去想I和E，Zhw想C。Zhw想出了C的做法，提交后WA了，加了个特判之后就过掉了。而Qza终于猜出了I的题意并开始写，但最终也没有过掉。
== 题解 ==
A：直接O(T\sqrt{n})判所有的因子即可。
B：枚举三个位置的运算符是什么（+、-、*、连接符），然后根据连接符的位置将表达式化为仅包含数字和数学运算符的表达式，然后先处理乘号再处理加减就行了。
C：容易发现，第i个点经过k次时，从i点出发到达i的两个儿子的次数是确定的。所以可以从根开始向下递推，将根节点经过k次和k-1分别递推下去，看下面哪个位置多了1，即可知道第k次落入哪个位置。
D：
E：先将相同颜色的段并成一个点，然后设f[i][j]表示[i,j]是否能被全部消掉，g[i][j]（要求i，j颜色相同）表示[i,j]这一段的其他颜色消除，并最大化与ij相同的位置的个数。然后g[i][j]>=m可以使f[i][j]成立，g的转移就枚举[i,j]一段和ij颜色相同的k，判断能否从k处断开并转移。f可以向更大的区间转移。最终f[i][1]即为答案。
F：基环树dp，先把每个根的子树覆盖完，然后强制0号点选/不选，在序列上跑个dp更新答案即可。
G：
H；二分瓶颈的值，然后用大于等于瓶颈的边跑最小生成树。二分最后能得到瓶颈，根据这个跑出来最小生成树，将树边从大到小添加到图中，添加时改边即作为一个瓶颈，将其贡献加到答案里即可。
I：tarjan图论板子合集。求割点数量、割边数量、点双数量、边数最多的点双的边数。
J：
K：
L：
M：简单模拟即可。

[/wiki/2020-team11 返回]

概述

solved: 6/13 dirt: 46%

rank: 6

总结

开场发现A是个签到，结果因为Qza把>=写成了>而WA了一发。接下来Qza发觉B可以通过极其暴力的分类讨论过掉，而Zhw开出了M，因为M比较好写，所以Zhw先上去把M过了，然后Qza上去开始枚举B的情况。过掉B后，又去开H、I，发现H是个简单的dp后就把H过掉了。后来Qza去想I和E，Zhw想C。Zhw想出了C的做法，提交后WA了，加了个特判之后就过掉了。而Qza终于猜出了I的题意并开始写，但最终也没有过掉。

题解

A：直接O(T\sqrt{n})判所有的因子即可。

B：枚举三个位置的运算符是什么（+、-、*、连接符），然后根据连接符的位置将表达式化为仅包含数字和数学运算符的表达式，然后先处理乘号再处理加减就行了。

C：容易发现，第i个点经过k次时，从i点出发到达i的两个儿子的次数是确定的。所以可以从根开始向下递推，将根节点经过k次和k-1分别递推下去，看下面哪个位置多了1，即可知道第k次落入哪个位置。

D：

E：先将相同颜色的段并成一个点，然后设f[i][j]表示[i,j]是否能被全部消掉，g[i][j]（要求i，j颜色相同）表示[i,j]这一段的其他颜色消除，并最大化与ij相同的位置的个数。然后g[i][j]>=m可以使f[i][j]成立，g的转移就枚举[i,j]一段和ij颜色相同的k，判断能否从k处断开并转移。f可以向更大的区间转移。最终f[i][1]即为答案。

F：基环树dp，先把每个根的子树覆盖完，然后强制0号点选/不选，在序列上跑个dp更新答案即可。

G：

H；二分瓶颈的值，然后用大于等于瓶颈的边跑最小生成树。二分最后能得到瓶颈，根据这个跑出来最小生成树，将树边从大到小添加到图中，添加时改边即作为一个瓶颈，将其贡献加到答案里即可。

I：tarjan图论板子合集。求割点数量、割边数量、点双数量、边数最多的点双的边数。

J：

K：

L：

M：简单模拟即可。