2014 Multi-University Training Contest - jcvb

2014 Multi-University Training Contest

jcvb posted @ 2014年7月23日 21:40 in 未分类 , 1072 阅读

(除草)

昨天和xyz、fancy组团打了第一场,只搞到rank3=-=sad...(最后在1008挣扎,写到一半发现自己题意还没懂。。只能弃疗

1001:果断打表找规律,发现被p-1整除的值是p-1,否则是0。然后判奇偶输出就行了。(证明只要取原根化成等比数列即可)

1002:求一个不超过k条的路径覆盖,使边权和尽量大。费用流,流量>=n-k时更新答案。

(一开始莫名其妙wa了。。。查了一会儿发现输出case编号有问题。。贡献了一个-1、、)

过了这两题后就开始颓了。。开出来的题都不会,直到开到1006时发现是个SB题,建可持久化线段树就行了。

这时我们队迟迟没过1004。XYZ说他只会做第一问的贪心。提醒以后发现贪心对第二问也成立。。然后就水过了(好像因为I64d蛙过一次。。。TUT

剩下几题(我都不会捉)被xyz和fancy瓜分了,最后一个多小时留了道阅读理解+码农题给我。hhhhhhhhhhhh这种题我看都看不懂怎么可能写的粗来呢于是我们队被巨大的罚时卡成rank3了hhhh。

比完发现也不全是不可做题,于是把剩下几道也填上(我是嘴巴选手):

1003:找重心为根树形DP,每个结点的孩子放在一起做背包。。。。复杂度好像能证明是O(n^3)的。

1004:按x降序枚举任务,同时维护所有x不小于它的机器,每次从中取一个y尽可能小的进行匹配。因为2*100<500所以这样的策略能在个数最大的同时保证权最大。

1009:只要考虑01的个数,计数时再乘上组合数就行。要考虑可行的01个数,只要每次转移后记个min和max,再判下奇偶性,中间这段的奇/偶数都是可行的。

1010:状态数大概是(1000/50)^2=400,高斯消元解方程就好了吧。

1011:建树然后点分治。

还有几道慢慢来。。。(坑)


upd:

上次在blog里立了奇怪的flag,结果真应验了,以奇怪的方式挂掉了奇怪的省选。

听从xllend3大爷的教诲,这次不敢再乱来了。求不遇到奇怪的题目,求不要犯逗,求不要被线卡。

Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee