目录

1.煤球数量；

2.生日蜡烛；

3.凑算式

4.方格填数

5.四平方和

6.交换瓶子

7.最大比例

---

1.煤球数量

题目解析：可以根据·题目的意思，找到规律。

1     *-  1个

2    ***   3个

3   ******  6个

4 ********** 10个

不难发现 第一层的个数加上第二层的层数就是第二层的煤球数目。本质就是找规律数学。

#include <iostream>
#include<vector>
using namespace std;int main()
{int n = 0, sum = 0;for(int i = 1; i <= 100; i++){n += i;sum += n;}cout << sum << endl;return 0;
}

2.生日蜡烛

题目解析：直接枚举就行；

#include<iostream>
using namespace std;
int main()
{for (int i = 1;i <= 100; i++){int sum = 0;for (int j = i; j <= 100; j++){sum += j;if (sum == 236)cout << i << endl;}}return 0;
}

3.凑算式

题目解析：是不是和三羊献瑞有点像，又可以使用next_premutation();

注意这个题目弄错了是1-9数字；md我就整整调试1个多小时，心态差点崩溃了，都开始怀疑自己了。

using namespace std;
#include<iostream>
#include<algorithm>int ret = 0;
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};bool check()
{int x = a[3] * 100 + a[4] * 10 + a[5];int y = a[6] * 100 + a[7] * 10 + a[8];if(((a[1] * y) + (a[2] * x)) % (a[2] * y) == 0 && a[0] + ((a[1] * y) + (a[2] * x)) / (a[2] * y) == 10){return true;}else{return false;}
}int main()
{do{if(check()){ret++;}}while(next_permutation(a, a + 9));cout << ret << endl;return 0;
}

4.方格填数

题目解析：动态规划类型题目，就是在方格中填数，如果这个方格没有被使用过并且方格相邻不重复就将数字填进去，填完就是一种方案数。累计方案数。

细节：初始化为-20，因为如果为填9就算相邻区分不出来。

#include <iostream>
#include<bits/stdc++.h>
using namespace std;//方格矩阵，因为要使用到相邻的元素所以就会使用到就多创建行列
// -20   -20  -20-20
//    +--+--+--+
//    |  |  |  | -20
// +--+--+--+--+
// |  |  |  |  | -20
// +--+--+--+--+
// |  |  |  |    -20
// +--+--+--+
//-20  -20 -20 -20 -20
int a[4][5];
//判断是否被使用过
int vis[10];
int sum = 0;
int dx[4] = {-1, -1, -1, 0};
int dy[4] = {0, 1, -1, -1};bool check(int x, int y, int num)
{for(int i = 0; i < 4; i++){int xx = dx[i] + x;int yy = dy[i] + y;//边界检查if(xx < 3 && xx >= 0 && yy < 4 && yy >= 0){//如果相邻的话那么相差一定为1；if(abs( a[xx][yy] - num ) == 1)return false;}}return true;
}void dfs(int x, int y)
{//出口：第二行第三列if(x == 2 &&  y == 3){sum++;return;}//开始填数for(int i = 0; i < 10; i++){//判断没被使用过的方格并且不相临if(vis[i] == 0 && check(x, y, i)){vis[i] = 1;a[x][y] = i;//递归下一个方格,或者下一行if(y + 1 < 4)dfs(x, y + 1);elsedfs(x + 1, 0);//回溯vis[i] = 0;}}
}int main()
{//矩阵初始for(int i = 0; i < 4; i++){for(int j = 0; j < 4; j++){a[i][j] = -20;}}//从第0行第一列开始；dfs(0,1);cout << sum << endl;return 0;
}

5.四平方和

题目解析：可以想到暴力枚举的方法，复杂度为0(n^4)是非常恐怖的，那么就要想办法降低；就需要优化。

首先要知道 N=  a*a + b*b + c*c + d*d;

那么 a 一定不会超过 N / 4; b 一定不会超过 N / 3; c 一定不会超过 N / 2;

d 一定不会超过 N; 

其次我们可以先算 a 和 b，那么 N - a*a + b*b = c*c + d*d;

#include <iostream>
#include<map>
#include<cmath>
using namespace std;int main()
{//输入int N; cin >> N;map<int,int> exit;//c值存一下。for(int c = 0; c * c <= N / 2; c++){for(int d = c; c*c + d*d <= N; d++){if(exit.find(c * c + d * d) == exit.end())exit[c * c + d * d] = c;}}for(int a  = 0; a * a <= N / 4; a++){for(int b = a; a*a + b*b <= N / 3; b++){if(exit.find(N - a * a - b * b) != exit.end()){int c = exit[N - a * a - b * b];int d = (int)sqrt(N - a*a - b*b - c*c);cout << a << b << c << d << endl;//找到直接返回return 0;}}}return 0;
}

6.交换瓶子

题目解析：是不是会想到冒泡，但是你看看数据范围，那么就是肯定要优化；将当前元素与下标进行比较，如果相同直接跳过，不相同那么就要找到和下标相同的数据下标进行交换。

#include<iostream>using namespace std;
int a[10001];
int N;
int sum = 0;int pos(int x)
{for(int i = 1; i <= N; i++){if(a[i] == x){return i;}}return -1;
}void Swap(int i, int j)
{int tmp = a[i];a[i] = a[j];a[j] = tmp;
}int main()
{//数据处理;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(pos(i), i);sum++;}}cout << sum << endl;return 0;
}

 7.最大比例

题目解析：本道题说到所有级别的奖金构成一个等比数列，先进行排序，将第一个数作为分母，分子分别都是后面的数，求取他们的最大公约数，再用两个数组将分子分母分别除以最大公约数，再存放起来。最后再对分子分母分别求差最小就会得到最终答案。

#include <iostream>
#include<algorithm>
using namespace std;#define N 100
long long max = 1000000000;
long long x[N], a[N], b[N];long long gcd(long long a, long long b)
{return b ? gcd(b, a % b) : a;
}long long gcd_sub(long long a, long long b)
{if(b == 1) return a;if(b > a)  swap(a, b);return gcd_sub(b, a / b);
}int main()
{//输入完成：int n;cin >> n;for(int i = 0; i < n; i++){cin >> x[i];}//排序sort(x, x + n);long long dd;//求最大公约数int cnt = 0;for(int i = 1; i < n; i++){if(x[i] != x[i-1]) //去除为1的情况{dd = gcd(x[i], x[0]);a[cnt] = x[i] / dd; //分子b[cnt] = x[0] / dd; //分母cnt++;}}long long up = a[0], down = b[0];for(int i = 1; i < cnt; i++){up = gcd_sub(up, a[i]);down = gcd_sub(down, b[i]);}cout << up << "/" << down;return 0;
}

其实静下心来感受会觉得题目不难，就是要找到规律，总结方法，写代码注意细节，那么绝对可以取得高分。