1001Typhoon题意：给你台风的轨迹坐标以及避难所的坐标，台风的半径不可预测，求让每个避难所不安全的最小台风半径是多少。分析:枚举每个点到所有“线段”的距离取个min。代码:附上队友的代码（懒）:#include#include#definerep(i,a,b)for(inti=a;i-eps)return0; if(x>0)return1; return-1;}#ifndefPOINT_H#definePOINT_Hstructpoint{ /*以向量的形式表示*/ doublex,y; point(){} point(doublea,doubleb):x(a),y(b){} void

1003SimpleSetProblem题意：分别从k个集合中选一个元素组成一个数组\((a_1,a_2,a_3,...,a_k)\)，求max\((a_1,a_2,a_3,...,a_k)\)-min\((a_1,a_2,a_3,...,a_k)\)的最小值。分析：我们给每个集合中的元素添加一个id标识它属于哪个集合，然后将所有集合合并并按数值大小从小到大排序，这样问题就转化成：找一个最小区间，该区间满足每个id都至少出现一次，求这些最小区间右端点的值减去左端点的值的最小值是多少？显然可以用双指针来做，用st数组维护[i,j]不同id的出现次数，cnt统计区间[i,j]内的id种类数，当st

1005.OutofControl题意:有n个数\(x_1,x_2,...,x_n\)，在其中选k个数依次放入栈中。如果当前放入栈中的数\(x_i\)小于栈顶的数，则向栈中放入与先前的栈顶相同的数而不是\(x_i\)。求对于每个k对应的方案数。分析：先排序离散化，然后考虑dp。状态定义:f[i][j]表示长度为i且最后一个数是j的方案数。状态转移：f[i][j]=\(\sum_{t=1}^jf[i-1][t]\)答案：长度为i的栈由长度为i-1的栈转移过来,且长度为i-1的栈最后一位要小于等于j。那么对于长度为i的这类问题的答案即\(\sum_{j=i+1}^nf[i][j]\)，条件就是小于

1001AliceGame题意：起初有n个物品，玩家可以有如下操作：①若该堆物品数量小于等于k，全部拿走。②若该堆物品数量大于k，则只能选择拿走k个物品，并将剩余物品分成不为空的两堆。Alice先手，问谁必胜。分析：打表可知当n%(4*k+2)==k+1时Alice必败，其他时候必胜。打表代码：#includeusingnamespacestd;typedeflonglongLL;constintN=1e6+5;LLf[N];intsg(intx,intk){ if(f[x]!=-1) returnf[x]; setS; if(x0) S.insert(sg(0,k)); else

1001Hide-And-SeekGame题意:给出一颗树，两人在树上特定两点来回走，问最早在那个节点相遇。分析：两条路径相交，则一条路径的LCA一定在另一条路径上。我们可以预处理一个dfs时间戳，结合LCA来判断路径相交。由于本题的点数较小,所以我们可以枚举相交链上的每一个点，然后计算他们在这个点最早相遇的时间，找到其中相遇时间最早的点作为答案输出。对于相交链上的一个点x,我们可以计算出A到达x的时间满足2k1·dis(Sa,Ta)+dis(Sa,x)或者2k1.dis(Sa,Ta)+dis(Sa,Ta)+dis(Ta,x)。(其中k为任意正整数)类似的，B到达x的时间满足2k2·dis(S