uva 10004 Bicoloring (交叉染色法判断二分图模板题)

uva10004题目链接

题意:给出一个无向图,问是否可以组成二分图。

思路:交叉染色法。

首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:

          1.未染色    那么继续染色此节点(染色为另一种颜色)

          2.已染色但和当前节点颜色不同      跳过该点

          3.已染色并且和当前节点颜色相同       返回失败(该图不是二分图)

 

学习链接

 

upd:更正dfs中的一个错误。

把dfs(v,1-x)改成了 if (!dfs(v,1-x)) return false;

之前的写法中,当前层之后的层的没有起到任何作用。。。

而实际上应该是后面只要某一层不满足,整体就该为false.

写成这样这题还能过我也是醉了。。。。

BZOJ 3680: 吊打XXX (广义费马点,模拟退火+爬山)

3680: 吊打XXX

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 2043  Solved: 732
[Submit][Status][Discuss]

Description

gty又虐了一场比赛,被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身,但还是被人多势众的蒟蒻抓住了。蒟蒻们将
n个gty吊在n根绳子上,每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同,绳
结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标,由于他太弱了决定向你求助。
不计摩擦,不计能量损失,由于gty足够矮所以不会掉到地上。

Input

输入第一行为一个正整数n(1<=n<=10000),表示gty的数目。
接下来n行,每行三个整数xi,yi,wi,表示第i个gty的横坐标,纵坐标和重力。
对于20%的数据,gty排列成一条直线。
对于50%的数据,1<=n<=1000。
对于100%的数据,1<=n<=10000,-100000<=xi,yi<=100000

Output

输出1行两个浮点数(保留到小数点后3位),表示最终x的横、纵坐标。

Sample Input

3
0 0 1
0 2 1
1 1 1

Sample Output

0.577 1.000

HINT

Source


By wangxz

思路:

看起来是物理题。。其实就是求广义非费马点。。

也就是带权费马点。

一般的费马点是说,所有点到这个点的距离之和最小。

带权的费马点就是每个点到这个点的距离*权值,和最小。

这道题用到的才是真正的模拟退火!

模拟退火很重要的一部分就是允许有一定概率向不优的方向走,之前写的所谓的“模拟退火”的题目,全都没有体现这一点。

所以那些,其实就是一个爬山法吧。。

而且看到主席如是说…

webwxgetmsgimg

 

 

这道题真的很棒。

初始搜索范围很大的时候用模拟退火,快速得到一个大致范围。

但是由于精度不能很好的保证,于是在做完模拟退火后在答案附近爬山。

完美的分段思想!

一直调不对样例的原因是。。。

忘记把ans初始化成最大值23333

 

hdu 5017 Ellipsoid (模拟退火,计算椭球到定点的最小距离)

 

hdu 5017 题目链接

题意:给出椭球方程的6的参数 a,b,c,d,e,f 

问椭球上的点到原点(0,0,,0)的最小距离是多少。

思路:感觉难点在于,如何保证搜到的点一直在椭球上。

一开始我考虑到了用椭球的参数方程。。。。然后发现不记得是什么了2333

然后看了题解,发现比较巧妙的做法是,只搜索x,y,然后从椭球方程中解出z。

x,y确定以后,椭球方程就变成了一个关于z的一元二次方程,可解。

由于是要求距离原点的最小距离,而现在可能得到的两个解是关于xoy平面对称的,只有z坐标不同,因此我们取距离原点近的那个z。

以及,感觉在平面上搜4个方向就好。。。没必要8个方向。。?

2016-08-31 14-49-34 的屏幕截图

wa到死是因为。。。计算距离。。忘记开根号。。。。。呵呵呵呵呵呵呵呵呵我是傻逼。。。

poj 2069 Super Star (模拟退火)

poj 2069 题目链接

题意:给出n个点,找出包含这n个点的最小半径的外接球。求球的半径。

思路:模拟退火。不过在走的时候,不是随机上下左右前后6个方向走,而是每次往距离当前球心最远的点的方向走。这样才能通过(随机6个方向的写法样例也是可以通过的)

所以模拟退火的精髓大概是“概率减小” 而不是“随机”?

以及,我看到的资料中,对于模拟退火的介绍,都有一部分是“允许一定概率向着不优的方向移动,但是这个概率会越来越小(因此叫退火)”

但是做了几道所谓的“模拟退火”的题目,发现并没有这部分。。。?

那样的话应该是爬山法?

以及看到说模拟退火适合并行计算。。。

是不是体现在我可以放k个初始解,然后每次最优的答案是在k个答案中取最优?

 

 

 

2016 ACM ICPC Asia Hong Kong Regional rules

貌似香港赛区的规则和大陆有所不同?

来整理一波。

 

D. 中国大陆赛站及境外赛站的关系。

(a) 中国大陆各赛站及香港,北朝鲜赛站同为亚洲East Continent子赛区的一部分。

(b) 中国大陆队伍,可在香港及北朝鲜赛站竞争WF参赛名额。

(c) 蒙古,北朝鲜,及香港队伍,亦可在中国大陆各赛站竞争WF参赛名额。如果要在CHINA-Final赛站争取WF名额时,需经CHINA-Final组委会同意。

(d) 中国大陆各赛站的参与名额是把East Continent子赛区的总名额减掉香港赛站及北朝鲜赛站的名额而得(亚洲各赛站的参与名额是由亚洲区主席根据2016亚洲规则而定。)

