Codeforces Global Round 15
source link: http://www.shuizilong.com/house/archives/codeforces-global-round-15/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
https://codeforces.com/contest/1552
Problem C.
给定一个圆环，初始已经连了一些线段，要求连剩下的线段，问最优情况下，最后总交点最多是多少。
不考虑已经连的线段，对于剩下的我们按照最优情况 1234..1234.. 这样连就行。。
最后把已经连的拉进来一起统计即可。
Problem D.
给定一个长度为 n 的序列 a，问是否可以构造一个长度同样为 n 的序列 b，使得 a 中的每个元素都是 b 中某两个元素的差。
n <= 10
Problem E. Colors and Intervals
给 n 种颜色，初始时给长度为 n*k 个位置染色，使得每种颜色恰好出现 k 次。
求构造 n 组区间的方案，满足对于每种颜色，都有一组区间的端点是这种颜色。
且，不存在某个位置，使得被区间覆盖超过 \ceil{n, k-1} 次。
(n, k <= 100)
贪心？显然我们总是选择那些尽可能小的区间，因此对于每种颜色，我们只需要考虑 k-1 种相邻的区间即可。
我们按照所有区间大小排序来依次选择？很遗憾这样是错的。但是稍微改改，按照每个区间的右端点来排序就对了。
证明？反证法。
考虑某种颜色，我们枚举了所有 k-1 种区间发现都不满足，那么对于这些区间 [a, b]，
每个区间都存在 \ceil{n, k-1} 个区间使得它们的右端点均位于 [a, b] 的内部，因为覆盖 [a, b] 的区间因为右端点比 b 大还没有被我们扫描到。
那么此时一共已经选择了 (k-1)*\ceil{n, k-1} >= n 个区间，但是我们还没有选择那么多，与假设矛盾。
Problem F. Telepanting
数轴上有 n 个传送门，每个传送门用三元组表示为 (xi, yi, {0,1})，表示传送门所在位置为 xi，传送的目标位置为 yi，以及当前是否 active。（yi < xi）
有一只蚂蚁从 0 出发，每个单位时间向右移动一格，当走到传送门时，如果 inactive 则变为 active，如果 active 则被传送至 yi 并置该传送门为 inactive。
问走到 xn + 1 需要多少时间。
Posted by
xiaodao
Category: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK