迷宫问题 1 2 3 4 /************************************************************************* 5> File Name: code/2015summer/searching/KK.cpp 6> Author: 111qqz 7> Email: rkz2013@126.com 8> Created Time: 2015年07月25日 星期六 13时33分00秒 9************************************************************************/ 10 11 …

http://poj.org/problem?id=3087 用bfs写的，但是其实就是个模拟啊喂！ 只有一种操作，何谈最短？　一直往下写就行了． 有一点疑惑，就是map的初始值 比如我定义的　map<string,int>d;它的初始的value是什么？随机值？０？还是什么，百度了下，没找到，求指教． 1 2 #include<iostream>3 #include<iomanip>4 #include<cstdio>5 #include<algorithm>6 #include<cmath>7 #include<cstring>8 …

http://poj.org/problem?id=3126 题意是说,给定两个四位素数a b 问从a变换到b,最少需要变换几次. 变换的要求是,每次只能改变一个数字,而且中间过程得到的四位数也必须为素数. 因为提到最少变换几次,容易想到bfs,bfs第一次搜到的一定是最短步数. 先打个素数表 然后写个函数判断两个四位数有几位数字不同,如果只有一位,返回true,否则返回false 然后竟然wa了两次! 下表写错! pri[k++]=i;是先给pri[k]赋值,再k++; pri[++k]=i;才是先增加,再赋值.这个搞错了.所以wa了....sad 1 2 …

http://poj.org/problem?id=3279 反转类问题. 有N*M个方格,每个上面有数字0或者1 操作一个方格,这个方格即其相邻的四个方格(有公共边)会改变状态(由0变1或者由1变0) 问至少需要多少次操作,所有的状态都为0 如果有多组,输出字典序小的那一组. 跟开关灯的那题相似. 因为每个开关灯的动作还影响其他相邻灯的状态.所以对于这种题,一般思路是,先定住一部分,再由已知定住的这部分去确定其他部分. 对于这道题而言 首先我们可以很容易发现,操作数为偶数和为0是等价的. 操作数为1和为奇数是等价的. 对于这道题而言,我们可以首先枚举第一行的状态,一共有 2< 然后如果 a[i-1][j]为1,因为i-1行的 …

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83295#problem/I 最多18个点，选3个点，能够成的三角形不超过1000个，O(n2)暴力就可以。 思路就是枚举三个点点，对于每一个构成的三角形，把这个三角形的最小角和次小角存起来。 然后枚举三角形，判断是否有两个三角形的最小角和次小角分别对应相等。 需要注意的是题目中问的是相似三角形的最大个数 如果A B 相似 C D 相似，但是B C 不相似，答案应该是2. 还有三角形自身和自身是相似的。 一开始求角度的时候只求了cos值，忘了求下acos了。 需要注意的是，枚举的到时候，三个点可能共线，这个还挺好，题目中说的 …

http://poj.org/problem?id=2398 题意大概是说将一个盒子用n个board分成n+1 部分 然后往里面放toy,给定盒子,board,和toy的坐标 问所有的toy放完后,有多少部分中有t个toy; 简单计算几何 需要判断的是点和直线的关系. 判断 某一点在直线左右侧 左右方向是相对前进方向的,只要指定了前进方向就可以知道左右(比如指定前进方向是从直线的起点到终点).判断点在直线的左侧还是右侧是计算几何里面的一个最基本算法.使用矢量来判断. 定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量： ** S(P1,P2,P3)=|y1 y2 y3|= …

http://poj.org/problem?id=2251 简单bfs，只不过是三维的。。。 唯一的坑点在输出上... Escaped in %d minute(s) 这意思是答案为1输出minute,不为1输出minutes还是说是不是1都输出minute(s)? 试了下，答案是后者。 另：终于找到了好的读地图的方法。。。而不用担心回车符。 就是先读成字符串。 具体见代码 1 2 3 /************************************************************************* 4> File Name: code/2015summer/searching/B.cpp …

http://codeforces.com/contest/558/problem/C 题目大意是说，给定N个数，可以对任意数进行任意次两种操作，×2，和/2（整除） 问最少操作多少次，可以让所有数相等。 嘛，前半个小时A掉了前两个提，d E貌似都是线段树。。并不会。。。就一直搞C。。。。 然而并没有做出来。位运算是什么神奇的黑魔法。 转载一份题解：http://blog.csdn.net/qq_24451605/article/details/46906813 思路是声明两个数组，一个数组表示到达i的步数，另一个数组表示n个数中能够达到i的数的个数（包括本身） 1 2 …

http://poj.org/problem?id=1564 dfs 三个参数 x,sum,k, x表示开始的坐标,sum表示当前的和,k表示这是一组答案中的第几个数,是用来记录路径的... 调了好久没写出来...我写完之后答案会有重复.一开始想开一个boolean数组记录,这样第一组样例的3+1就只会输出一遍,但是这样,2+2就不会被记录到答案中了. 然后看了下别人的代码... 卧槽,只是加了个判断...当前的数和上一个如果不同,就继续dfs.... 我为何就没想到...这特么是判断重复的直译啊.... 1 2 …

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82557#problem/A Zk的解法：拆点，把每一个点存成两份，r[i]和r[n+i] 连边的时候如果u和v相连，我们就分别连 u&&v; 和 u+n&&v;+n 和 u&&v;+n 其中最后一个存法是要使用魔法的情况... 最后求从1到n+n的最短路径即可 如图 斜着的边表示使用魔法的情况。 由1到n+n，只经过一次斜边，这是与题干中只使用一次魔法相对应的.... 由于权值变成一半可能出现浮点数... 我们不妨先 权值先整体*2 最后结果的时候再/2 zk好聪明（逃） 然 …