Java教程
君君算法课堂-基础算法补充
- 基础算法补充
- 复杂度
- 时间复杂度
- 空间复杂度
- 数量级大小关系判断
- 卡常数
- 模拟
- [NOIP2014]生活大爆炸版石头剪子布
- [NOIP2015]神奇的幻方
- [NOIP2016]玩具谜题
- [NOIP2017]时间复杂度
- 高精度运算
- 枚举
- [NOIP2001 提高组] 一元三次方程求解
- 例题：六元组
- [AHOI2009]飞行棋
- 递归
- 递归的时间复杂度
- 贪心
- 例题：采药（伪）
- [PA2014]Bohater
- 【USACO2007 Dec】挑剔的美食家
- 复杂度
基础算法补充
复杂度
时间复杂度
概念
在程序设计竞赛中，一般只需了解时间复杂度可以大致地通过一个算法运算的次数来描述程序运行的效率，
常常用大写字母 Ο 来表示。在表示时间复杂度的时候，只保留数量级最大的一项，并忽略系数。
举个栗子
对于给定的常数 \(N\)，若某一个算法计算的次数是 \(3N^3+N^2+10^5\)，则我们可以认为它的时间复杂度为 \(Ο(N^3)\)。
令 \(k = \displaystyle \frac{3N^3+N^2+10^5}{N^3}\)，则时间复杂度实际为 \(O(k*N^3)\)。
\(k\) 被称作 常数，根据 \(k\) 的大小，可以判断程序运行的常数大小。
空间复杂度
概念
顾名思义就是用来衡量内存的占有量的。除了计算复杂度，我们常常也需要直接算出来运行程序需要占用多少内存。
超高校级的单位换算
\(1YiB=2^{10}ZiB=2^{20}EiB=2^{30}PiB=2^{40}TiB=2^{50}GiB=2^{60}MiB=2^{70}KiB=2^{80}B\),
\(1B\) (\(byte\), 字节)=\(8b\) (\(bit\), 比特).
常见数据类型
\(char/bool/short: 1B\ \ \ int/float: 4B\ \ \ long\ long/double: 8B\)
数量级大小关系判断
\(Ο(1)<Ο(log\ n )<Ο(\sqrt{n})<Ο(n)<Ο(2^n )<Ο(n!)……\)
\(CPU\) 主频，一般都在 \(2\) ~ \(4GHz\) 左右，也就是说每秒钟包含数十亿个个时钟周期。
由于执行一次运算操作需要花费数个时钟周期，我们在设计算法的时候需要保证运算次数不超过每秒钟 \(10^8\) 次。
空间按照题目给出的要求算一算就好，一般情况下数组开到几千万没有问题，记得不要把数组开的太满。
卡常数
运算速度的比较：
① 位运算>加减运算>乘法运算>>除法、取模运算；
② 整数运算>>实数运算，【玄学】无符号型>有符号型；
③ 调用函数>直接运算，手写数据结构>偷懒用 STL；
空间不够用怎么办：
数组重复利用？变量现用现开？使用变长数组？建立内存池？
模拟
题目说啥你做啥，对动脑筋的要求近乎于零。
只要按着题目中的叙述一步一步地写代码，就能获得满分。
写这类题时，一般提前想好思路，不要想一步写一步，不然可能需要调试很长时间。
[NOIP2014]生活大爆炸版石头剪子布
题目链接
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 300;
int n, na, nb, a[N], b[N], cta, ctb;
int vs[9][9] = {{0, 0, 1, 1, 0}, {1, 0, 0, 1, 0}, {0, 1, 0, 0, 1}, {0, 0, 1, 0, 1}, {1, 1, 0, 0, 0}};
int main() {
cin >> n >> na >> nb;
for(int i = 0; i < na; ++ i) cin >> a[i];
for(int i = 0; i < nb; ++ i) cin >> b[i];
for(int i = 0; i < n; ++ i) {
cta += vs[a[i % na]][b[i % nb]];
ctb += vs[b[i % nb]][a[i % na]];
}
cout << cta << " " << ctb;
return 0;
}
[NOIP2015]神奇的幻方
题目链接
#include<bits/stdc++.h>
using namespace std;
int a,b,x,y,s[100][100];
int main() {
cin >> a; b = 1;
int x = 1, y = a / 2 + 1;
for(int i = 1; i <= a * a; ++ i) {
if(i == 1) s[1][a / 2 + 1] = b;
else if((b - 1) % a == 0) {
if(x + 1 == a + 1) x = 1;
else x = x + 1;
s[x][y] = b;
}
else {
if(y + 1 == a + 1) y = 1;
else y = y + 1;
if(x - 1 == 0) x = a;
else x = x - 1;
s[x][y] = b;
}
b ++;
}
for(int i = 1; i <= a; ++ i) {
for(int j = 1; j <= a - 1; ++ j) {
cout << s[i][j] << ' ';
}
cout << s[i][a] << endl;
}
}
[NOIP2016]玩具谜题
题目链接
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 2;
int read() {
int x = 0, f = 1;char ch = getchar();
while(ch < '0'||ch > '9') f = (ch == '-') ? -1 : 1, ch = getchar();
while(ch >= '0'&&ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
int n, m, pos = 0;
struct peo {
int c; char name[12];
}p[N];
int main() {
n = read(); m = read();
for(int i = 0; i < n++ i) p[i].c = read(), cin >> p[i].name;
for(int i = 1, a, s; i <= m; ++ i) {
a = read(); s = read();
s %= n;
switch(a) {
case 0:if(p[pos].c) pos = (pos + s) % n;
else pos = ((pos + n) - s) % n;
break;
case 1:if(p[pos].c) pos = ((pos + n) - s) % n;
else pos = (pos + s) % n;
break;
}
}
cout << p[pos].name;
return 0;
}
[NOIP2017]时间复杂度
题目链接
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;
string a, b;
int c, d, m, n, e, h, k, f[200], g[200], l[200];
int main() {
int t; cin >> t;
while(t --> 0) {
c = d = m = n = e = h = k = 0;
memset(f, 0, sizeof(f)); memset(l, 0, sizeof(l));
do{a = b; cin >> b;} while(b[0] != 'O');
int la = a.length(), lb = b.length();
for(int i = 0; i < la;++ i) c = c * 10 + (a[i]^48);
for(int i = 4; i < lb - 1; ++ i) d = d * 10 + (b[i]^48);
while(c --> 0) {
cin >> a;
if(a[0] == 'F') {
e ++; cin >> a;
if(f[a[0]-96]) e = -1;
else f[a[0]-96] = 1, g[e] = a[0] - 96;
cin >> a >> b;
if(a[0] != 'n'&&b[0] == 'n'&&k == 0) h ++, l[e] = 1;
else if((a.length() == b.length()&&a > b)||(a.length() > b.length())
||(a[0] == 'n'&&b[0] != 'n' && k == 0))
k = 1, n = e;
}
else {
m = max(m, h); f[g[e]] = 0;
if(l[e] == 1) l[e] --, h --;
e --;
if(n > 0&&e < n) k = n = 0;
}
if(e == -1) cout << "ERR" << endl, c = -1;
}
if(e > 0) cout << "ERR" << endl;
if(e == 0&&m == d) cout << "Yes" << endl;
if(e == 0&&m != d) cout << "No" << endl;
}
return 0;
}
高精度运算
\(int\) 的范围在 \(10^9\) 级别，\(long\ long\) 的范围在 \(10^{19}\) 级别。
如果你需要对更长的数进行计算，要如何是好？
竞赛中有时甚至需要用到 \(10^{10000000+}\) 级别的数字，这要怎么办？
回忆：
十年前，当你只会念叨个位数加减乘除的时候，是如何学习更高位数的数字运算的呢？
列竖式！算算算！
用一个数组来模拟一个数字。
列竖式算加减乘的时候都是从低位到高位进行计算，所以为方便起见，我们也要倒着把数字放进数组。
就像这样：
\(123450 → \{0, 5, 4, 3, 2, 1\}\)
char str[1000005];
struct bigint { int num[1000005], len; };
void Read(bigint &a) {
scanf("%s", str);
a.len = strlen(str);
for(int i = 0; i < a.len; ++ i) a.num[i] = str[i] - '0';
reverse(a.num, a.num + a.len);
}
加法
要保证答案中的每一位都是非负的一位数。
在进位的地方，一定要处理好。
void Plus(bigint &a, bigint &b, bigint &c) {
c.len = max(a.len, b.len);
for(int i = 0; i < c.len; ++ i) c.num[i] = a.num[i] + b.num[i];
for(int i = 0; i < c.len; ++ i) {
if(c.num[i] > 9) c.num[i + 1] += 1, c.num[i] -= 10;
}
if(c.num[c.len]) ++ c.len;
}
减法
和加法一模一样，进位变成了退位而已。
注意需要更新答案的长度。
void Minus(bigint &a, bigint &b, bigint &c) {
c.len = a.len;
for(int i = 0; i < c.len; ++ i) c.num[i] = a.num[i] - b.num[i];
for(int i = 0; i < c.len; ++ i) {
if(c.num[i] < 0) c.num[i + 1] -= 1, c.num[i] += 10;
}
while(c.len > 1 && c.num[c.len - 1] == 0) -- c.len;
}
高精度乘低精度
将加减直接改成乘法就好了，没有任何额外的难度！
低精度除高精度
除法是从高位到低位进行运算的。
使用一个临时变量来记录余数，注意细节。
高精度乘高精度
请自己尝试实现 \(Ο(n^2)\) 算法
利用高超的数学技巧可以做到 \(Ο(n∗logn)\)
void Multi(bigint &a, int b, bigint &c) {
c.len = a.len;
for(int i = 0; i < c.len; ++ i) c.num[i] = c.num[i] * b;
for(int i = 0; i < c.len; ++ i) {
c.num[i + 1] += c.num[i] / 10;
c.num[i] %= 10;
if(c.num[i + 1] && i + 1 == c.len) ++ c.len;
}
}
int Div(bigint &a, int b, bigint &c) {
c.len = a.len; int t = 0;
for(int i = c.len - 1; i >= 0; -- i) {
t = t * 10 + a.num[i];
c.num[i] = t /b; t %= b;
}
while(c.len > 1 && c.num[c.len - 1] == 0) -- c.len;
return t;
}
常数优化：
一个 \(int\) 可以存储高达 \(10^9\) 级别的数字，在高精度计算的时候，我们却仅仅用它来保存一位数字。
这是不是过于浪费了呢？
不如，让一个 \(int\) 保存四位数字吧，我们管这种方式叫做压位！
通过压位的方式，空间压缩的同时，运算速度也加快了不少。
思考：
为什么我们常常会四位四位地把数字压起来，而不是九位九位地压呢？
枚举
定义：
又被称为穷举法。指从可能的集合中一一枚举各个元素，
用题目给定的约束条件判定哪些是无用的，哪些是有用的。
能使命题成立者，即为问题的解。
也就是对所有可能成为解的元素，挨个批判一番，检查它究竟是不是解。
最重要的就是确定枚举对象、枚举范围和判定条件。
[NOIP2001 提高组] 一元三次方程求解
题目链接
题解：观察题目，发现答案范围又小，精度要求又低，依次试答案即可。
#include<cstdio>
#include<iostream>
using namespace std;
double a, b, c, d, i, j, k, xx;
double fc(double x) {
return a * x * x * x + b * x * x + c * x + d;
}
int main() {
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
for(int x = -100; x <= 100; ++ x) {
i = x; j = x + 1;
if(fc(i) == 0) printf("%.2f ", i);
else if(fc(i) * fc(j) < 0) {
while(j - i >= 0.001) {
xx = (j + i) / 2;
if(fc(i) * fc(xx) <= 0) j = xx;
else i = xx;
}
printf("%.2f ", i);
}
}
return 0;
}
例题：六元组
给出 \(n\) 个互不相同的整数，
问使用这些整数可以组成多少个不同的六元组 \((a, b, c, d, e, f)\)，
使满足条件：\((a×b+c)÷d-e=f\)？
数据范围：\(n ≤ 100\)
题解：
朴素算法：六重循环，时间复杂度 \(Ο(n^6)\)
参考算法：
首先给式子变一个形，成为 \((a×b+c)=d∗(e+f)\) 的形式。
之后枚举左式的值，使用 \(map\) 统计每一个值的出现次数。
再枚举右式的值，在 \(map\) 中查询。
由于在 \(map\) 中进行一次操作的代价是 \(Ο(log\ n)\) 级别的，
因此总时间复杂度为 \(Ο(n∗log\ n )\)。
通过平衡枚举与验证的时间来降低总时间复杂度。
[AHOI2009]飞行棋
题目链接
朴素算法：枚举四个点，再判断是否构成矩形。时间复杂度 \(Ο(n^5)\)
稍机智算法：枚举两个点，如果它们是圆的直径，就以这两个点为对顶点扩展出矩形。
时间复杂度 \(Ο(n^2)\)
参考算法：发现一个矩形的两个对角线都是圆的直径。
进而，每两条互异直径都可以确定一个矩形。
因此就可以直接统计出直径的个数 \(c\)，再用 \(\displaystyle \frac {c∗(c-1)}{2}\) 算一下就是答案啦。
通过观察题目特殊性质降低时间复杂度。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5, p = 500009;
int read() {
int x = 0, f = 1; char ch = getchar();
while(! isdigit(ch)) f = (ch=='-')?-1:1, ch = getchar();
while(isdigit(ch)) x = (x<<3)+(x<<1)+(ch^48), ch = getchar();
return x * f;
}
int n, sum, ans, tot, a[N], s[N], h[p + 5];
void insert(int x) {
int u = x % p;
while(h[u] != -1&&h[u] != x) u = (u + 1) % p;
h[u] = x;
}
bool find(int x) {
int u = x % p;
while(h[u] != -1&&h[u] != x) u = (u + 1) % p;
return h[x] != -1;
}
int main() {
memset(h, -1, sizeof(h));
n = read();
for(int i = 1; i <= n; ++ i) { a[i] = read(), s[i] = s[i-1] + a[i]; }
sum = s[n];
for(int i = 1; i <= n; ++ i) insert(s[i] % sum);
if(sum % 2) { printf("0\n"); return 0; }
for(int i = 1; i <= n; ++ i) tot += find((s[i] + sum/2) % sum);
tot /= 2;
printf("%lld\n", (long long) tot * (tot - 1) / 2);
return 0;
}
/*
8
1 2 2 3 1 1 3 3
*/
递归
定义：
如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。
什么样子的算法可以被称之为递归算法？
① 有反复执行的过程（调用自身）。
② 有跳出反复执行的条件（递归出口）。
阶乘的计算：
\(fac(0)=1,fac(n)=fac(n-1)∗n\)
当 \(n\) 过大的时候，程序可能会崩掉？系统栈空间惹的祸！
斐波那契数列的计算：
\(fib(0)=fib(1)=1, fib(n)=fib(n-2)+fib(n-1)\)
这里递归时有很多重复计算，一旦 \(n\) 稍大，运行就会变得及其缓慢…
不如在运算的时候把结果记录下来，当再次递归到已经计算过的位置时，就可以直接返回答案了。
这种记忆化思想很常用！
递归的时间复杂度
归并排序→\(O(n∗log\ n)\)
快速排序→平均 \(O(n∗log\ n)\) ，最坏 \(O(n^2)\)
\(<algorithm>\)
\(sort(first, last, cmp)\)
\(BFPRT\) 算法（求 \(n\) 个元素中第 \(k\) 大值）
\(T(n)=T(\displaystyle \frac{n}{5})+T(\displaystyle \frac{7n}{10})+c∗n→O(n)\)
$ $
\(nth_element(first, nth, last, cmp)\)
贪心
定义：
在求最优解问题的过程中，依据某种标准，从问题的初始状态出发，总是做出当前看来最优的选择，最终得出整个问题的最优解。这种求解方法就是贪心算法。
可以看到，贪心算法所做出的选择只是在某种意义上的局部最优解。它最后是否能获得准确的答案是由题目本身性质决定的，但许多问题可以利用贪心给出一个近似最优解。
贪心算法常需要配合排序算法或堆等数据结构以便求局部最优解。
例题：采药（伪）
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
假算法：我们可以贪心地先去采单位时间收益最大的草药。以 耗时／收益 为关键字，将草药降序排序，从前到后依次采摘。若草药可以拆分，则这一算法具有正确性。
很显然，对这道题而言贪心算法并不是一个正确的算法，但它可以用比正解更低的时间复杂度给出很优秀的解。
所以，在考试中如果想不到正解，为何不试试贪心骗分呢~
[PA2014]Bohater
题目链接
题解：显然，对于补血比耗血多的怪，先打掉一定是较优的，顺序显然可以按照打怪的耗血量从小到大依次来打。
后面， 要处理的就是耗血量更多的怪了。按照什么顺序呢？
答案是按照回血量从大到小的顺序。倒过来看，这个过程相当于复活一个怪需要吐出来一口血，再复原打怪消耗的血量——和前半部分问题是异曲同工的呢。
【USACO2007 Dec】挑剔的美食家
题解：先把牛和牧草都按照鲜嫩度从大到小排序。
在枚举牛的同时，把鲜嫩度不小于它的要求的牧草都插进一个数据结构里去。
之后，在数据结构中查询并删除满足当前牛的价格要求的最便宜牧草即可。
这个数据结构需要支持插入、查询不小于某数值的最小元素以及删除等操作，
我们可以利用 \(STL\) 中的 \(multiset\)。
-
TiDB 资源管控的对撞测试以及最佳实践架构07-04
-
万字长文聊聊Web3的组成架构07-03
-
springboot项目无法注册到nacos-icode9专业技术文章分享07-02
-
结对编程到底难不难？答案在这里06-26
-
《2023版Java工程师》课程升级公告06-19
-
matplotlib作图不显示3D图，怎么办？06-15
-
03-Loki 日志监控06-15
-
04-让LLM理解知识 -Prompt06-15
-
做软件测试需要懂代码吗？06-05
-
14-ShardingSphere的分布式主键实现06-05
-
为什么以及如何要进行架构设计权衡？06-03
-
全网首发第二弹！软考2024年5月《软件设计师》真题+解析+答案！（11-20题）05-31
-
全网首发！软考2024年5月《软件设计师》真题+解析+答案！（21-30题）05-31
-
【Java】百万数据excel导出功能如何实现05-30
-
我们小公司，哪像华为一样，用得上IPD（集成产品开发）？05-30
