luogu_1
原创Posted Updated 数据结构39 minutes read (About 5784 words)0 visits

luogu_1

版权申明：本文为原创文章，转载请注明原文出处

原文链接：http://example.com/post/9c1a1a1.html

luogu_1

实践证明如果是要准备机试，只练leetcode是完全不够的！(╯▔皿▔)╯

并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 \(N,M\) ,表示共有 \(N\) 个元素和 \(M\) 个操作。

接下来 \(M\) 行，每行包含三个整数 \(Z_i,X_i,Y_i\) 。

当 \(Z_i=1\) 时，将 \(X_i\) 与 \(Y_i\) 所在的集合合并。

当 \(Z_i=2\) 时，输出 \(X_i\) 与 \(Y_i\) 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 \(Z_i=2\) 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

题解

对于此种频繁进行合并集合的要求，使用并查集可加快效率，即同一集合的两个数字的根父节点应相同

step1：每个数字的初始父节点为其本身

step2：需要合并两个数字时，首先寻找两个数字的根父节点，如果不同，就将其中一个根父节点的父节点更改为另一个的父节点

1
parent[find_p(x)] = find_p(y)

step3：判断两个数字是否属于同一集合，就是判断其根父节点是否相同

代码

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
#include<bits/stdc++.h>
using namespace std;

int n, m;
vector<int> parent;

int find_p(int x){
    while(parent[x] != x){
        x = parent[x];
    }
    return x;
}
void union_p(int x, int y){
    int p_x = find_p(x);
    int p_y = find_p(y);
    if(p_x != p_y){
        parent[p_x] = p_y;
    }
}

int main(){
    cin >> n >> m;
    parent.resize(n + 1, 0);
    for(int i = 1; i <= n; i++){
        parent[i] = i;
    }
    while(m--){
        int z, x, y;
        scanf("%d%d%d", &z, &x, &y);
        if(z == 1){
            union_p(x, y);
        }else if(find_p(x) != find_p(y)){
            printf("N\n");
        }else{
            printf("Y\n");
        }
    }
}

排序

题目描述

将读入的 \(N\) 个数从小到大排序后输出。

输入格式

第一行为一个正整数 \(N\)。

第二行包含 \(N\) 个空格隔开的正整数 \(a_i\)，为你需要进行排序的数。

输出格式

将给定的 \(N\) 个数从小到大输出，数之间空格隔开，行末换行且无空格。

思路

快速排序（前序遍历思想），首先选择一个枢轴，将数组分为前中后三部分，前为小于枢轴部分，中为等于枢轴部分，后为大于枢轴部分，然后分别再对前部分和后部分进行快速排序

代码

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
#include <bits/stdc++.h>
using namespace std;

int n;
int b[100001], m[100001], l[100001];
void quick_sort(int s, int e, vector<int> &a) {
    if (s >= e) return;
    // 随机选择一个枢轴并交换到起始位置
    int pivot_index = s + rand() % (e - s + 1);    
    int q = a[pivot_index];
    int b_i = 0, m_i = 0, l_i = 0;
    for(int i = s; i <= e; i++){
        if(a[i] > q) b[b_i++] = a[i];
        else if(a[i] < q) l[l_i++] = a[i];
        else m[m_i++] = a[i];
    }
    int a_i = s;
    for(int i = 0; i < l_i; i++) a[a_i++] = l[i];
    for(int i = 0; i < m_i; i++) a[a_i++] = m[i];
    for(int i = 0; i < b_i; i++) a[a_i++] = b[i];
    quick_sort(s, s + l_i - 1, a);
    quick_sort(e - b_i + 1, e, a);
}

int main() {
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    quick_sort(0, n - 1, a);
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", a[i]);
    }
    printf("%d\n", a.back());
}

堆

题目描述

给定一个数列，初始为空，请支持下面三种操作：

  1. 给定一个整数 \(x\)，请将 \(x\) 加入到数列中。
  2. 输出数列中最小的数。
  3. 删除数列中最小的数（如果有多个数最小，只删除 \(1\) 个）。

输入格式

第一行是一个整数，表示操作的次数 \(n\)。
接下来 \(n\) 行，每行表示一次操作。每行首先有一个整数 \(op\) 表示操作类型。 - 若 \(op = 1\)，则后面有一个整数 \(x\)，表示要将 \(x\) 加入数列。 - 若 \(op = 2\)，则表示要求输出数列中的最小数。 - 若 \(op = 3\)，则表示删除数列中的最小数。如果有多个数最小，只删除 \(1\) 个。

