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
ret+=tmp*Size[Q[i]];
}
ret初始为从当前结点直接跑各个子树时的时间和…
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
update@8.7
E就是暴力啊……
回复中国脑筋:ym- -…不会记录方案….
E的题解是russian啊!