OI已退 | codechef APRIL16 题解
如题
已决定
4月10日UR后就退OI，包括退cc
UR已炸，世界再见
cc已弃疗，世界再见
高数你好
今天居然14号了，还没有把题解放出了
说了做了一半弃疗了，所以只有7个傻逼题的题解
COLOR
傻逼题，颜色可以任意变换，求出哪个颜色出现最多就好。
CHBLLNS
$$\min(R,K-1)+\min(G,K-1)+\min(B,K-1)+1$$
CHEFPATH
边长都$>1$，且有一个偶数，就可以
$1\times 2$的也可以
其他都不行
BIPIN3
$$(K-1)^{N-1}\times K$$
FIBQ
$$F_n=\frac{\alpha^n-\beta^n}{\sqrt{5}}$$
其中$\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$，所有数在数域$a+b\sqrt{5}(a,b\in\mathbb{Q})$下进行。
问题就变成求$\sum_{S_0\subseteq S}\alpha^{sum(S_0)}$，推一下就会发现等于$\prod_{s\in S}(\alpha^s+1)$，单点修改区间求积搞一下就好。
FUNGRAPH
首先考虑只有一张图的情况，给每个点设一个点权，表示与它相邻的边的权值和的一半。那么考虑Mario(还是阿狸叫的带感)的分数减去Luigi的分数就是所有黑色点的点权减去所有白色点的点权。因为考虑一条边，如果它两边是相同颜色，那么这个边权会有贡献，否则这个边权的两个贡献会抵消。
写暴力的话。。每次把点权从大到小排序，求奇数项之和减去偶数项之和就好。
现在用BST维护这堆点，变成：维护奇数项之和，每次删除/加入一个数。
所以是傻逼题
DEVGOSTR
简单地吐槽一下
这题我想容斥想了很久
后来打了个表，发现字符集为$2$的时候长度为$9$的good字符串就不存在了
字符集为$3$的时候长度为$27$的good字符串就不存在了，而且good字符串数量少(长度为$19$的good串不超过$10^5$个，且是最多的)，搜索+剪枝可以搜出来。
tips:不要一组数据搜一次，应该预先把$A=3$的所有$<27$的长度都搜出来，一组数据的时候直接在里面找。
就这样咯
(坑：求最长的good字符串长度与字母表大小的关系 猜想是$3^A$，但是不会证
(upd 原来这玩意是有定理的，对于任意的$N$和$c$，最长的字符集为$c$的、不存在长度为$N$的同色等差序列的字符串的长度都是有限的($W(c,N)$)。
(upd 有一个$W$函数的表格。。原来不是$3^A$。。wyh2000如果要人类求出W(3,5)，人类就认真求；但是如果要人类求出W(6,6)，人类就和他干一架
AMAEXPER(因为没A掉所以不算
首先，每棵子树直径可以$O(n)$dp出。就是设$f_i$为子树$i$的直径长度，$g_i$为子树$i$中最深的点到$i$的距离，那么$g_i$很好推，$f_i$用$g_{\text{child of }i}$的前两大值和$f_{\text{child of }i}$的最大值更新。方案什么的随便记记就好。
然后，对于这个题，对每个子树我们需要记录直径，然后求出直径的中点。(就是直径中离最远点最近的点啦)。中点可以$O(\log n)$求，就是$O(n\log n)$的。不知道过得了不，看上去很卡常，也许树链剖分可以过吧。
评论 (0)