CF1146 Forethought Future Cup Elimination Round Tutorial

---

叮，守夜冠军卡

https://codeforces.com/blog/entry/66639

B

有一个串\(s\)，生成了一个新串\(t=s+s'\)，\(s'\)是\(s\)去掉所有'a'之后的串，给出\(t\)，求\(s\)

如果只看不是'a'的数量也只有最多一个位置满足条件，直接判一下这个位置即可。

https://codeforces.com/contest/1146/submission/53060920

C

有一棵n个点的树(\(n\leq 100\))，你可以进行不超过9次询问，每一次询问你给出两个非空且不交的集合\(x,y\)，返回\(\max_{a\in x,b\in y}dist(a,b)\)。求树的直径

考虑\(query(S)=\max_{a,b\in S}dist(a,b)\)，答案就是\(query(\{1,2,...,n\})\)。

\(query(S)\)可以先将\(S\)分成两个集合\(A,B\)，询问\(A,B\)，再分别处理\(query(A)\)和\(query(B)\)，\(query(S)\)就是这些的最大值。如果A,B尽量平均分配，那么只需要\(\log n\)
次就可以将\(S\)分的只剩一个点。但是这样好像还是\(O(n)\)的，然后又发现可以分别处理\(query(A)\)和\(query(B)\)的时候，将\(A\)分成\(A_1,A_2\)，\(B\)分成\(B_1,B_2\)，那么询问可以合在一起询问。每一层都合在一起询问就只需要\(\log n\)了（所以\(n\)还能出大一点？）

https://codeforces.com/contest/1146/submission/53065055

D

咕着

E

有一个数列，每次操作给定x和不等号，将\(>x\)或\(<x\)的所有数乘-1，求最后数列。所有数的绝对值\(\leq 100000\)

显然只要对每个数算最后情况就行了。好像不是很好算，发现对于每个数\(x>0\)，\(x\)与\(-x\)最后只会有4中情况：都不变，都变成相反数，都变成\(-x\)，都变成\(x\)。

只要用线段树维护这个东西，分类讨论一下就好了。

线段树维护两个标记：区间赋值（都变成\(-x\)，都变成\(x\)），区间取反（都不变，都变成相反数），计算答案时如果有区间赋值标记则优先，否则用区间取反标记。

https://codeforces.com/contest/1146/submission/53072116

F

咕着

G

竟然又是一道sb套路一眼秒的网络流，给出题人好评！

某沙雕要修\(n\)栋房子，每栋房子高度可以是\(0\)到\(h\)，如果高度是\(a\)获得\(a^2\)的收益。还有\(m\)个限制，如果\(l\)到\(r\)有任意一栋房子高度大于\(x\)则要付出\(c\)的代价。

所有数\(\in [0,50]\)

显然裸的最小割，会做切糕的都会这个题。还有一道差不多的：cf434d

https://codeforces.com/contest/1146/submission/53073780

H

这题应该不会改（鱼的恐惧）