Bippity Jippity Bugaboos

[TOC]

1. CF1214H - Tiles Replacement [Euclid]

题面

给定一棵 $n$ 个点的树，要求将其每个点染上 $1\sim k$ 中的一种颜色，使得任意长为 $k$ 的路径均包含 $k$ 种不同的颜色，要求给出构造或判定无解

$1\le k\le n\le2\times10^5$

题解

我们找出这棵树的直径 $u\leftrightarrow v$，如果直径 $<k$ 那么随便构造，可以发现直径上的点的染色是固定的（所有情况均对称）

考虑直径 $\ge k$ 的情况，如果有一条支链 $x\leftrightarrow y$ 和 $u\leftrightarrow v$ 的公共点为 $x$，且 $len(u\leftrightarrow y)\ge k\land len(v\leftrightarrow y)\ge k$，那么不难发现当 $k\ge2$ 时一定无解，$k=2$ 的情况可以特判掉

一条支链 $x\leftrightarrow y$ 一定至多和直径的一边形成长度 $\ge k$ 的链

如果没有形成长度 $\ge k$ 的点那和其他链也不可能形成，因此随意染色即可

否则我们按照支链上的点 $x$ 到直径的距离以及支链与直径相交的点的颜色来给 $x$ 染色即可，只有这样染色不会产生跨过支链与直径的链不符合要求的情况，那我们需要考虑是否会形成支链内部的链不符合要求

这是不可能的，设我们考虑的两条支链为 $x\leftrightarrow y,x\leftrightarrow z$，那么 $len(y\leftrightarrow z)\le len(x\leftrightarrow y)+len(x\leftrightarrow z)$，如果 $len(x\leftrightarrow y)+len(x\leftrightarrow z)\ge k$，那么由于 $len(u\leftrightarrow prv(x))+len(x\leftrightarrow y)<k$（我们假设 $len(u\leftrightarrow prv(x))\le len(v\leftrightarrow nxt(x))$，其中 $prv(x)$ 和 $nxt(x)$ 分别表示 $x$ 在直径上前后的点），所以 $len(u\leftrightarrow prv(x))\le len(x\leftrightarrow y)$，则 $u\leftrightarrow v$ 不为直径，矛盾

按这种方式构造即可，复杂度 $O(n)$

3. CF1131G - Most Dangerous Shark [Euclid]

题面

给定一个长为 $m$ 的骨牌序列，第 $i$ 个骨牌高度为 $a_i$，代价为 $c_i$

第 $i$ 个骨牌向左倒会使 $[i-a_i+1,i-1]$ 内的骨牌均向左倒，向右倒同理

你手动推倒第 $i$ 个骨牌会花费 $c_i$ 的代价，问将所有骨牌推到最少需要多少代价

$1\le m\le10^7$

题解

考虑 $O(n^2)$ dp，设 $f_i$ 表示前 $i$ 个骨牌推倒的最小代价，$f_i=\min(f[l_i-1]+c_i,f[j-1]+c_j\{r_j\ge i\})$，其中 $l_i,r_i$ 分别表示将 $i$ 向左/向右推倒经过连锁反应能够推倒的最左边/最右边

考虑 $l_i,r_i$ 怎么求

不难发现 $l_i=\min(l_j)\{i-a_i+1\le j\le i-1\}$，那么我们可以用一个单调栈来维护，每次算出 $f_i$ 将 $f_{i-a_i+1}$ 至 $f_{i-1}$ 均弹出，加入 $f_i$，复杂度 $O(m)$

考虑 $[i,r_i]$ 之间要么是相离要么是包含，因此形成树状关系，我们模拟建这棵树的过程，每到一个 $i$ 删除所有 $r_j<i$ 的点，把 $[i,r_i]$ 入栈，然后取栈中最小值作为 $f_i$ 的值，复杂度 $O(m)$

总复杂度 $O(m)$

4. CF1028G - Guess the number [Euclid]

题面

有一个在 $[1,10004205361450474]$ 内的数 $x$，你有 $5$ 次询问。

每次询问你需要给出一个数 $k$ 和一个长为 $k$ 的整数序列 $a$，满足 $k\le10^4,a_1x$，那么你会当场死亡，如果存在一个 $a_i$ 等于 $x$，那么你胜利，否则，交互库会返回在这些数中有多少个数小于 $x$

题解

定义 $f(l,v)$ 表示最大的 $r-l+1$ 使得如果我们知道 $x\in[l,r]$，那么我们能在 $v$ 次操作内确定 $x$

不难发现当 $l\ge10000$ 且 $v$ 相同时 $f(l,v)$ 的值一定是不变

$f(l,v)$ 的值可以通过下面的代码求出：

long long cur=l,ans=0;
for(int i=1;i<=l;++i)
{
	ans+=f(cur,v-1)+1;
	cur+=f(cur,v-1)+1;
}
ans+=f(cur,v-1);

那么我们不难发现 $cur$ 一旦大于 $10^4$ 之后就可以快速计算，而同样不难发现 $f(l,v)$ 增长的很快，所以计算的复杂度是正确的

然后根据这个来进行询问即可

5. CF991F - Concise and clear

题面

给定一个整数 $n$，要求输出满足如下条件的最短算式：

只包含 0~9，+，*，^(乘方)
禁止连续使用乘方运算，如 2^3^4
算式的结果等于 $n$

$1\le n\le10^{10}$

题解

提前特判掉 $10^{10}$，那么如果答案不是直接将原数输出，其字符数一定 $\le9$

答案一定是如下形式之一：

a^b+c^d+x
a^b*c^d+x
k*a^b*c^d
a*b^c+d^e
a^b+c^d
a^b*c^d
a*b^c+x
b^c+x
a*b^c
b^c
x

前四种形式最少有 $9$ 个字符，因此涉及的操作数必须是一位数，$9^5$ 枚举即可

考虑 a^b 的形式只有 $O(\sqrt n)$ 种，可以预处理出来放到 map 里

对于 a^b+c^d 和 a^b*c^d 可以枚举 a^b 然后在 map 中查询 c^d

对于 a*b^c+x 不难发现 x 最多是三位数，因此可以枚举 x,b,c 然后计算 a

剩下的情况比较简单