比赛
难度系数绿紫蓝黑,考的方向有点偏。
一个弹的投
感觉是比较麻烦的模拟题,重点是瓶颈的处理,
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(d[i].yi!=d[j].yi) break; // 判定
if((d[i].v<=0&&d[j].v>=0)||d[i].v<d[j].v) continue; // 判定
if(dis(d[i].yi,d[i].v,d[j].v)>=abs(d[i].xi-d[j].xi)) d[i].p++,d[j].p++;
}
}
注意只有 $y$ 相同的时候才可能有交点。
下面是一个树状数组求逆序对类型的转移,贪心即可。
一个仇的复
多米诺骨牌加强版,一眼发现最多只能使用 $1\times2$ 的竖着的长方形以及一些横着的长方形来摆放。
先考虑放横着的长方形的情况,
抱着计数问题有一个基准点的想法,我们先假设给上面分 $i$ 块横着的长方形,由于长方形长度不确定,不妨假设有 $b$ 个容纳位,由于下面是容斥的缘故,用卷积优化为 $O(1)$。
大体上,我们假设采用 $j$ 个竖着的 $1\times2$ 长方形,并把原来一整段的 $2\times n$ 大小的长方形分成了 $i$ 个独立的小段长方形的情况的方案数,
如何填数?其实是一个插板问题,可以写个暴力$DP$来对拍和特判。
总体而言难度不大,但数学性过强了点。
一个网的路
比较明显的树形$DP$,有两种操作,可以分类讨论,
如果炸网。最后需要再连一些边,具体的操作次数就是 $u$ 的儿子个数。
如果不动,考虑要困难一些,但是不难发现,我们只有保留$0/1/2(此时为中间点$个儿子的情况,由于$DP$的重叠性,我们不能断掉就不管了,但是具体操作也很好算。
仔细思考发现我们要设置四个状态机。
最后需要将所有树连接起来的方案算上。
本算法瓶颈在于枚举两个儿子,可以用数据结构优化至 $O(nlogn)$,不嫌麻烦也可以讨论至 $O(n)$。
一个截的拦
用了去年$T4$的$trick$,平面图转对偶图求最小割,太麻烦了不想写。
实话说T1评个蓝/紫都不过分