输出格式

对于每个操作 \(2\)，输出一行一个整数表示答案。

思路

小根堆，队头元素小，队尾元素大

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>> pq;

int main(){
    scanf("%d", &n);
    int op;
    while(n--){
        scanf("%d", &op);
        if(op == 1){
            int num;
            scanf("%d", &num);
            pq.push(num);
        }else if(op == 2){
            printf("%d\n", pq.top());
        }else{
            if(!pq.empty()) pq.pop();
        }
    }
}

线性筛素数

题目背景

本题已更新，从判断素数改为了查询第 \(k\) 小的素数
提示：如果你使用 cin 来读入，建议使用 std::ios::sync_with_stdio(0) 来加速。

题目描述

如题，给定一个范围 \(n\)，有 \(q\) 个询问，每次输出第 \(k\) 小的素数。

输入格式

第一行包含两个正整数 \(n,q\)，分别表示查询的范围和查询的个数。

接下来 \(q\) 行每行一个正整数 \(k\)，表示查询第 \(k\) 小的素数。

输出格式

输出 \(q\) 行，每行一个正整数表示答案。

思路

  • 思路一：暴力求解，对每一个数进行是否是素数的判断，当然，获得的结果是通篇TLE
  • 思路二：欧拉筛素数，确定比n小的所有素数，用的是排除法
    • step1：默认所有小于n的数初始状态为素数（>=2），但是维护一个最终素数列表最开始为空
    • step2：从头开始遍历，每个数如果初始状态为素数，就加入素数列表，同时将遍历的新数字遍历和最终素数列表相乘，并修改素数状态为false
    • step3：两个特殊情况，如果乘积大于n，就跳出循环，如果遍历的某个数字和遍历的最终素数列表某个数整除，则跳出循环，因为只要能整除，那后面的素数和这个数字的成绩可以通过这两个数字的乘积遍历，不需要重复计算

代码

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
#include<bits/stdc++.h>
using namespace std;
int n, q;
bool isPrime(int item){
    if(item == 1) return false;
    if(item == 2 || item == 3) return true;
    for(int i = 2; i <= sqrt(item); i++){
        if(item % i == 0) return false;
    }
    return true;
}
int main(){
    scanf("%d%d", &n, &q);
    vector<int> ans;
    int k;
    int start = 1;
    vector<int> q_num;
    while(q--){
        scanf("%d", &k);
        q_num.push_back(k);
        while(ans.size() < k){
            if(isPrime(start)) ans.push_back(start);
            start++;
        }
    }
    for(auto item : q_num){
        printf("%d\n", ans[item - 1]);
    }
    return 0;

}
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
#include<bits/stdc++.h>
using namespace std;

void euler(int n, vector<int> &primes){
    vector<bool> isPrime(n + 1, true);
    for(int i = 2; i <= n; i++){
        if(isPrime[i]){
            primes.push_back(i);
        }
        for(int prime : primes){
            if(i * prime > n) break;
            isPrime[prime * i] = false;
            if(i % prime == 0) break;
        }
    }
}
int main(){
    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> ans;
    int k;
    euler(n , ans);
    vector<int> q_num;
    while(q--){
        scanf("%d", &k);
        q_num.push_back(k);
    }
    for(auto item : q_num){
        printf("%d\n", ans[item - 1]);
    }
    return 0;

}

最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 \(N,M\)，表示该图共有 \(N\) 个结点和 \(M\) 条无向边。

接下来 \(M\) 行每行包含三个整数 \(X_i,Y_i,Z_i\)，表示有一条长度为 \(Z_i\) 的无向边连接结点 \(X_i,Y_i\)。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

思路

step1: 用将边信息作为tuple插入自定义排序的优先队列

step2: 优先队列的排序设置为按照权重值由低到高排序

step3: 在重构图时，为每个节点设置一个parent值，每插入一条从优先队列中获取的边，就合并该边两个点父节点

step4: 如果队列空了边的数量还没有 n-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
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;

int n, m;
vector<int> parent;

