回转数 数学和计算几何 C. 回转数 题意:给定n个点，顺次连接这些点得到折线。m次询问，每次给出一个点，询问折线绕该点的回转数 如果暴力用atan2去算每个每个角度来计算，虽然每次询问的复杂度是O(n)，但atan2的计算很耗时间，会TLE。本题需要用光线投影法来做。 首先需要特判该点是否在折线的边/顶点上，如果不在，做一条过该点的直线L（射线也行），遍历折线上的每条边，...

图论 A. 蜘蛛的网 题意：给定一个无向连通图，求至少要去掉几条边才能使图不连通，即求无向连通图的最小割 Stoer-Wagner 算法 关于算法的证明： Stoer-Wagner 算法 - OI Wiki (oi-wiki.org) 算法流程: 在图G中确定一点S，每次把S的邻居中边权最大的那个邻居与S合并，更新边和边权。 2作为我们确定的S，...

Data Structures A. 猫为什么讨厌狗是有理由的 题意:有$n$个罐子，每个罐子有坚固度$a_i$，同时有$m$个钥匙，每个钥匙型号为$b_i$，可以打开坚固度恰好为$b_i$的罐子。我们可以不断攻击罐子，每次攻击让罐子的坚固度$x$变为$x/d$(向下取整)。$Q$次询问，每次询问$L$到$R$区间，在满足用钥匙开罐子最多的情况下，使用钥匙的最少数。 对于一个钥...

DP A. 代码查重 题意: 有$A$，$B$两个字符串，求$f(a,b)_{max} = xLCS(a,b)-y a -z* b $，其中$x$,$y$,$z$是题目里给的常数，$a$,$b$是$A$,$B$在子串。 分析：设$dp(i,j)$为$A$的前$i$位，$B$的前$j$...