CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
^  A  ^  B  ^  C  ^  D  ^  E  ^  F  ^
|  +  |  +  |  +  |  +  |  +  |  O  |
rank:433
 
=====A=====
  * 题意:卡其脱离太

  * 题解:莫那莫那一

=====B=====
  * 题意:水题

  * 题解:但是我跟没睡醒一样这么水都能卡半个小时，光速下分，太菜了。

=====C=====
  * 题意:两桶不同温度的水，先放一杯热的到一个无限桶里，再放一杯冷的到一个无限桶里，轮流交替，至少要放一次，问最少放多少次可以使得无限桶里水的平均温度和题目给出的温度最接近。

  * 题解:放偶数次得到的就是两种温度的平均值，否则奇数次越放温度越低，二分一下即可，卡精度要用$long long$，这题又卡了半个小时，吐了。

=====D=====
  * 题意:给定一个整数序列，可以选择一个区间，删除其中的一个最大值，使剩下没被删的数和最大，求这个最大值。

  * 题解:枚举每一个元素作为最大值时可以得到的答案。两遍单调栈找到左右区间，然后维护区间前后缀最小值即可。

=====E=====
  * 题意:求满足下列条件的长度为$k$的序列数量，$1 \le a_1 < a_2 < \dots < a_k \le n$且对任意非负整数$x$有$(((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k}$，其中$p_i$是任意一个$1$到$k$的排列。$(1 \le n, k \le 5 \cdot 10^5)$

  * 题解:如果$a_i(i > 1)$都是$a_1$的倍数显然满足条件，否则一定存在非负整数$x$使得第二个条件不成立。因此答案为$\sum_{i=1}^{n}{\binom{k - 1}{n / i - 1}}$。

=====F=====
  * 题意:$n$个点，每个点有一个速度和方向，求最短时间使得存在两个点的路径有交点。$(1 \le n \le 25000)$

  * 题解:本质就是二分时间+求$n$条射线是否有交点。这个题给了六秒，可以$O(n^2)$卡过<del>（不知道是不是故意的）</del>。正解是$O(n \log^ 2 n)$的扫描线。考虑一条竖直的扫描线，按照线段的左右端点加入和删除每条线段到一个set里。我们用竖直扫描线与每条线段交点的纵坐标的大小来定义两条线段的大小。显然如果没有交点，那么两条线段的大小关系不会随着扫描线的变化而变化，而如果有交点这个算法就结束了。画图可以发现，如果两个线段有交点，那么一定存在扫描线的一个位置使得这两个线段在set中是相邻的。因此我们只需要每次加入和删除线段的时候判断一下新产生的相邻线段是否相交即可。因为这题有可能一条射线和一个点相交，直接判断线段相交容易因为精度而WA，因此我们可以直接求出对应直线的交点，然后判断交点距离两个起始点是否位于正确的方向以及适当的距离即可。注意如果两直线平行，需要讨论共线以及不共线的情况。
CVBB ACM Team

用户工具

站点工具

页面工具
