昨天晚上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！
官方题解：这么久还没出什么鬼
评论 (0)
