2014 Multi-University Training Contest 1 滚粗总结&部分题解

too young,too simple.
sometimes naive.

本场多校由我、gwj、csy组队来打。。
感觉各种发挥不正常。。
参加人员还有主席。。。(虽然不参加写代码)。。就当编外人员好了。。

situation

开场:
我看01..csy看02..gwj看03...
和主席扯了很多结论。。结果一点用都没有。。
开场半小时的时候用错误的结论写了01。。而且还没意识到结论的问题而wa了两次。。
后来走到正道上了。。搞了半天。。
推出结论的时候有种卧槽的感觉。。
1点才过01真是不能多说。。

csy一开场就交了05。。。挂掉了。。原因是题意没读懂。。
而且这题坑爹之处就是不管怎么错。。你总是能过样例。。

接下来我就去看T10了。。这时候主席跟我说T4可以线段树加速匹配来水过。。
T10是一道裸高斯消元。。我用double精度挂了wa*1。。我不会说我一开始连方程都不会建了还是问gwj才弄出来的。。(主要是昨天熬夜。。上午起床起得早。。下午像梦游)

换long double之后a掉了。。
这时候终于过了2题了。。
感觉非常卧槽。。真的高中生垫底了。

我做10的时候。。csy发现06是道裸数据结构。。他打算写树套树(我们在集体梦游的证据之二)。。结果mle(re)*2了。
而gwj则想了个09的结论。。wa*3。。

比赛过了两个小时我们却只有2题。。

感觉真是非常炫酷。。

然后gwj告诉了我她09想的结论。。我觉得可以cha掉。。但是当时一时半会没想出数据。。她也放弃去做04了。。

然后gwj说04可以裸贪心。。我还在想线段树。。然后我就放弃去看T3了。。
这时候csy发现自己在梦游。。用主席树碾压了06。。、

gwj一会之后也过掉了04。。

然后我写03的dp。。
发现预处理n^3..
然后最后算答案的时候怎么都搞不到n^3..
(最后发现是自己蠢)

然后我就帮忙想09。。感觉最终长度可以是一个连续区间。。
结果样例把我cha掉了。。我就没继续想了。。

然后csy过掉了02和05。。

比赛最后就在我不停的tle中结束了。。

赛后发现09区间的确可以秒。。分情况讨论递推就可以。。
然后gtk喷我们居然没过11。
我看了一下11。。裸点分治卧槽。。

总体感想就是因为我没有过掉03、09、11而拖了全队后腿。。

solution

01

以下是扯淡的推导。。(我猜不用这么复杂)。。

其中g是p的原根。。
这点很显然。
然后

由费马小可知

注意到如果k满足的话。。求和式模p显然是0,就没啥意义了。。

然后注意到在k=1,2,.的时候。。构成了一个长度为p-1的循环。。循环内任意两数不同(废话)

如果输入的是K,p的话。。
那么K/(p-1)是奇数的时候。。先手必胜。。否则只能平手。。

回头看推导感觉我和主席就是在梦游。。

02

上下界费用流

03

背包dp。。
待补充

04

看起来是匹配模型。。
但是排序贪心就可以了

05

递推。。
注意一下题意

06

主席树

07

待补充

08

放弃。

09

注意到n次操作后。。

如果存在一个局面,有k个数为1.。
那么很显然所有种k个数为1的方案都是可以达到的。。

我们可以通过递推之类的方法算出来最后最多有多少个数为1.最少多少个数为1.

然后假设这个最小值是l,最大值是r。。

很显然如果x是[l,r)里面的一个合法的1的个数的话。。

x+2也是合法的。。
(调整一下就能调整出x+2了)。。

x+1一定是不合法的。。
因为很显然。。最后局面的1的个数的奇偶性一定和所有x的和的奇偶性相同。

我当时就是因为too naive发现搞不出x+1就滚粗了。。

知道这一点之后。。就发现能拼出来的长度一定是一个{x,x+2,x+4,..,y}的集合

我们记录左右端点。。从1到n扫描维护它就可以了。。

10

裸高斯消元。
因为+-rating都是50的倍数。。所以实际状态量是(1000/50)^2的。。所以可以高斯消元。。
别像我这样在考场上突然不会列方程就行了。

11

随便用种方法搞出最短路树。。再用你喜欢的分治方法(点分治、边分治之类的)求出答案就可以了。
考场上没看这题真是too young。。

最后总结:

高中生垫底很不甘心。

Comments

comments powered by Disqus