标签:# 计算几何

Educational Codeforces Round 48

Code A - Death Note B - Segment Occurrences C - Vasya And The Mushrooms D - Vasya And The Matrix E - Rest In The Shades F - Road Projects G - Appropriate Team (咕咕咕) A - Death Note 模拟翻页就好,用一个数记录当前剩余的页数 B - Segment Occurrences 计算字符串sss的每个位置是否满足往后mmm位等同于ttt 查询的时候要判断区间的范围是否合法 因为N<=1000N<=1000N<=1000,所以可以直接O(n2)O(n^2)O(n2)暴力处理,然后暴力查询 C - Vasya And The Mushrooms 维护值比较麻烦的一道DP 可以发现,会进行以下几步 1. 进入新的一列, 2. 选择往右走的话,那么后面选择的方案是唯一,直接算出价值 3. 如果选择往上或往下(看进入新列时所在的位子是在第一行还是第二行),那么就会回到第一步 因此我们考虑维护每次往右走方案的价值,然后枚举列,计算出最大值即可 往右走的路径是一个环,根据所在行的不同,需要维护上方开始的环和下方开始的环,然后前缀和处理即可 D - Vasya And The Matrix 构造题 如果所有行的异或和 与 所有列的异或和 异或的结果不为000,那么肯定输出NoNoNo 否则我们考虑在最后一列和最后一列放数字,其他全部放0,这这样除了矩阵最右下角的数字以外 其他行和列是肯定满足的,最后一个也可以直接通过异或算出来 E - Rest In The Shades 对于每一个点,根据其所在的纵坐标,我们可以构造相似三角形 然后求出线段ABABAB覆盖的最左点与与最右点 也就是 $(y-d) / d 倍的倍的倍的AB$ 长度 然后二分找到边界,利用前缀和统计时间后再除回原时间即可 F - Road Projects 将1−n1-n1−n路径扯成一条链,其余的点都是挂在链上的点 如果某一个链上挂了两个点,那么无论怎么加边,都直接将边放在两点上,答案都是不变的 不然就只有挂在链上的一个点的情况 ,然后剩余情况就扫描以下即可
Read More ~

「POJ3304」 Segments

Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Read More ~