小胡同的诗

上来拿个1<<10勋章…题目链接：woj107DescriptionConsider a 3 by 3 arrangement of the digits 1 to 9, as illustrated in the following diagram:1 3 58 7 64 9 2Figure 1The arrangement can by modified by ...

题目链接：HDU1429解题思路：正常搜最短路的图，但是走过的路可能重复走，因为可能拿到钥匙后沿路返回。要有一个记录口袋中钥匙相应状态的数组，由于有“a-j”10把钥匙，可以用10位二进制的数将其状态压缩到这个数中0表示没有，1表示有。可以加一个步数即使走最短路也到达不了终点的剪枝。注意记录行走状态的数组book要提前标记，不能等到pop了才标记，不然会爆内存…（PS:这题题目没说清楚被魔王抓回...

解题思路：裸拓扑排序 ，由于要输出字典序最小的ans，所以用堆作容器，复杂度由原来的O(V+E)变为O((V+E)*logV),题中输入的数据都符合DAG 的要求，所以不必判环。解题细节拓扑排序写法：初始化：将入度为0的节点V入队将入度为0的节点加入排序结果集中删除与入度为0的节点相连的边删除，相连的边入度-1将跟新边后入度为0的节点入队AC代码:#include &amp;lt;c...

题目链接：HDU2647题目大意：给一张n节点m条边的图，(n&lt;=10000,m&lt;=20000)。并且要求每次输入的u,v节点 v的价值大于u的价值。最终输出总价值的最小值。解题思路：利用拓扑排序输出的序列价值要递增比较容易建图，这张m边有向图边的方向满足 (v,u):u的价值大于v的价值 这样一个偏序关系。关键点在于 反向建图 。AC代码：#include &lt;cstd...

题目链接：超级密码题目大意：给n,c,m以及m个数字(可能是包括16进制内的任意数),问组合成的数组能整除n的最小是多少,c位每个数字的进制。解题思路：求最小，即数位最短以及字典序最小，先把m个数排个序，然后bfs，注意m+k与m%n+k对于n来说一定是同余的,即：(m+k)%n == (m%n+k)%n。所以当前面搜到余数位s的时候就标记一下。同时，每次搜一种可能的状态都要先把数字做模处理，...

PS：代码超时的，可惜。正解好像是DP，很好奇为什么DFS能卡过而BFS不行题目链接：费解的开关题目描述你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种...

前言网络中的交换机能够实时的进行数据的接收转发，如果我们要从A地传送一组数据报到达B地，在不存在丢包的前提下一次分发B地最多能接收多少报文呢？这种网络模型可以利用水流的模拟来解决，学名称网络流。算法介绍总所周知，水往低处流。每个节点可以抽象成一个木桶，所以一次能通过的流量是有瓶颈的，根据木桶原理，我们每次可以流过的流量取决于前面最小的弧。这里很容易走进一个误区，贪心地每次去找下一条路径的最...

