FXJFXJ
0%

发表于 更新于 分类于
本文字数： 410 阅读时长 ≈ 1 分钟

最长不下降子序列

这里的注释说明更易理解 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const int MAXN = N;
int a[MAXN];
int d[MAXN];

int main()
{
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    if (n == 0) // 0个元素特判一下
    {
        cout<<'0'<<'\n';
        return 0;
    }
    d[1] = a[1]; //初始化
    int len = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] >= d[len])
            d[++len] = a[i]; 
    //如果可以接在len后面就接上，如果是最长上升子序列，这里变成>
        else//否则就找一个最该替换的替换掉
        {
            int j = upper_bound(d + 1, d + len + 1, a[i]) - d; 
//找到第一个大于它的d的下标，如果是最长上升子序列，这里变成lower_bound
            d[j] = a[i];
        }
    }
    cout<<len<<'\n';
    return 0;
}

最长不上升子序列

阅读全文 »

发表于 更新于 分类于
本文字数： 1k 阅读时长 ≈ 4 分钟

kruskal

Kruskal 算法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>//kruskal算法
using namespace std;
#define int long long
int n, m, ans = 0;
int u, v, cnt = 0;
struct edge
{
    int x, y, val;
} a[200010];
int f[200010];
int find(int x)
{
    // while(x!=f[x])
    //     x = f[x] = f[f[x]];
    // return x;
    if (f[x] == x)
        return x;
    return f[x] = find(f[x]);
}
void kruskal()
{
    for (int i = 1; i <= m; i++)
    {
        u = find(a[i].x);
        v = find(a[i].y);
        if (u == v)
            continue;
        ans += a[i].val;
        f[u] = v;
        if (++cnt == n - 1)
            break;
    }
}
int cmp(edge a, edge b)
{
    return a.val < b.val;
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 1; i <= m; i++)
        cin >> a[i].x >> a[i].y >> a[i].val;
    sort(a + 1, a + 1 + m, cmp);
    kruskal();
    if (cnt != n - 1)
        cout << "orz" << endl;
    else
        cout << ans << endl;
}

Prim 算法

阅读全文 »

发表于 分类于
本文字数： 361 阅读时长 ≈ 1 分钟

阶：

  • 定义：满足同余式 \(a^n \equiv 1 \pmod m\) 的最小正整数 \(n\) 存在，这个 \(n\) 称作 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\) 或 \(\operatorname{ord}_m(a).\)

由欧拉定理可知，对 \(a\in \mathbf{Z}\)，\(m\in\mathbf{N}^{*}\)，若 \((a,m)=1\)，则 \(a^{\varphi(m)}\equiv 1\pmod m\).

  • 性质：
阅读全文 »

发表于 分类于
本文字数： 369 阅读时长 ≈ 1 分钟

1 威尔逊定理

内容： 对于素数 \(p\) 有 \((p-1)!\equiv -1\pmod p.\)

推论： \((p-1)!\equiv0(mod\) \(p),(p>4\land p\) 为合数$ )$

计算余数算法:

实现 \(n!\) % \(p\).

阅读全文 »

发表于 更新于 分类于
本文字数： 316 阅读时长 ≈ 1 分钟

欧几里得算法：\(gcd(a,b)=gcd(b,a\) \(mod\) \(b)\)

证明

扩展欧几里得算法\(:(Extended Euclidean algorithm, EXGCD)\)

常用于求 \[ ax+by=gcd (a, b) \] 的一组可行解。

\(ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)\)

阅读全文 »

发表于 分类于
本文字数： 244 阅读时长 ≈ 1 分钟

算法学习笔记(53): 拓扑排序 - 知乎

以下是一个 \(O(n+m)\) 的实现（ \(n,m\) 分别表示点数和边数），利用了队列： 一般使用的是邻接表存储图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// deg 是入度，在存图的时候需要录入数据
// A 是排序后的数组
int deg[MAXN], A[MAXN];
bool toposort (int n)
{
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!deg[i])
            q.push (i);
    while (!q.empty ())
    {
        int t = q.front ();
        q.pop ();
        A[cnt++] = t;
        for (auto to : edges[t])
        {
            deg[to]--;
            if (!deg[to]) // 出现了新的入度为 0 的点
                q.push (to);
        }
    }
    return cnt == n;
}

返回值为是否成功进行拓扑排序，也即是否存在环。也就是说拓扑排序是可以用来简单地判环的。有时会要求输出字典序最小的方案，这时把 queue 改成 priority_queue 即可，复杂度会多一个 \(\log\)。 [[B3644 拓扑排序 & 家谱树 - 洛谷]][B3644 【模板】拓扑排序 / 家谱树 - 洛谷](https://www.luogu.com.cn/problem/B3644) 练习： [[510C]] Problem - C - Codeforces

发表于 分类于
本文字数： 783 阅读时长 ≈ 3 分钟

线性筛法

线性筛法(也称为 \(Euler\) 筛法（欧拉筛法）) 最常用！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void init(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * pri[j] > n) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) {
        // i % pri[j] == 0
        // 换言之，i 之前被 pri[j] 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i乘上其他的质数的结果一定会被
        // pri[j]的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

\(Eratosthenes\) 筛法

\(Eratosthenes\) 筛法即埃拉托斯特尼筛法, 简称埃氏筛法。时间复杂度是 \(O(n\log\log n)\)。

阅读全文 »

发表于 更新于 分类于
本文字数： 226 阅读时长 ≈ 1 分钟

1 B3612 【深进1.例1】求区间和 - 洛谷

1 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, a[100010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++)
        a[i] = a[i - 1] + a[i];
    cin >> m;
    for (int i = 0; i < m; i++)
        cin >> l >> r,cout << a[r] - a[l - 1] << '\n';
}

2 题目描述

给定 \(n\) 个正整数组成的数列 \(a_1, a_2, \cdots, a_n\) 和 \(m\) 个区间 \([l_i,r_i]\)，分别求这 \(m\) 个区间的区间和。 ## 3 输入格式 \[ \boxed{ \begin{align} &n &\\ &a_{1} \ a_2 \cdots \ a_n \\ &m \\&l_1\ \ r_1 \\&l_2\ \ r_2\\ &\vdots \\&l_m\ r_m​ \end{align} } \]

阅读全文 »

发表于 分类于
本文字数： 367 阅读时长 ≈ 1 分钟

1 内容：

2 设 \(a,b\) 是不全为零的整数，则存在整数 \(x,y\), 使得 \(ax+by=gcd(a,b)\).

2.1 证明：

设取 \(x_0\), \(y_0\) 时，\(ax+by\) 的最小整数是 \(s\).即 \(ax_0+by_0\) = \(s\)

因 \(gcd(a,b)|ax_0\) ， \(gcd(a,b)|ay_0\)

阅读全文 »