3
18
2015
0

Codeforces Round #296 (Div. 1)

昨天晚上cf开始前5分钟断网了打得话还可以涨rating

A.给出一个n*m的棋盘,切k次,每次横着或者竖着切一刀,每次切了之后分出的最大的块的大小是多少?n,m,k<=20W

题解:最大的块肯定是最大的宽*最大的长,所以我们可以用一个set来维护相邻元素差的最大值。什么?最大值递减怎么搞?倒过来就行了。

B.n个点的图,每个点有两个属性x[i],w[i]。当两个点满足|x[i]-x[j]|>=w[i]+w[j]时连双向边i到j。求这个图的最大团。

题解:其实看起来很麻烦,仔细推一下发现就变水题了。

            不妨认为x[i]>x[j],那么

             x[i]-x[j]>w[i]+w[j]推出x[i]-w[i]>=x[j]+w[j]

             so  x[i]-w[i]>=x[j]+w[j]>=x[j]-w[j]>=x[k]+w[k] 也就是说j连的边,i都能连!!!

             DP一下就好了f[i]表示选了i的最大团,然后用线段树求一下区间最大值即可。

D.给出串S和串T。求T在S中出现了多少次。注意:S[i]与T[j]匹配的充要条件是存在 l,满足S[p]=T[j],且 |p-i|<=k    S和T的长度以及K<=20W

题解:Orz 好题。

            我们首先可以预处理出S串的i位置附近(k以内)是否存在ATCG。然后我们不妨认为b[i]表示i位置能否作为匹配的初始位置。考虑暴力的去匹配每一位T。令a[j][i]表示i位置附近j字符是否存在。

           这样我们每次检验Tj的时候,我们需要让b[i]&=a[t[j]][i+j-1]  等等,这是什么?整体的与操作!!!

           bitset大法好。Orz!

官方题解:这么久还没出什么鬼

Category: codeforces | Tags: | Read Count: 434

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com