J

题意：给定8000个点的完全图(邻接表)，边为黑色或白色。问能形成多少个边同色的三角形。（三角形为三个点和三条他们之间的边组成的子图

LYF解：

发现统计同色的不容易做。正难则反，考虑容斥：三角形总数为C(8000,3)，减去边不同色的三角形即为答案。容易发现，对于每个黑边-点-白边这样的东西，必然会出现在不同色三角形中，且数量为不同色三角形的两倍。做完了。

E

WD&ZRC 打表

推导可以利用数学竞赛中的韦达定理

不然就打表找规律吧

ZRC 模拟 24点没啥好说的只是要感叹一句开O2对stl的加速效果真的强

题意：

有一个n100000行m列的白色棋盘，将其中的格子染黑有两种方法。第一种方法是用给你的代价来染；第二种方法是，如果某一个矩形的三个角都黑了，那剩下的一个角就可以不用任何代价染黑。问最小代价

解：

非常巧妙。考虑将每行每列都看成点，原图中的黑点看成行点与列点之间的一条边，这样显然就形成了一张二分图。每次方法一的染色都会改变图的连通性，将对应的行点和对应的列点连边，而方法二染色则不会改变。由此，考虑在二分图上跑最小生成树。它就是正确的。