C++中的逻辑与运算
样例
#include<iostream> using namespace std; int main(){ cout<<(1&1)<<endl; //1 cout<<(1&-1)<<endl; // 1 cout<<(-1&-1)<<endl; //-1 cout<<(-2&-3)<<endl; //-4 return 0; }2.解释
1&1：
1 0000 0001
&
1 0000 0001
-----------------------
1 0000 0001
1&-1：
1 0000 0001
&
-1 1111 1111 （补码）
-----------------------
1 0000 0001
解释：1的补码是1111 1111，然后进行逻辑与运算即可。
-1&-1：
-1 1111 1111 （补码）
&
-1 1111 1111 （补码）
-----------------------
1111 1111
解释：负数和负数的逻辑与运算比较特殊。
-1 & -1 的直接结果是1111 1111，出符号位以外，剩下111 1111
然后把最低位减一得： 111 1110
然后按位取反得： 000 0001, 也就是1
加上符号就是-1，所以最后结果是-1
-2&-3：
-2 1111 1110 （补码）
&
-3 1111 1101 （补码）
-----------------------
1111 1100
解释：
-2 & -3 的直接结果是1111 1100 ，出符号位以外，剩下111 1100
然后把最低位减一得： 111 1011
然后按位取反得： 000 0100, 也就是4
加上符号就是-1，所以最后结果是-4
字符串的输入输出汇总
【算法】分治算法
前言
所谓分治算法就是指分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。
比如，我们玩过最简单的猜数游戏，一开始，对方先想一个1000以内的正整数，然后你给出一个数x。对方只要回答“比x大”或者“比x小”或者“猜中”。
开始猜测是1到1000之间，你可以先猜500。运气好的一次猜中，如果比500大，显然结果不是1到500之间，那么下一次就猜501到1000。如果比500下，那么下次就猜1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。这样不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。
基本思想及策略
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法适用的情况
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
应用
（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
（11）一元三次方程求解
快速排序：
void qsort(int left, int right){ int i=left; j =right; mid=a[left+right]/2; while(i<=j){ while(a[i]<mid) i++; while(a[j>mid]) j--; if(i<=j){ swap(a[i],a[j]); i++; j--; } } if(left<j) qsort(left,j); if(i<right) qsort(i,right); }一元三次方程求解：
描述
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。
给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
输入
一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。
输出
一行，包含三个实数，为该方程的三个实根，按从小到大顺序排列，相邻两个数之间用单个空格隔开，精确到小数点后2位。
样例输入
1.0 -5.0 -4.0 20.0
样例输出
-2.00 2.00 5.00
【STL】二分查找函数 lower_bound 和 upper_bound
【STL】二分查找函数(算法)—binary_search
【题解】采药的最短路径
【题目描述】
少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
下图 显示了一个迷阵的样例及李逍遥找到仙药的路线。
【输入描述】
第1行输入两个非零整数 M 和 N ，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。
接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:
1) ‘@’：少年李逍遥所在的位置；
2) ‘.’：可以安全通行的方格；
3) ‘#’：有怪物的方格；
4) ‘*’：仙药所在位置。
【输出描述】
求李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。
【样例输入】
8 8 .@##...# #....#.# #.#.##.. ..#.###. #.#...#. ..###.#. ...#.*.. .#...###
【样例输出】
10
【题解】小X玩游戏
【题目描述】
小X喜欢玩游戏。
这天，小X觉得传统的游戏都玩腻了，自己随手在草稿纸上画了一行N个格子作为棋盘， 制定了如下规则：格子从左到右依次编号为1到N，玩家初始位于格子1，初始前进方向为向右，游戏共进行M轮，第i轮玩家前进Ai格，若玩家到达格子N则改变前进方向为向左，若玩家到达格子1则改变前进方向为向右。
小X想知道玩家最后会停在哪个格子，但这个游戏太漫长了，他已经玩得快睡着了，希望你帮帮他。
【输入描述】
第一行包含用一个空格隔开的两个整数N,M。
接下来M行，第i行包含一个整数Ai。
【输出描述】
第一行包含一个整数，表示玩家最后停留的格子编号。
【样例输入】
3 2 2 3
【样例输出】
2
【提示】
样例说明
玩家的路线为 1->2->3->2->1->2。
【数据范围】
对于30%的数据，N=2，M≤10，Ai=1。
对于60%的数据，N≤1000，M≤1000，Ai≤1000。
对于 100%的数据，2≤N≤100000，1≤M≤100000，1≤Ai≤1000000000。
【题解】最短路径问题
【题目描述】
平面上有n个点（n≤100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
【输入描述】
共n+m+3行，其中:
第一行为整数n。
第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。
第n+2行为一个整数m，表示图中连线的个数。
此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。
【输出描述】
一行，一个实数（保留两位小数），表示从s到t的最短路径长度。
【样例输入】
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5
【样例输出】
3.41