intmain() { double a, b, c, p, ans; cin >> a >> b >> c; p = (a + b + c) / 2; ans = sqrt(p * (p - a) * (p - b) * (p - c)); //开平方根 cout << fixed << setprecision(1) << ans;
intmain() { double a, b, c, d, e, f; cin >> a >> b >> c >> d; if (b > d) { e = c - a - 1; f = 60 + d - b; } else { e = c - a; f = d - b; } cout << e <<" " << f; return0; }
intmain() { int a, b, c; cin >> a >> b >> c; if (a < b) { if (b < c) cout << a << " " << b << " " << c; elseif(a < c) cout << a << " " << c << " " << b; else cout << c << " " << a << " " << b; } elseif (a > b) { if (b > c) cout << c << " " << b << " " << a; elseif(c > a) cout << b << " " << a << " " << c; else cout << b << " " << c << " " << a; } else { if(b > c) cout << c << " " << b << " " << a; else cout << b << " " << a << " " << c; } return0; }
intmain() { int a, b, max = 8, q = 0; for (int i = 1; i < 8; i++) { cin >> a >> b; if ((a + b) > max)//神之一手 { max = a + b;//锁住最大值 q = i; } } cout << q; return0; }
该题看着不难，却有几个条件限制住无法AC。
一开始我以为必须输入完7行后再进行输出判断，但后来才意识到输入区和输出区是独立开来的。
然后本题的神之一手就是max变量的使用，牢牢锁住最大值，让我受益颇丰！！！
P1909 买铅笔（重要）
题目描述：
P 老师需要去商店买 $n$ 支铅笔作为小朋友们参加 NOIP 的礼物。她发现商店一共有 $3$ 种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起见，P 老师决定只买同一种包装的铅笔。
商店不允许将铅笔的包装拆开，因此 P 老师可能需要购买超过 $n$ 支铅笔才够给小朋友们发礼物。
现在 P 老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 $n$ 支铅笔最少需要花费多少钱。
intgcd(int a, int b); intmain() { int a[3]; cin >> a[0] >> a[1] >> a[2]; sort(a, a + 3); int max = a[2]; int min = a[0]; int t = gcd(max,min); cout << min/t << "/" << max/t; return0; }
intgcd(int a, int b)//求两个数的最大公约数 { int temp; while (b > 0)//辗转相除法 { temp = a % b; a = b; b = temp; } return a; }
intmain() { int m[3]; for (int i = 0; i < 3; i++)//输入三角形的三边 { cin >> m[i]; } sort(m, m + 3);//对三边从小到大排序 int a = m[0], b = m[1], c = m[2];//赋值给a,b,c
if ((a + b) > c && ((b - a) < c || (c - a) < b || (c - b) < a))//可以构成三角形 { if (a * a + b * b == c * c) cout << "Right triangle" << endl; if (a * a + b * b > c * c) cout << "Acute triangle" << endl; if (a * a + b * b < c * c) cout << "Obtuse triangle" << endl; if (a == b||b == c) cout << "Isosceles triangle" << endl; if (a == c) cout << "Equilateral triangle" << endl; } else cout << "Not triangle";
return0; }
该题不难，主要就是用好数组和sort()排序函数。
if条件不可以出现a == b == c这种连等，会先计算 a == b，它会返回 true 或 false（即 1 或 0），然后再将这个值与 c 进行比较。这样会导致逻辑错误。
intmain() { int n, a = 1; cin >> n; for (int i = n; i > 0; i--) { for (int m = i; m > 0; m--) { cout << setw(2) << setfill('0') << a;//不足两位自动补0 ++a; } cout << endl; } return0; }
intmain() { int n, x; stringstream ss; cin >> n >> x; for (int i = 1; i < n+1; i++) { ss << i; } string s = ss.str(); cout << count(s.begin(), s.end(), x + '0') << endl;//整数加字符0可转化为对应的整数字符 return0; }
intmain() { int N; cin >> N; if (N >= 0) { string n = to_string(N);//整数——>字符串 reverse(n.begin(), n.end());//逆置 int m = stoi(n);//字符串——>整数 cout << m; } else { string n = to_string(N).substr(1);//去掉负号 reverse(n.begin(), n.end()); int m = stoi(n); cout << "-" << m; } return0; }
数据保证，$1 \leq M \leq N \leq 2 \times 10^9$，$N-M \leq 5 \times 10^5$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#include<bits/stdc++.h> usingnamespace std;
intmain() { int M, N; cin >> M >> N; stringstream ss;//字符串流对象 for (int i = M; i <= N; i++) { ss << i; } string s = ss.str(); for (int i = 0; i <= 9; i++) { cout << count(s.begin(), s.end(), i + '0') << " ";//数某个数字出现过的次数 } return0; }
intmain() { int N,now; cin >> N; int flag = N * N;//用来计数 int t = 0; while (flag) { cin >> now;//输入当前要输入t的个数 for (int j = 0; j < now; j++) { cout << t; --flag;//每输出一个数字，flag减一 if (flag % N == 0) cout << endl;//每行达到N个数字时，换行。 } if (t == 0) t = 1;//0、1切换 else t = 0; } return0; }
intmain() { int n, m, sum = 0; cin >> n >> m; int* a = newint[n];//存放输入的正整数 int* b = newint[n - m + 1];//存放连续三个正整数的和 for (int i = 0; i < n; i++)//输入n个正整数刺痛值 { cin >> a[i]; } for (int i = 0; i < n - m + 1; i++)//从第一个整数开始连续数3个 { for (int j = 0; j < m; j++)//防止i+j越界 { sum = sum + a[i + j]; } b[i] = sum; sum = 0; } sort(b, b + (n - m + 1)); cout << b[0]; delete[] a; // 释放动态分配的内存 delete[] b; return0; }
boolisPrime(int x)// 判断是否为质数 { if (x < 2) return0; for (int i = 2; i <= sqrt(x); i++) { if (x % i == 0) return0; } return1; }
intmain() { int N; cin >> N; // 输入正偶数 N
// 遍历从 4 到 N 的所有偶数 for (int m = 4; m <= N; m += 2) { // 遍历所有可能的质数对 for (int i = 2; i <= m / 2; i++)//核心 { //i从小到大 if (isPrime(i) && isPrime(m - i)) // 检查 i 和 m-i 是否都是质数 { cout << m << "=" << i << "+" << m - i << endl; // 输出结果 break; // 找到第一个满足条件的质数对后退出循环 } } } return0; }
该题问了AI，它真的好强。。。
for (int i = 2; i <= m / 2; i++)中的i <= m / 2是因为前面的质数要小于等于后面的质数，如i <= m - i 。
int a[10], n; intmain() { cin >> n; for (int i = 1; i <= n; i++) { a[i] = i; } do { for (int i = 1; i <= n; i++) { cout << setw(5) << a[i]; } cout << endl; } while (next_permutation(a + 1, a + n + 1));
return0; }
全排列问题，使用next_permutation()函数。
next_permutation 的作用是：
将序列更改为字典序中的下一个排列。
如果当前序列已经是字典序中的最后一个排列，则将其重置为第一个排列，并返回 false。
注意场宽为5使用setw()函数。
【算法1-4】递推与递归
P1255 数楼梯
题目描述
楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
输入 #1
1
4
输出 #1
1
5
说明/提示
对于 $60%$ 的数据，$N \leq 50$；
对于 $100%$ 的数据，$1 \le N \leq 5000$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
#include<bits/stdc++.h> usingnamespace std;
intmain() { int a[27],n; cin >> n; a[1] = 1;//初始条件 a[2] = 2; for (int i = 3; i <= n; i++) { a[i] = a[i - 1] + a[i - 2];//递推公式 } cout << a[n]; return0; }
boolcmp(coin x, coin y){ return x.v * y.m > y.v * x.m;//判断单价，避免浮点数运算 } intmain() { int N, T, i; double ans = 0; cin >> N >> T; for ( i = 0; i < N; i++) cin >> a[i].m >> a[i].v; sort(a, a + N, cmp);//对单价排序 for ( i = 0; i < N; i++) { if (a[i].m > T) break; T -= a[i].m;//背包的剩余重量 ans += a[i].v; }
if (i < N) ans += 1.0 * T / a[i].m * a[i].v;//剩余空间装下部分金币（切割） cout << setprecision(2)<< fixed <<ans;//保证答案是两位小数 return0; }
int n, m, q, a[1000010]; intfind(int x){ int l = 1, r = n; while (l <= r) { int mid = (l + r) / 2;//找到中间值 if (a[mid] == x) return mid;//刚好是中间值 elseif (a[mid] > x) r = mid - 1;//缩小半区 else l = mid + 1; } return-1;//找不到 } intmain() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i];//给定n个数 for (int i = 0; i < m; i++)//查询m次 { cin >> q;//要查找的数 cout << find(q)<<" "; } return0; }
int n, m, q, a[1000010]; intfind(int x){ int l = 1, r = n; int result = -1; while (l <= r) { int mid = (r + l) / 2;//找到中间值 if (a[mid] == x) { result = mid;//刚好是中间值 r = mid - 1;//继续向左查找 } elseif (a[mid] > x) r = mid - 1;//缩小半区 else l = mid + 1; } return result;//找不到 } intmain() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i];//给定n个数 for (int i = 0; i < m; i++)//查询m次 { cin >> q;//要查找的数 cout << find(q)<<" "; } return0; }
int n, m, tmp; intmain() { vector<int> stu;//建立一个一维的可变数组 cin >> n >> m; for (int i = 0; i < n; i++) { cin >> tmp; stu.push_back(tmp);//将学生的学号依次加入到数组中 } for (int i = 0; i < m; i++) { cin >> tmp;//输入要查找的学生序号，注意最先进入教室的学生是stu[0]; cout << stu[tmp - 1] << endl; } return0; }
intmain() { cin >> n >> m; for (int i = 1; i <= n; i++) q.push(i);//n个小朋友依次放入队列 while (q.size() != 0) { for (int i = 1; i < m; i++) { q.push(q.front());//将队首元素复制，加入到队尾 q.pop();//队首元素出队 } cout << q.front()<<" ";//数到m的小朋友出队，不再入队 q.pop(); } return0; }
int n, m, p, x, y; int fa[MAXN];//并查集的父节点数组，fa[i] 表示第 i 个人的父节点。 intfind(int x)//查询是否是同一个集合 { if (x == fa[x]) return x; returnfind(fa[x]);//这里挺关键的，一直指向根节点 } voidjoin(int a, int b)//将a和b加入集合，并把a的代表换为b { int f1 = find(a), f2 = find(b);//寻找a和b的代表 if (f1 != f2) fa[f1] = f2;//如果代表不相同，说明a和b不在同一个集合中 } intmain() { cin >> n >> m >> p; for (int i = 1; i <= n; i++) fa[i] = i;//初始化：将每个人的父节点设为自己。 for (int i = 0; i < m; i++) { cin >> x >> y; join(x, y); } for (int i = 0; i < p; i++) { cin >> x >> y; if (find(x) == find(y)) cout << "Yes" << endl; else cout << "No" << endl; } return0; }
本题使用并查集。
注意：find函数
查找 x 所属集合的 根节点（即集合的代表）。
在查找过程中，进行 路径压缩，将路径上的所有节点直接指向根节点，优化后续查询效率。
【数据结构1-4】图的基本应用
P5318 查找文献
题目描述
小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。
假设洛谷博客里面一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$）以及 $m(m\le10^6)$ 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
#include<bits/stdc++.h> usingnamespace std; #define MAXN 100050 int n, m; vector<int> p[MAXN]; bool u[MAXN];//记录文献是否已被阅读，u[x] 为 true 表示文献 x 已被阅读。 queue<int> q;
voiddfs(int x)//深度优先搜索（DFS）遍历文献 { cout << x << " ";//此时输出的就是小K看文献的顺序 for(int i=0,sz=p[x].size();i<sz;i++) if (!u[p[x][i]]) { u[p[x][i]] = true; dfs(p[x][i]); } }
intmain() { cin >> n >> m; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; p[x].push_back(y);//用邻接表记录下文章x有参考文献y } // 对邻接表排序，确保优先访问编号较小的文献 for (int i = 1; i <= n; i++) { sort(p[i].begin(), p[i].end()); } //DFS u[1] = true; dfs(1); cout << endl;
memset(u, 0, sizeof(u)); u[1] = true; q.push(1); //广度优先搜索（BFS）遍历文献 while (!q.empty())//如果队列不为空 { int x = q.front();//队首赋值给x q.pop();//始终都是队首出队 cout << x << " "; for(int i=0,sz=p[x].size();i<sz;i++) if (!u[p[x][i]]) { u[p[x][i]] = true; q.push(p[x][i]); } } return0; }
#include<bits/stdc++.h> usingnamespace std; #define MAXN 100050 int n, m; vector<int> p[MAXN];//存放邻接表 int a[MAXN];//存放每个顶点的A值
voiddfs(int x, int y)//深搜 { if (a[x]) return;//如果该点被访问过，返回，不再进行深搜 a[x] = y;//将点x的A值更新为y，最开始是自己 for (int i = 0; i < p[x].size(); i++) { dfs(p[x][i], y); } }
intmain() { cin >> n >> m;//输入n个点，m个边关系 for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; p[v].push_back(u);//建反向边 } for (int i = n; i >= 1; i--)// 从大到小遍历每个点 { dfs(i, i); } for (int i = 1; i <= n; i++)//输出每个顶点的A值 cout << a[i] << " "; return0; }
本题为了降低时间复杂度，选择反向建边，从最大值点开始dfs。
从编号最大的点开始，依次遍历每个点。
对于每个点 u，如果它没有被访问过，则进行一次 DFS。
每次 DFS 的时间复杂度是 O(N+M)。
【算法2-2】常见优化技巧
P1102 A-B 数对（双指针）
题目描述
给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 $N,C$。
第二行，$N$ 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。
输入 #1
1 2
4 1 1 123
输出 #1
1
3
说明/提示
对于 $75%$ 的数据，$1 \leq N \leq 2000$。
对于 $100%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。
#include<bits/stdc++.h> usingnamespace std; #define MAXN 200010 int s[MAXN];
intmain() { int n, c; cin >> n >> c; for (int i = 0; i < n; i++) cin >> s[i]; sort(s, s + n);
int l = 0, r = 0; longlong sum = 0; for (int i = 0; i < n; i++) { while (s[l] < s[i] - c && l < n) l++; while (s[r] <= s[i] - c && r < n) r++; if (s[i] - s[l] == c) { sum += r - l; } } cout << sum; return0; }
intmain() { int n, a, f = 0, ans = -10000; cin >> n; for (int i = 0; i < n; i++) { cin >> a; f = max(f + a, a);//核心，动态规划 ans = max(f, ans); } cout << ans; return0; }
#include<bits/stdc++.h> usingnamespace std; int t[610], n, w; intmain() { int tmp; cin >> n >> w; for (int i = 1; i <= n; i++) { cin >> tmp; t[tmp]++;//加入对应分数的桶中 int sum = 0;//累加人数 for (int j = 600; j >= 0; j--) { sum += t[j]; if (sum >= max(1, i * w / 100))//满足获奖人数时 { cout << j << " ";//输出获奖的最后一名的成绩 break; } } } return0; }
#include<bits/stdc++.h>//万能头文件 using namespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 1e5 +10; int a[N],d[N]; int n, p, q; int l, r, x; int sum = 0; signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n >> p >> q; for (int i = 1; i <= n; i++)//下标从1开始 { cin >> a[i]; } d[1] = a[1]; for (int i = 2; i <= n; i++)//构建一维差分数组 { d[i] = a[i] - a[i - 1]; }
for (int i = 0; i < p; i++)//区间加 { cin >> l >> r >> x; d[l] += x; d[r + 1] -= x; } for (int i = 1; i <= n; i++)//恢复a数组 { a[i] = a[i - 1] + d[i]; } for (int i = 0; i < q; i++) { cin >> l >> r; for (int i = l; i <= r; i++) { sum += a[i]; } cout << sum << endl; sum = 0;//重置 } return0; }
#include<bits/stdc++.h>//万能头文件 using namespace std;
intmain() { int k; cin >> k; int ans = 0; if (k == 1 || k == 2) { cout << 1; return0; } int a = 1, b = 1; for (int i = 3; i <= k; i++) { ans = a + b; a = b; b = ans; } cout << ans;
#include<bits/stdc++.h>//万能头文件 using namespace std;
int a, b; int day = 1; intmain() { cin >> a >> b; for (int i = 1; i <= b; i++) { day *= a; day %= 1000;//每次循环都要进行%取余运算，不然会造成数据溢出 } cout <<setw(3)<<setfill('0') << day;
#include<bits/stdc++.h>//万能头文件 using namespace std;
int a, b, n, x = 0; intmain() { cin >> a >> b >> n; for (int i = 0; i < n; i++) { x = a * 10 / b;//取当前位 a = a * 10 % b;//得到剩下的余数 } cout << x; return0; }
#include<bits/stdc++.h>//万能头文件 using namespace std;
int m, n; int a = 0, b = 0; intmain() { cin >> m >> n; int max = m; if (n > m) max = n;
//最大公约数 //我们从较大的那一个值开始枚举 //当可以同时整除n和m的时候，即目标所求 for (int i = max; i >= 1; i--) { if (m % i == 0 && n % i == 0) { a = i; break;//求最大公约数，找到即最大，立刻跳出 } }
//最小公倍数 //最小公倍数,两个数的成绩一定是这两个数的公倍数 //我们假设当前公倍数就是最小公倍数，我们从这个位置开始往前枚举，如果存在别的公倍数，那么就更新 for (int i = m * n; i >= 1; i--) { if (i % m == 0 && i % n == 0) { b = i;//求最小公倍数，一直向下找，不需要跳出 } }
cout << a << " " << b; return0; }
无需STL函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#include<bits/stdc++.h>//万能头文件 using namespace std; int m, n; int a = 0, b = 0; intmain() { cin >> m >> n; a = gcd(m, n);//C++17 b = lcm(m, n);//C++20
#include<bits/stdc++.h>//万能头文件 using namespace std; vector<int> p; int n = 0, t = 0; voidprim_10000()//求出10000以内所有的质数 { int flag = 0; for (int i = 2; i <= 10000; i++) { flag = 0;//重置 for (int j = 2; j <= sqrt(i); j++) { if (i % j == 0) { flag = 1; break; } } if (flag == 0) p.push_back(i); } }
intmain() { int a, b; cin >> a >> b;
prim_10000(); for (int i = a; i <= b; i++) { t = i; cout << t << "="; for (int j = 0; j < p.size(); j++)//用存好的质数轮流检查 { if (t % p[j] == 0) { t /= p[j]; if (t != 1) cout << p[j] << "*"; else { cout << p[j] << endl;//分解完了 break; } j--;//继续检查刚刚的p[j] } } } return0; }
#include<bits/stdc++.h>//万能头文件 using namespace std; double x; int n; double sum = 0; doublefunc(double a, int n)//计算整数幂 { double sum = 1.0; for (int i = 0; i < n; i++) { sum *= a; } return sum; } intmain() { cin >> x >> n; double t = 0; for (int i = 0; i <= n; i++) { t = func(x, i); sum += t; } cout << setprecision(2) << fixed << sum; return0; }
constint N = 1e4 + 10; int n; map<int, vector<int>> st; int sum = 0; voidfunc(int x)//分解因数 { for (int i = 1; i <= x / 2; i++)//x/2即可 { if (x % i == 0) st[x].push_back(i); } } intmain() { cin >> n; for (int i = 2; i <= n; i++)//分解n以内每个数的因数 { func(i); } for (int i = 2; i <= n; i++) { for (int num : st[i])//对每个st[i]中的元素进行累加 { sum += num; } if (i == sum)//判断 { cout << i << " " <<"its factors are" << " "; for (int num : st[i]) cout << num << " "; cout << endl; } sum = 0;//重置 } return0; }
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
int s[10] = { 13,1,2,3,5,4,4,2,2,2 };//存储每个汉字的笔画数 int y = 2000, m = 1, d = 1;//初始化日期为第一天 int sum = 0, ans = 0; signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
while (1) { if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) {//大月31天 if (d > 31) { m++; d = 1; } } elseif (m == 2) { if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) //闰年,2月多一天是29天 { if (d > 29) { m++; d = 1; } } else { if (d > 28) { m++; d = 1; } } } else {//小月30天 if (d > 30) { m++; d = 1; } }
if (m > 12) { y++; m = 1; }
sum = 0; //计算每一个数字的笔画数，年、月、日 sum += s[y % 10] + s[y / 10 % 10] + s[y / 100 % 10] + s[y / 1000 % 10]; sum += s[m % 10] + s[m / 10];//2月表示为02 sum += s[d % 10] + s[d / 10];//2日表示为02 if (sum > 50) ans++;
if (y == 2024 && m == 4 && d == 13)//停止枚举 break;
d++; } cout << ans; return0; }
枚举每一天，依次进行判断。核心是区分好大月、小月和2月。
题目 3215: 训练士兵（模拟）
题目描述
在蓝桥王国中，有 n 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 i 名士兵来说，进行一次训练所需的成本为 pi 枚金币，而要想成为顶尖战士，他至少需要进行 ci 次训练。
为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 S 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。
作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵都成为顶尖战士？
输入格式
输入的第一行包含两个整数 n 和 S ，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。接下来的 n 行，每行包含两个整数 pi 和 ci ，用一个空格分隔，表示第 i 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 1e5 + 10; int n, k, T; int a[N], b[N]; double avg = 0, v = 0;//avg表示k个成绩的均值，v表示与均值差距最大的数 int dex = 0;//存放k个数中与均值差距最大的数的下标 boolcalculate(){//计算k个成绩的方差并验证 double sum = 0;//最终的方差 avg = 0;//计算均值 for (int i = 1; i <= k; i++) { avg += b[i]; } avg /= k;//更新avg
for (int i = 1; i <= k; i++) { sum += (b[i] - avg) * (b[i] - avg); } sum /= k; if (sum < T) return1; else return0; }
signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0); cin >> n >> k >> T; //这里不判断的话将少一半分数 if (n < k)//如果n小于k就不需要考虑了，直接输出-1，结束程序 { cout << -1; return0; }
for (int i = 1; i <= n; i++)//存入每个同学的成绩 { cin >> a[i]; if (i <= k) {//先将前k个成绩存入b数组中 b[i] = a[i]; avg += b[i]; } } avg /= 10;
if (calculate()) {//如果前k个成绩的方差已经小于T了，直接输出下标并结束程序 cout << k; return0; }
v = b[1];//令其先等于第一个数 dex = 1; for (int i = 2; i <= k; i++) {//找出k个数中与均值差距最大的数 if (abs(b[i] - avg) > abs(v - avg)) { v = b[i]; dex = i;//存放该数的下标 } }
for (int i = k + 1; i <= n; i++) { if (abs(a[i] - avg) < abs(v - avg)) {//往后找一个与均值差距较小的 b[dex] = a[i];//替换 if (calculate()) {//再次计算方差 cout << i; return0; } else {//如果方差还是不小于T，在新的k个成绩中再次找到一个与均值差距最大的数 v = b[1];//令其先等于第一个数 dex = 1; for (int j = 2; j <= k; j++) {//在数组b中找出k个数中与均值差距最大的数 if (abs(b[j] - avg) > abs(v - avg)) { v = b[j]; dex = j;//存放该数的下标 } } } } } cout << -1;//遍历完全部成绩，依然没有找到 return0;//必须要写 }
根据题意模拟，思路挺清晰的。
题目 3216: 团建（DFS+哈希表）
题目描述
小蓝正在和朋友们团建，有一个游戏项目需要两人合作，两个人分别拿到一棵大小为 n 和 m 的树，树上的每个结点上有一个正整数权值。
cin >> n >> m; for (int i = 1; i <= n; i++) {//存入节点的权值 cin >> a[i];//A树 } for (int i = 1; i <= m; i++) { cin >> b[i];//B树 } for (int i = 1; i < n; i++) {//构建邻接表 int x, y; cin >> x >> y; c[x].push_back(y);//A树 c[y].push_back(x); } for (int i = 1; i < m; i++) { int x, y; cin >> x >> y; d[x].push_back(y);//B树 d[y].push_back(x); } if (a[1] == b[1]) dfs(1,1,1,0,0); else cout << 0; cout << ans; return0;//必须要写 }
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 1e7 + 10; int n; int ans = 0; signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n; for (int i = 1; i <= n; i++) { int t = i; string s = to_string(i);//转换为字符串，方便统计该数的总位数 int q = 0; int flag = 1;//用来标记现在进行到第几位 while (t != 0) { q = t % 10;//逐位取 t /= 10; if (flag % 2 != 0 && q % 2 != 0)//奇数位上的数字是奇数 { flag++; continue; } elseif (flag % 2 == 0 && q % 2 == 0)//偶数位上的数字是偶数 { flag++; continue; } else { break;//若都不满足，直接跳出，考虑下一个数 } } if (--flag == s.size())//如果成功遍历完，那就说明这个数是好数 ans++; flag = 0;//重置
} cout << ans; return0;//必须要写 }
MyAns
直接暴力即可，对每个数逐位判断。
不会超时的理由：
虽然 O(n log n) 在 N = 10^7 时理论上会有 7 × 10^7 次操作，
但由于整数运算高效、输入优化以及编译器优化，程序运行时间仍然在 1 秒以内，因此不会超时。
2024年第十五届蓝桥杯大赛软件类省赛C/C++大学C组真题
试题A: 拼正方形（本题总分：5 分）
【问题描述】
小蓝正在玩拼图游戏，他有7385137888721 个2 x 2 的方块和10470245 个1 x 1 的方块，他需要从中挑出一些来拼出一个正方形，比如用3 个2 x 2 和4个1 x 1 的方块可以拼出一个4 x 4 的正方形，用9 个2 x 2 的方块可以拼出一个6 x 6 的正方形，请问小蓝能拼成的最大的正方形的边长为多少。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 2e5 + 10; int st[10]; int n; int num[N];
boolcmp(int a, int b)//自定义排序规则 { int x = a, y = b;//避免改变形参的值 int sum1 = 0, sum2 = 0; while (x != 0) { int t = x % 10;//取每个位 x /= 10; sum1 += st[t];//逐位计算 } while (y != 0) { int t = y % 10;// 取每个位 y /= 10; sum2 += st[t];//逐位计算 } //返回规则 if (sum1 == sum2)//记得是两个等号 { return a < b; } return sum1 < sum2; } signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 3e5 + 10; int n, m; int a[N], d[N], p[N]; typedef pair<int, int> pii; vector<pii> st; signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n >> m; st.resize(m + 1); // 预分配空间，防止 st[i] 访问越界 for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; st[i] = {l, r};
d[l]++;//差分数组 d[r + 1]--; }
int sum = 0; for (int i = 1; i <= n; i++)//恢复原数组 { a[i] = a[i - 1] + d[i]; if (a[i] == 0)//统计商品为0的种类数 sum++; } for (int i = 1; i <= n; i++)//构造前缀和数组，用于存放前i个数里，1的个数 { p[i] = p[i - 1] + (a[i] == 1); }
for (int i = 1; i <= m; i++)//时间复杂度降为O(m) { int l = st[i].first; int r = st[i].second; cout << sum + p[r] - p[l - 1] << endl; }
小蓝有一个长度均为 n 且仅由数字字符 0 ∼ 9 组成的字符串，下标从 0 到 n − 1，你可以将其视作是一个具有 n 位的十进制数字 num，小蓝可以从 num 中选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件 numnew < num，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。
#include<bits/stdc++.h>//万能头文件 using namespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint n = 5010; int f[n][n];//默认全为0 signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
string s; cin >> s; int ans = 0; //区间DP for (int len = 2; len <= s.size(); len++)//子串长度为2、3、4、5...时1 { for (int l = 0; l + len - 1 < s.size(); l++)//左右边界的下标l和r { int r = l + len - 1;//右边界下标 if (s[l] > s[r]) f[l][r] = 1;//表明这段连续子串是合法的 elseif (s[l] == s[r]) f[l][r] = f[l + 1][r - 1];//状态转移，从较长子串的状态转移到较短子串的状态 ans += f[l][r]; } } cout << ans;
return0;//必须要写 }
该题使用到了区间DP，好厉害的算法。
题目 3145: 买瓜（DFS+剪枝+贪心）
题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜，每个瓜的重量为 Ai 。
小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜，请输出 −1 。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 32; int n, m; int ans = INF; int a[N]; int s[N];//后缀和数组
voiddfs(int u, double w, int cnt) { //u：当前已经考虑了第u个瓜 //w：要买的瓜的总重量 //cnt：砍过的刀数 if (w == m) { ans = min(ans, cnt);//选个更小的 return; } //如果遍历过了所有的瓜，那就返回 if (u >= n)//dfs出口 return;
//剪枝策略 //如果当前答案已经不如最优解了，那就返回 if (cnt >= ans) return; //如果瓜的重量已经超了，那就返回 if (w >= m) return; //如果后面瓜的重量之和加上考虑过的，已经小于m了，那就返回 if (w + s[u] < m) return;
for (int i = 0; i < f_son[x].size(); i++)//遍历当前节点的所有儿子节点 { dfs(f_son[x][i], it);//把当前节点的哈希表it传给儿子节点，便于后续上传颜色数信息 }
int pre = 0, flag = 1;//判断当前子树是否是颜色平衡树 for (auto i : it) { mp[i.first] += i.second;//把当前子树的哈希表信息上传给父亲节点 if (pre && pre != i.second) // 如果pre已经被赋值但是不与其他颜色数相等，则不是颜色平衡树 flag = 0; pre = i.second; } if (flag)//颜色数都相同，说明该子树是颜色平衡树 ans++; } signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n; int f; for (int i = 1; i <= n; i++) {//输入 cin >> color[i] >> f; f_son[f].push_back(i);//存放每个节点的孩子节点 }
for (int i = 1; i <= n; i++)//存入A，B值 cin >> a[i] >> b[i];
//找最小值V int l = 1, r = 1e9; while (l < r) { int mid = (l + r) / 2; if (check_min(mid)) r = mid; else l = mid + 1; } cout << l <<" "; //找最大值V l = 1, r = 1e9; while (l < r) { int mid = (l + r + 1) / 2;//避免死循环 if (check_max(mid)) l = mid; else r = mid - 1; } cout << l << " ";
return0; }
该解使用二分答案法，要记住对应的模板。
当mid落入合法区域时，V值正好，满足b[i] = a[i] / mid
当mid落入合法区域的右边时，V值过大，满足b[i] > a[i] / mid
当mid落入合法区域的左边时，V值过小，满足b[i] < a[i] / mid
关于找最大值时mid = (l + r + 1) / 2的解释：
场景 1：找最大值
在找最大值时，如果 mid 满足条件，我们希望 l 向右移动，即 l = mid。
如果使用 mid = (l + r) / 2，当 l 和 r 相邻时，mid 会偏向左侧，导致 l 无法更新，陷入死循环。
intmain(){ // main 函数的返回类型必须是 int cin >> k; cin >> s >> c1 >> c2;
vector<int> c1_positions; // 存储 c1 的位置（下标） for (int i = 0; i < s.size(); i++) { if (s[i] == c1) c1_positions.push_back(i); }
ll ans = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == c2) { if (i - k + 1 < 0 || c1_positions.empty())//i-k+1是满足条件的子串的起始位置的下标，从这里开始到c2的长度等于K continue; //i+1<k,说明长度不满足K，直接跳过就好
// 二分查找满足条件的 c1 的数量 int l = 0, r = (int)c1_positions.size() - 1; // 避免无符号整数溢出 while (l < r) { int mid = (l + r + 1) / 2; if (c1_positions[mid] <= (i - k + 1)) l = mid; else r = mid - 1; } if (c1_positions[l] <= i - k + 1) // 找到满足条件的字符串：以 c2 结尾，开头是从右向左的第一个 c1 ans += (l + 1); // 加1，数组下标比实际少1 } } cout << ans << endl; return0; // main 函数返回 0 }
该解使用二分法，挺抽象的，一开始理解不了i - k + 1的含义，好难。。。
我总觉得这个题解写得不够好，太乱了。
题目 3151: 飞机降落
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早
可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li个单位时间。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long
constint N = 2e5 + 10; typedef pair<int, int> pii; map<pii, int> st;//记录{x, y}的距离是多少 int a[N]; vector<pii> edge[N];//存图
//s表示你要求的路径的起点 //u表示你当前走到了哪个点 //father表示你当前这个点的父亲节点是谁。避免重复走造成死循环 //v表示你要求的路径的终点 //sum表示从s走到u的路径花费总和。 booldfs(int s, int u, int father, int v, int sum) { if (u == v) { st[{s, v}] = sum; st[{v, s}] = sum; returntrue; } for (int i = 0; i < edge[u].size(); i++) { int son = edge[u][i].first;//u点的邻接点 if (son == father) continue; int w = edge[u][i].second;//邻边的权值 if (dfs(s, son, u, v, sum + w)) returntrue; } returnfalse;//如果没有找到路径，返回false; }
signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; for (int i = 0; i < n - 1; i++)//存图 { int x, y, t; cin >> x >> y >> t; edge[x].push_back({y, t});//无向边 edge[y].push_back({x, t}); } for (int i = 0; i < k; i++)//输入原本要参观的k个景点 cin >> a[i]; //求出按顺序走完整路线的总花费时间 int ans = 0; for (int i = 0; i < k - 1; i++) { dfs(a[i], a[i], -1, a[i + 1], 0); ans += st[{a[i], a[i + 1]}]; //cout << ans << endl; } //裁剪 for (int i = 0; i < k; i++) { int tmp = ans; if (i == 0)//如果去除第1个点 tmp -= st[{a[i], a[i + 1]}]; elseif (i == k - 1)//如果去除最后1个点 tmp -= st[{a[i - 1], a[i]}]; else//如果去除中间的点 { tmp -= st[{a[i - 1], a[i]}]; tmp -= st[{a[i], a[i + 1]}]; dfs(a[i - 1], a[i - 1], -1, a[i + 1], 0);//记录该点前一个点到该点后一个点的边权 tmp += st[{a[i - 1], a[i + 1]}]; } cout << tmp << " "; }
return0;//必须要写 }
该解使用dfs暴力遍历，只能拿43分。
从该题学会了写算法题的基本模板。
题目 3157: 砍树
题目描述
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),
. . . , (am, bm)，其中 ai 互不相同，bi 互不相同，ai ≠ bj(1 ≤ i, j ≤ m)。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long
constint N = 2e5 + 10; typedef pair<int, int> pii; map<pii, int> id;//记录{x, y}的距离是多少 int w[N];//存放每个边的权值，初始为0 vector<int> edge[N];//存图
//s表示你要求的路径的起点 //u表示你当前走到了哪个点 //father表示你当前这个点的父亲节点是谁。避免重复走造成死循环 //v表示你要求的路径的终点 booldfs(int s, int u, int father, int v) { if (u == v)//找到终点 returntrue; for (int i = 0; i < edge[u].size(); i++) { int son = edge[u][i];//避免重复走造成死循环 if (son == father) continue; if (dfs(s, son, u, v)) { int ID = id[{u, son}];//找到对应边的边号 w[ID]++; returntrue; } } returnfalse; } signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m; for (int i = 0; i < n - 1; i++)//存图 { int x, y; cin >> x >> y; edge[x].push_back(y);//无向边 edge[y].push_back(x); id[{x, y}] = id[{y, x}] = i;//设置边号 } for (int i = 0; i < m; i++)//dfs遍历每条边，并赋予权值 { int x, y; cin >> x >> y; dfs(x, x, -1, y); } int ans = 0; for (int i = n - 2; i >= 0; i--)//从最大编号的边开始，符合题意 { if (w[i] == m) { ans = i + 1;//边号从1开始，数组下标要加一 break; } } cout << ans; return0;//必须要写 }
该解使用dfs遍历，和上一题类似，但本质上还是暴力，只能拿33分。
感觉对dfs的理解更深刻了。
题目 3155: 整数删除
题目描述
给定一个长度为 N 的整数数列：A1, A2, . . . , AN。你要重复以下操作 K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。输出 K 次操作后的序列。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 5e5 + 10; int n, k, pos = 0; int a[N];//存储数字 int st[N];//标记某个数字是否被删除 signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n >> k; for (int i = 0; i < n; i++)//存储n个数字 cin >> a[i]; while (k) { int MIN = INF;//每一轮重置最小值 for (int i = 0; i < n; i++)//找到每一轮的最小数 { if (a[i] < MIN && !st[i])//该数更小且未被删除过 { MIN = a[i]; pos = i; } } st[pos] = 1;//标记该数为删除状态
//对相邻的数字进行操作 for (int i = pos - 1; i >= 0; i--)//从该数左边开始遍历 { if (!st[i])//如果该数未删除过 { a[i] += MIN; break;//找到一个就跳出 }
}
for (int i = pos + 1; i < n; i++)//从该数右边开始遍历 { if (!st[i])//如果该数未删除过 { a[i] += MIN; break;//找到一个就跳出 } } k--; } for (int i = 0; i < n; i++) { if (!st[i]) cout << a[i] << " "; } return0;//必须要写 }
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 1e5 + 10; int n, ans = 0; int a[N];
intget_first(int x)//获得最高位数字 { int num = 0; while(x) { num = x % 10;//获得最低位 x /= 10;//去除最低位 } return num; } intget_last(int x)//获得最低位数字 { return x % 10; }
//u表示：当前考虑到了第几个数字,以下标形式表示 //last表示：方案中已经选了的数列最后一个数字是多少 //cnt表示：当前方案中一共有多少个数字 voiddfs(int u, int last, int cnt) { if (u >= n)//dfs出口 { ans = max(ans, cnt); return; } if (n - u + cnt <= ans)//优化（没有也行，有了更好） { return; }
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
int n;
intcal_ans(const vector<int>& a, const vector<int>& b, const vector<int>& c)//计算x，y，z各自胜利时最多发生的事件数 { vector<int> tmp(n); int sum = 0, cnt = 0;
for (int i = 0; i < n; i++) tmp[i] = a[i] - (b[i] + c[i]);
sort(tmp.begin(), tmp.end());//从小到大排序 for (int i = n - 1; i >= 0; i--)//从最大的开始加，让a持续地保持赢的状态，直到 sum + tmp[i] <= 0 ，跳出循环 { if (sum + tmp[i] > 0) { sum += tmp[i]; cnt++; } elsebreak; } return cnt; } signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n; vector<int> a(n), b(n), c(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; for (int i = 0; i < n; i++) cin >> c[i];
int a_ans = cal_ans(a, b, c);//a赢 int b_ans = cal_ans(b, a, c);//b赢 int c_ans = cal_ans(c, a, b);//c赢
int ans = max({ a_ans, b_ans, c_ans }); if (ans > 0) cout << ans; else cout << -1;
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
map<int, vector<int>> st; int cnt = 0;
voidprim(int x, int pos)//分解质因数,将该数的位置存放在st中 { for (int i = 2; i <= x / i; i++) { if (x % i) continue; st[i].push_back(pos); while (x % i == 0) x /= i; } if (x > 1) st[x].push_back(pos); }
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 2e5 + 10; int n, m, x; int l, r; int a[N]; signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n >> m >> x; for (int i = 0; i < n; i++)//存数 { cin >> a[i]; } while (m--) { cin >> l >> r; bool flag = false; for (int i = l - 1; i <= r - 1; i++)//注意l，r都要减一，数组下标形式 { for (int j = i + 1; j <= r - 1; j++) { if ((a[i] ^ a[j]) == x) { flag = true; break; } } if (flag) break;//跳出2层for循环的方法 } if (flag) { cout << "yes" << endl; } else { cout << "no" << endl; } } return0;//必须要写 }
MyAns
依旧是暴力枚举，可以得73分。
本题又学习到了如何跳出多层内部循环。
2022年第十三届蓝桥杯大赛软件类省赛C/C++大学B组真题
题目 2656: 刷题统计（暴力）
题目描述
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
int a, b, n; int sum = 0, day = 0; signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> a >> b >> n; while (1)//循环，7天为一个周期 { for (int i = 1; i <= 7; i++) { if (i == 6 || i == 7) sum += b; else sum += a; day++; if (sum >= n) { cout << day; return0; } } }
return0;//必须要写 }
MyAns
该解就是简单的暴力枚举，可以过百分之八十的数据。
题目 2657: 修剪灌木（模拟）
题目描述
爱丽丝要完成一项修剪灌木的工作。有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 1e6 + 10; int a[N]; int n, m;
boolcmp(int x, int y){//自定义排序规则 int sum1 = 0, sum2 = 0; int a = x, b = y; while (a != 0) { sum1 += a % 10;//x的数位和 a = a / 10; } while (b != 0) { sum2 += b % 10;//y的数位和 b = b / 10; } if (sum1 == sum2) {//数位和相同时，值小的在前面 return x < y; } return sum1 < sum2;//否则，数位和小的在前面 } signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n >> m; for (int i = 1; i <= n; i++)//存放1到n { a[i] = i; } sort(a + 1, a + n + 1 , cmp);//sort排序
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 1e5 + 10; int n, m, l, r; int a[N], cnt[N], diff[N]; int sum1 = 0, sum2 = 0; signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n; for (int i = 1; i <= n; i++)//输入原数组，令下标从1开始 { cin >> a[i]; } cin >> m; for (int i = 0; i < m; i++)//构建差分数组，用于cnt数组的构建 { cin >> l >> r; diff[l]++; diff[r + 1]--; } cnt[1] = diff[1]; for (int i = 2; i <= n; i++)//统计每个位置出现的次数 { cnt[i] = cnt[i - 1] + diff[i]; }
for (int i = 1; i <= n; i++)//计算原数组的区间和 { sum1 += a[i] * cnt[i]; } //从小到大排序，确保大数的出现次数更多 sort(a + 1, a + n + 1); sort(cnt + 1, cnt + n + 1); for (int i = 1; i <= n; i++)//计算原数组的区间和 { sum2 += a[i] * cnt[i]; } cout << sum2 - sum1; return0;//必须要写 }
看到题目以为要考前缀和，最后果然还是上了个难度。
利用一维差分统计数列每个位置的出现次数，然后对原数组和cnt数组进行从小到大的排序，
确保大数的出现次数更多，小数的出现次数更少，故大数的“贡献”更多。
做完之后才发现这其实根本上是贪心法。
题目 2688: 技能升级（暴力+贪心）
题目描述
小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数都会减少 Bi。(上取整) 次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力？
输入格式
输入第一行包含两个整数 N 和 M。
以下 N 行每行包含两个整数 Ai 和 Bi。
输出格式
输出一行包含一个整数表示答案。
样例输入
1 2 3 4
3 6 10 5 9 2 8 1
样例输出
1
47
提示
对于 40% 的评测用例，1 ≤ N, M ≤ 1000；
对于 60% 的评测用例，1 ≤ N ≤ 104 , 1 ≤ M ≤ 107；
对于所有评测用例，1 ≤ N ≤ 105，1 ≤ M ≤ 2 × 109，1 ≤ Ai , Bi ≤ 106。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 1e5 + 10; int n, m, a, b; vector<int> st; int sum = 0; boolcmp(int a, int b) { return a > b; // 如果 a > b，则 a 排在前面 } signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a >> b; int t = (a + b - 1) / b;//最大升级次数，上取整 while (t--) { st.push_back(a);//存放每个技能升级后可加的攻击力 a -= b; } } sort(st.begin(), st.end(), cmp);//从大到小排序 for (int i = 0; i < m; i++) { sum += st[i];//求前m个攻击力的累加之和 } cout << sum; return0;//必须要写 }
一开始想用贪心法，但是不知道如何能够每次取到最大攻击力。
其实只需要把每组样例中可以升级的攻击力都存到vector数组中，最后进行一个降序就完成了。
然而，这依然属于暴力枚举，只能拿39分。
题目 2691: 重复的数（暴力）
题目描述
给定一个数列 A = (a1, a2, · · · , an)，给出若干询问，每次询问某个区间 [li ,ri ] 内恰好出现 ki 次的数有多少个。
输入格式
输入第一行包含一个整数 n 表示数列长度。
第二行包含 n 个整数 a1, a2, · · · , an，表示数列中的数。
第三行包含一个整数 m 表示询问次数。
接下来 m 行描述询问，其中第 i 行包含三个整数 li ,ri , ki 表示询问 [li ,ri ] 区间内有多少数出现了 ki 次。
输出格式
输出 m 行，分别对应每个询问的答案。
样例输入
1 2 3 4 5 6 7 8
3 1 22 5 1 11 1 12 1 21 1 22 1 32
样例输出
1 2 3 4 5
1 0 2 0 1
提示
对于 20% 的评测用例，n, m ≤ 500, 1 ≤ a1, a2, · · · , an ≤ 1000；
对于 40% 的评测用例，n, m ≤ 5000；
对于所有评测用例，1 ≤ n, m ≤ 100000, 1 ≤ a1, a2, · · · , an ≤ 100000, 1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ n。
#include<bits/stdc++.h>//万能头文件 usingnamespace std; #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f3f3f3f
constint N = 1e5 + 10; int n, m, l, r, k; //a数组用于存放数列，st数组用于存放每个数出现的次数,flag数组用于避免重复计算 int a[N],st[N],flag[N]; int sum = 0; boolcmp(int a, int b) { return a > b; // 如果 a > b，则 a 排在前面 } signedmain() { ios::sync_with_stdio(0);//关流 cin.tie(0); cout.tie(0);
cin >> n; for (int i = 1; i <= n; i++)//存放数列 { cin >> a[i]; } cin >> m; for (int i = 1; i <= m; i++) { cin >> l >> r >> k; for (int i = l; i <= r; i++)//存放该区间内每个数字出现的次数 { st[a[i]]++; } for (int i = l; i <= r; i++) { if (st[a[i]] == k) { if (flag[a[i]] == 0)//避免重复计算，只统计第一次出现的数 { sum++; flag[a[i]] = 1; } } } cout << sum << endl; //重置 sum = 0; memset(flag, 0, sizeof(flag)); memset(st, 0, sizeof(st)); } return0;//必须要写 }
(上取整) 次之后，再升级该技能将不会改变攻击力。