2018-team11-001

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(homework8.PNG)]]
== 流水账 ==
开局周哥读错了A，1WA，我去写H，1A，然后写A，失误了一发才A掉，然后周哥上去写J,1A，学姐发现G题是个假的期望题，我上去过掉，1A，然后我重新读了F的题意，上去写了F，1A，然后又写了C，1A，最后幸亏是周哥发现了B题坐标的范围非常小，最后写了个二维前缀和过去了。
== 总结 ==
=== zb ===
好久没有训练了，一直在担心状态会不会不是很好，正好今天这个题面三个人读起来都很不舒服。关于A题的题意，感觉周哥都想打我了，虽然我读的才是对的【小小声
后面开题也不是很顺利，学姐一直在读题却都不懂，这套题A和F的题面都好坑啊，我们俩都花了将近半小时在读题和猜测题意上
我和周哥状态也不是很好，一直在思考签到题，甚至很早写了C题（喜提热心网友的表扬），中间半小时过了3题
今天应该是大家都很久没训练状态不是很好，否则应该是可以8题的，感觉E题还是很可做的
每次白给队的题目都是衡量签到成功的标准，不会再这样了
=== zyh ===
开场的A挺自闭的，题意总感觉很别扭。本来还不服sg的题意结果sgA了以后我又交了一发wa，彻底证明了我猜的题意是错的（
然后我做了什么……想了一会J和学姐讨论了一下发现可做，上去写了一会测样例发现有一个子树内路径没考虑，简单改了一下就1A了
然后就自闭了，想了很久很久的B和E，看着大家都过了可我就是不会，很难受
我还是要说学姐nb！能做出G太神仙了
快结束的时候发现B的数据范围比较小，秒了B
总体来说还是没有把握好节奏，可能也是心里没有太认真对待的缘故吧（
中档题和读题能力还要继续加强
=== sj ===
读题读的很自闭，开场读的几个题都没读懂题意
除了想出G以外什么都没干
== 题解 ==
A.
题意 给一个骰子的上面，问是否可能
做法：签到题，手玩所有情况判一下
B.
题意：给出若干点，多组询问某点最近切比雪夫距离
做法：数据范围比较小，可以直接用二维矩阵处理
bonus：（前缀和换成线段树？）
C.
题意：给个规则算分
做法：模拟即可
D.
题意：给出若干01串，问随机生成一个无限长的01串，期望多长会出现给出的串
做法：AC自动机构造出各个串之间的转换关系，每条边有1/2的权重，高斯消元解出期望
E.
题意：一个首尾相连的字符串选出若干长度给定的字串使得覆盖所有位置，使选出字串字典序最大的最小
做法：原串复制一遍贴到后面，做SA，取前n个后缀用SA再排序，多于k位的部分可以当作没有，取能全覆盖的最小后缀。
F.
题意：问有多少01串跟给定串加和后刚好有k个1
做法：一开始没看懂题意，猜测题意半天x，看懂了发现就随便做，有点数位dp的意思，处理处理就好
G.
题意：国际象棋俩个马随机走，问期望谁赢的概率大
做法：发现曼哈顿距离只会变化奇数，结果是确定的
H.
题意：轮流讲一堆石子分成若干小堆，问胜负情况
做法：考虑sg函数处理即可
I.
题意：给n(<=3e3)*4个点，要求使用这些点组成若干正方形，正方形不能互相覆盖，每个点只能且必须使用一次，求组成的若干正方形面积和
做法：每次选择一个最左下的点，选择一个面积最小的正方形。证明略~~（反正我会）~~
证明就是考虑最左下的点，x为第一关键字，形成的俩个矩形之间一定会有交，这时选择大的矩形一定会覆盖小的矩形的一个顶点，一定会出现不合法情况，因此要选择最小的矩形
J.
题意：给一个树，每个点有点权，求所有路径按位并的和v<2^20
做法：按位搞一搞，简单树上dp

流水账

开局周哥读错了A，1WA，我去写H，1A，然后写A，失误了一发才A掉，然后周哥上去写J,1A，学姐发现G题是个假的期望题，我上去过掉，1A，然后我重新读了F的题意，上去写了F，1A，然后又写了C，1A，最后幸亏是周哥发现了B题坐标的范围非常小，最后写了个二维前缀和过去了。

总结

zb

好久没有训练了，一直在担心状态会不会不是很好，正好今天这个题面三个人读起来都很不舒服。关于A题的题意，感觉周哥都想打我了，虽然我读的才是对的【小小声

后面开题也不是很顺利，学姐一直在读题却都不懂，这套题A和F的题面都好坑啊，我们俩都花了将近半小时在读题和猜测题意上

我和周哥状态也不是很好，一直在思考签到题，甚至很早写了C题（喜提热心网友的表扬），中间半小时过了3题

今天应该是大家都很久没训练状态不是很好，否则应该是可以8题的，感觉E题还是很可做的

每次白给队的题目都是衡量签到成功的标准，不会再这样了

zyh

开场的A挺自闭的，题意总感觉很别扭。本来还不服sg的题意结果sgA了以后我又交了一发wa，彻底证明了我猜的题意是错的（

然后我做了什么……想了一会J和学姐讨论了一下发现可做，上去写了一会测样例发现有一个子树内路径没考虑，简单改了一下就1A了

然后就自闭了，想了很久很久的B和E，看着大家都过了可我就是不会，很难受

我还是要说学姐nb！能做出G太神仙了

快结束的时候发现B的数据范围比较小，秒了B

总体来说还是没有把握好节奏，可能也是心里没有太认真对待的缘故吧（

中档题和读题能力还要继续加强

sj

读题读的很自闭，开场读的几个题都没读懂题意

除了想出G以外什么都没干

题解

A.

题意 给一个骰子的上面，问是否可能

做法：签到题，手玩所有情况判一下

B.

题意：给出若干点，多组询问某点最近切比雪夫距离

做法：数据范围比较小，可以直接用二维矩阵处理

bonus：（前缀和换成线段树？）

C.

题意：给个规则算分

做法：模拟即可

D.

题意：给出若干01串，问随机生成一个无限长的01串，期望多长会出现给出的串

做法：AC自动机构造出各个串之间的转换关系，每条边有1/2的权重，高斯消元解出期望

E.

题意：一个首尾相连的字符串选出若干长度给定的字串使得覆盖所有位置，使选出字串字典序最大的最小

做法：原串复制一遍贴到后面，做SA，取前n个后缀用SA再排序，多于k位的部分可以当作没有，取能全覆盖的最小后缀。

F.

题意：问有多少01串跟给定串加和后刚好有k个1

做法：一开始没看懂题意，猜测题意半天x，看懂了发现就随便做，有点数位dp的意思，处理处理就好

G.

题意：国际象棋俩个马随机走，问期望谁赢的概率大

做法：发现曼哈顿距离只会变化奇数，结果是确定的

H.

题意：轮流讲一堆石子分成若干小堆，问胜负情况

做法：考虑sg函数处理即可

I.

题意：给n(<=3e3)*4个点，要求使用这些点组成若干正方形，正方形不能互相覆盖，每个点只能且必须使用一次，求组成的若干正方形面积和

做法：每次选择一个最左下的点，选择一个面积最小的正方形。证明略（反正我会）

证明就是考虑最左下的点，x为第一关键字，形成的俩个矩形之间一定会有交，这时选择大的矩形一定会覆盖小的矩形的一个顶点，一定会出现不合法情况，因此要选择最小的矩形

J.

题意：给一个树，每个点有点权，求所有路径按位并的和v<2^20

做法：按位搞一搞，简单树上dp

附加文件