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.