基于洛谷113号题单对线性表的总结

1 P3156 询问学号

传送门

没啥好说的，跳

2 P3613 寄包柜

传送门

二维数组秒了

虽然这题的题目是寄包柜，但他真的是考察寄包柜吗？是的

根据问题找答案，显然对于每个问题有三个元素:第i个寄包柜，第j个格子里的物品。如果用二维数组，显然105 * 109会MLE，即使是动态数组也不太妥。

所以呢？最简单的方法当然是STL大法！

但有个问题，一个map元素只有两个值，比如map<int,int> b;但我们有三个元素。

aabandon

2.1 方法1

把第一个int改成long long，将第一个元素改成105*i + j

2.2 方法2

map<int,int> b[MAX]; b[i][j] = k;

3 P1449 后缀表达式

传送门

很显然，这题需要用到栈。当输入不是数字时，将这个数字压入栈。

1
2
3
4
5
while(i < postfix.length() && isdigit(postfix[i]))
{
   val = val * 10 + (postfix[i] - '0');//这里注意，由于是从char型字符转化为int型字符，所以需要postfix[i] - '0'
   i++;
}

当输入不是数字时，就从栈中弹出两个数字进行运算，注意顺序：第一个弹出来的是val2，第二个弹出来的是val1，这对于减法和除法很重要

AC代码 

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
#include<iostream>
#include<stack>
#include<string>

using namespace std;

string postfix;
stack<int> s;

int main()
{
    cin >> postfix;
    
    int i = 0;
    
    while(i < postfix.length())
    {
        if(postfix[i] == '@') break;
        else if(isdigit(postfix[i]))
        {
            int t = 0;
            while(isdigit(postfix[i]))
            {
                t = t * 10 + (postfix[i++] - '0');
            }
            i++;
            s.push(t);
        }
        else
        {
            int val2 = s.top(); s.pop();
            int val1 = s.top(); s.pop();
            char c = postfix[i];
            switch(c)
            {
                case '+' : s.push(val1 + val2); break;
                case '-' : s.push(val1 - val2); break;
                case '*' : s.push(val1 * val2); break;
                case '/' : s.push(val1 / val2); break;
            }
            i++;
        }
    }
    
    cout << s.top() << endl;
    return 0;
}

------------------------手动分割线--------------------

单纯做这题其实并不难，但是我想到了一个问题：前缀表达式和前序遍历、中缀表达式和中序遍历、后续表达式和后序遍历之间是否有关系？

根据我自己的探索，发现其实前、中、后缀表达式可以说是前、中、后序遍历的一种特殊形式

举个例子，对于3*(5-2)+7这个表达式，可以转化为树。

很显然，我们最先算3*(5-2)与7的和，其次算3和(5-2)的乘积，要算5-2我们要先做5和2的减法，因此*的子节点是3和-。显然-的子节点是5和2。最后计算的是

1
2
3
4
5
6
7
    +
   / \
  *   7
 / \
3   -
   / \
  5   2

前缀表达式(前序遍历)： +*3-5.2.7

中缀表达式(中序遍历) 3*5-2+7

后缀表达式(后序遍历): 3.5.2.-*7+

4 P1996

传送门

这题有两个方法：模拟法和递推法。模拟法更加直观，而递推法更加优雅

4.1 模拟法

模拟法很直观，直接模拟整个出圈的过程，可以使用队列来解决。

将所有小朋友排好编号排成一列，在出列时报数。如果报数不是m的倍数则入列；否则直接出列，同时输出小朋友的编号

4.1.1 AC代码

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
#include<iostream>
#include<queue>

using namespace std;

int n, m;

void joes(int n, int m)
{
    queue<int> q;

    for (int i = 1; i <= n; i++)
        q.push(i);

    int t = 0;

    while(!q.empty())
    {
        t++;
        if(t % m != 0)
        {
            int x = q.front();
            q.pop();
            q.push(x);
        }
        else
        {
            cout << q.front() << " ";
            q.pop();
        }
    }

    cout << endl;
}

int main()
{
    cin >> n >> m;
    
    joes(n, m);
    
    return 0;
}

4.2 数学法(约瑟夫环递推公式)

约瑟夫环问题有一个著名的递推公式解法。设f(n,m)为n个人报数，每次数到m出列的最终胜利者，则有递推关系：

f(n,m) = (f(n - 1), m) mod n

从只有一个人开始推，直到n个人。基于此我们可以反向推导出每一步出圈的人的编号。

现在让我们进行递推公式

设f(n, m)为n个人报数，每次数到m的情况下，最后那个人的位置。

当只有一个人的时候，(即n=1)，很显然此人(编号'0')是最后的存活者

基于前一个数量的结果，但是因为我们现在有 n 个人，所以我们要在这个位置基础上加上 m（因为每次都是数到 m 的人出列），然后对当前人数 n 取模，以确保我们得到的索引是有效的（即不会超出当前的人数范围）

举个例子

假设现在有3个人，每次数到2时出列，我们要找到最后存活的位置

  1. f(1,2) = 0;
  2. f(2,2) = (f(1,2) + 2) % 2 = 0;
  3. f(3,2) = (f(2,2) + 2) % 3 = 2;

4.2.2 AC代码

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
#include<iostream>
#include<vector>

using namespace std;

vector<int> josephus(int n, int m)
{
    vector<int> people(n);
    for (int i = 0; i < n; i++)
        people[i] = i + 1;
        
    vector<int> result;
    int index = 0;
    
    while(!people.empty())
    {
        index = (index + m - 1) % people.size();
        result.push_back(people[index]);
        people.erase(people.begin() + index);
    }
    
    return result;
}

