2019, XII Samara Regional Intercollegiate Programming Contest(Gym 102215)

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

Records

Contest

Solutions

A(Solved by: lzy)

记录每个第二类道路右侧第一个能被这条路阻断的位置.

对于每个查询进行一次区间RMQ查询即可.

B(Solved by: lzy)

签到题, 对四种列的情况计数判断一下即可.

C(Solved by: sqc)

发现最多走$$p$$次之后就必定开始重复,暴力枚举前$$p$$次走到的点

D(Solved by: sqc)

考虑判断两个点集构成的连通块有没有交

我们将所有红点求出一个共同的$$LCA$$,那么从每个红点到$$LCA$$的链的并都在这个连通块中

然后我们就将每个红点$$u$$ 到 $$LCA$$ 的链加,然后查询蓝点到蓝点共同 $$LCA$$ 的链上是否有红点就行

树链剖分维护

E(Solved by: lzy)

离散化之后DP, 然后随便转移就行了.

F(Solved by: lzy)

考虑一个人被打死的情况,那就是维护攻击力前2的人.

再考虑两个人被打死的情况,对所有人按血量排序, 枚举血量多的人, 他能打死的人是血量序列的一个前缀, 看一下这个前缀里攻击最高的人能不能打死枚举者即可.

G(Upsolved by: lzy)

本质是一个二叉哈夫曼树, 但这里限制了高度.

注意到值越大在树里的高度越低, 我们排序之后进行区间DP即可.

利用四边形不等式优化到$$O(n^2k)$$.

H(Solved by: sqc)

先考虑$$[0,2^k)$$的做法

考虑询问某一位的所有数字,那么由于是连续的一段,所以询问后判断一下这位该是$$0$$或$$1$$的数量有没有满

然后这样问题规模就减半了

所以应该是$$2^{k-1}+2^{k-2}+\cdots+1$$次询问,也就是$$2*n$$级别的

这个随便一个枚举位的顺序都可以

然后考虑一般情况,从高位往低位做会被$$[0,2^k]$$的卡成$$4*n$$次

我们发现从低位往高位做就可以继续保证每次减半,就可以过了

I(Solved by: lzy & sqc)

考虑从左往右到头,然后向下移动$$b$$格,然后再从右往左

但是发现这样是不对的

因为我们最后几行可能是竖着走比较优

那我们枚举分界点,在这之前横着走,之后竖着走,然后推个公式计算一下就行

J(Solved by: sqc)

考虑当一个人的$$A+B+C$$超过另外一个人的$$min(A+B+2,B+C+2,A+C+2)$$时,这个人就能打败另一个人

然后排序+二分查找

K(Solved by: lzy)

显然字母数不到$$3$$以及一开始就合法, 都是合法情况.

观察样例$$1$$可以发现一个策略,就是把颜色$$x$$扔到一个栈里, 颜色$$z$$扔到另一个栈里, 颜色$$y$$尽量保证不分开$$x$$和$$z$$.

枚举$$6$$种排列都判断一下即可.

L(Solved by: sqc)

考虑将两个圆的圆心连起来,然后和两圆交点为$$A$$,$$B$$

新的圆的圆心就在 $$AB$$ 中点处,$$R = AB/2$$

(cf上用long double输出可能会出事,尽量转成double)

M(Solved by: lzy)

算好一开始的期望, 把候选游戏从大到小排序. 每次投给最大的, 直到当前游戏的价值不超过期望即可.