题目链接：leetcode199思路：宽搜由于每一层只能有一个结点加入答案集，这种跟层次有关的bfs都可以解决，不过每次还要多维护一个层次的标记，当下一个队头改变了层次，当前的结点就要加入答案集。深搜妙，利用到了先来先得的特型，右子树的优先级最高其次是左子树，当一层有个结点加入答案集该层其余的结点就没机会加入，用向量的长度恰好可以完成这个逻辑。具体看Code。/** *...

题目链接：leetcode787思路：首先这题可以bfs做，因为第一个约束是K中转站内，即搜K+1层然后松弛dist数组，当终点的dist没有被松弛过说明不通。根据这个思路可以设计一个二维状态dp[i][j]dp[i][j]dp[i][j]表示到达j点最多经过i个中转站的最少费用，于是状态转移方程可以推导为: dp[i][to]=min(dp[i][to], dp[i-1][from]+w[...

解题思路：对优先队列有了更深的理解。以前写优先队列是针对那种有权的最短路问题，搜出来的必定是道路的花费最优解，我们可以用book标记走过的地方，下次不必要再走；而本题由于用了优先队列，走过的点到底要不要再考虑呢？假设上次到达本点拐弯了1次，而现在却拐弯了2次，当然不要本次的这个方法走，相反如果本次用1次，而上次用2次，就要用本次的方法。如果两次的拐弯数一致呢？其实两种都要搜，为什么？因为你进来的方...

解题思路：（吐槽：还是菜。弱爆了！咋办）最终的代码还是翻了翻题解思路才勉强A了，而且还是没预处理的方法A的，数据卡了点时间过的。而代码1我觉得理论上是比代码2来得快的，居然TLE了。代码2却过了。百思不得其解QAQ。做这种题要注意状态数组如何设置！我这边用vis表示走带x，y点找到几个人。记得至少要3维！！！然后0表示1个都没找到，1找到一个，2找到另一个，3都找到！TLE一早上  感觉没爱了QA...

AC代码：#include#include#include#include#include#includeusing namespace std;struct node{ int x,y,time; friend bool operator < (node a,node b) { return a.time>b.time; }};

题目大意：一张6×6的图，给你一个起点，终点，以及三道墙，这三道墙给两边的坐标，每次寻找路径时候不能翻墙行走，输出从起点到终点的最短路径。解题思路：这题难就难在之前都是搜索点，这题搜索格子，并且边上有障碍物。所以要如何建立这张有障碍物的无权图呢？起初就是想用偶数格子表示边，奇数格子表示格子，硬生生地建图两个奇数格子要移动之前看看中间有没有障碍物。奈何自己太弱，不敢这样写，中间代码逻辑处理不来。（p...

题解：本题难点就是遇到楼梯的判断，我用一个优先队列保存到当前的步数，如果下一步是楼梯，如果截至目前步数为奇数，则楼梯方向要变，并且如果楼梯的方向变成与当前要走的方向不一致，则要等一分钟；否则直接到楼梯的另一头。可能读我代码的会觉得我的代码会存在这样的问题，就是到了楼梯的另一端可能还会返回，但我有用book数组标记了，即这种情况会被筛掉。以下代码在HDOJ测0msAC代码如下：#include

传送门：点击打开链接解题思路：两层，#表示楼梯，然后基本的bfs，注意特殊的这些情况，两层的同一个位置都是楼梯，会进入无限循环导致TLE。下楼或上楼撞墙死的也要筛掉。bfs或dfs都可以，图不大建议bfs吧快点，bfs0ms，不过oj不怎么稳定有时候会15msAC代码如下：#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;cst...

传送门： 点击打开链接题目大意：给你2个四位数的数字，要求把上面那个转变成下面那个。转换规则：每个位置的数字每次只能+1或-1，或者和相邻的位置的数字交换，这里不存在第一个和最后一个交换的情况。问最少需要多少步数。解题思路：由于求最短交换步数，用bfs搜索。46ms时间。这里有个进阶的做法：双向搜索。什么是双向搜索呢？就是利用bfs的特性，每次一层一层地搜索。一个循环从正向搜索，一个循环从终点过来...

新年第一A，2018继续加油，新年快乐传送门：点击打开链接题目大意：给你一张地图，S和Z两个人在地图上找到对方的最短步数。并且两个人每次走的方向都刚好相反。当S越界或者碰壁时呆在原地不动。解题思路：bfs的正常操作，一个四维图记录两个人走过的地方。注意的地方是，你主要判断的应该是Z而不是S，什么意思呢？就是Z走后再把S“带着走”，例如有这种情况：Z碰壁或者出界无论S什么情况都不能使这种情况入队，此...

题解：搜图的题，有权最短路用优先队列+bfsAC代码如下：#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;cstring&gt;#include&lt;queue&gt;#include&lt;algorithm&gt;using namespace std;struct node{ int x,y,ste...

题目大意：就是给你2个杯子和一瓶水，问如何将这瓶水二等分，并且输出最少的倒水次数解题大意：最终的结果一定是最大的杯子和第二大的杯子各放一半水。然后每一次三个瓶子的装水情况下一步如何倒水一共有六种倒法，然后bfs模拟这个倒水，记得用一个数组纪录倒水后各个瓶子的装水情况。AC代码如下：#include&lt;stdio.h&gt;#include&lt;string.h&gt;#include&l...