第1题 煤球数目
题目：
有一堆煤球，堆成三角棱锥形。具体：
第一层放1个，
第二层3个（排列成三角形），
第三层6个（排列成三角形），
第四层10个（排列成三角形），
….
如果一共有100层，共有多少个煤球？
请填表示煤球总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
分析：
根据下面的图，可以看出，煤球的堆叠是第1层1个，第2层1+2个，第3层1+2+3个……设煤球层数为n，那么第n层的每球数符合等差数列前n项和公式，如下图所示，则答案很明确了：
代码：
#include <iostream>
using namespace std;
int main()
{
long long sum = 0;
for (int i = 1; i <= 100; i++)
sum += (i * (1 + i)) / 2;
cout << sum;
return 0;
}
答案：171700
标签：简单计算、数学归纳
第2题 生日蜡烛
题目：
某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。
现在算起来，他一共吹熄了236根蜡烛。
请问，他从多少岁开始过生日party的？
请填写他开始过生日party的年龄数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
分析：
从某一年龄开始过生日的年龄为a，现在的年龄为b，那么直到吹熄236根，即由a到b的等差数列之和为236，可以通过遍历搜索的方式来求得答案中的a。
代码：
#include <iostream>
using namespace std;
int main()
{
for (int a = 1; a <= 100; a++)
{
for (int b = 1; b <= 100; b++)
{
if ((b - a + 1)*(a + b) / 2 == 236)
cout << a;
}
}
return 0;
}
答案：26
标签：遍历枚举
第3题 凑算式
题目：
这个算式中AI代表19的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。
分析：
这个题可以有三种解法，一种是暴力枚举，一种是DFS，一种是直接利用next_permutation()函数，三种方法的目的相同，都是求取1~9的全排列，并且9个数字不能重复，下面给出后两种方法的代码。
DFS代码：
#include <iostream>
using namespace std;
int ans = 0; //存放答案
double a[10]; //存放十个数字的全排列
int mark[10] = {0}; //记录10个数字是否被选中，防止重复
void dfs(int step)
{
if (step == 10)
{
if (a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]) == 10)
ans++; //找到一种答案
return;
}
for (int i = 1; i <= 9; i++) //遍历9个数，全排列的DFS套路
{
if (mark[i] == 0) //如果未被选中
{
a[step] = i; //加入序列
mark[i] = 1; //标记已经看过
dfs(step + 1); //继续探索
mark[i] = 0; //再恢复
}
//return;
}
}
int main()
{
dfs(1);
cout << ans <<endl;
return 0;
}
使用next_permutation()函数代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[]) {
int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
int sum = 0;
while (next_permutation(a + 1, a + 10))
{
int lala = a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]);
if (lala == 10)
sum++;
}
cout << sum;
return 0;
}
注意：必须变成浮点型的数才可以比较，否则结果不正确
答案：29
标签：暴力枚举、全排列
第4题 快速排序
题目：
排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
代码：
#include <stdio.h>
void swap(int a[], int i, int j) //简单的首尾相接交换函数
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r) //分割函数
{
int i = p;
int j = r + 1;
int x = a[p]; //取第一个作为pivot
while (1) {
while (i < r && a[++i] < x); //找到左边第一个大于pivot的
while (a[--j] > x);// 找到右边第一个小于pivot的
if (i >= j) break; //当j跑到i左边就结束
swap(a, i, j); //交换两者位置
}
//______________________;
swap(a, p, j);
return j;
}
void quicksort(int a[], int p, int r)
{
if (p < r) {
int q = partition(a, p, r); //分割函数，把大的放到右边，小的放在左边
quicksort(a, p, q - 1); //对左边递归排序
quicksort(a, q + 1, r); //对右边递归排序
}
}
int main()
{
int i;
int a[] = { 5,13,6,24,2,8,19,27,6,12,1,17 }; //定义一个数组，待排序
int N = 12; //元素数目
quicksort(a, 0, N - 1); //快速排序函数
for (i = 0; i < N; i++) printf("%d ", a[i]); //输出结果
printf("\n");
return 0;
}
分析：这类题目直接将代码复制粘贴到编译器中运行并作注释，一点点分析。分析过程在上面的代码中，其他填空题目都如此，分析过程略。
答案：swap(a, p, j)
标签：快速排序
第5题 抽签
题目：
X星球要派出一个5人组成的观察团前往W星。
其中：
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
….
那么最终派往W星的观察团会有多少种国别的不同组合呢？
下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为：
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
….
(以下省略，总共101行)
代码：
#include <stdio.h>
#include <iostream>
#define N 6
#define M 5
#define BUF 1024
using namespace std;
int cnt = 0;
void f(int a[], int k, int m, char b[])
{
int i, j;
if (k == N) {
b[M] = 0; //字符串结尾标志
if (m == 0) { printf("%s\n", b);cnt++;};
return;
}
for (i = 0; i <= a[k]; i++) { //循环第K个国家人数
for (j = 0; j < i; j++) b[M - m + j] = k + 'A'; //填充字符串b，几个人几个相同的国家标记k+'A'
//______________________; //填空位置
f(a, k + 1, m - i ,b); //继续探索下一个国家
}
}
int main()
{
int a[N] = { 4,2,2,1,1,3 };
char b[BUF]; //存放字符串
f(a, 0, M, b);
cout << cnt;
return 0;
}
答案：f(a, k + 1, m - i ,b)或者f(a,k+1,m-j,b)
标签：DFS、递归
第6题 方格填数
题目：
如图，如下的10个格子，填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）一共有多少种可能的填数方案？
请填写表示方案数目的整数。
第6题 方格填数
分析： 这题是一道结果填空，所以又可以用暴力递归来求解，建立一个数组，用next_permutation()函数来进行全排列，判断一下即可。注意对角线也不能一样。（这里有个想法，因为判断条件很多，可以把条件单独列出来，赋给bool变量，判断的时候就方便很多）
代码：
#include <iostream>
#include <algorithm>
using namespace std;
bool judge(int arr[])
{
bool j1, j2, j3, j4, j5, j6, j7, j8, j9;
j1 = (abs(arr[0] - arr[1])>1) && (abs(arr[0] - arr[3]) > 1) && (abs(arr[0] - arr[4]) > 1)&&(abs(arr[0] - arr[5]) > 1);
j2 = (abs(arr[1] - arr[2]) > 1) && (abs(arr[1] - arr[4]) > 1) && (abs(arr[1] - arr[5]) > 1) && (abs(arr[1] - arr[6]) > 1) ;
j3 = (abs(arr[2] - arr[5]) > 1) && (abs(arr[2] - arr[6]) > 1);
j4 = (abs(arr[3] - arr[4]) > 1) && (abs(arr[3] - arr[7]) > 1) && (abs(arr[3] - arr[8]) > 1);
j5 = (abs(arr[4] - arr[5]) > 1) && (abs(arr[4] - arr[7]) > 1) && (abs(arr[4] - arr[8]) > 1) && (abs(arr[4] - arr[9]) > 1);
j6 = (abs(arr[5] - arr[6]) > 1) && (abs(arr[5] - arr[8]) > 1) && (abs(arr[5] - arr[9]) > 1);
j7 = (abs(arr[6] - arr[9]) > 1);
j8 = abs(arr[7] - arr[8]) > 1;
j9 = abs(arr[8] - arr[9]) > 1;
if (j1&&j2&&j3&&j4&&j5&&j6&&j7&&j8&&j9)
return true;
else
return false;
}
int main()
{
int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //放数字的数组
int ans = 0;
while (next_permutation(arr, arr + 10))
{
if (judge(arr))
ans++;
}
cout << ans;
return 0;
}
答案：1580
标签：搜索、全排列
第7题 剪邮票
题目：
如图1, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，图2，图3中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
图1
图2
图3
分析：这里用到一个技巧，设定了一个数组a[]，其中有5个1，那么这个数组的每一个全排列就代表一种情况。check()函数将全排列的结果存入二维数组中，dfs()对每个格子进行深度优先遍历，如果遍历联通，就把数组相应位置置为0，每次遍历一个连通块就计次数，计数超过一标明块不连续。
补充：手动写全排列的框架函数如下：
#include <iostream>
using namespace std;
void f(int arr[], int k, int n)
{
if (k == n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
cout << '\n';
return;
}
for (int i = k + 1; i < n; i++)
{
int t = arr[i]; arr[i] = arr[k]; arr[k] = t;
f(arr, k + 1, n);
t = arr[i]; arr[i] = arr[k]; arr[k] = t;
}
}
int main()
{
int a[] = { 1, 2, 3};
f(a, 0, 3);
return 0;
}
由于本题解决方法很多，这里只给出思路，不给出解题过程。
答案：116
标签：全排列、联通问题
第8题 四平方定理
题目：
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法
分析：可以枚举a b c d，0<=a²<=N/4，0<=b²<=N/3，0<=c²<=N/2，0<=d²<=N/1。可以得到一部分分数。但是枚举数量过大，需要剪枝。这里用到了map映射数据结构，通过把c²+d²映射到字典里，可以直接查找到，不用遍历c和d从而减小复杂度，减少循环时间。如果在其中找到对应的c，直接可以算出d。然后满足要求之后直接输出即可，因为结果已经满足升序排列。
代码：
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
int main()
{
map<int, int> catche;
int n;
cin >> n;
for (int c = 0; c*c <= n / 2; c++)
{
for (int d = c; c*c + d * d <= n; d++) //这里的范围可以试着改变一下
{
catche[c*c + d * d] = c; //映射较小的值，另一个数可以算出
}
}
for (int a = 0; a*a <= n / 4; a++)
{
for (int b = a; a*a + b * b <= n / 2; b++)
{
if (catche.find(n - a * a - b * b) != catche.end()) //如果找到映射
{
int c = catche[n - a * a - b * b]; //取出c
int d = (int)sqrt(n - a * a - b * b - c * c); //计算d
cout << a << " " << b << " " << c << " " << d << endl; //输出结果
return 0;
}
}
}
return 0;
}
标签：暴力枚举、优化
第9题：交换瓶子
题目：
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：
2 1 3 5 4
要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入格式为:
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
分析：其实，我认为这个题就是找逆序对，全部搜索即可。但是还有一种方法“归位”，不在位置上就交换，可以较高效地排序。
代码：
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
int a[10001];
int pos(int num, int n)
{
for (int i = 1; i <= n; i++)
{
if (a[i] == num)
return i;
}
return -1;
}
void swap(int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int main()
{
int n; //瓶子数
int ans = 0; //答案数
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i]; //输入瓶子位置
for (int i = 1; i <= n; i++)
{
if (a[i] == i)
continue;
else {
swap(i, pos(a[i], n));
ans++;
}
}
cout << ans;
return 0;
}
标签：暴力枚举、逆序数
第10题：最大比例
题目：
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且，相邻的两个级别间的比例是个固定值。
也就是说：所有级别的奖金数构成了一个等比数列。比如：
16,24,36,54
其等比值为：3/2
现在，我们随机调查了一些获奖者的奖金数。请你据此推算可能的最大的等比值。输入格式：
第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额
要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数
测试数据保证了输入格式正确，并且最大比例是存在的。
例如，输入：
3
1250 200 32程序应该输出：
25/4
再例如，输入：
4
3125 32 32 200
程序应该输出：
5/2
再例如，输入：
3
549755813888 524288 2
程序应该输出：
4/1
分析：这里新学到了一种算法，当知道两个数 x,y。 x=p^i y=p^j 那么我们怎么求这个p呢？ 下面介绍一种类似辗转相除法的算法，做这题这个是关键。
我们假设这个最大的公比是q=（q1/q2）（q1,q2均为正整数且互质）
我们将这个序列按照升序排列之后,a1,a2,a3......an,可以得出a2/a1=q1x1/q2x1, a3/a2=q1x2/q2x2......由于这个q一定是存在的，所以现在的问题就是分别找到分子和分母，既然前提假设了q是确定的，那么q1,q2也一定是确定的，要想从 q1x1,q1x2,......q1xn中找到q1,我们可以利用类似于求gcd的辗转相除法，我们将所有的ai/ai-1进行约分确立分子和分母，然后分别对所有的分子和分母进行辗转相除，最后约分输出就好了。还要注意的一点就是一定要对数组去重= =，不然会认为存在一个qx==1。
代码：
#include <iostream>
#include <algorithm>
#include "Year_2013_7.h"
using namespace std;
long long qgcd(long long a, long long b)
{
if (a == b) return a;
else
{
return qgcd(min(b / a, a), max(b / a, a));
}
}
long long gcd(long long a, long long b)
{
return b ? gcd(b, a%b) : a;
}
int main()
{
long long a[101], b[101], x[101], n, N;
cin >> n; //输入数字个数
for (int i = 1; i <= n; i++)
cin >> x[i]; //输入数字内容
sort(x + 1, x + 1 + n); //对数字进行排序
for (int i = 2; i <= n; i++) //去重
{
if (x[i] == x[i - 1]) {
for (int j = i; j <= n; j++)
x[j - 1] = x[j];
n--;
}
}
for (int i = 2; i <= n; i++)//存储所有的相邻数字的比例
{
a[i] = x[i];
b[i] = x[i - 1];
int p = gcd(x[i], x[i - 1]);
a[i] /= p;
b[i] /= p;
}
int A = a[2], B = b[2];
for (int i = 3; i <= n; i++)
{
A = qgcd(A, a[i]);
B = qgcd(B, b[i]);
}
cout << A <<" "<< B;
return 0;
}
