Codeforces Round #357 (Div.2)
暑假已经开始一个多月了，浪也浪得差不多了（虽然还想继续浪下去TAT），我也决定开始偶尔做些事了。正好之前和lzw约好一起做题，于是就在前天晚上选了这套Codeforces的题一起来做，当时做了三道题就睡觉去了，昨天边玩边做总算将剩下两题AC了，所以今天就写篇题解，顺便更新一下blog。
Problem 2A
题意大概就是给你n个人参加某场CF前后的分数，让你判断一下有没有一个人参加前是红名（分数>=2400）而且参加后的分数上升了。按照题意来就行了。
Problem 2B
给出一个值n，让你判断是否存在a、b、c满足a*1234567+b*123456+c*1234=n。因为n不超过$10^9$，所以a最大不超过$10^9/1234567$，大概是810左右，同理，b最大不超过8100，然后从0开始枚举a和b再判断是否有符合要求的c就行了。
Problem 2C
给出一个初始为空的堆，进行三种操作：插入一个数、查询最小值和删除最小值，再给出一系列的操作，要求你输出操作数目最少的一种操作方案，使得输入给出的操作方案是输出的操作方案的子序列，并且要求每次查询和删除操作的时候堆都不为空。
首先，插入操作是不需要管的，主要是查询操作和删除操作。删除操作也是简单的，直接删去即可，如果堆中没有任何元素，那么先插入一个任意数，再删去。查询的主要问题在于查询时的最小值必须和给定操作中给出的最小值相同，所以，根据简单的贪心原理，如果当前堆中没有元素，那么就插入给定操作查询出来的最小值（我们假设为x），如果当前堆中最小元素小于x，那么就将所有小于x的元素全部删去，直到堆为空或者堆中最小值大于x，再向堆中插入x即可，否则，堆中最小值就是x，直接查询就行了。
因为早就不会手写堆了，所以只能用STL中的priority_queue，于是去网上找了几个模板，当场学习了一下，最后打了出来。中间还闹了一个乌龙：我忘了STL中的优先队列到底是小根堆还是大根堆了（虽然印象中应该是大根堆），再加上懒，于是就当小根堆来用，样例竟然全都过掉了（这样例该有多水），之后就自以为没有任何问题，直到我膝盖中了一箭WA了两次之后才想起来STL中的优先队列可能是大根堆，就验证了一下——果然如此。最后好不容易才根据网上的模板打出了小根堆将这题AC了。
Problem 2D
给出一片森林（可能不止一棵树），每个结点都有一个指向结点（保证为其祖先，且其祖先包括但不限于他本身），要求给出一个列表，满足对于每个结点，列表中从上到下出现的第一个是它祖先的结点就是它指向的结点。
我们只考虑一棵树的情况（反正每棵树之间不会互相影响）。一开始，我发现，如果一个结点指向的结点是它父亲结点指向结点的真·祖先（即非其本身），那么肯定是不存在符合要求的表格的，所以我们在DFS的时候记录一下结点的深度，再以此为依据判断一下就可以了。但是除此之外，还有一种情况，那就是某个结点子结点指向的结点在这个结点和这个结点指向的结点之间（并不是这个结点指向的结点），也就是说，假设一个结点x指向的结点是c[x]，如果x有一个子结点y，满足dep[c[y]]<=dep[x]&&dep[c[y]]>dep[c[x]]，那么无论是c[x]还是c[y]放在前面，最后得出的表格都是不符合要求的。
既然考虑清楚了，那么就直接深搜就可以了，从下往上向列表中添加结点，然而，由于我们的搜索是按照结点加入树中的顺序进行的，并非按照结点的深度进行的，所以可能会出错。比如说结点1有两个子结点（结点2和结点3），结点3和结点1指向的结点都是结点1，但是结点2指向的结点是它本身，那么如果深搜先搜结点3，在列表中，结点1排在前面，结点2排在后面，那么就会与给定的要求不符，所以我们不能一口气从上搜到下，只能从叶子结点开始往回搜。首先，先确定所有的叶子结点然后加入到一个堆中，按照结点的深度从大到小排序，之后将结点一个个取出来进行判断，并不断地填充列表，当一个结点的所有子节点都已经判断完毕之后，将该结点加入到堆中，一直到所有结点都判断了一遍。
Problem 2E
这是一道比较坑的计算几何题（对我来说所有计算几何题都是神坑）。一个平面上有n个圆，在平面的某个位置上有一只蟑螂，蟑螂会等概率地选择一个方向以v的速度前进，一旦进入到一个圆的范围内就会停止，问：蟑螂最多奔跑T秒，到达一个圆内的概率是多少。
蟑螂以速度v奔跑T秒，我们可以以其初始位置为圆心，作一个半径为v*T的圆（我们将其标号为0），我们可以以此来判断这个圆和其他各个圆的关系。如果圆x和该圆是外切甚至相离关系，那么蟑螂是不可能跑到圆x的范围内的（虽然如果是外切关系的话，是存在一个方向使蟑螂在第T秒恰好跑到圆x的范围内的，但由于只是一个方向，相比$2\pi$实在是太小了，所以就忽略不计）。如果是包含或者内切关系，从圆0的圆心作圆x的切线，可以得到一个圆心角，只要蟑螂选择的方向在该圆心角之内，那么就可以在规定时间内到达圆x。对于相交的情况，我开始认为应该是求两个交点，交点所成圆弧所对应的圆心角内都是符合要求的，然而后来才发现，从圆0的圆心开始作圆x的切线，如果切点在圆0内，则按照切线所成圆心角来算，否则按交点所成圆心角来算。
经过计算之后，我们会得到许多圆心角，将这些圆心角并起来再求出总度数，除以$2\pi$就是答案了。其实，这道题与BZOJ1043 下落的圆盘有异曲同工之妙，如果做过后者，做起这道题来也就方便许多了。
Code：
2022年8月08日 18:50
Finding the best WiFi names for their new connections or routers is that they want some cool or funny names that make them feel nice and at the same time when your friends, family, or someone comes over to your place don’t you think a nice name would make the charm of the house as well. WiFi Names Moreover, you can not just add cool names to your Network SSID but have some Puns or Jokes intended through the WiFi name that can bring a nice laugh out of anyone who comes across your connection in their WiFi settings finder. Also sometimes you want to hide WiFi SSID for security reasons.
2022年8月20日 20:24
Apple Back to School Sale 2021: Learn more about free delivery and returns. Enjoy 20 per cent off AppleCare+ coverage.2. mac student discount Learn more about AppleCare+. Free personal engraving. Apple. Apple on Wednesday launched its annual Back to School promotion in Australia, New Zealand, South Korea, and Brazil.