博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Noip 2014酱油记+简要题解
阅读量:5126 次
发布时间:2019-06-13

本文共 1149 字,大约阅读时间需要 3 分钟。

好吧,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

你可能感兴趣的文章
aboutMe
查看>>
【Debug】IAR在线调试时报错,Warning: Stack pointer is setup to incorrect alignmentStack,芯片使用STM32F103ZET6...
查看>>
一句话说清分布式锁,进程锁,线程锁
查看>>
FastDFS使用
查看>>
服务器解析请求的基本原理
查看>>
[HDU3683 Gomoku]
查看>>
下一代操作系统与软件
查看>>
【iOS越狱开发】如何将应用打包成.ipa文件
查看>>
[NOIP2013提高组] CODEVS 3287 火车运输(MST+LCA)
查看>>
Python IO模型
查看>>
DataGridView的行的字体颜色变化
查看>>
局域网内手机访问电脑网站注意几点
查看>>
[Serializable]的应用--注册码的生成,加密和验证
查看>>
Linux操作系统 和 Windows操作系统 的区别
查看>>
Android-多线程AsyncTask
查看>>
LeetCode【709. 转换成小写字母】
查看>>
如何在Access2007中使用日期类型查询数据
查看>>
CF992E Nastya and King-Shamans(线段树二分+思维)
查看>>
如果没有按照正常的先装iis后装.net的顺序,可以使用此命令重新注册一下:
查看>>
linux install ftp server
查看>>