(e) 2016年亚洲规则规定,所有亚洲队伍都可以去亚洲任何赛场参加比赛,但是一个队伍必须从自己的子赛区出线。

来源:西杰阿雄的博客

 

关于香港网络赛的规则:

  • Additional rules specific to this Online Preliminary are as follows:
    1. Accepted teams are allowed to attempt this online contest from anywhere with internet access.
    2. Each coach (a faculty member of that team’s University) will supervise his/her team(s) during the 5-hour online contest so that ICPC rules are respected, especially on these three important points:
      1. The usage of only one computer per team of three students.
      2. The usage of only hard copy reference materials (and no internet materials), up to 25 pages single-sided, letter or A4 size.
      3. The member of each team can only discuss the problemset among the three of them during the 5 hours.
    3. Coach will have to take photos of their team(s) working on the preliminary (or right after the end of the preliminary) and submit that photo to the secretariat (acmicpc@cse.cuhk.edu.hk) for documentation and verification purposes.
    4. The result of the Online Preliminary is not final until the organizers perform checks on code submitted by top qualified teams.

来源:2016亚洲区域赛香港赛站官网

简单翻译一下:

这次网络预选赛的特别规则如下:

1.申请通过的队伍可以再任何由网络的地方参加比赛。

2.每个学校的教练将再比赛期间监督队员确保icpc的规则得到执行,尤其是以下三点:

a.每一队的三名队员只允许使用一台电脑。

b.只允许使用纸质参考资料(不允许网络资料),纸质参考资料最多25页,单面A4纸。

c.每个队的队员在比赛期间只允许和同队的队员进行交流。

3 .要求教练在网络赛期间或者网络赛刚刚结束时对每个队拍照,并将照片发送到acmicpc@cse.cuhk.edu.hk

4.最终结果组委会对提交的代码查重后的为准。

 

网络赛所用的oj: kattis

可以选择语言包括所有该oj支持的语言,不过题目只保证可以用c++和java解决。

 

晋级规则:一所学校最多晋级2队,前45名非本地(香港,澳门)队伍可以晋级。

(除此之外,如果有排名在前面的队伍不能参加,那么排名45以后的非本地队伍将按照排名得到不能参加的队伍的名额)

 

 

 

 

2016暑假总结

开学了orz。。。。。。

随手写个总结(好像团队老师也要个人写报告的样子。。。?

大概一开始随便刷了点图论题,干掉了树的直径。。。次小生成树。。。这些算是在辣鸡比赛cccc之前把。。。

然后大概就是。。学了。。。博弈论。。。主要是sg函数。。。其实是个很容易理解但是会经常和其他算法一起考察的工具。。。?

然后大概花了几天时间。。。学习了后缀数组。。。完成了论文题中的一部分。。。

然后顺手学了kmp。。。。真的不明白kmp这种”傻逼算法”(语出某菊苣)我竟然五年时间才搞懂(雾

然后顺手学了ac自动机。。。。之前先学了trie树。。。

然后。。。好像终于完全理解了单调栈和单调队列。。。。?

感觉之前总是不会写八成是因为我之前看到的代码太丑了2333.

然后好像领悟到了模拟退火的本质。。。。?(也可能并没有2333

所以说其实大概就这些。。。。?

果然是又颓了一个假期啊。。。。哎。。。

线段树还是没来得及搞。。。。

今年大概会去沈阳。。。。?

所以还有大概一个半月的时间。。。。

干!

 

poj 1385 Lifting the Stone (多边形的重心)

poj 1385 题目链接

题意:求多边形的重心。

思路:

抄模板(逃

 

 

 

 

 

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

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

 

poj 2420 A Star not a Tree? (模拟退火模板题求多边形费马点)

poj 2420

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

思路:模拟退火裸题。

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

我就记住了一句话2333:

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

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

等写一波题再来总结

以及:感觉适牛的版好简洁嘿嘿嘿。

 

poj 1380 Equipment Box (简单几何)

题目链接

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

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

 

poj 1386 Play on Words (欧拉路)

poj 1386

题意:n个单词,问能否形成一个串(单词接龙,收尾相连,当且仅当前一个单词的末尾字母和后一个单词的首字母相同)

思路:欧拉路。

关于欧拉路:

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

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

(3) 无向图存在欧拉回路:  图连通,所有点都是偶数度,

(4)无向图存在欧拉路:图联通,只有两个点的度数为奇数。

有向图判断联通性判断的弱联通,因此可以用并查集实现。

具体办法是,判断根的个数,个数为大于1表示不联通。

 

 

 

 

 

 

 

poj 1383 Labyrinth (树的直径裸题)

poj 1383题目链接

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

思路:树的直径。

 

 

poj 1379 Run Away (模拟退火)

poj 1379题目链接

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

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

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

加上之后1A

 

 

seerc 2014 Circle of digits (二分+后缀数组)

题目链接

题意:把一个长度为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值来决定某一段的长度是LEN还是LEN-1(如果rk值比当前的大,那么就只能取LEN-1,否则取LEN)

如果此时k段的长度之和超过了n,说明此时的最大值还可能更小。

于是继续二分区间的前一半。

 

 

seerc 2014 D – Frame (傻逼题)

题目链接

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

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

 

seerc 2014 A Banks (暴力)

题目链接

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

思路:我们知道,如果一个负数想变成整数的话,只能通过magic 操作。唯一可能影响次数的就是顺序。

不过手动写了几个发现顺序好像无关紧要?

于是大胆猜测,写了发暴力2333。