2020.07.18 2020牛客暑期多校训练营(第三场) prob:7:8:12
rnk:112/1175
2020.07.20 2020牛客暑期多校训练营(第四场) prob:4:5:10
rnk:60/1112
2020.07.23 2020.07.23codeforces加训 prob:6:6:11
rnk:7/17
做了点后缀自动机的题。
牛客三
牛客四
无
牛客三
牛客四
题目链接:Takahashi's Basics in Education and Learning
tag:矩阵快速幂 思维
题意:
给一个等差数列的首项 $A$ 公差 $B$ 和项数 $L$,把这 $L$ 项连接起来得到一个很长的整数。求这个数对 $M$ 取模的结果。
$1 \le L,A,B \le 10^{18}$
$1 \le M \le 10^9$
保证等差数列的每一项都不超过 $10^{18}$。
题解:
如果暴力维护答案就是 $ans = ans \times 10^{bits} + a_i$,这种线性递推式考虑用矩阵快速幂优化。
把 $L$ 项按照位数划分,对于每一组位数为 $\text{bits}$ 的项,都构造如下矩阵:
$$ \begin{bmatrix} 10^{bits} & 1 & 0 \\ 0 & 1 & B \\ 0 & 0 & 1 \end{bmatrix} $$
左乘矩阵
$$ \begin{bmatrix} ans \\ a_i \\ 1 \end{bmatrix} $$
代码:
推荐理由:
做矩阵快速幂的题只在刷专题的时候做过,然而比赛的时候容易想不到,可以用来提示一下^。以及这个按位拆分也挺有意思的(吧)。
来源:在做POJ 3004 Subway Planning的时候看到了这个——三类贪心区间覆盖问题 BY Ra煞
tag:贪心。
概述:
1. 给出 $n$ 个区间,问最少使用多少个可以实现某个大区间的完全覆盖?
2. 给出 $n$ 个区间,问最多选择多少个可以使得两两不重叠?
3. 给出 $n$ 个区间,问最少选择多少点可以使得每个区间中都有至少一个点(点可被共用)?
答案:
1. 排序,枚举起始区间,之后选择左端点在当前覆盖范围内且右端点最大的一个,重复直至目标达成。
2. 排序(第一关键字左端点从大到小,第二关键字右端点从小到大),按顺序尝试加入每一个区间(这个顺序可以维持留给左边的空白区域达到极大),如果重叠则丢掉。
3. 排序(第一关键字左端点从小到大,第二关键字右端点从小到大),按顺序加入,维护当前重叠区域的右端点,如果新区间左端点大于当前右端点,则丢掉之前维护的区域答案++
增加一个点,否则如果新区间右端点小于当前右端点,更新右端点。
comments:虽然很简单但可能会在出现在奇怪的辅助位?可以撕烤一下。
来源:uoj#171
tag:带花树,一般图匹配。
概述:
给定$n$个球和$m$个篮子,每个篮子最多放3个球,给定$e$个关系,关系$(x,y)$代表编号为$x$的球可以放在编号为$y$的篮子里,我们定义一个半满的篮子为篮子中有不超过1个球。
问最多有多少半满的篮子,并给出其中一种方案。
答案:
可以先设想,每个篮子都是一个有三个凹槽,所以我们把一个篮子拆成3个点,如果一个球和这个篮子有关系,那就把这个球和三个凹槽都连上边。同时我们把这三个凹槽之间也相互连边,这样我们得到的这个图的最大匹配数其实就相当于半满的篮子数+n。
因为题目中保证有一种方案能放下所有的球,而如果某个篮子是半满的篮子,那么一定有两个凹槽形成了一个匹配。所以我们把匹配好的球从答案中减去,就是半满的篮子数。
comments:因为上周出现了带花树所以做一点带花树的题,这是一个比较妙的建图。