APIO2017滚粗记

Day 1

先是坐火车到了dulwich hill,然后转轻轨到了比赛地点,robert的办公室果然就是不一样2333

然后发现我似乎早到了?对面站了一个小哥我以为是组织人员(然而确实是的)OVO

于是我去买了一瓶可乐,发现要3.5刀结果我只有3.4刀囧,被迫买了罐装。

然后还有一小时的样子,我想想农药似乎要铂金四了,诸葛亮也要紫色熟练度了,来赢一把爽一爽吧,输了就证明我APIO会滚粗

然后就输了,被血虐。。(好一个flag)

继续阅读

[ioi2012] ideal city

考虑把网格的四条边看成图意义上的四条边,那么问题就相当于一张有环图中的两点之间距离之和

同列/行的格子可以缩在一起,那么就变成了一棵树,树上求距离之和非常简单,点分治+FFT就行了考虑记s[i]表示第i个点为根的子树的权值和,那么这条通往父亲的树边的贡献就是s[i]\times(n-s[i]),时间复杂度O(N)

难点在于转化为树,然后缩环这种思想。

 

[bzoj1597][Usaco2008 Mar]土地购买

简单题,为了练习CHT所以来写一下。。结果发现写错了一个地方导致没1AQQ图片20160623113044

这种题N辣么小,肯定是想dp的对吧,但是我们发现并不能连续的做,那么怎么办呢?

我们发现,对于两个土地i,j,如果满足a[i]\geq a[j],b[i]\geq b[j],那么在买i的时候永远可以带上j

继续阅读

[BZOJ3482][COCI2013]hiperprostor

Orz Claris菊苣

对于这道题我们发现q很小,那么大概率是让你在线去做

然后我们知道n,m也很小,大概率是用n,m做一个dp

所以设f[i][j]表示从s出发,到达i,恰好经过jx边的最短路,利用spfa求出。

如果对于任意的i都有f[t][i]=\infty,则答案为无解。

继续阅读

[BOI2012] balls

题目大意

给你n个球和n个洞,第i个球对应第i个洞,洞i里如果获得一个球则加c_i分,你现在有一个挡板,可以向左也可以向右,可以任意长度。该挡板能将一段区间内的球下落在挡板左侧/右侧的洞里,问分数最大是多少(对于向左向右两种情况分别输出)。

继续阅读

[bzoj 1503][NOI2004]郁闷的出纳员

Description

OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难吧?

继续阅读