Codeforces Round #230 (Div. 1)

又到了开学的时候……
二月颓太久了,是时候挖坑(不填)了

upd

居然填好了,在嘴巴上都a掉了

A

……好像没啥可讲的……

int i,j;
j = N;
REP(i,N+1){
    while((ll)i * (ll)i + (ll)j * (ll)j > R) j--;
    a[i] = j;
}REP(i,N)ans+=max(a[i+1]-a[i],1);
cout<<ans*4<<endl;

没有了……

B

没有看错的话就是dp……
依旧是汉诺塔的经典套路……考虑最底下的那个盘子是怎么挪过去的
假设三个柱子分别为ABC,一开始都在A,然后要挪到C
最底下的盘子到C有两种可能
A->C或者是A->B->C
记忆化搜索一下就可以了

C

显然的可以乱搞构造矩阵……

二项式展开后就能用来表示了……
然后就得到了一个线性递推关系,感觉强构矩阵是不会tle的……
那么就这样了
以上三题都不想写也没有写,都是我瞎编的

D

其实是经典题?
……
我们把每个在A或B或C中出现的数,对其求出它第一次在A、第一次在B、第一次在C出现得位置(没有则记无限大
将其看成三维空间的点(x,y,z)
那么我们可以选择三个半空间……将x<=a的所有点删掉,将y<=b的所有点删掉,将在z<=c的所有点删掉
我们的目标是在删掉所有点的同时……求出a+b+c的最小值

如果你会做二维的情况的话三维应该就很好想了……

我们从大到小枚举a的大小,同时维护一个集合——所有x坐标大于a的点……
那么对于我们枚举的a,那些在集合里面的点是不能由a这个半空间覆盖的……只能由b和c两个垂直的半空间覆盖……
因为b,c垂直所以我们就忽略x这一维……把它们当成二维空间的问题就可以了……

现在的问题是:
维护一个平面上的点的集合,支持加入一个点的操作,以及回答一个询问:
询问为:
找一个集合内的满足横坐标x+纵坐标y最小的点(x,y),满足集合内所有横坐标大于它的点的纵坐标小于它
这个是经典题吧……容易发现任意一个时刻……集合内的可能成为答案的点的右上角都没有其它点……
那么加入一个新的点之后可能会破坏这个性质……我们将需要删除所有在它左下角的可能成为答案的点
因为可能成为答案的点一定满足一个单调性——随着横坐标的增加,纵坐标一定减小
所以加入一个点是lgn的回答也是lgn的……
(二维的没有弄懂的话可以做一下uva 11020)

那么到原题这里就是直接扫一下就可以了……
如果嫌我语文太差……可以看一下ACMonster或者rng58的代码……比较清晰

E

我坚信chinese round中的E没有可做题……
这题还是比较可做的……
一开始读错了题目……
好像删掉了一个区间的数之后……留出空的话,右边的数字会往左shift来填补,就像祖玛一样= =而不是删掉之后所有数字都停留在原位置……
然后观察一下删掉的数字串的特点……
说白了就是先递增然后再递减并且差分值为1
先递增再递减可以拆成两个单调的区间……
那么就可以考虑O(n^3)的dp了

以下dp思路全部都是看hza代码yy的……>_<……非原创

因为删除之后是会像祖玛一样shift的……所以我们可以倒着枚举决策……删除一个子序列,把序列分成若干段再进行独立dp
dp1(l,r)表示[l,r]区间的解,dp2(l,r)表示[l,r]区间中删掉一个从l开始到r结束的山峰的子序列之后,然后再随便删的最优值+删除得分,dp3(l,r)表示从[l,r]区间删掉一个从l到r的单调递增/递减的差分为1的山峰的子序列之后,剩下的元素的删除得分(如果没有包含l,r的单调递增/单调递减的差分为1的子序列那么dp3(l,r)=-INF……)

那么考虑怎么dp了……
(这dp套来套去还是有点麻烦的……)
首先看我们要求的东西……

正确性还是比较明显的……就不多说了……
然后再看dp2(l,r),(默认l<r)

然后dp3(l,r),为了简洁起见……下面的方程针对于a[l]<=a[r]的情况……a[l]>=a[r]这种情况是对称的

边界条件是……l==r的时候dp3(l,r)=0……

然后这样记忆化搜索就可以过了……正确性还是显然的

Comments

comments powered by Disqus