int find_f(int x){
    if(parent[x] != x) parent[x] = find_f(parent[x]);
    return parent[x];
}
void union_f(int x, int y){
    int x_f = find_f(x);
    int y_f = find_f(y);
    if(x_f != y_f) parent[x_f] = y_f;
}
int main(){
    scanf("%d%d", &n, &m);
    parent.resize(n + 1);
    for(int i = 1; i <= n; i++){
        parent[i] = i;
    }
    auto cmp = [](const tuple<int, int, int>& t1, const tuple<int, int, int>& t2) -> bool{
        return get<2>(t1) > get<2>(t2);
    };
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(cmp)> pq(cmp);
    int x, y, z;
    while(m--){
        scanf("%d%d%d", &x, &y, &z);
        pq.push(make_tuple(x, y, z));
    }
    int count = 0;
    int weights = 0;
    while(count != n - 1 && !pq.empty()){
        auto edge = pq.top();
        pq.pop();
        int x_f = find_f(get<0>(edge));
        int y_f = find_f(get<1>(edge));
        if(x_f != y_f){
            union_f(x_f, y_f);
            count++;
            weights += get<2>(edge);
        }
    }
    if(count == n - 1) printf("%d\n", weights);
    else printf("orz\n");
}

[NOIP2004 普及组] 火星人

题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 \(1,2,3,\cdots\)。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 \(1,2,3,4\) 和 \(5\)，当它们按正常顺序排列时，形成了 \(5\) 位数 \(12345\)，当你交换无名指和小指的位置时，会形成 \(5\) 位数 \(12354\)，当你把五个手指的顺序完全颠倒时，会形成 \(54321\)，在所有能够形成的 \(120\) 个 \(5\) 位数中，\(12345\) 最小，它表示 \(1\)；\(12354\) 第二小，它表示 \(2\)；\(54321\) 最大，它表示 \(120\)。下表展示了只有 \(3\) 根手指时能够形成的 \(6\) 个 \(3\) 位数和它们代表的数字：

三进制数 代表的数字
\(123\) \(1\)
\(132\) \(2\)
\(213\) \(3\)
\(231\) \(4\)
\(312\) \(5\)
\(321\) \(6\)

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

共三行。
第一行一个正整数 \(N\)，表示火星人手指的数目（\(1 \le N \le 10000\)）。
第二行是一个正整数 \(M\)，表示要加上去的小整数（\(1 \le M \le 100\)）。
下一行是 \(1\) 到 \(N\) 这 \(N\) 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式

\(N\) 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

思路

找到每一次数字演变的规律即可，假如对于一个要演变的数字1 2 3 5 4

step1：从后往前存入一个大根堆(大根堆里存值键对)，每访问一个数字就和大根堆第一个数字进行比较，如果比大根堆第一个数字大说明该数字是要被替换的对象

step2：从大根堆依次弹出，找到最小的比当前数字小的数，交换这两个位置的数

step3：如果当前要被替换的对象数字不是最后一个的前一个则要对这一段从小到大进行排序

代码

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
#include<bits/stdc++.h>
using namespace std;

int n, m;
vector<int> nums;
priority_queue<pair<int, int>> pq;

void clean_pq(){
    while(!pq.empty()) pq.pop();
}

int main(){
    scanf("%d%d", &n, &m);
    nums.resize(n);
    for(int i = 0; i < n; i++){
        scanf("%d", &nums[i]);
    }
    
    while(m--){
        clean_pq();
        for(int i = n - 1; i >= 0; i--){
            if(pq.empty() || nums[i] > pq.top().first){
                pq.push(make_pair(nums[i], i));
            }else{
                auto index = pq.top();
                while(!pq.empty() && pq.top().first > nums[i]){
                    index = pq.top();
                    pq.pop();
                }
                swap(nums[i], nums[index.second]);
                if(i != n - 2){
                    sort(nums.begin() + i + 1, nums.end());
                }
                break;
            }
        }
    }
    for(int i = 0; i < n - 1; i++){
        printf("%d ", nums[i]);
    }
    printf("%d\n", nums.back());
}

[NOIP2012 普及组] 摆花

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 \(m\) 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 \(n\) 种花，从 \(1\) 到 \(n\) 标号。为了在门口展出更多种花，规定第 \(i\) 种花不能超过 \(a_i\) 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

输入格式

第一行包含两个正整数 \(n\) 和 \(m\)，中间用一个空格隔开。

