POJ3685 Matrix
题面大秦为你打开题目传送门 (看不懂就看下面吧)
有一个$N× N$ 的矩阵
第 $i$ 行第 $j$ 列的值为 $𝑖^2 +100000× 𝑖 + 𝑗^2 −100000× 𝑗 + 𝑖 × 𝑗$
求矩阵中第 $M$ 小的数。
题意二分第 $M$ 小的数,然后 $check$ 时枚举 $i$ ,再二分找小于 $mid$ 的数字,加起来看看是不是 $M$
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include<bits/stdc++.h>using namespace std;typedef long long ll;int n;ll m;void Input(){ scanf("%d%lld", &n, &m);}ll Calc(ll i, ll j, ll x){ if(i==n+1) return max(x, ...
517七段第四课D
题面大秦为你打开题目传送门 (看不了的就看下面吧)
找出最小的自然数据 $N$ ,使得 $N!$ 刚好有 $Q$ 个后缀零。$N!=1\times2\times…\times N$ 例如 $5!=1\times2\times3\times4\times 5=120$, $120$有 $1$ 个后缀 $0$ 。
题意显而易见的,$N$ 越大,阶乘的后缀零越多,所以这是一个二分题。
二分答案 $N$ ,对于它数 $1$ 至 $N$ 有几个因子 $5$ 。显然,$1$ 至 $N$ 中 $5$ 的倍数是 $\lfloor N/5\rfloor$ 但是,这还不够,因为有一些数字有多个因数 $5$ 。所以要把那些 $5$ 的倍数拿出来反复如上操作,如下图。
我们设 $N = 30$ ,然后做第一个除以 $5$ 的操作,答案是 $6$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N
N
N
N
Y
N
N
N
N
Y
N
N
N
N
Y
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
N
N
N
N
Y ...
517七段第四课B
题面大秦为你打开题目传送门 (看不了的就看下面吧)
看下图
已知三角形 $ABC$ ,$DE$ 平行于 $BC$ ,给定三角形 $ADE$ 与四边形 $BCED$ 的面积之比,求 $AD$ 的长度。
题意显而易见的,使用相似,这道题可以用数学方法 $O(1)$ 求解。三分的话我们可以直接三分答案拿着算出的答案就去和比例比,就可以了。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<bits/stdc++.h>using namespace std;const double eps = 1e-10;double AB, AC, BC, k;void Input() { scanf("%lf%lf%lf%lf", &AB, &AC, &BC, &k); // cout<<AB<<AC<<BC<<k& ...
517七段第四课A
题面大秦为你打开题目传送门 (看不了的就看下面吧)
给定三维空间中的两个点 $A(x_1, y_1, z_1), B(x_2, y_2, z_2)$ ,以及点 $P(x, y, z)$ 。
计算点 $P$ 到线段 $AB$ 的最短距离。
思路首先,三点确定一平面,此题一定有解。
其次,对于一个点与线段的关系,会有如下 $3$ 种。
而这一类型的题显然是用三分做的(我不介意你用数学方法做)
我们可以三分点与线段的最短线段的交点位置,然后求解。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<bits/stdc++.h>using namespace std;const double eps=1e-10;double ax, ay, az, bx, by, bz, cx, cy, cz;void Input(){ scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf", &ax, ...
01分数规划
问题:需求有n对元素 $(𝑣_1,𝑤_1),(𝑣_2,𝑤_2), (𝑣_3,𝑤_3), …,(𝑣_𝑛,𝑤_𝑛)$。要求从中挑选出 $k$ 对,使得 $v$ 的和除以 $w$ 的和最大。
解法:分析显然是一道二分题,我们直接二分最大值可得式子:( $x[i]$ 表示选或不选,值是 $0$ 或 $1$ )
\cfrac{\sum\limits_{i=1}^n{v_i\times x_i}}{\sum\limits_{i=1}^n{w_i\times x_i}} >mid由于浮点精度误差问题,将其改写为乘法形式
\sum\limits_{i=1}^n{(v_i\times x_i)}>mid \times \sum\limits_{i=1}^n{(w_i\times x_i)}接着移项
\sum\limits_{i=1}^n{(v_i\times x_i)}-mid \times \sum\limits_{i=1}^n{(w_i\times x_i)} > 0由于有 $x_i$ 的共因子,所以提取出来
\sum\limits_{i=1}^n{w_i(v_i-mid ...
三分法
理论:什么是三分提到三分,首先就要回顾二分,二分是一种可以在单调函数上寻找值的算法,复杂度 $O(\log n)$ 。
三分与二分不一样的地方是,他把要寻找的值域分为三份,目的是寻找单峰函数的极值。
实现:怎么写三分如图:
假设我们要在 $l$ 到 $r$ 中查找最值,先取整个区间的中点。
1double mid = (l + r) / 2;
然后我们再取右半部分的中点 $midr$
1double midr = (mid + r) / 2;
然后比较 $mid$ 和 $midr$ 哪个更靠近最值,若 $mid$ 更靠近最值,则舍弃右区间,若 $midr$ 更靠近最值则舍弃左区间。
1234if(Check(mid) > Check(midr)) r = midr;else l = mid;
完整代码:
1234567891011double ssearch(double l,double r){ while(l+eps<=r){ double mid = (l + r) / 2; midr = (mid ...
倍增算法
理论:如何设计需求:要解决的问题对于一些题目,他们要求你计算一个区间内的最小值,没有操作,但是询问次数特别多,以至于树状数组和线段树 $O(m\log n)$ 的时间复杂度已经不够优秀,我们需要引入新的数据结构。
构造:寻找合理方案同样的,我们说过,数据结构是时空平衡的,想要把单次询问复杂度降下来,就需要更高的预处理和空间复杂度。根据我们数据结构的根本是分组的思想,我们需要重新修改分组。
我们思考一下,理想状态是什么?理想状态是我们预处理出来的值可以直接拿出来用,或者经过 $1$ 次运算可以得出。我们可以和两个极端比较一下。
预处理
单次
数组
读入 $O(n)$
for 一遍 $O(n)$
预处理出所有区间最值
$O(n^2)$
$O(1)$
理想数据结构
不知道
由于查询次数极多,所以必须需要单次 $O(1)$ 的算法
首先我们坑定得是 $1$ 对多的分组方式,我们可以打表看看
对于序列 $a[10] = [ 1, 4, 7, 3, 2, 8, 5, 9, 6, 10 ]$ 可以得出如下表格。
区间 $[l,r]$
1
2
3
4
5
6
...
树状数组,这一篇就够了!
概念:什么是树状数组?需求:发现问题、提出问题在信息学竞赛中,我们经常会遇到求一段区间和的题目。一般来说,我们就只需要使用前缀和数组这是一个预处理时间复杂度 $O(n)$,单次查询 $O(1)$,修改 $O(n)$ 的算法。显而易见,在遇到一些数据范围特别大,修改次数特别多的题目时,就会发生爆炸。而这时我们需要一个可以均衡这个时间复杂度的数据结构。
构造:寻找解决问题的方案那么如何制造一个这样的数据结构呢?我们可以从数据结构的根本考虑,数据结构是一种可以将时间和空间均衡,使得解决题目的东西。对于前缀和无法完成的题目,就需要更好的数据结构。不可能会有时间短,空间小,功能强大的数据结构,想要让时间变少,就得用空间换,想要让空间少,就得用时间换。我们可以对于基本的数据结构经行比较。
单点修改时间复杂度
区间查询时间复杂度
期望效果
数组
$O(1)$显而易见的,对于当前的点经行修改便是
$O(n)$对于区间 for 一遍求解
由于想要使前缀和数组的单点修改复杂度降低、综合数组的区间查询,作为代价,必须要增加这里的时间复杂度
前缀和
$O(n)$当前缀和中一个点修改时,之 ...
STL:Map,Set(Multiset & Bitset)
七段第三课:STL这篇主要讲了STL中的MAP,SET,MULTISET,BITSET。
Map定义你可以理解成是一个下标可以为任意东西的数组。在 $\tt c++$ 中,你可以以如下方式定义一个 $\tt map$ :
1map<typename _Key, typename _Tp>mp;
它你可以以如下格式访问它某一个值:
1mp[(_Key) x] = (_Tp) y; // 括号里面的不用写,是注解作用
它表示,在 $\tt mp $ 的下标为 $\tt _Key$ 类型的 $x$ 位置存储着 $\tt _Tp$ 类型的 $y$ 。
使用从某种意义上来讲,$\tt map$ 类型的 $\tt STL$ 可以被称为哈希表。因为它的前面的项没有限制,而之后的也没有限制(只要在对应数据类型范围内)而这一个工具的单次时间复杂度是优秀的 $O(\log n)$ 。
使用的话,除了定义和赋值,还可以以循环的方式查询,而 $\tt map$ 内部的排序默认是按照从小到大排序。(也就是说你可以自定义 $\tt map$ 的排序方式)
$\tt for$ 循环的写法如下:
1234 ...
二分图
二分图定义二分图,是一种可以将所有点分成两个点集,同点集不连,异点集相连的图,如图:
像这样的图就是二分图。
如何判断二分图显而易见的,想要构造一个不是二分图的图,我们可以通过构造环来看,毕竟从理论上来讲因该是可以从环来推出规律。
先构造一个三个点的奇环:显而易见,不是二分图
再来是四个点的偶环:可能一想不是二分图,但是画出来以后发现是二分图
再来是五个点的奇环:不用画图就显而易见,不是二分图
所以,我们发现其实这个二分图只要没有奇环就可以了
代码实现判断奇环,只需要使用奇偶染色法就可以了,代码如下:
12345678910111213bool Dfs(int u, int c) { // vis : 0 - 未访问 ; 1 - 奇 ; 2 - 偶 vis[u] = c; for(int i = hd[u]; i; i = e[i].nt) { int v = e[i].to; if(vis[v] == c) return false; if(vis[v] == 0 && !Dfs(v, 3 ...