Codeforces#250(题解待补完)

我:杜教我既不会计算几何也不会dp,怎么过C啊!
杜教:和我一样,(扔上来聊天记录):“点开vfk的题发现既不会计算几何也不会dp。。。就弃疗了”
我:……

situation

我开题的顺序是BACD。。。
ydc的开题顺序是ABCD。。。
然后因为我先开B,所以罚时比ydc好一点,就踩了他两名。
总之开场发现B是一道裸的排序+并查集。。。
纠结了一会怎么写之后,过了pretest。。
然后看A发现一眼不会做,ydc告诉我直接从大往小删就行。。
写的时候yy了一下正确性。。感觉显然是对的。
A题我写的时间炒鸡长。。。真是不能多说。。。
然后看C,要求三角剖分数?
这tm不是经典题么?
出这题有意思?
这时候看榜已经有3人过C,1人过D了。。
我就去开D,发现是数据结构题。。。
然后发现了暴力出奇迹。。。
就写了个线段树,过了pretest。。。
接下来一个多小时都在搞C题。。。

还有10分钟结束的时候终于发现C题错在哪了。。。
但是最后还是没改成功。。。
浅谈我C题是怎么挂的。。。

我C题是定义f[l][r]为第l到第r个点顺次连接,再连接rl这条边得到得到多边形的三角剖分数。
valid[i][j][k]表示第i,j,k三个点组成的三角形是否合法(例如没有退化之类的)
然后递推方程很显然。。

边界条件yy一下就行了。。。
事实上这个也挺对的。
关键是我当时搞valid[i][j][k]的时候。。。
只考虑它面积不能退化。。也就是i,j,k不能共线。。。
结果就跪了。。。
因为多边形可能不是凸多边形。。。
那么ijk三个点组成的三角形的边可能和某条多边形的边规范相交。。。
这时候三角形也是不合法的。。。
我漏判了这一点就跪了。。。

结果最后十分钟因为忘记怎么判规范相交了而滚粗。。。
简直了。。。

Comments

comments powered by Disqus