第二行有 \(n\) 个整数，每两个整数之间用一个空格隔开，依次表示 \(a_1,a_2, \cdots ,a_n\)。

输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 \(10^6+7\) 取模的结果。

思路

  • 思路1：dfs回溯求解，缺点：代码1中可能或重复计算相同s和相同flower_num的结果，s是起点，flower_num是剩余可填充值（TLE）
  • 思路2：用dp保存记忆，dp[i][j]保存使用前i种花总数为j的排列方式数

代码

  • 代码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
    #include<bits/stdc++.h>
    using namespace std;

    int n, m;
    int ans;
    vector<int> a;
    vector<int> min_a;
    int dfs(int s, int flower_num){
        if(s > n){
            return flower_num == m ? 1 : 0;
        }
        int max_possible = min(m - flower_num, a[s]);
        for(int i = min_a[i]; i <= max_possible; i++){
            result = (result + dfs(s + 1, flower_num + i)) % 1000007;
        }
        return result;
    }

    int main(){
        scanf("%d%d", &n, &m);
        a.resize(n + 1);
        min_a.resize(n + 1);
        int sum = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            sum += a[i];
        }
        for(int i = 1; i <= n; i++){
            min_a[i] = max(0, m - sum + a[i]);
        }
        dfs(1);
        printf("%d\n", ans);
    }

  • 代码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
    #include<bits/stdc++.h>
    using namespace std;

    int n, m;
    vector<int> a;
    vector<vector<int>> dp;
    int main(){
        scanf("%d%d", &n, &m);
        a.resize(n + 1);
        dp.resize(n + 1, vector<int>(m + 1, 0));
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= min(j, a[i]); k++){
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % 1000007;
                }
            }
        }
        
        printf("%d\n", dp[n][m]);
    }

书本整理

题目描述

Frank 是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以 Frank 首先将书按高度顺序排列在书架上。但是 Frank 发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k本书，使得书架可以看起来整齐一点。

书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有 \(4\) 本书：

\(1 \times 2\)
\(5 \times 3\)
\(2 \times 4\)
\(3 \times 1\)

那么 Frank 将其排列整齐后是：

\(1 \times 2\)
\(2 \times 4\)
\(3 \times 1\)
\(5 \times 3\)

不整齐度就是 \(2+3+2=7\)。

已知每本书的高度都不一样，请你求出去掉 \(k\) 本书后的最小的不整齐度。

输入格式

第一行两个数字 \(n\) 和 \(k\)，代表书有几本，从中去掉几本（\(1 \le n \le 100, 1 \le k<n\)）。

下面的 \(n\) 行，每行两个数字表示一本书的高度和宽度，均小于等于 \(200\)。

保证高度不重复

输出格式

一行一个整数，表示书架的最小不整齐度。

思路

  • 思路1：dfs回溯，用last_book保存最后的书本状态(TLE)
  • 思路2：用dp保留记忆，dp[i][j]表示前i个书本（一定选择第i个）选择j个的最小宽度绝对值差，dp[i][j] = min(dp[k][j-1] + abs(books[k].second - books[i].second)) for k in range(j-1, i-1)

代码

  • 代码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
    35
    36
    37
    38
    39
    40
    #include<bits/stdc++.h>

    using namespace std;

    int n, k;

    vector<pair<int, int>> books;
    int max_num = INT_MAX;

    void dfs(int item, int re_k, int path_num, pair<int, int> last_book){
        if (item >= n) {
            if(re_k == 0) {
                max_num = min(max_num, path_num);
            }
            return;
        }
        if (path_num >= max_num) return;
        if (n - item - 1 >= re_k){
            if(last_book.first != -1)
                dfs(item + 1, re_k, path_num + abs(books[item].second - last_book.second), books[item]);
            else
                dfs(item + 1, re_k, path_num, books[item]);
        }
        if (re_k > 0){
            dfs(item + 1, re_k - 1, path_num, last_book);
        }
    }

    int main(){
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; i++) {
            int h, w;
            scanf("%d%d", &h, &w);
            books.push_back(make_pair(h, w));
        }
        sort(books.begin(), books.end());
        dfs(0, k, 0, make_pair(-1, -1));
        printf("%d\n", max_num);
        
    }

  • 代码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
    #include<bits/stdc++.h>

    using namespace std;

    int n, k;

    vector<pair<int, int>> books;
    int max_num = INT_MAX;


    int main(){
        scanf("%d%d", &n, &k);
        books.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            int h, w;
            scanf("%d%d", &h, &w);
            books[i] = make_pair(h, w);
        }
        sort(books.begin(), books.end());
        vector<vector<int>> dp(n + 1, vector<int>(n - k + 1, 0));
        for(int i = 1; i <= n; i++){
            for(int j = 2; j <= min(i, n - k); j++){
                dp[i][j] = max_num;
                for(int k = j - 1; k < i; k++){
                    dp[i][j] = min(dp[i][j], dp[k][j - 1] + abs(books[k].second - books[i].second));
                }
            }
        }
        for(int i = n - k; i <= n; i++){
            max_num = min(max_num, dp[i][n - k]);
        }
        printf("%d\n", max_num);
        
    }

