记ACM生涯的第一个First Blood 【2011 Chengdu Site —— Online Contest 】

今天拿了A题的First Blood.

截止3个小时的时候，依然是1个AC，近300个提交

其实开搞这题的时候是很犹豫的。毕竟瞬间n个提交，0AC…于是果断觉得是坑爹题.

YY了一下，得到了个sqrt(n)*Q*t的算法.算了算复杂度非常有压力.

但是想想块状表的常数小到爆了…于是写了个对应复杂度的3重循环试试会不会TLE.结果返回了WA！！！

于是果断开敲，把程序搞了出来.sample调了下..没过= =

然后颓然发现我统计的是他防守住了多少波。点点点点啊.但是块状表本身不是很熟.不想去改动它

于是瞬间上了树状数组(反正就几行)统计每一位被攻击了几次,把那个减一下就是答案了…

接着感觉没啥好改的了，就交了…看着100+个提交…0AC.看着都胆寒啊- -….然后…就返回了AC

以上扯淡，下面说说我的解法。

【题目地址】http://acm.hdu.edu.cn/showproblem.php?pid=4031

【题解】

首先是对n个格子均匀分块。设每个块的大小为L。

那么对于攻击的操作，我们考虑对每个块设定标记使得整个块的操作能够不搞到底层就可以维护起来。需要的时候再把标记传下去。

可以围观到0<=t<=50。可以考虑在上面作文章。

我的标记是由以下几个东西组成的：

1、int l,r表示块的起始和终结位置

2、int Time 表示这个块内的元素最后一次被打到的时间是什么时候。

3、int F[55],pre[55] 我们可以将块内元素按照 (Time-最后一次被打的时间) 分成t+1([0,t])类。如果超过这个减出来的值超过t的，就可以变成t，因为超过t的无论接下来什么时间来了攻击，都可以抵挡，和等于t的其实是一样的…。分成这t+1类以后，F[i]表示第i类元素将会承受住多少次攻击(= =就是这地方我搞错了，就套了个树状数组，其实可以维护成第i类元素将会被打中多少次)。pre[i]表示第i类元素上一次被打的时候是什么时间。

 

这样，在攻击操作来临的时候，我们对于整块的，就去更新一下里面的F[55]和pre[55]，对于不是整块的，就直接暴力…

这一步的时间复杂度是O( (n/L)*t + 2*(L+t) )

、

然后对于询问操作，就简单地把标记推下去，然后统计就好了。

这一步时间复杂度O( L )

、

如果粗略地令L=sqrt(n)。那么复杂度就是O(Q*t*sqrt(n))。

现在我们尝试在其中寻找到平衡点。

令(n/L)*t = L得L=sqrt(n*t)

于是第一步时间复杂度(n*t/sqrt(n*t) + sqrt(n*t) ) 就是O(sqrt(n*t))

第二部同样是O(sqrt(n*t))

最终复杂度是O(Q*sqrt(n*t))

程序在218…写得也比较搓…就不发了。。。

By edward_mj@Evzones