COCI 2020-2021#2

cc0000 · 2022-09-04 22:04:21 · 个人记录

COCI2020-2021 #2 讲解

T1 Crtanje

Josip 想给他的公司画一张描述财务状况的折线图。他现在已经知道 n 天中，相比前一天，公司是盈利，亏损，还是收支平衡。在折线图上，对于这一天，如果盈利，则用 / ,亏损则用 \ ，收支平衡则用 _ ,空白则用 . 代替

Josip 需要用最少的面积表示出所有的信息，请你帮他画出这张图（这题网上没有翻译，我自己语文也不好，看不懂的话一定是我的锅 QwQ）

样例输入1

7
++---==

样例输出1

./\....
/..\...
....\__

样例输入2

5
+=+=+

样例输出2

..._/
._/..
/....

没啥要讲的，就照着题意画一下，边界好好看一下就行了（简单到洛谷没有原题）

T2 Odašiljači

二维平面上有 n （n\leq 10^3）个无线电基站，你可以调整每个无线电基站的辐射范围，辐射范围相交的无线电基站可以互相通信，假设 a 和 b 可以相互通信，b 和 c 可以相互通信，则 a 可以通过 b 和 c 通信。求出最小的辐射范围使得所有的基站可以相互通信。（题面也是我自己翻译的）

（我知道这题很简单，但是我不知道能不能再加强，所以帮我想想能不能加强啊 QAQ）

二分辐射范围，对于可以直接通信的基站连边，然后 O(n) 判一下图是否联通

复杂度 O(n^2logn)

T3 Euklid

对于正整数 a, b，定义 R(a, b) 为：

\begin{cases}R(b,a)&a<b\\R\left(\left\lfloor\dfrac{a}{b}\right\rfloor,b\right)&1<b\leq a\\a&1=b\leq a\end{cases}

给定正整数 g, h，求正整数 a, b 使得 \gcd(a,b)=g，R(a,b)=h。

保证 g,h \leq 2\times10^5 （能加到 10^9）

可以证明一定有解且答案的大小一定在 10^{18} 以内

1 \leq g \leq 2\times 10^5,2 \leq h \leq 2\times 10^5

答案不唯一，输出任意一组解即可

人类智慧题

令 a=xg,b=yg,a<b

R(a,b)=R(\lfloor \frac b a\rfloor,a)=R(\lfloor \frac{y}{x}\rfloor,xg )

然后我们来研究一下这个 R 函数

再往下回溯一步 $R(1,h)=R(h,H),(\lfloor \frac H h\rfloor =h)

也就是说 H\in [h^2,2h^2)

再往下找几步就会发现 R(a,b)=R(\lfloor \frac x y\rfloor ,xg),\lfloor \frac y x \rfloor=h, xg\in [h^i,2h^i), 所以只需要找到最小的 i 满足条件使得 h^i > g ，这样在 [h^i,2h^i) 中一定存在一个 g 的倍数，x=\lceil \frac {h^i}{g}\rceil

然后 a 就求出来啦，我们现在想求 y

其实只需要 $y=x\times h +1$ 就可以。（但是在这里需要注意一点细节，就是 $x\not = 1$ ,因为 $x=1$ 时，$y=h+1$, 此时 $x$ 与 $y$ 不互质，所以在上面求 $x$ 时，如果 $h^i=g$ 时，$x$ 需要再加一步）因为相邻两个数一定互质，同时也能保证 $\lfloor \frac y x \rfloor = h

结论就是 a=\lceil \frac {h^i} {g}\rceil g,b=a\times h+g

代码 5 行搞定

复杂度是 O(log_{h}g)

T4 Sjekira

一棵树，每个点都有点权，删去一条边的代价为这条边连接的两个子树里的点权最大值的和，求把所有边删去的最小代价。

n\leq 10^5

（Tips：貌似 O(nlogn) 还挺好想的，但是正解是 O(n)）

