absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] JSOI Round 3 碎碎念
[破碎的状态] [-48] 北大夏令营 Day 1

[破碎的状态] JSOI Round 3 Day 2 碎碎念

absi2011 posted @ May 18, 2016 05:34:27 PM in OI系列 with tags DP NOI 计算几何 小高考 碎碎念 搜索 DFS JSOI NOIP 杂文 瞎搞 , 852 阅读

终于,进省队了

翻盘了

这一次考完,也算是最后一次省选了

昨天立下的flag,再重复一遍,我,说到做到:

如果这次进省队,我在这次省选到NOI期间除非在比赛期间,否则保持不打game的状态

感觉自己这一次还是完成了一次翻盘

所以,我会坚守承诺,希望NOI再考好一点

嗯..分组赛希望别滚粗太惨,大概意思就是别倒数第一....

希望今年能创造一次奇迹,我真的不想学数学..

太累..

谈谈今天考试吧

t1:

有n个村庄感染了瘟疫,每天第i个村庄会死ai个人

你一开始在1号村庄,每天你可以:

1,治疗当前村庄的所有人,若此样做,这个村庄从此以后不会有人死掉,即将ai变为0

2,从i号村庄走到i-1号或者i+1号村庄(不可越界)

PS:如果你走过某个村庄x而没有救该村庄的话,等你下一次调头的时候,你必须一直走到该村庄并治愈该村庄(允许中途治愈别的村庄但不允许再次调头)

也就是说,你可以1-->2(救)-->3-->4(救)-->3(救)-->2-->1(救)-->2-->3-->4-->5-->6(救)-->5(救)-->6-->7(救)这样走

求最少死亡人数

其他数据范围记不得了

100%数据范围保证 n<=3000 ai<=109

t2:

给你n个数,你要找出最多的数,满足两两之和不为质数

10%的数据 n<=10

40%的数据 n<=150

80%的数据 n<=1000

100%的数据 n<=3000,Ai<=100000

t3:

你有t个能量源,s个防御塔,现在有d个敌人

求每个防御塔攻击某个敌人时,穿过的能量屏障之和

保证所有敌人在x轴及上方,所有防御塔和能量源在x轴及下方

PS:俩能量源的连线即为一个能量屏障

20%的数据 t,s,d<=30

50%的数据 t,s,d<=150

100%的数据 t,s,d<=800,坐标<=109,保证不会三点共线,所有坐标是整数

==============================

 

t1是个简单dp,很快我就发现了,但不太敢写

t2感觉不会做,把题目转化成了n个点求最大的团(似乎很作死),想到了BZOJ 1006然而发现忘记怎么求了(实际上和那题并不一样)

t3感觉是个计算几何题,不敢碰它

然后我仔细思考了下t1,感觉很sb题就把它写过掉了,测了个大数据发现炸int了改了下过了

t2感觉还是不会做

t3仔细看了下

会做了,写了个20分n4,然后优化到50分n3log n,再优化到满分n2log n,20-50-100拍上了

好像满分的算法炸int了不然就AK了..

然后..看了下t2

暴力大法能过10分

然后剩下的实在不会,瞎写了个做法:每次随机一个点开始随机加点找最大的团,如果感觉TLE了就退出输出最大答案

================================

结局似乎有点出乎意料,t3炸了,t2过了

只看到结局的人,又怎么能理解过程的惊心动魄

100 + 100 + 40 = 240

第一天160,据说卡线进队了

真是仍然很害怕,万一t3没放我过40分岂不是gg

而且t3我过的是后4个点.....非常的神奇呢.....

分组赛祝waltz进A队,你们加油,我希望NOI能考的好一点吧


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter