【比赛】The 13th Northeast Collegiate Programming Contest

玩了一场，7个题放在当年是rk3，而且前两个队也是7个题
就是罚时太高了前2个小时3个人对着自己的题轮流WA，rk1的DDD队已经6个题了...

A

待填坑

B

签到题

C

签到题，但是是我WA的题，原本涉及计算几何都是队友写的，到我写就遇到各种问题
存储一个直线，防止爆精度可以存一个经过的点 (x, y) 和一个方向向量 (dx, dy)
这题的目的是区分不同斜率的线段，所以只要重载一个能给斜率按某种顺序排个序的就行了
重点是，应当令dx始终为正（dx=0时令dy始终为正），因为对于重载的小于号，符号一反，不等号方向就变了，可能导致斜率相同的两条线被第三条线划分到两侧的情况，排序就失败了
还好经常写计算几何的队友提出来了这个错误...不然签到题就WA到最后了...

struct Line {
    ll dx, dy, x, y;
    bool equalb(Line o) {
        ll vx1 = x+dx-o.x, vy1 = y+dy-o.y, vx2 = x-o.x, vy2 = y-o.y;
        return vx1*vy2-vx2*vy1==0;
    }
    bool equalk(Line o) {
        return dx*o.dy==o.dx*dy;
    }
    bool operator < (const Line &o) const {
        if (dx*o.dy!=o.dx*dy) return dx*o.dy< o.dx*dy;
        ll vx1 = x+dx-o.x, vy1 = y+dy-o.y, vx2 = x-o.x, vy2 = y-o.y;
        return vx1*vy2-vx2*vy1< 0;
    }
};

D

注意到m很小，想了个树链剖分+线段树+set维护的O(mlog^2n + m^2logn)做法
正解是注意到m很小，涉及的树的节点只有O(m)个，所以建一个O(m)的新树暴力操作O(n+m^2)就行了...
想简单了，学一下虚树

E

不知道，队友过的（

F

实际上比较板子的博弈论，就是第一次上手写结果真过了
模板问题：轮流操作挪动有向图上的一个棋子，不能移动者输，图可能有环
结论：每个节点存在3个状态：必胜、必败和平局

1. 无后继节点的节点必败
2. 后继结点存在必败节点的节点必胜
3. 后继结点全是必胜节点的节点必败
4. 其他情况都是平局

写法上考虑建个反图，用队列维护bfs一波，队列里的都是已经确定必胜/必败的节点，最后还没被确定的节点都当成平局
对于情况3的例子，需要记录每个节点后继结点中未确定的节点个数hope[]，hope=0就必败了
代码

G

不知道，队友过的（

H

不知道，队友过的（

I

不会

J

签到题