CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
=====A - LCM Problem=====

====问题描述====

给定l,r。求一组x,y满足$l\le x<y \le r$,$l\le lcm(x,y)\le r$

====数据范围====

$1\le l<r \le 10^9$

====解题思路====

因为x<y，所以$lcm(x,y)\ge 2x$。若$r<2l$则无解，否则输出$l,2l$。

=====B - Array Walk=====

====问题描述====

给定长为n序列a。一开始在第一格，分数是$a_1$。每次可以向左或向右走一格，但最多一共向左走z次，且不能连续向左走两格。问走k次后最大分数。

====数据范围====

$2\le n\le 10^5$,$1\le k\le n-1$,$0\le z\le 5$

====解题思路====

dp1[i][j]表示走到i，一共向左走了j次，且最后一次是向右走的最大分数。dp2[i][j]表示走到i，一共向左走了j次，且最后一次是向左走的最大分数。

递推的时候记得在外面循环j。通过位置和向左走的步数，可以推出一共走了几次。

=====C - Good String=====

====问题描述====

给定一个由数字构成的字符串。问最少删去几个，可以满足$t_2t_3t_4\cdots t_{n-1}t_nt_1$=$t_nt_1t_2\cdots t_{n-2}t_{n-1}$

====数据范围====

$2\le|s|\le 2\cdot 10^5$

====解题思路====

若n为奇数，要求$t_1=t_2=...=t_n$；若n为偶数，要求$t_1=t_3=...=t{n-1}$，$t_2=t_4=...=t_n$

所以，只需枚举最终的$t_1,t_2$，每种可以$O(|s|)$求值。

=====D - Segment Intersection=====

====问题描述====

一开始有n个a区间，每个都是$[l_1,r_1]$，n个b区间，每个都是$[l_2,r_2]$。每次操作可以将一个区间向外扩展1。问最少多少次操作，使得$\sum_{i=1}^n（a_i和b_i交集的长度）\ge k$

====数据范围====

$1\le n\le 2\cdot 10^5$,$1\le k\le 10^9$,$1\le l_1\le r_1 \le 10^9$,$1\le l_2\le r_2 \le 10^9$

====解题思路====

分类讨论即可。若两个区间相离，可以枚举我们要操作其中i个区间。不多解释

=====E - Calendar Ambiguity=====

====问题描述====

一种历法，一年有m个月，每个月有d天，每周有w天。求数对(x,y)的个数，$x<y$且x月y号和y月x号的都是星期某。

====数据范围====

$1\le m,d,w\le 10^9$

====解题思路====

等价于要求$xd+y\equiv yd+x pmod w$,即$(y-x)(d-1)\equiv 0 pmod w$。设$n=gcd(d-1,w)，w_0=\frac w{n}$。等价于要求$w_0 | y-x$

枚举y-x，再等差数列求和即可。

=====F - Biocolored Segments=====

====问题描述====

给定n个闭区间，每个区间有一个颜色t。从中取若干区间，要求任意两个颜色不同的区间没有交集为空。问最多取几个区间

====数据范围====

$1\le n \le 2\cdot 10^5$,$1\le l_i \le r_i \le 10^9$,$t_i\in \{1,2\}$

====解题思路====

每个区间建一个点。若两个区间不能放在一起，则连上边。本题等价于求这个二分图的最小割（去掉若干个点，剩余点两两不相连），也就等价于求这个二分图的最大匹配。

这个最大匹配我们可以贪心。首先按区间左端点排序。每次放入一个新点，删去原图中所有右端小于新点左端的点。找到与新点颜色不同的点中，右端最小的，和其进行匹配。

设这个最大匹配是m，最终答案为n-m

=====G - Directing Edges=====

不会，跳了
CVBB ACM Team

用户工具

站点工具

页面工具
