poj 1385 题目链接

题意：求多边形的重心。

思路：

抄模板（逃

嘛。。三角形的重心是三个点坐标的平均数。。。

多边形的重心其实就是先求三角形的重心然后再加权平均一下就好了。。。权值是面积比。

poj 2420

题意：求多边形费马点，也就是距离所有点的距离之和最小的点。

思路：模拟退火裸题。

关于模拟退火的学习： 模拟退火讲解

我就记住了一句话2333：

**爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。**

**　 模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。**

题目链接

题意：问一个小矩形能否放在一个大矩形中，给定两个矩形的尺寸。

思路：主要是斜着放比较难判断。学弟貌似写了离散化角度旋转。。。我的做法是。。直接考虑对角线。。。因为我认为对角线是最有可能放进去的位置。

poj 1386

题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同）

思路：欧拉路。

关于欧拉路：

(1)**有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。**

(2)有向图G为半欧拉图(存在欧拉路)，当且仅当G的基图连通（弱联通），且存在顶点u的入度比出度大1、v的入度比出度小1，其它所有顶点的入度等于出度。

阅读更多

poj 1383题目链接

题意：一个迷宫图，求最远两点的距离是多少，保证每两个点都是联通的。

思路：树的直径。

  1#include <cstdio>
  2#include <cstring>
  3#include <iostream>
  4#include <algorithm>
  5#include <vector>
  6#include <queue>
  7#include <set>
  8#include <map>
  9#include <string>
 10#include …

poj 1379题目链接

题意：给出一个矩形区域的长宽，给出区域中若干点，问距离所有点的最近距离的最大值是多少。

思路：很容易想到模拟退火。

比赛的时候因为忘记判断矩形边界导致答案错得离谱2333

题目链接

题意：把一个长度为n的只由数字构成的串分成k个不为空的字串，使得最大的串最小（大小是说串所对应的十进制数的大小）

思路：由于长度为x的串肯定大于长度为x-1的串，因此很容易想到，我们要尽可能使得k组串的长度尽可能平均（避免出现某一个串的长度非常大的情况）

题目链接

思路：注意xy-(x-2)*(y-2)=2x+2y-4，一定被2整除。因此siz为2的也是合法的。这个比较容易忘掉。

其他的判定条件都很好想。具体见代码；

题目链接

题意：n个数围成一圈，对于负数可以进行magic操作，也就是取反，但是会影响到左右相邻的，加上这个负数。问最少进行多少次magic操作，使得所有数都是非负。

最近入手了x1 c

然后发现没办法支持 f22…..

没办法，只好上f24了。。。虽然明知道一堆bug…

最近发现。。之前在系统设置->键盘->打字  中的调整键盘延迟和速率的选项。。。不见了。。。

想家了。

破游戏，不玩了。

上次绝望的想哭，还是那场校内选拔赛

我真的在努力了啊，我真的在认真了啊…

可是一年过去，我还是这么菜。

真的想哭，真的不想玩了

题目链接

题意：有n扇门，n种钥匙，一一对应。每扇门打开后可能得到k把钥匙（k可能为0）。一扇门还可以用一颗炸弹炸开。现在问要开所有门，使用炸弹的期望个数。

题目链接

题意：给出一个数，问包含这个数三个数组成的勾股数，输出另外两个数。

思路：

所谓勾股数,就是当组成一个直角三角形的三边长都为正整数时,我们就称这一组数为勾股数. 那么,组成一组勾股数的三个正整数之间,是否具有一定的规律可寻呢?下面我们一起来观察几组勾股数： 规律一：在勾股数（3,4,5）、（5,12,13）、（7,24,25）（9,40,41）中,我们发现 由（3,4,5）有：32=9=4+5 由（5,12,13）有：52=25=12+13 由（7,24,25）有：72=49=24+25 由（9,40,41）有：92=81=40+41. 即在一组勾股数中,当最小边为奇数时,它的平方刚好等于另外两个连续的正整数之和.因此,我 …

题目链接

题意：把一个数n(n<1000)转化成二进制输出。。。

思路：。。。搜acm bitset 搜到这题。。。所以其实这并不是“bitset”优化的题。。。只是题目名字交这个了2333。

1.定义与初始化 在定义 bitset 时，要明确 bitset 有多少位，这个位数是整形常量

(tips:如果长度和输入的数m有关，在做翻转操作以后再统计时候会多算，一个可以的做法是设置一个长度为m，所有位上都是1的位串，然后翻转之后先与一下。类似的技巧还有很多。)

题目链接

题意：n个城市，m条双向路，要从k条中选择一个，使得到其他n-k个城市中的某个城市的距离最短。

思路：直接暴力 枚举。1A

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月20日 星期六 21时02分14秒
 4File Name :code/cf/#368/B.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8 …

题目链接

。。。这题也能成hack题。。。。有毒啊。。然后我room里所有人都写对了。。。是我看这道题看得太早了？

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月20日 星期六 21时01分57秒
 4File Name :code/cf/#368/A.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9 …

。。第一场组队赛。。。罚时爆炸。。。pacedect不在。。。没rk1好不开心啊。。。我的锅我的锅。。。

晚上cf听从适牛的写题策略。。先从c开始。。。终于蓝了。。。也是感动。。。

hdu 1754 题目链接 题意：单点更新，区间查询最大值。 思路：线段树。 一开始借鉴了clj的pointer写法。。wjmzbmr’s code 直接MLE。。。看来也许只能在cf上用。。。 下面是MLE的代码：