BZOJ乱炖
UOJ#132 小园丁与老司机

POI19填坑计划

HJWJBSR posted @ 2015年11月30日 08:59 in 题解 , 502 阅读

等了好久终于可以开始填POI这种神坑了。。感觉如果能静下心来想的话其实有些题推起来也不算太过艰难。但我的智商是个大玄学。。打到一半才上线。。

[UPD 11.30] 因为感冒还有一些奇怪的事情再次推迟2天= =

 

现在完成了:

16

[Letters]:NOIP某题即视感。就是求个逆序对数。

[Distance]:大暴力?对于每个数处理出它所有因数打上标记,然后再每个数枚举因数求答案就好了

[Rendezvous]:一个环套树森林,随便乱搞搞就好了

[Well]:想了很久不会。。后来发现是有个玄学姿势没有get:二分答案的时候要从左往右扫一遍然后从右往左扫一遍使相邻的两个不超过x。其余部分就是比较愉快了,很容易发现以每个点为0点左右边界一定是单调的。所以是O(n log n)

[Vouchers]:n log n大暴力

[Tour de Byteotia]:把所有大于k的点的连通分量缩掉然后用剩下的总边数减去生成森林的边数就是答案。

[A Horrible Poem]:直接哈希就好了= =,一直在想些奇怪的东西= =,真是naive。我数了下因数个数naive地以为是n log n级别的。。然后T了。据说有两种特技可以加,一个是所有字母出现次数gcd一下,一个是这里。感觉第二种比较优美。改完之后果然跑的飞起。

[Fibonacci Representation]:首先很明显一个数只会出现一次。因为两个相同的这个数是可以分解成另外两个不同的Fibonacci数的。然后还有个性质就是肯定会包含值跟它相邻的两个数之一。所以直接上爆搜大力出奇迹?还有那个输入小于1e17是个坑= =应该是小于1e18

[Warehouse Store]:很明显是贪心从小到大取,每次取一个非0量。随便找个什么东西维护一下就是n log n的了。还要注意后面取的点对前面答案的影响。

[Squarks]:构造题。。TAT脑抽不会。。直接枚举第二个和第三个是哪个数就好了的。。n^3 log n真是厉害,事实是可以加很多剪枝所以根本就不会摸到上界。

[Salaries]:只会乱搞= =后来wa了以为不是正解= =别人做法都死麻烦= =后来才发现是正解,但是被我写的奇丑无比= =调好久发现处理上界的时候不能直接是父亲上界减一= =真是日

[Festival]:YY很久。首先差分约束系统显然,建出图来之后强连通分量之间答案独立显然。然后剩下的里面都是没有负环的强连通分量,我猜是里面的Max最短路的长度+1?感觉复杂度是个大玄学。还有判负环应该就是看a[i][i]是不是负数吧。wa了几个点调了好久最后发现我用了一年的我自己YY的Tarjan是错的TAT,不知道为什么一直都没错过。

[Cloakroom]:有人说n^2*k/32能过?真是厉害。。貌似只要改变设的状态就可以nk了?改为设b的最大值就好了。

[Bidding]:hehe,x可能的值只有不到100个。貌似BZOJ上面交这个有bug?

[Prefixuffix]:记得这题被数国队出到过NOIP模拟题里面。真是sxbk。。从中间往两边扫,左起点往左移一位答案的范围是原来答案范围+2以内。

[Minimalist Security]:这题放到后面才动。。主要是一开始被吓到了,看顶标什么的以为是权匹配相关。。于是感觉比较报警。。结果现在看是个SB题。。直接每个连通块设个x代表其中一个点应该减去多少,然后就可以得出整张图的量了,然后就是m个不等式求个交。如果图不可以黑白染色肯定就是解唯一。反正随便搞。。BZOJ上面的题面把背景省了我还以为z可以带小数TAT。

[Leveling Ground]:好神啊不会啊弃疗了留坑吧下次填好了。

所以就算完结了?

接下来一段时间准备把高一naive的时候参加过的培训资料过一遍好了,所以暂时不会开新坑。


登录 *


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