poj 2069 题目链接 题意：给出n个点，找出包含这n个点的最小半径的外接球。求球的半径。 思路：模拟退火。不过在走的时候，不是随机上下左右前后6个方向走，而是每次往距离当前球心最远的点的方向走。这样才能通过（随机6个方向的写法样例也是可以通过的） 所以模拟退火的精髓大概是“概率减小” 而不是“随机”？ 以及，我看到的资料中，对于模拟退火的介绍，都有一部分是“允许一定概率向着不优的方向移动，但是这个概率会越来越小（因此叫退火）” 但是做了几道所谓的“模拟退火”的题目，发现并没有这部分。。。？ 那样的话应该是爬山法？ 以及看到说模拟退火适合并行计算。。。 是不是体现在我可以放k个初始解，然后每次最优的答案是在k个答案中取最优？ …

貌似香港赛区的规则和大陆有所不同？ 来整理一波。 **D. ****中国大陆赛站及境外赛站的关系。** (a)** **中国大陆各赛站及香港，北朝鲜赛站同为亚洲East Continent子赛区的一部分。 (b)** **中国大陆队伍，可在香港及北朝鲜赛站竞争WF参赛名额。 (c)** **蒙古，北朝鲜，及香港队伍，亦可在中国大陆各赛站竞争WF参赛名额。如果要在CHINA-Final赛站争取WF名额时，需经CHINA-Final组委会同意。 (d) 中国大陆各赛站的参与名额是把East Continent子赛区的总名额减掉香港赛站及北朝鲜赛站的名额而得（亚洲各赛站的参与名额是由亚洲区主席根据2016亚洲规则而定。） (e) 2016 …

开学了orz。。。。。。 随手写个总结（好像团队老师也要个人写报告的样子。。。？ 大概一开始随便刷了点图论题，干掉了树的直径。。。次小生成树。。。这些算是在辣鸡比赛cccc之前把。。。 然后大概就是。。学了。。。博弈论。。。主要是sg函数。。。其实是个很容易理解但是会经常和其他算法一起考察的工具。。。？ 然后大概花了几天时间。。。学习了后缀数组。。。完成了论文题中的一部分。。。 然后顺手学了kmp。。。。真的不明白kmp这种"傻逼算法"（语出某菊苣）我竟然五年时间才搞懂（雾 然后顺手学了ac自动机。。。。之前先学了trie树。。。 然后。。。好像终于完全理解了单调栈和单调队列。。。。？ 感觉之前总是不会写八成是因 …

poj 1385 题目链接 题意：求多边形的重心。 思路： 抄模板（逃 嘛。。三角形的重心是三个点坐标的平均数。。。 多边形的重心其实就是先求三角形的重心然后再加权平均一下就好了。。。权值是面积比。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> …

poj 2420 题意：求多边形费马点，也就是距离所有点的距离之和最小的点。 思路：模拟退火裸题。 关于模拟退火的学习： 模拟退火讲解 我就记住了一句话2333： **爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。** **　模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。** 等写一波题再来总结 以及：感觉适牛的版好简洁嘿嘿嘿。 /* *********************************************** Author :111qqz …

题目链接 题意：问一个小矩形能否放在一个大矩形中，给定两个矩形的尺寸。 思路：主要是斜着放比较难判断。学弟貌似写了离散化角度旋转。。。我的做法是。。直接考虑对角线。。。因为我认为对角线是最有可能放进去的位置。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> …

poj 1386 题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同） 思路：欧拉路。 关于欧拉路： (1)**有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。** (2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。 （3） 无向图存在欧拉回路: 图连通，所有点都是偶数度， （4）无向图存在欧拉路：图联通，只有两个点的度数为奇数。 有向图判断联通性判断的弱联通，因此可以用并查集实现。 具体办法是，判断根的个数，个数为大于1表示不联通。 …

poj 1383题目链接 题意：一个迷宫图，求最远两点的距离是多少，保证每两个点都是联通的。 思路：树的直径。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> …

poj 1379题目链接 题意：给出一个矩形区域的长宽，给出区域中若干点，问距离所有点的最近距离的最大值是多少。 思路：很容易想到模拟退火。 比赛的时候因为忘记判断矩形边界导致答案错得离谱2333 加上之后1A /* *********************************************** Author :111qqz Created Time :2016年08月28日 星期一 19时10分47秒 File Name :code/poj/1379.cpp ************************************************ */ #include <cstdio> …

题目链接 题意：把一个长度为n的只由数字构成的串分成k个不为空的字串，使得最大的串最小（大小是说串所对应的十进制数的大小） 思路：由于长度为x的串肯定大于长度为x-1的串，因此很容易想到，我们要尽可能使得k组串的长度尽可能平均（避免出现某一个串的长度非常大的情况） 我们可以知道，最大值的串的长度一定为 LEN=(n+k-1)/k; 而每一组的长度，只可能是LEN或者LEN-1。 然后build_sa 注意循环串的几个地方记得%n 接下来二分sa数组的下标。 二分check的时候，先枚举断点，断环为链。 由于每部分最长的长度为LEN，所以0..LEN-1中一定存在一个断点。 然后贪心，尽可能取LEN 根据rk值来决定某一段的长度 …