Noip 2014酱油记+简要题解

好吧,day2T1把d默认为1也是醉了,现在只能期待数据弱然后怒卡一等线吧QAQ

Day0 第一次下午出发啊真是不错,才2小时左右就到了233,在车上把sao和fate补掉就到了= = 然后到宾馆之后,没wifi的生活就是惨啊QAQ 把空境补完就睡了= =

Day1 时隔一年,终于又回到了六中,不过题目真是越来越简单了QAQ,day1 3道水题直接水过了,然后就开始对拍了,不过我对拍+出数据的正确方法还没掌握,必须给力一点啊QAQ 回到宾馆之后,去找偏远小渔村补番队的蹭了下wifi 下了魔法少女伊利亚 ,不得不说伊利亚真是太萌了,结果看到12点把第一季看完了,真是不好啊

Day2 题目还是依旧水,不过t1居然被样例误导了默认d为1了!!!!对拍时数据也都是d为1的特殊情况,结果就gg了QAQ,t2水过之后直接看T3,貌似想到了正解(不过和别人的不一样,但应该能过吧)就水了70分,结果就只能470分滚粗可能是我最后一届的noip了QAQ,现在只能期待奇迹了QAQ

这次暴露出了很多问题啊,尤其是day2,一开始轻视了,以为前两题是很容易的就有点轻视了,不能这样子啊QAQ

不过既然已经考完了,就不要理了,这100分放在省选也就5分的差距而已,加油!在省选上拿回这5分!!

我的oi之路永不停息!

附:noip简要题解:

day1 :

T1:直接暴力枚举就行了,主要表不要打错就行了

T2:树形DP,记点i的儿子之和以及最大,就能转移了,可能爆栈,建议用队列实现

T3:dp,很容易推出O(nm^2)的做法,然后就可以发现,对于向上飞的情况可以用一个桶来存,就把时间降到o(nm)了

day2:

T1:直接暴力枚举每个点然后计算就行了QAQ(别跟我再提这道题了QAQ)

T2:变成反向边两次bfs搞定

T3:首先如果直接暴力枚举+高精度乘法可以拿50分

用秦九韶算法就能将计算转成高精度除单精度+高精度减法就能70分了

观察70分算法,发现算法瓶颈在于需要对很多不可能的解进行试除

可以发现x必须是a0的约数,而a0的约数在1~m的范围内大概只有10000个左右,又转成70分算法了

线性筛出m范围内的素数,然后对a0进行m以内的分解质因数后枚举a0的约数后进行计算,复杂度o(n*位数*a0的位数)就能100分了

ps:以上的正解纯属瞎扯= =(自己打后还是不能过= =)

正解应该是:可以发现,如果在mod m条件下f(x)=0,那么x以及x的倍数就可能为f(x)=0 的一个解,那么先用一个小素数(10000左右)筛下,然后用一个大素数(2*10^9左右)来判断就可以啦~~~

原文地址:https://www.cnblogs.com/New-Godess/p/4348909.html