Codeforces Beta Round #79 (finished)

A

Cnt[26]表示每个字母出现次数,然后sort一下,贪心地从个数少的开始删,删剩下的就是必须有的。

B

离散化以后就各种好搞- -。写圡了,按ti排序以后发现ti相同的那些转移有点问题。于是直接开个

map

CF上第一个hack…成功了叉了一个n^2都敢交的…

C

=_=经lcc指点后顿时泪流满面。

旋转原来那个东东,就相当于把一路上加的C向量和原来的向量都跟着一起旋转再叠加。

于是乎把目标的B向量旋转到4个方向,分别看看能不能用C旋转4个方向的向量拼出B-A.

然后C旋转4个方向的向量由于是90 180 270度的,所以可以只取其中两个垂直的。然后就是看是否存在整数(x,y)满足

x*C + Rotate90(C)*y = B-A

这个化出来以后就和两直线求交一个样- -,套个模板或者推一推就好了。

D

这个题要是当时看了就好了…卡了C以后没去搞这个…好经典的0_0

dfs的时候,按照这个函数对当前结点的儿子排下序

bool cmp(int x,int y){
     return Size[y]*Sum[x]}

其中Size表示子树下结点的数目,Sum[x]表示子树以及x与父亲相连的所有边的权和*2的值。

然后这样模拟算一算延迟的值就好了.

          sort(Q.begin(),Q.end(),cmp);
          long long tmp=0;
          for(int i=1;i              tmp+=Sum[Q[i-1]];
              ret+=tmp*Size[Q[i]];
          }

ret初始为从当前结点直接跑各个子树时的时间和…

代码:http://ideone.com/UsOfC

E

还不会捉。

题意就是

F[0,0]=(a[0]+b[0])%p

F[i,j]=max(F[i-1,j],F[i,j-1])+(a[i]+b[j])%p

输出F[n-1,m-1]以及取的方案

n,m<=20000.

时限15S

空间限制 45MB

 

=_=rating涨了一点点…

 

—————————————————————————————————————

E

看了官方题解。问题相当于找一个从(0,0)走到(n-1,m-1)的路线。pick完路上的权,最后权最大。只能向上或右走。

路径长度必然是(n-1 – 0)+(m-1 – 0)。然后把路径分为均匀的前后两半,于是可以确定一个最优解的中介点。递归下去。就得到了答案。

令r=n+m-2,那么复杂度这么算:r*r + 2*(r*r)/4 + 4*(r*r)/16 ….  k*(r*r)/(k*k)  … <= r*r + r*r

代码:http://ideone.com/XgoR1

 

[email protected]

加入对话

3条评论

留下评论

您的电子邮箱地址不会被公开。