【AC_LCC_CWJ 第四场】Algorithmic Engagements 2009 & 【第一把SRM】

【AC_LCC_CWJ】

 本场纯打酱油……

就切了J题这个线段树。

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22200

【题目大意】

给一个A[1..n],问是否存在1~n的一个排列,满足所有p[i]<=A[i]。然后后面还有m次修改,每次修改某个位置的A[i]的值。

n,m<=200000     1<=A[i]<=n

【算法分析】

……令Sum[k]表示数组A[i]里包含多少个<=k的数字。然后这个判定性问题转化为是否所有Sum[k]<=k。

然后就用线段树维护所有Sum[k]里,Max(Sum[k]-k)是不是小于等于0,如果是就满足,否则不满足。

【其它】

还想了好一会儿,真是太弱了。

【CODE】

http://xiudaima.appspot.com/code/detail/4489019

哎,弱得一塌糊涂……神马都弱

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

然后是昨天晚上的第一把SRM。

Orz,一进去就见到WJMZBMR和zbwmqlw!!!

WJMZBMR还被人用中文膜拜……

然后看到很多熟悉的ID,像swgr,RoBa之类的…

膜拜完以后开始比赛,显然第一把必须DIV2。

250神马二叉算法都能秒,直接暴力枚举。然后编译了半天不成功,都不知道干神马……

弄了好久,发现语言选了JAVA

接着打开500,据说就是DIV1的275。

觉得就是左边扫一遍右边扫一遍,得到每个位置的上限和下限,于是直接枚举。复杂度就是O(N√N + M)。

Orz表示1000^2 * 50毫无压力的神犇们!!!原来TC的精髓就是暴力……

搞完以后看到最后一题瞬间被秒。。。最后没有交1000。

其实当时的想法很接近正解,也是求连通块,就是没想出每个连通块有n!/2种方案。

好像DIV2里面也没有多少个交1000的……居然搞了DIV2里面第6,Rating一下变到1700+,然后名字就变成黄色了。。。

今天听说别人TC都用插件,下了个KawigiEdit,导入了以后再里面点Run Test Case显示神马g++不行之类的,鸭梨山大。改天再搞一搞。

刚在调这个KawigiEdit的时候被zbwmqlw神牛喊了一声没有听到Orz~罪过罪过

加入对话

8条评论

留下评论

回复 WJBZBMR 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注