2018-team11-014

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(hw11.PNG,700px)]]

== 总结 ==

=== zb ===
感觉今天整个人状态有些急躁，最要命的问题是中间没有相信周哥，一直在纠结要不要自己接着写，弄得大家都不太愉快，以后应该充分相信队友，而且一旦开了题就不要轻易换人。

然后I题我背锅，已经好几次我负责的网络流部分没有做出来了，努力。

=== zyh ===
还是自己的代码水平不够，几个简单问题合在一起就傻掉，整体思路也不够清晰。

但是自己也应该坚定一点，不能遇到一点困难就退缩，想着推给sg写，这样对节奏影响很大

=== sj ===

读了L题以为自己会写了，结果WA了，后来发现有些情况没有考虑到，周哥改了代码以后A了。

== 题解 ==
A.Another Meaning

题意：可以把一个字符串换成??，问可生成多少不同的字符串。

做法：KMP出哪些位置可以换，然后dp即可。

B.After a Sleepless Night

题意：给定一棵无根树，是原树每个点取子树权值最大值之后的形态，求原树形态以及点权。

做法：权值最大的一定是一条链而且根在链的一端，分别判断即可。

E.Lucky7

题意：求一个区间内能被7整除，但是不满足一些模数互质的同余方程的数的个数。

做法：中国剩余定理解同余方程组，然后容斥。

F.Substring

题意：求一个字符串包含给定字母的本质不同字串个数。

做法：答案等于不同字串个数减去去掉所有给定字母的不同字串个数，广义后缀自动机统计。

J.The All-purpose Zero

题意：给定一个自然数序列，每个0可以换成任意数，求lis。

做法：一定存在一种最优方案选了所有0，去掉0之后每个数减去后面0的数量，直接lis即可。

K.Where Amazing Happens

题意：签到题。

做法：处理一下。

L.Bubble Sort

题意：问冒泡排序过程中一个数最左位置和最右位置的差。

做法：一个数会有三个位置，起始终止和中间态，中间态就是起始位置减去它后面比它小的数的个数。

I.String problem

题意：选择一个字符串子序列，俩个位置之间互相有贡献，每个字母选择的代价是一个关于数量的一次函数。

做法：最大权闭合子图模型，源点表示选择。

总结

zb

感觉今天整个人状态有些急躁，最要命的问题是中间没有相信周哥，一直在纠结要不要自己接着写，弄得大家都不太愉快，以后应该充分相信队友，而且一旦开了题就不要轻易换人。

然后I题我背锅，已经好几次我负责的网络流部分没有做出来了，努力。

zyh

还是自己的代码水平不够，几个简单问题合在一起就傻掉，整体思路也不够清晰。

但是自己也应该坚定一点，不能遇到一点困难就退缩，想着推给sg写，这样对节奏影响很大

sj

读了L题以为自己会写了，结果WA了，后来发现有些情况没有考虑到，周哥改了代码以后A了。

题解

A.Another Meaning

题意：可以把一个字符串换成??，问可生成多少不同的字符串。

做法：KMP出哪些位置可以换，然后dp即可。

B.After a Sleepless Night

题意：给定一棵无根树，是原树每个点取子树权值最大值之后的形态，求原树形态以及点权。

做法：权值最大的一定是一条链而且根在链的一端，分别判断即可。

E.Lucky7

题意：求一个区间内能被7整除，但是不满足一些模数互质的同余方程的数的个数。

做法：中国剩余定理解同余方程组，然后容斥。

F.Substring

题意：求一个字符串包含给定字母的本质不同字串个数。

做法：答案等于不同字串个数减去去掉所有给定字母的不同字串个数，广义后缀自动机统计。

J.The All-purpose Zero

题意：给定一个自然数序列，每个0可以换成任意数，求lis。

做法：一定存在一种最优方案选了所有0，去掉0之后每个数减去后面0的数量，直接lis即可。

K.Where Amazing Happens

题意：签到题。

做法：处理一下。

L.Bubble Sort

题意：问冒泡排序过程中一个数最左位置和最右位置的差。

做法：一个数会有三个位置，起始终止和中间态，中间态就是起始位置减去它后面比它小的数的个数。

I.String problem

题意：选择一个字符串子序列，俩个位置之间互相有贡献，每个字母选择的代价是一个关于数量的一次函数。

做法：最大权闭合子图模型，源点表示选择。

附加文件