2019 Shandong CPC

来自PC Wiki
跳到导航 跳到搜索

Records

Problems

Solutions

A(Solved by : lzy)

考虑每个月都是整周,于是算一下2000-1-1是星期几作为base即可.

B(Solved by : zhn)

我们定义当前状态与目标状态不同的位置数为距离,那么有动态规划.

定义$$dp_{i, j}$$为前$$i$$轮,距离为$$j$$的方案数,那么我们可以利用组合数转移.

C(Solved by : lzy)

注意到最优解只会在第一轮或者最后一轮取到,模拟即可.

D(Solved by : lzy)

总能取到剩$$n - 1$$条边作为生成树,算下是哪个倒霉蛋即可.

E(Solved by : zhn)

考虑对于每个$$a_i$$,他上一次出现的位置为$$pre_i$$,然后我们就找出$$(pre_i,i)$$中有多少不同的数,记为$$k$$,那么就在答案数组中$$[1,k]$$上加一。

F(Solved by : sqc)

设我们最后要统一高度为$$x$$,把所有元素$$- x$$; 二分找出$$\text{正的} \geq \text{负的}$$的最大的$$x$$,答案就是正的元素的和

G(Upsolved by : lzy)

我们从后向前考虑建堆的过程。

在这个过程中,贪心地将当前位置的$$b_i$$尽量填$$0$$,必须填$$1$$再填$$1$$。

我们会发现这样的情况下,插入$$a_i$$之前的序列是可以唯一确定的。

于是从后向前模拟这个过程贪心即可,事实上因为这也是模拟建堆,所以复杂度依然是$$O(n)$$。

H(Solved by : zhn)

线段按左端排序,然后扫描时坐标$$+ 1$$

把左端在当前坐标的线段扔进堆,把右端小于当前坐标的扔出堆,同时在堆里维护右端

当堆空时直接跳到下一个线段的左端

I(Solved by : lzy)

我们考虑一个区间如果连通,那么区间内部点之间的边数一定是区间点数减一.

我们将边按大编号点指向小编号点定向.

从左向右枚举区间的右端点$$r$$,并将该点指出的边做对应修改.

考虑如果区间$$[l, r]$$可行,那么有$$\sum_{i = l}^r d(i) = r - l$$,其中$$d(i)$$表示$$i$$号点当前的入度.

我们考虑计算以$$r$$为右端点的后缀和,记为$$s(i)$$,那么若$$s(i) = r - i$$,则$$[i, r]$$是合法区间.

我们令初始值$$s(i) = i$$,则题目转化为区间加一和求区间最大值以及个数,线段树维护即可.

J(Upsolved by : lzy)

观察发现,原图是存在欧拉回路,因此我们考虑删除一条路。

因为删除一条路后,原图存在欧拉路,所以欧拉路权值和最大等价于删除的路权值和最小。

我们从起点向终点跑一遍最短路,删除最短路上的边之后,再跑一遍欧拉路即可。

K(Upsolved by: sqc)

考虑将$$a$$拆成$$2^c*l$$,

然后$$a^x=2^{cx}*l^x$$

$$x < \left\lceil \frac{p}{c} \right\rceil$$时,暴力check

$$x \geq \left\lceil \frac{p}{c} \right\rceil$$时,$$2^c * l \equiv 0 \pmod{2^p}$$

此时要求$$x^a \equiv 0 \pmod{2^p}$$

其中$$\left\lceil \frac{p}{c} \right\rceil \leq x \leq 2^p$$

考虑将$$x$$也写成$$2^k * t$$的形式,即$$2^{ak} * t^a \equiv 0 \pmod{2^p}$$

此时$$a * k < p$$时无解

$$a * k \geq p$$时, $$\left\lceil \frac{p}{a} \right\rceil$$为最小的$$k$$,记为$$m$$,所有$$\left\lceil \frac{p}{c} \right\rceil \leq x \leq 2^p$$的$$x$$,满足$$x$$是$$2^m$$的倍数的$$x$$都符合

所有答案就是$$2^p / \left\lceil \frac{p}{a} \right\rceil - \left( \left \lceil \frac{p}{c} \right\rceil - 1 \right) / \left\lceil \frac{p}{a} \right\rceil$$

加上之前暴力计算的就是最终答案

L(Solved by : sqc)

先传递闭包判断环,有环则全为$$0$$

传递闭包搞出可达$$x$$和$$x$$可达的点的数量,记为$$a$$和$$b$$

然后就是$$a, b$$都要小于$$\frac{n + 1}{2}$$就满足

M(Solved by : sqc)

$$\log$$次答案就会变成$$1$$,暴力