2016-C04-team5

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== wtthhh === 
今天跟往常差不多，最后还是有两个题没有写完。可写的题比较多，最后过了4题，前期还是比较顺利，没有大的失误。比较挫的地方就是G题，最后也没能过掉，以后不应该一直跟榜，什么时候该弃题是一门玄学。。
== 总结 ==

=== jcq1234 ===
 * 今天又划了一天水。。。
 * 英语水平还是要学习一个，题目描述太长读不懂
 * 依然还是不能太纠结一道题目，大家都过了的题不一定真的简单。。

=== wtthhh ===
 * 今天的C题是个验证图是不是二分图，当时想到了奇偶环的问题，但没有想清楚包含关系怎么处理，如果多想一想的话应该能解决
 * E题是个水二分匹配，当时差点敲了网络流模板。。感觉模板还是敲自己的比较舒服，比赛的时候打印一波自己的模板？
 * G题最后用动态开内存树状数组还是T了，非常不爽。。cdq分治原来也做过不少题。。现在都忘了ˊ_>ˋ。。唉
 * 计算几何十分有趣，球面上求线面交之类的。。比赛的时候想了一下还是弃了。。感觉很容易被坑，要补一波
 * 配合比之前稍微好了一点？

=== triomino === 
 * 读题要读清楚，A题读题不清胡乱做题浪费了时间。
 * D会爆int没有考虑太蠢了。

 == 题解 ==

=== B ===
把所有包括其他区间的区间和不包括其他区间的区间分成两份。对不包括其他区间的区间的数组排序。最优的解一定是相邻的区间分到同一个组，因此可以用动态规划解决。然后再考虑包含其他区间的区间数组，这些区间只有在单独分配到一组的情况下可能产生更大的答案。所以先对数组排序，然后从左到右枚举前i个员工独立分配的情况。

=== F ===
球面上求线面交，两段弧的交点必定属于这两个弧所在大圆的交点。叉积求得弧所对应的大圆的向量，两个大圆的向量叉积即可得到两个交点的单位向量，验证一下哪个是交点。


=== G ===
1、CDQ分治
2、三个序列中，考虑一对关系，如果不符合条件，则必然出现两个逆序对，用总对数减去逆序对数即可

 == 补题 ==

=== imjcq ===
 * ~~B~~, ~~G~~

=== wtthhh ===
 * ~~C~~, ~~F~~

=== triomino ===
 * ~~G~~， ~~B~~

流水账

wtthhh

今天跟往常差不多，最后还是有两个题没有写完。可写的题比较多，最后过了4题，前期还是比较顺利，没有大的失误。比较挫的地方就是G题，最后也没能过掉，以后不应该一直跟榜，什么时候该弃题是一门玄学。。

总结

jcq1234

• 今天又划了一天水。。。
• 英语水平还是要学习一个，题目描述太长读不懂
• 依然还是不能太纠结一道题目，大家都过了的题不一定真的简单。。

wtthhh

• 今天的C题是个验证图是不是二分图，当时想到了奇偶环的问题，但没有想清楚包含关系怎么处理，如果多想一想的话应该能解决
• E题是个水二分匹配，当时差点敲了网络流模板。。感觉模板还是敲自己的比较舒服，比赛的时候打印一波自己的模板？
• G题最后用动态开内存树状数组还是T了，非常不爽。。cdq分治原来也做过不少题。。现在都忘了ˊ_>ˋ。。唉
• 计算几何十分有趣，球面上求线面交之类的。。比赛的时候想了一下还是弃了。。感觉很容易被坑，要补一波
• 配合比之前稍微好了一点？

triomino

• 读题要读清楚，A题读题不清胡乱做题浪费了时间。
• D会爆int没有考虑太蠢了。

题解

B

把所有包括其他区间的区间和不包括其他区间的区间分成两份。对不包括其他区间的区间的数组排序。最优的解一定是相邻的区间分到同一个组，因此可以用动态规划解决。然后再考虑包含其他区间的区间数组，这些区间只有在单独分配到一组的情况下可能产生更大的答案。所以先对数组排序，然后从左到右枚举前i个员工独立分配的情况。

F

球面上求线面交，两段弧的交点必定属于这两个弧所在大圆的交点。叉积求得弧所对应的大圆的向量，两个大圆的向量叉积即可得到两个交点的单位向量，验证一下哪个是交点。

G

1、CDQ分治

2、三个序列中，考虑一对关系，如果不符合条件，则必然出现两个逆序对，用总对数减去逆序对数即可

补题

imjcq

• B, G

wtthhh

• C, F

triomino

• G， B