Bakser's Blog

我是逗比。

搬家了~

| Comments

新blog
搬到163去了。
logdown是个好blog,但实在太卡了~
今后还会有一些需要公式编辑器和一些哲学内容会在这里发吧~
say goodbye QAQ

bzoj3680 吊打GTY

| Comments

这题其实是经典问题了,我从奇怪的地方找到了几组数据,又自己加强了一坨数据就出上去了。
bzoj还把题目名给和谐了。。。。。原名是吊打GTY来着。

Usaco2013 Jan Gold 题解

| Comments

即bzoj3048-3050
老师给我们出成了模拟题。
当时考场上一看,T1太神不会,T2弃疗暴搜,T3一开始写的链表。
后来发现T3数据范围似乎更适合线段树,就30min写了个线段树+拍完,然后心满意足的把链表交上去了。。。(论手残)链表还写挫了个地方只有80.
最后还骗到了120+真是幸运。

T1:

枚举左端点,在满足不同颜色数不超过k+1时尽量向右扩展。
然后发现右端点是单调右移的,用离散+数组(O(n))或map(O(nlogn))就可以统计颜色数和答案了。

T2:

其实看到15就应该有一种状压dp的赶脚是吧。
当时我以为是noip摸你题233,就暴搜交上去了。
flood-fill求出每个island,然后bfs计算任两个island的距离然后状压dp
f[i][s]表示现在在i点,经过了s中的岛屿的最短距离,转移显然。

T3:

线段树就是裸题吧,每个节点维护左端点开始的最长空闲,整段区间的最长空闲和右端点的。
链表做法就是每个元素代表一段极大的空闲,记录左右端点,然后分裂合并都暴力就好了。
本来以为链表会虚,然后bzojrank2。。。不过不知道为什么同写链表的小伙伴不开O2会T。

bzoj3329 xorequ

| Comments

这题搞了好久。。。。
第二问还比较快看出来了,然后第一问蛋疼了许久。
去问faebdc神犇,然后faebdc神犇秒了。。。。

NOI2014题解(待补)

| Comments

同步赛打的跟翔一样。。。。暴力写错不能多说
Day1:
T1:按位贪心,看一看这一位取1或0会有什么后果,在限制内从高位到低位贪心。
T2:按a排序然后按a从小到大加边,发现对b来说就是求MST,LCT维护动态MST即可。
T3:提答不多说。
Day2:
T1:next指针反向会构成一颗树,在这颗树上向上跳一步就是最长的公共前后缀的长度,两步就是次长的...所以问题就是询问从这个点到根有多少个比它的二分之一小的。我写的是vfk(Orz)教的做法,就是倒着枚举每个点,并查集维护以每个点做答案的点集,然后当这个点不能做答案时就将它与它父亲点集合并,以它父亲做答案。
PS:搞了半天发现递归的并查集带路径压缩也会爆栈,感觉整个人都萌萌哒了~~~~
T2:从小到大枚举1~n*m,如果在能选的范围内就选,否则跳过。所以怎么判可行成为了亮点。事实告诉我们,暴力维护每一行能取的左右边界就可以。。。。
T3:就是这道题待补啦0w0,真相是那一坨技能都遗忘了。。。。