[USACO3.2] 阶乘问题

题目描述

也许你早就知道阶乘的含义，\(N\) 阶乘是由 \(1\) 到 \(N\) 相乘而产生，如：

\[12!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times 11\times 12=479{,}001{,}600\]

\(12\) 的阶乘最右边的非零位为 \(6\)。

写一个程序，计算 \(N\ (1\le N\le5\times 10^7)\) 阶乘的最右边的非零位的值。

注意：\(10{,}000{,}000!\) 的末尾有 \(2499999\) 个零。

输入格式

仅一行包含一个正整数 \(N\)。

输出格式

一个整数，表示最右边的非零位的值。

思路

因为会影响结果的就是整除5的数，先去掉所有能整除5的的数

1
2
2	3   4   6	7	8	9	 11	  12  13   14  16  17  18  19  21 ...
2 	6 	4 	4 	8 	4 	6 	  6	   2   6    4   4   8   4   6	6...

可以发现规律，因此实际上只需要考虑个位数上的运算就可以了

接下来需要关注小于n的所有5的倍数，分别为

1
5 5*2 ... 5*(n/5)

所以最终答案变成了 \(5^{n/5}\) * (n/5)!

后者运算方式和前面相同，而根据上面分析我们确认最终答案肯定在{2, 4, 6, 8}集合，而该集合任意一个数*10不会更改最后一个数字，同样*6也不会更改，所以4 * 2 * 5 = 4 * 2 * 8的结果（因为2 * 8= 16）

所以\(5^{n/5}\)相当于\(8^{n/5}\)，可以通过找规律得到最终结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> tail = {6, 8, 4, 2};
int main() {
    cin >> n;
    int res = 1;
    while(n > 0){
        for(int i = 1; i <= n % 10; i++){
            if(i != 5) res = (res * i) % 10;
        }
        n = n/5;
        res = res * tail[n % 4] % 10;
    }
    cout << res << endl;
    return 0;
}

[NOIP2007 普及组] Hanoi 双塔问题

题目描述

给定 A、B、C 三根足够长的细柱，在 A 柱上放有 \(2n\) 个中间有孔的圆盘，共有 \(n\) 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为 \(n=3\) 的情形）。

现要将这些圆盘移到 C 柱上，在移动过程中可放在 B 柱上暂存。要求：

  1. 每次只能移动一个圆盘；
  2. A、B、C 三根细柱上的圆盘都要保持上小下大的顺序。

任务：设 \(A_n\) 为 \(2n\) 个圆盘完成上述任务所需的最少移动次数，对于输入的 \(n\)，输出 \(A_n\)。

输入格式

一个正整数 \(n\)，表示在 A 柱上放有 \(2n\) 个圆盘。

输出格式

一个正整数, 为完成上述任务所需的最少移动次数 \(A_n\)。

思路

每次只能移动一个，所以C上第一个正式放的只能是最大的圆盘，为了能移动最大的圆盘且保证C上为空，首先是把上面(n-1) *2的圆盘移到B，当最大的圆盘放到C之后，接下来就是把上面(n-1) *2的圆盘从B放回C，所以把n *2圆盘从A放到C之前，首先要把(n-1) *2圆盘搬两次，外加最大的圆盘要搬一次，所以n和n-1的规律就是An = An-1 * 2 + 1，最后结果要乘以2，因为每个圆盘有两个

这里直接用longlong也会超数据限制，所以要用数组代替

