2020-team11-C10

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team11 返回]

== 概述 ==

solved: 4/12  dirt: 50%

rank: 11


==  ==

== 总结 ==

开场Qza有事没有来，一开始是Zhw和Wjh双打。开局看A觉得没有思路，开始分工翻译题面，直到有人过了H，开始看H，Zhw和Wjh讨论了一下觉得是水题，开始敲，敲完交了1发Wa了，手玩数据没有发现问题，觉得先放一下H开始看G，也是签到题就开始码，交了一发还是Wa了，检查了一会发现是全是1的情况没有特判，判掉之后交了就A了。回头看H，发现bug，改了交了A掉。之后去看D，也是签到，写完交了结果输出格式落了一个：导致贡献了一发Wa。J题也是签到题，写完J的时候过去了两个半小时。之后看B题过了很多人，遂去看B，一开始想找规律然后矩阵优化，思路不通放弃，改为想卷积。但是由于Zhw卷积很烂没有想出来，于是换题L，计算几何，觉得细节偏多不敢开题换回B。
Qza在三个半小时的时候回来，回来之后讨论了B一会，无果，Qza开始开L，Zhw开始看A。但是最后由于时间不够，QzaL没写完，Zhw在最后十分钟确定了A的做法上机写A，但由于Bug没调出来最后于比赛结束两分钟A掉。

赛后Qza过掉了L，发现错误在于少一个特判情况以及把行列式写错了。

== 题解 ==

A.考虑合并。最大的数肯定会和前面的数一起放。那么将两个数合并成一个数，它们的权值就变成了两个数的平均数。以此类推，A和B两个数组最后全部会变成递减的两个数组，贪心即可。

B.

C. 

D.连续的三个数翻转可以看成间隔一个位置的两个数翻转，那么将数组按奇数位和偶数位分组，只需分别考虑各组相邻换换成相等的数组需要几次即可。

E.

F.

G.将数组排序，取两两差值的gcd，最后所有数必定会变成这个gcd的倍数。那么只需要取gcd的所有素因子，看A[1]需要操作几次才能变成这个素因子的倍数即可。

H. 贪心策略。考虑前面全放a，直到前面不同位数的差值大于等于后面字母不同位数的个数。后面两个字母相同放a，不同则放其中一个数组的字母。

I.

J.看起来是博弈，实际上最终状态是确定，即无论按什么顺序取石子，最终状态是一样的，所以只需要考虑会操作几次。

K.

L.疯狂讨论即可。首先取白色线段的任意一点向黑色线段两端点连直线，记这两条直线的方向向量为v1和v2，在一般情况下，这两条直线将平面分成4个部分，容易发现，白线段的另一个端点落到四个区域中的两个时无解，落到另外两个区域时有解。判断是否有解可以用白线段的方向向量叉乘v1和v2，判断这两个叉乘结果是否同号，同号有解，异号无解。如果上述两条直线重合，特判白线段另一个点是否也在直线上，在则输出0，否则输出无穷。判断有无解之后，就要判断解是否为无穷。将白线段两端点和黑线段两端点相连，此时需保证他们不交于两直线中间（即交点在两直线同侧），解出交点坐标，解为无穷当且仅当该点离黑线段更近。此处的判断我写得很繁琐，以上为我化简过的思路。否则，知道了白线段端点、交点，即可用叉乘求三角形面积。记得要开double，交点坐标很可能不是整数。

[/wiki/2020-team11 返回]

概述

solved: 4/12 dirt: 50%

rank: 11

总结

开场Qza有事没有来，一开始是Zhw和Wjh双打。开局看A觉得没有思路，开始分工翻译题面，直到有人过了H，开始看H，Zhw和Wjh讨论了一下觉得是水题，开始敲，敲完交了1发Wa了，手玩数据没有发现问题，觉得先放一下H开始看G，也是签到题就开始码，交了一发还是Wa了，检查了一会发现是全是1的情况没有特判，判掉之后交了就A了。回头看H，发现bug，改了交了A掉。之后去看D，也是签到，写完交了结果输出格式落了一个：导致贡献了一发Wa。J题也是签到题，写完J的时候过去了两个半小时。之后看B题过了很多人，遂去看B，一开始想找规律然后矩阵优化，思路不通放弃，改为想卷积。但是由于Zhw卷积很烂没有想出来，于是换题L，计算几何，觉得细节偏多不敢开题换回B。

Qza在三个半小时的时候回来，回来之后讨论了B一会，无果，Qza开始开L，Zhw开始看A。但是最后由于时间不够，QzaL没写完，Zhw在最后十分钟确定了A的做法上机写A，但由于Bug没调出来最后于比赛结束两分钟A掉。

赛后Qza过掉了L，发现错误在于少一个特判情况以及把行列式写错了。

题解

A.考虑合并。最大的数肯定会和前面的数一起放。那么将两个数合并成一个数，它们的权值就变成了两个数的平均数。以此类推，A和B两个数组最后全部会变成递减的两个数组，贪心即可。

B.

C.

D.连续的三个数翻转可以看成间隔一个位置的两个数翻转，那么将数组按奇数位和偶数位分组，只需分别考虑各组相邻换换成相等的数组需要几次即可。

E.

F.

G.将数组排序，取两两差值的gcd，最后所有数必定会变成这个gcd的倍数。那么只需要取gcd的所有素因子，看A[1]需要操作几次才能变成这个素因子的倍数即可。

H. 贪心策略。考虑前面全放a，直到前面不同位数的差值大于等于后面字母不同位数的个数。后面两个字母相同放a，不同则放其中一个数组的字母。

I.

J.看起来是博弈，实际上最终状态是确定，即无论按什么顺序取石子，最终状态是一样的，所以只需要考虑会操作几次。

K.

L.疯狂讨论即可。首先取白色线段的任意一点向黑色线段两端点连直线，记这两条直线的方向向量为v1和v2，在一般情况下，这两条直线将平面分成4个部分，容易发现，白线段的另一个端点落到四个区域中的两个时无解，落到另外两个区域时有解。判断是否有解可以用白线段的方向向量叉乘v1和v2，判断这两个叉乘结果是否同号，同号有解，异号无解。如果上述两条直线重合，特判白线段另一个点是否也在直线上，在则输出0，否则输出无穷。判断有无解之后，就要判断解是否为无穷。将白线段两端点和黑线段两端点相连，此时需保证他们不交于两直线中间（即交点在两直线同侧），解出交点坐标，解为无穷当且仅当该点离黑线段更近。此处的判断我写得很繁琐，以上为我化简过的思路。否则，知道了白线段端点、交点，即可用叉乘求三角形面积。记得要开double，交点坐标很可能不是整数。