FXJFXJ
0%

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

两个数有： \(gcd(a,b)\times lcm(a,b)=a\times b\)

求两个数的最小公倍数，先求出最大公约数即可。

多个数： 当我们求出两个数的 \(gcd\) 时，求最小公倍数是 \(O(1)\) 的复杂度。那么对于多个数，我们其实没有必要求一个共同的最大公约数再去处理，最直接的方法就是，当我们算出两个数的 \(gcd\)，或许在求多个数的 \(gcd\) 时候，我们将它放入序列对后面的数继续求解，那么，我们转换一下，直接将最小公倍数放入序列即可

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

P3379 【模板】最近公共祖先（LCA） - 洛谷 ## 简介 LCA --算法竞赛专题解析（29） - 罗勇军999 - 博客园 Lowest Common Ancestor LCA 是指在一棵树中，距离两个点最近的两者的公共节点。也就是说，在两个点通往根的道路上，肯定会有公共的节点，我们就是要求找到公共的节点中，深度尽量深的点。还可以表示成另一种说法，就是如果把树看成是一个图，这找到这两个点中的最短距离。 定义 性质 LCA 算法有在线算法也有离线算法，所谓的在线算法就是实时性的，而离线算法则是要求一次性读入所有的请求，然后在统一得处理。而在处理的过程中不一定是按照请求的输入顺序来处理的。说不定后输入的请求在算法的执行过程中是被先处理的。

这里主要是讨论 tarjan 算法|与|倍增算法(待更)与树链剖分(需要学到高级数据结构(待更))的做法，这三种可以解决几乎所有问题。倍增和树链剖分用的尤其多。具体其他做法看 oi. wiki 即可

最近公共祖先 (Lowest Common Ancestor) - 知乎有详细说明 也可以看董晓算法的视频 322 Tarjan算法 P3379【模板】最近公共祖先（LCA）_哔哩哔哩_bilibili 董晓算法很详细的讲了三种方法：倍增，tarjan，树链剖分,甚至更深入的知识。

朴素算法

倍增算法

阅读全文 »

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

1 P3375 【模板】KMP - 洛谷

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;
string s1, s2;
int ne[1000010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> s1 >> s2;
    // ne[0] = 0;
    for (int i = 1, j = 0; i < s2.length(); ++i)
    {
        while (j && s2[i] != s2[j])
            j = ne[j - 1];
        if (s2[i] == s2[j])
            j++;
        ne[i] = j;
    }
    for (int i = 0, j = 0; i < s1.length(); ++i)
    {
        while (j && s1[i] != s2[j])
            j = ne[j - 1]; // 不断前移j指针，直到成功匹配或移到头为止
        if (s1[i] == s2[j])
            j++; // 当前位匹配成功，j指针右移
        if (j == s2.length())
        {
            cout << i - j + 2 << '\n'; //输出对应匹配的位置
            // 对s1[i - j + 1 .. i]进行一些操作
            j = ne[j - 1];
        }
    }
    for (int i = 0; i < s2.length(); i++)
        cout << ne[i] << ' ';
}

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

简单来说就是 [[图论/spfa]] 与 [[图论/dijkstra]] 连用

\(Johnson\) 算法则通过另外一种方法来给每条边重新标注边权。

我们新建一个虚拟节点（在这里我们就设它的编号为 \(0\)）。从这个点向其他所有点连一条边权为 \(0\) 的边。

接下来用 \(Bellman-Ford\) 算法求出从 \(0\) 号点到其他所有点的最短路，记为 \(h_i\)。

假如存在一条从 \(u\) 点到 \(v\) 点，边权为 \(w\) 的边，则我们将该边的边权重新设置为 \(w+h_u-h_v\)。

阅读全文 »

发表于 分类于
本文字数： 43 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
//可以生成一个序列
#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> p(10);
    iota(p.begin(), p.end(), 1);
    for( auto v:p)
        cout << v << " ";
}
1
2
//output
1 2 3 4 5 6 7 8 9 10

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

递归求法： 

1
2
3
4
5
//用的最多
int gcd(int a, int b)//快速算最大公因数
{
    return !b ? a : gcd(b, a % b);
}
迭代求法： 
1
2
3
4
5
6
7
8
9
int gcd(int a, int b) {
  while (b != 0) {
    int tmp = a;
    a = b;
    b = tmp % b;
  }
  return a;
}

C++14 可用 __gcd (a, b)

阅读全文 »

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

P3371 P4779