代码

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
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> ans(1, 1);
void multi_a(){
    int cin = 0;
    for(auto& i : ans){
        i = i * 2 + cin;
        cin = 0;
        if(i >= 10){
            cin = 1;
            i %= 10;
        }
    }
    if(cin == 1) ans.push_back(1);
}
void add_a(){
    for(auto& i : ans){
        i += 1;
        if(i < 10) return;
        i %= 10;
    }
    ans.push_back(1);
}
int main(){
    cin >> n;

    while(--n){
        multi_a();
        add_a();
    }
    multi_a();
    for(int i = ans.size() - 1; i >= 0; i--){
        cout << ans[i];
    }
}

[NOIP2001 提高组] 统计单词个数

题目描述

给出一个长度不超过 \(200\) 的由小写英文字母组成的字母串（该字串以每行 \(20\) 个字母的方式输入，且保证每行一定为 \(20\) 个）。要求将此字母串分成 \(k\) 份，且每份中包含的单词个数加起来总数最大。

每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th。

单词在给出的一个不超过 \(6\) 个单词的字典中。

要求输出最大的个数。

输入格式

每组的第一行有两个正整数 \(p,k\)。 \(p\) 表示字串的行数，\(k\) 表示分为 \(k\) 个部分。

接下来的 \(p\) 行，每行均有 \(20\) 个字符。

再接下来有一个正整数 \(s\)，表示字典中单词个数。 接下来的 \(s\) 行，每行均有一个单词。

输出格式

\(1\)个整数，分别对应每组测试数据的相应结果。

思路

使用数学归纳法，当我们要求前i个字符串要分成j份的最大数，可以分为两部分，第一部分是前l个字符串分为j-1份，然后从l开始到i为一份，找这份中的单词数目，所以dp[i][j] = max(dp[l][j-1] + nums(str.substr(l+1, i)))其中nums()代表该段字符串的单词数量

代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>

using namespace std;


int p, k;
int s;
string str;

struct preTree {
    int status;
    bool end;
    vector<preTree*> nextTree;

    preTree(int status = 1, bool end = false) : status(status), end(end), nextTree(26, nullptr) {}
    ~preTree() {
        // 释放所有子节点，防止内存泄漏
        for (auto& next : nextTree) {
            if (next != nullptr) {
                delete next;
            }
        }
    }
};
preTree* tree = new preTree();
vector<vector<int>> dp;
// 统计在前缀树中匹配到的单词数量
int nums(string ss, preTree* tt){
    int res = 0;
    for(int i = 0; i < ss.size(); i++){
        if(tt->nextTree[ss[i] - 'a'] != nullptr){
            preTree* tmp = tt;
            int j = i;
            while(j < ss.size() && tmp->nextTree[ss[j] - 'a'] != nullptr){
                if(tmp->nextTree[ss[j] - 'a']->end == true){
                    res++;
                    break;
                }
                tmp = tmp->nextTree[ss[j] - 'a'];
                j++;
            }
        }
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);  // 优化I/O
    cin.tie(0);
    cin >> p >> k;
    string ss;
    str = " ";
    while(p--){
        cin >> ss;
        str += ss;
    }
    dp.resize(str.size() + 1, vector<int>(k + 1, 0));
    cin >> s;
    while (s--) {
        cin >> ss;
        preTree* tt = tree;
        for (int i = 0; i < ss.size(); i++) {
            int index = ss[i] - 'a';
            if (tt->nextTree[index] == nullptr) {
                tt->nextTree[index] = new preTree();  // 按需创建节点
            }
            tt = tt->nextTree[index];
        }
        tt->end = true;  // 标记该节点为单词结尾
    }
    for(int i = 1; i <= str.size(); i++){
        for(int j = 0; j <= i - 1 && j <= k; j++){
            if(j == 0){
                ss = str.substr(1, i);
                dp[i][j] = max(dp[i][j], nums(ss, tree));
                continue;
            }
            for(int l = j + 1; l <= i; l++){
                ss = str.substr(l, i - l + 1);
                dp[i][j] = max(dp[i][j], dp[l - 1][j - 1] + nums(ss, tree));
            }
        }
    }
    cout << dp[str.size()][k] << endl;
    return 0;

}

luogu_1

http://example.com/post/9c1a1a1.html

Author

yyyyyyxnp

Posted on

2024-10-08

Updated on

2024-10-15

Licensed under

#
You need to set install_url to use ShareThis. Please set it in _config.yml.

Like this article? Support the author with

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Follow

Recents

×