【题解】BFS—迷宫问题(1)
【题目描述】
一个5*5的矩阵，矩阵内用0，1显示。其中，0是路，表示这个点可以走，1是墙表示这个点不可以走。
问，从给定的矩阵中从左上角到右下角最少需要走多少步？
注：题目保证有解（不存在左上角和右下角为1的情况）
【输入描述】
一个5*5的矩阵
【输出描述】
一行，表示最少要走多少步？
【样例输入】
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
【样例输出】
8
【题解】BFS、DFS——走迷宫问题
【题目描述】
给定一个 n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。
数据保证 (1,1)处和 (n,m)处的数字为 0，且一定至少存在一条通路
【输入描述】
第一行包含两个整数 n 和 m。
接下来 n行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
【输出描述】
输出一个整数，表示从左上角移动至右下角的最少移动次数。
【样例输入】
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
【样例输出】
8
【数据范围】
1≤n,m≤100
【题解】求逆序对个数
【题目描述】
有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000)，若i<j，并且A[i]>A[j]，则称A[i]与A[j]构成了一个逆序对，求数列A中逆序对的个数。
例如，5 2 4 6 2 3 2 6，可以组成的逆序对有
（5 2），（5 4），（5 2），（5 3），（5 2），
（4 2），（4 3），（4 2），
（6 2），（6 3），（6 2），
（3 2）
共：12个
【输入描述】
共两行，第一行有一个正整数n，第二行有n个整数。
【输出描述】
只有一行为逆序对个数。
【样例输入】
8 5 2 4 6 2 3 2 6
【样例输出】
12
【题解】光荣的梦想
【题目描述】
Prince对他在这片大陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。在他动身之前，Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代，平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量，平衡瞬间即被打破。KB决定求助于你，帮助他完成这个梦想。
一串数列即表示一个世界的状态。
平衡是指这串数列以升序排列。而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。
【输入描述】
第一行为数列中数的个数n,第二行为n ≤ 10000个数。表示当前数列的状态。
【输出描述】
输出一个整数，表示最少需要交换几次能达到平衡状态。
【样例输入】
4 2 1 4 3
【样例输出】
2
【题解】黑白棋子移动
【题目描述】
有2n个棋子（n≥4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：○○○○○●●●●●
移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。
如n=5时，成为：○●○●○●○●○●
任务：编程打印出移动过程。
【输入描述】
输入n。
【输出描述】
移动过程。
【样例输入】
7
【样例输出】
step 0:ooooooo*******-- step 1:oooooo--******o* step 2:oooooo******--o* step 3:ooooo--*****o*o* step 4:ooooo*****--o*o* step 5:oooo--****o*o*o* step 6:oooo****--o*o*o* step 7:ooo--***o*o*o*o* step 8:ooo*o**--*o*o*o* step 9:o--*o**oo*o*o*o* step10:o*o*o*--o*o*o*o* step11:--o*o*o*o*o*o*o*
【题解】循环比赛日程表
【题目描述】
设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。
【输入描述】
输入：M。
【输出描述】
输出：表格形式的比赛安排表。一行各数据间用一个空格隔开。
【样例输入】
3
【样例输出】
1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1
【题解】字符串
【题解】数学游戏
【题目描述】
Kri 喜欢玩数字游戏。 一天，他在草稿纸上写下了t 对正整数(x,y) ，并对于每一对正整数计算出了z=x*y*gcd(x,y);可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 y都擦除了，还可能改动了一些 z。
现在 Kri 想请你帮忙还原每一组的 y，具体地，对于每一组中的 x和 z，你需要输出最小的正整数 y，使得 z=x*y*gcd(x,y) 。如果这样的 y不存在，也就是 Zay 一定改动了z ，那么请输出 -1。 注：gcd(x,y) 表示 x和 y的最大公约数，也就是最大的正整数 d，满足 既是x 的约数，又是 y的约数。
【输入描述】
第一行一个整数 t ，表示有 对正整数 x和z 。
接下来 t 行，每行两个正整数 x和z ，含义见题目描述。
【输出描述】
对于每对数字输出一行，如果不存在满足条件的正整数y ，请输出-1 ，否则输出满足条件的最小正整 数 y。
【样例输入1】
1 10 240
【样例输出1】
12
【样例1解释】
x*y*gcd(x,y)=10*12*gcd(10,12)=240
【样例输入2】
3 5 30 4 8 11 11
【样例输出2】
6 -1 1
【数据范围】
对于20%的数据，t,x,z<=103。
对于40%的数据，t<=103, x<106, z<=109。
对于另30% 的数据，t<104 。
对于另20% 的数据，x<106 。
对于100%的数据，1<=t<=5*105, 1<=x<=109, 1<=z<=263 。
【题解】王国比赛
【题目描述】
智慧之王 Kri 统治着一座王国。 这天 Kri 决定举行一场比赛，来检验自己大臣的智慧。 比赛由 n道判断题组成，有 m位大臣参加。现在你已经知道了所有大臣的答题情况，但尚未拿到答 案，于是你决定先行预测。 具体来说，对于第 i道题，有 x个大臣选对， y个大臣选错（显然有x+y=m ），如果x>y，那 么你预测这题答案为对，否则为错。为了方便，我们保证 m是奇数。 在统计完成后，你拿到了答案，你想知道通过你的预测方式你最后有几道题预测正确。
【输入描述】
第一行两个正整数 n,m，保证m 是奇数。 接下来 m行，每行n 个整数，第i 行第j个整数 aij代表第 i位大臣对第 j道题的答案， 1表示他选 对， 0表示他选错。 接下来1 行 n个整数， 表示比赛答案， 第i 个数 bi若为 1表示第i 道题答案是对，若为 0表示答案是 错。
【输出描述】
输出一个整数，表示你最后有几题预测正确。
【样例输入1】
3 3 1 0 1 0 1 1 0 1 0 1 1 1
【样例输出1】
2
【样例1解释】
第一题 你预测答案为错（即0），实际答案为1，预测错误。
第二题 你预测答案为对（即1），实际答案为1，预测正确。
第三题 你预测答案为对（即1），实际答案为1，预测正确。 所以预测正确的题数为2。
【样例2输入】
5 6 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0
【样例2输出】
4
【数据范围】
对于20%的数据，n<=5，m=1 。
对于50%的数据，n<=10，m<=10 。
对于100%的数据， n<=1000 , m<=1000，m为奇数 。
【题解】报数游戏
【题目描述】
路飞在和他朋友们一块玩一个游戏。由于路飞的机智，这个游戏由路飞担任裁判。
首先，路飞会给他们一个人一个编号，并且每个人的编号都不相同。接下来的每一个回合，会给一个数，编号不超过它的最大编号
的人要报出自己的编号。如果没有人的编号比路飞给出的数要小，那么编号最小的人要报出自己的编号。每个人可以重复报号。
路飞会按照一个列表顺次报出每个回合的数，他的朋友们想知道每回合报出的编号应该是多少？
【输入描述】
输入数据共3行。
第一行有两个整数n,m( 1<=n<=105 , 1<=m<=105 )，分别表示参与游戏的路飞朋友的个数和游戏回合数。
第二行n个整数 ai (1<=ai<=108) ，表示朋友们每个人的编号。对于 0<=i<j<n， 都有 ai<aj，即他们的编号递增排列。
第三行m个整数 qi(1 <= qi <=108), 表示每回合路飞给的数字。
【输出描述】
输出共一行m个整数，表示每回合报出的编号，每两个整数之间一个空格，最后一个数后面没有空格。
【样例输入】
5 5 1 5 10 15 20 3 6 12 18 24
【样例输出】
1 5 10 15 20