[[图论/链式前向星存图]] # 堆优化版 ：\(O(mlogm)\) 

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
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
//#define int long long
int n, m, s;
struct
{
    int v, w, next;
} a[200010];
bool vis[100010];
int dis[100010];
int cnt = 1;
int head[100010];
void add(int u, int v, int w)//链式前向星存图
{
    a[cnt].w = w;
    a[cnt].v = v;
    a[cnt].next = head[u];
    head[u] = cnt++;
}
#define pll pair<int, int>
priority_queue<pll, vector<pll>, greater<pll>> q;
void dijkstra(int s)
{
    memset(dis, 0x7f, sizeof dis);
    // for (int i = 1; i <= n; i++)
    //     dis[i] = INT_MAX;//弱化版还需要ll
    q.push({0, s});
    dis[s] = 0;
    while (!q.empty())
    {
        pll t = q.top();
        q.pop();
        int u = t.second;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = a[i].next)
        {
            int v = a[i].v;
            if (dis[v] > dis[u] + a[i].w)
            {
                dis[v] = dis[u] + a[i].w;
                q.push({dis[v], v});
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
}

朴素写法 ：\(O(n^2)\)

阅读全文 »

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

在某些题有奇效

bitset

1 Bitset 的构造函数：

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
//1.默认构造函数 :0
bitset<10> a;			//a:0000000000

//2.用一个数值初始化

(1)当用一个数值去构造的时候，其实就是将数值在内存中的存储方式显示出来。(数值在内存中是以补码形式存储的)
(2)若bitset的位数n小于数值的位数,只取数值(小端的)前n位初始化给bitset

bitset<4> a(-16);		//-16的补码为11111111.....10000,a有4位,因此a:0000

bitset<5> a(17);		 //17的补码为00000000.....10001,a有5位,因此a:10001

bitset<6> a(-8);		//-8的补码为 11111111.....11000,a有6位,因此a:111000

bitset<7> a(8);			 //8的补码为 00000000.....01000,a有7位,因此a:0001000

//3.用字符串string 或者 char[]初始化

//以string为例,char[]与其用法相同 

string b = "100101111";	//这里特别注意，bitset的size和字符串长度不匹配的时候如何构造

bitset<3> a(b);			//a:100			  //当bitset的size小于等于字符串长度，取字符串的前size位

bitset<6> a(b);			//a:100101

bitset<9> a(b);			//a:100101111

bitset<12> a(b);		//a:000100101111  //当bitset的size大于字符串长度，进行补零

运算符重载[], 支持下标从 0 开始访问, 与数组类似

阅读全文 »

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

示例 P1020 导弹拦截 用到了求最长下降子序列和最长上升子序列 ，还用到了 \(Dilworth 定理\) 证明第二问是最长上升子序列。

若 \(n=0\)，则需要特判。 # 最长上升子序列

目前我笔记有三种写法，第一种即可。 推荐 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
#include<bits/stdc++.h>//标准模板
using namespace std;
const int MAXN = N;
int a[MAXN], d[MAXN];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    //if(n==0)//后面不再重复写出
    //{
    //    cout << '0' << endl;
    //    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];
        else
        {
            int pos = lower_bound(d + 1, d + 1 + len, a[i]) - d;
            d[pos] = a[i];
        }
    }
    cout << len << endl;
}

推荐 2

阅读全文 »

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

P1439【模板】最长公共子序列 下面的模板代码只适用于每个数字只出现一次。 ## 1 【模板】最长公共子序列: \(O(nlogn)\) ### 1.1 模板：[[最长上升子序列|LIS]] 的应用 [[最长上升子序列]]

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int a[maxn],d[maxn],idx[maxn];
int LIS(int n) {//完全用的LIS模板，统一模板更不容易错。
    if(!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];
        else
        {
            int pos = lower_bound(d + 1, d + 1 + len, a[i]) - d;
            d[pos] = a[i];
        }
    }
    return len;
}
int main() {
    int n,temp;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {cin>>temp;idx[temp]=i;}
    for(int i=1;i<=n;i++) {a[i]=idx[a[i]];}
    int ans=LIS(n);
    cout << ans << endl;
}

1.2 手写二分

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
# 1.2 #include <bits/stdc++.h>
using namespace std;
int n;
int a[100010], b[100010];
int m[100010], f[100010];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], m[a[i]] = i;
    memset(f, 0x7f, sizeof f);
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    int len = 0;
    f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = 0, r = len, mid;
        if (m[b[i]] > f[len])
            f[++len] = m[b[i]];
        else
        {
            while (l < r)
            {
                mid = (l + r) / 2;
                if (f[mid] > m[b[i]])
                    r = mid;
                else
                    l = mid + 1;
            }
            f[l] = m[b[i]];
        }
    }
    cout << len << endl;
}

2 最长公共子序列

阅读全文 »