先说 O(nlogn)，很容易想到先把权值大的点周围的边删空是更优的，因为如果留着权值大的点，那么就能贡献更多次的答案，就会使答案变大。

于是我们反着想，把删边改成连边。那就是要先从小到大把点排序，维护一个并查集，把所有与当前点有的边连到的 y_i 所在的联通块全都合并，合并一次的代价是两个联通块的最大值的和。

复杂度卡在排序上

然后说 O(n) 的做法，说实话我真不知道这玩意咋想出来的，好神仙的式子

\displaystyle ans=\sum_{i=1}^n a[i]-\underset{1\leq i\leq n}{max} a[i]+\sum_{i=1}^{n-1} max(a[X[i]],a[Y[i]])

因为每次删的是当前最大的点的点权加上另外一端剩余子树的最大值，所以除了最大点，每个点都当过一次子树内最大值，肯定都有一次这样的贡献。然后每条边删掉的时候，那个作为当前最大的点也一定是每条边中较大的那个，所以要加上每条边中较大的权值

T5 Svjetlo

给出一颗树，树上每个节点有一个灯泡，你可以任选一个节点开始走，到任何一个节点结束，每次走到一个节点都要按一下节点上的开关，使亮的灯关上，关的灯打开。保证树上一定有关着的灯，问最多走多少步可以使整棵树的灯都亮着。

啊这个题的 DP状态好像似曾相识，但我忘了是哪个题了

既然是走的一段路径，至少得知道两个端点吧

$g[p][0/1]$ 指经过 $p$, 一个端点在子树里，另一个在子树外， $p$ 的状态为不亮/亮的最小步数 $h[p][0/1]$ 指经过 $p$ ,两个端点都在子树里，$p$ 的状态为亮 / 不亮的最小步数为了好转移， $f$ 伸出去的两个端点把其中一个算在 $p$ ,$g$ 应该伸出去的头算在 $p$ 上，$h$ 伸出去的两端点算一个在 $p$ 上然后就是大力分类讨论画张图搞一搞还不是很难想（（（（现在我们假设一个点前面的子树都更新完了，现在要加一棵子树进去。设 $f_0,f_1,g_0,g_1,h_0,h_1$ 为加入这棵子树之前的状态然后上转移方程 $f[p][1]=min(f_0+f[v][0]+2,f_1+f[v][1]+4)$ （这里的 +2 是走一次，但是如果走一次 $p$ 和 $v$ 的灯全灭了，就再转一圈，后面同理） $f[p][0]=min(f_1+f[v][0]+2,f_0+f[v][1]+4)

g[p][1]=min(g_0+f[v][0]+2,g_1+f[v][1]+4,f_0+g[v][1]+1,f_1+g[v][0]+3)

g[p][0]=min(g_1+f[v][0]+2,g_0+f[v][1]+4,f_1+g[v][1]+1,f_0+g[v][0]+3)

h[p][1]=min(h_0+f[v][0]+2,h_1+f[v][1]+4,f_0+h[v][0]+2,f_1+h[v][1]+4,g_1+g[v][1],g_0+g[v][0]+2)

h[p][0]=min(h_1+f[v][0]+2,h_0+f[v][1]+4,f_1+h[v][0]+2,f_0+h[v][1]+4,g_0+g[v][1],g_1+g[v][0]+2)

画张图理解一下

（~~自己画的图，凑合着看吧~~）

那端点在子树内的情况画完了，还有端点在 p 上的情况

g[p][1]=min(g[p][1],f[p][0]+1)

g[p][0]=min(g[p][0],f[p][1]+1)

h[p][0]=min(h[p][0],g[p][0])

h[p][1]=min(h[p][1],g[p][1])

一点细节

如果当前子树一开始就没有关上的灯泡，那就不用往下走了
把一个关着的灯泡当作根，因为所有转移是要回到根的，如果根是亮着的，那就没必要往根走了
答案就是 h[rt][1]

挺好的一个树形 DP