int main()
{
    int n, m;
    
    cin >> n >> m;
    
    vector<int> order = josephus(n, m);
    
    for (int person : order)
        cout << person << " ";
        
    cout << endl;
    
    return 0;
}

5 P1160 队列安排

传送门

此题有两个难点： 1. 如何插入同学？ 2. 如何删除同学？

5.1 如何插入同学？

对于此类需要频繁插入的问题，数组显然不行，第一反应当然是链表。

我们可以把每个同学想象成互相握住肩膀，比如a同学的右边是b同学，a同学握着b同学的肩膀，b同学握住a同学的肩膀。如果想要在a同学的右边插入c同学，首先要让c同学握住a同学，之后c同学握住a同学握着的b同学，接着a同学右边的b同学握住a同学的手转为握住c同学，a同学握住b同学的手转为握住c同学。

这题可以使用结构体，但结构体比数组慢，所以我们可以用数组来模拟结构体。

但是要注意避免数据溢出，即第一个同学左边的同学是谁？所以对于同学的编号我们应该从1开始而不是从0开始

5.2 如何删除同学？

当时第一反应是通过一个双重循环，即每输入一个需要删除的i号同学就搜索一遍链表，将i号同学改为0。输出时进行检查，如果是0则不输出。但显然时间复杂度则为O(N2)了。

正难则反，以退为进。我们不妨先用一个布尔数组标记所有要删除的学号，接着依次输出链表，当遇到要输出的学号被标记时则不输出，时间复杂度O(N)。

5.3 AC代码

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
#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int l[N], r[N], res[N];
int n;

int main()
{
    scanf("%d", &n);
    
    r[0] = 1, l[n + 1] = 1;
    r[1] = n + 1, l[1] = 0;
    
    for(int i = 2; i <= n; i++)
    {
        int k, p;
        scanf("%d%d", &k, &p);
        
        if(p == 0)
        {
            r[i] = k;
            l[i] = l[k];
            r[l[k]] = i;
            l[k] = i;
        } else if(p == 1)
        {
            l[i] = k;
            r[i] = r[k];
            l[r[k]] = i;
            r[k] = i;
        }
    }
    
    int idx = 1, temp = 0;
    
    while(r[temp] != n + 1)
    {
        res[idx++] = r[temp];
        temp = r[temp];
    }
    
    int m;
    bool isDeleted[N] = {false};
    
    scanf("%d", &m);
    
    while(m--)
    {
        int x;
        scanf("%d", &x);
        isDeleted[x] = true;
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(!isDeleted[res[i]])
            printf("%d ", res[i]);
    }
    
    puts("");
    
    return 0;
    
}

6 P1540 机器翻译

传送门

解题思路：

  1. 初始化
    • 使用一个固定大小的队列或列表来模拟内存
    • 使用一个计算器来记录查词典的次数
  2. 对于文章中的每个单词
    • 对于文章中每个单词首先要判断他是否在内存（这里用队列来模拟）中
      • 如果在，不需要做任何操作
      • 如果不在
        • 如果内存未满，直接将单词添加到内存中
        • 如果队列已满，移除最先进入内存的单词(直接pop())，然后将新单词添加到内存中
        • 每次将单词加入内存时，增加查词典的计数
  3. 输出结果
    • 文章处理完成后，输出查词典的总次数

AC代码 

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<iostream>
#include<deque>

using namespace std;

deque<int> words;
int m, n;//m为内存容量，n为文章长度
int res;
bool isFound;

int main()
{
    cin >> m >> n;
    
    while(n -- )
    {
        int x;
        
        cin >> x;
        
        isFound = false;
        
        for(auto it = words.begin(); it != words.end(); it ++ )
        {
            if(x == *it) 
            {
                isFound = true;
                break;
            }
        }
        
        if(!isFound)
        {
            res ++ ;
            
            if(words.size() >= m)
            {
                words.pop_front();
                words.push_back(x);
            }else words.push_back(x);
        }
    }
    
    cout << res << endl;
    return 0;
}

以上是本蒟蒻的代码，时间复杂度O(N2)。翻看题解，看到一位大佬的代码，居然将时间复杂度做到O(N)

用内存换时间，这是很划算的做法。 * 开辟两个数组a[MAX]、b[MAX] * 用b[MAX]表示依次存入的单词,比如b[1] = 3, b[2] = 5,表示第一个存入的单词是3，第二个存入的单词是5 * a[MAX]表示查询单词是否在区域中，如果在则为1，不在为0 * 用左、右指针计算内存的长度

大佬的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n,m,x,ans,l,r,a[1005],b[1005];
int main()
{
    cin>>m>>n;
    l=0;r=0;//初始化两个指针
    for (int i=1;i<=n;i++)
    {
         scanf("%d",&x);//边读入边做
         if (a[x]==0) 
         {
             ans++;
            r++;b[r]=x;a[x]=1;//因为每次遇到新单词都要做这些操作，不如搬到判断语句外做，这样程序更简洁
            if (r>m) {l++;a[b[l]]=0;}
        }
    }
    cout<<ans;
    return 0;//千万不能忘记打这句，不然在比赛中会出错
}
C++学习
#数据结构 #C++
基于洛谷113号题单对线性表的总结
http://crazythursdayv50tome.cn/2024/06/03/113/
Author
饺子
Posted on
June 3, 2024
Licensed under