摘要: 两个凸多边形的交

  阅读全文      摘要: 我的做法是，对于每条新边，记录树中与之对应的路径。然后对于每条树边，统计被对应的次数。最后记录每个点到树根的路径上，有多少个1（设为q[i]）。对于新边(x,y)，它对答案的贡献就是q[x] + q[y] - 2q[lca(x,y)]。除了这些，答案还应加上树中0边的数量 * m。

  阅读全文      摘要: 经典的DP，把环断开，f[i][j][0]记录i到j的最小值，f[i][j][1]记录最大值，然后递推计算。记录最小值是因为两个负数乘起来可能得到一个大的正数。

  阅读全文      摘要: 概率+DP，比较经典的题。按照递推的方式计算概率。

  阅读全文      摘要: 详情见内

  阅读全文      摘要: 简单的几何题，先把经纬度换算成球面坐标，再把球面坐标换算成直角坐标，然后求夹角，乘半径得到球面距离

  阅读全文      摘要: 我的做法是，枚举第一个多边形的第i条边和第二个多边形的第j条边重合，然后从这条重合的边开始，尽可能的向后扩展重合边，然后判断剩下的多边形是否是凸多边形。
比赛的时候，我在某个地方忘记对多边形点数求模，导致wa了很久，一直到比赛结束后才AC。以此为鉴！

  阅读全文      摘要: 听着很有感觉：）于是找了歌词翻译

  阅读全文      摘要: 经典的状态压缩DP，状态是f[i][j]，表示第i行，以3进制j为状态。j的位代表一个格子，只能是：0表示第i行和第i - 1行都没有炮兵，1表示第i行没有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS进行状态转移。一开始我做了超时，后来预处理了一下合法状态，快了不少，才AC。

  阅读全文      摘要: 今天郁闷了，贴个小代码

  阅读全文