双向BFS初级练习：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include 

【多叉树转二叉树】

这个东西只是在写树形动态规划中用过，总的来说感觉还不错，不用在树归再套一个01背包，写起来方便一点；

所谓的多叉树转二叉树，只要记住左儿子有兄弟就行了,如图（其实很简单）

贴一

       1、导致心血管疾病元凶( 油炸淀粉)

　　2、含致癌物质

　　3、破坏维生素，使蛋白质变性

　　二

令dp[ i ][ j ] 表示在到达第i个城市后还剩余j单位油所消费的最低的钱，那么可以从源点到汇点进行费用松驰操作，其实就是相当于DP，只不过用搜索来实现去了，为了保持最优，得用优先队列进行存储，我用STL的优先队列三百多ms, 手写的优先队列居然要四百多，可能是在数组那里开得比较大，手写的这里不好申请优先队列的数组大小，

#include 

题意：略

算法描述：昨天写了一个纯BFS的，结果TLE，把STL的队列改为手写的队列之后WA了N次才AC，原来是没有考虑蛇头已经在出口时的情况，最终两千多ms过掉了，最后参考了大牛写的A*算法，和位存储状态，于是我也试着写了一下，位运算火候不到家，写得很痛苦啊，好不容易写完了，过了样例，WA，随机测了一组数组，没过，发现是     int CC = (cur&31) + direction[ i ][ 1 ]; 这里位运算那里没有加括号，对于位运算，如果不是非常清楚其优先级还是最好老老实实的加上括号，加了之后，提交，AC

纯搜索题，第一次完成代码量5k以上的搜索题（加上一些注释）我用的单向BFS，最终一千多ms过了，把队列改成手写的，也是一千五百多ms,以为是数组开大了，于是加上滚动数组，居然一千七百多ms.这种题在比赛的时候就算知道怎么做，但想A感觉也不是一时半会的事，还是多练代码能力吧

#include <cstdio>

题意：略

分析：一看就是搜索，不过写起来还是有点麻烦，处理的细节稍微多了一点，代码量感觉不好控制，接近3.5k, 需要注意的细节：如果走两步或三步，要判断中间是否能通过， 还有是否已经走过（注意：这里只与该步的终点有关，与这一步的路上状态无关），还有就是不能在边界上面走，

PS：写完代码，果断出不了样例，最后发现了有四五个地方小错误，改了，过了样例，提交（坚信99%会WA，没想到返回accepted,爽）

开场比较顺利，似乎今天的网络格外配合~~~
12:03 SJTU的Luminer抢得First Blood!率先过D，D的疯狂提交由此开始。

12:26 HIT的HIT_Team01 以2Y率先敲开J，AbOr的大门。

13:03 ECUST的Overmind_2无压力地1Y了I。

13:16 UESTC的UESTC_Walz率先攻克了G,yayamao的插头。

13:16 WHU的OpenMomomo_O率先攻克了K,chjing的身体。

13:17 CSU的FightOn2率先攻克了A，AC的身体。

13:23 FDU的CERush 率先1Y了恶心的F，五魔方被攻陷了。

13:27 BJTU的

分析：因为物品最多为五个，所以可以申请一个五维数组表示状态，dp[ i ][ j ][ k ][ p ][ s ]表示得到i个物品1，j个物品2，K个物品3，P个物品4， S个物品5所花费最少的钱，于是可以按完全背包进行动态规划往后转移，因为物品可以小于5，所以我另外补充了剩余的物品，补充的物品数量为1，价值为0，数量为0,

然后把每个物品单独卖的时候也看成一个“特殊”的OFFER， 于是背包就是最后答案，WA两次，hash数组开小了..

关于数组的几道面试题

经典的状态压缩Dp:

分析：因为m<=10，所以可以用状态压缩来表示状态，状态s中二进制为1表示当前位置安置炮兵，可以预先处理“有效”的状态（在不涉及地图的情况下，由攻击范围确定）， 这样可以减少复杂度，然后再从第1行到第n行，枚举可行的状态，再从前面两行中可以达到该行状态来转移，具体见代码：

#include 

今天在看base64编码转换时，既然对负数的二进制表示有些遗忘，在网上找了一下资料，贴出来已备在此遗忘：

分析：做一次多重背包来实现每种面额的最少硬币合成数，注：如果用二进制压缩的话可以不事先对面额从大到小排序，但是如果用一个记录用了当前面额多少的方法来算的话那就得对面额按从大到小进来排序再进行多重背包，网上说可以用单调队列来优化，不过偶还不会...

代码比别人的长了许多啊...代码控制能力还有待提高

#include 

题意：有两个监狱，并且这两个监狱中的人一样多，一个监狱中的一些人和另外一个监狱里的一些人不能在一个监狱里面（一起可能会发生暴乱），现在要调换两个监狱中的人，调换人次数小于等于m/2(m为一个监狱的人数），求最大的调换次数，并且调换后的监狱里面不能有两个在一起会发生暴乱的人。

算法：刚开始看着没思路，看了别人的思路然后加上自己的一些理解，首先如果A监狱里面的第i个人与B监狱里面的第j个人不能在同一直监狱里面，则从i向j连一条无向边，于是最后是一个有多个连通分量的无向图，设每个连通分量在两个监狱