玩命加载中 . . .

洛谷官方提单——线性表题解

编程算法题解 洛谷 线性表
算法和程序设计
发布日期:   2020-05-02
文章字数:   1.8k
阅读时长:   8 分
阅读次数:  

题目0：询问学号

简单到不能简单的题目，无解释。

#include<iostream>
using namespace std;
long long memo[2000001];
int main() {
    long long n,m,x;
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>memo[i];
    for(int i=1;i<=m;++i) {
        cin>>x;
        cout<<memo[x]<<endl;
    }
    return 0;
}

题目1：寄包柜

由于我们存储的的大小不确定，所以应该使用链表的/vector（如果你是用数组那么你就等着MLE吧哈哈哈哈）

#include <iostream>
#include <vector>
using namespace std;
struct node{
    vector<int> num, w;
    int cnt = 0;
}memo[100050];
int main(){
    int n, q, kind, cabinet, lattice, k;
    cin >> n >> q;
    while (q--){
        cin >> kind;
        if (kind == 1){
            cin >> cabinet >> lattice >> k;
            memo[cabinet].cnt++; 
            memo[cabinet].num.push_back(lattice);
            memo[cabinet].w.push_back(k);
        }
        else{
            cin >> cabinet >> lattice;
            for (int i = memo[cabinet].cnt - 1; i >= 0; i--){
                if (memo[cabinet].num[i] == lattice){
                    cout << memo[cabinet].w[i] << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

题目2：后缀表达式

这里提前介绍下栈的几种题目，包括但不限于括号匹配，栈混洗问题，汉诺依塔问题等，这个后缀表达式就是最直接的栈的问题。

题目做法如下，创建一个数字栈，当其出现数字则全部存入数字栈，当出现符号的时候，取数字栈的最上面两个元素进行运算再放入数字栈，直至栈元素为最后一个元素的时候，即为答案。

#include<stdio.h>
#include<stack>
using namespace std;
stack<int> s;
char ch;
int num, first, second;
int main(){
    while (ch != '@'){
        ch = getchar();
        switch (ch){
        case '+': {
            first = s.top(); 
            s.pop();
            second = s.top();
            s.pop();
            s.push(first + second); break; }
        case '-': {
            first = s.top();
            s.pop(); 
            second = s.top();
            s.pop();
            s.push(second - first); 
            break; }
        case '*': {
            first = s.top(); 
            s.pop(); 
            second = s.top(); 
            s.pop(); 
            s.push(first * second); 
            break; }
        case '/': {
            first = s.top();
            s.pop();
            second = s.top(); 
            s.pop();
            s.push(second / first);
            break; 
        }
        case '.': {
            s.push(num); num = 0;
            break; 
        }
        default: {
            num = num * 10 + ch - '0';
            break; }
        }
    }
    return 0 * printf("%d\n", s.top());
}

题目3：约瑟夫问题

队列或者链表的基本问题，或者也可以使用公式法（《具体数学》第一章就有阐述）

//模拟做法
//12行可以取模，但是我懒的想
#pragma warning(disable:4996)
#include<stdio.h>
using namespace std;
bool book[200];
int main(){
    int n, m, s = 0; 
    scanf("%d%d", &n, &m);
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < m; i++) {
            if (++s > n) s = 1; 
            if (book[s]) i--; 
        }
        printf("%d ", s); 
        book[s] = true;
    }
    return 0;
}

题目4：队列安排

emmm题目叫做队列安排，实际上应该链表类的问题i，你可以使用STL的list文件，也可以手写list。手写list的方法也很多，可以使用数组用游标模拟，也可以使用指针写法。但是如果使用指针写法会被TLE掉- -我也很绝望，因此使用数组模拟。

#include<stdio.h>
int memo[100050][5];
int main(){
    int num, out_num, st = 1;
    scanf("%d", &num);
    memo[1][1] = 1;
    for (int i = 2; i <= num; i++){
        int temp_k, temp_p;
        scanf("%d%d", &temp_k, &temp_p);
        memo[i][1] = i;
        if (temp_p == 0){
            memo[memo[temp_k][3]][2] = i; 
            memo[i][2] = temp_k;
            memo[i][3] = memo[temp_k][3];
            memo[temp_k][3] = i;
            if (temp_k == st) st = i;
        }
        else{
            memo[i][2] = memo[temp_k][2];
            memo[memo[temp_k][2]][3] = i;
            memo[temp_k][2] = i; 
            memo[i][3] = temp_k;
        }
    }
    scanf("%d", &out_num);
    for (int i = 1; i <= out_num; i++){
        int temp_out;
        scanf("%d", &temp_out);
        if (memo[temp_out][1] != 0){
            memo[temp_out][1] = 0;
            memo[memo[temp_out][3]][2] = memo[temp_out][2];
            memo[memo[temp_out][2]][3] = memo[temp_out][3];
            num--;
            if (temp_out == st) st = memo[temp_out][3];
        }
    }
    int i = 1; 
    while (i <= num){
        printf("%d ", memo[st][1]);
        st = memo[st][2]; 
        i++;
    }
    return 0;
}

题目5：机械翻译

题目的含义就是队列的赤果果的解释鸭（另外实际上这道题就是典型的在CO中的cache，OS中的快表）。

#include<stdio.h>
#include<queue>
using namespace std;
queue<int> Q;
int book[1200];
int main() {
    int M,N,ans = 0;
    scanf("%d%d", &M,&N);
    for (int i = 0; i < N; i++) {
        int temp;
        scanf("%d", &temp);
        if (book[temp] == 1) continue;
        else {
            ans++;
            if (Q.size() >= M) {
                book[Q.front()] = 0;
                Q.pop();
            }
            Q.push(temp);
            book[temp] = 1;
        }
    }
    return 0 * printf("%d", ans);
}

题目6：海港

依次读入数据，并且维护一个ans表示任何时间段的不同国籍的人的数量。

由于存在24H后会把之前的人数给去掉，存在先进先出性质，因此需要使用队列

这里考虑队列存储什么，肯定是存储当前的船里面的人及这个人进入海港的时间。

那么每当来了一个船，我们先把判断这个船和之前先到达的船上的人（即person里面t）是不是同一天的，如果是同一天的则直接进入后半段循环，如果不是同一天的则需要把当前队列所有的记录人数的数组对应减1，并且检查是否变为0；

而后半段则输入船的每个人的情况，然后当大于等于1则ans++，否则ans不变（因为是考察是不是为0），然后输出当前的情况即可。

注意由于其输入序列是递增的，才允许使用在线，否则还是需要全盘存下。

#include<stdio.h>
#include<queue>
using namespace std;
int book[1000005];
struct person{
    int s, t;
};
queue<person>q;
int main(){
    int n, ans = 0, t, m, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        person temp;
        scanf("%d%d", &t, &m);
        while (!q.empty()){
            temp = q.front();
            if (temp.t + 86400 <= t){
                book[temp.s]--;
                if(book[temp.s] == 0)   ans--;
                q.pop();
                continue;
            }
            break;
        }
        for (int j = 0; j < m; ++j){
            scanf("%d", &x);
            temp.s = x, temp.t = t;
            q.push(temp);
            book[x]++;
            if(book[x] == 1)  ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

题目7：括号序列

看到括号先想想是不是栈的内容，实际上很容易想到这道题需要使用栈或者使用递归。其中有以下几种方案

  1. 若是左形括号，则直接入栈，并补充右括号，存入辅助数组
  2. 若是右形，则
    1. 若栈顶为同类型左形括号，直接弹出栈顶，然后存入辅助数组
    2. 若栈顶为非同类型的则添加左括号然后存入辅助数组

最后输出输入和辅助数组的结合即可。

#include<stdio.h>
#include<string.h>
int  stack[101], top = 0;
char input[101], temp_ans[101];
int main(){
    scanf("%s", input);
    int len = strlen(input);
    for (int i = 0; i < len; i++){
        if (input[i] == '(') stack[++top] = i,temp_ans[i] = ')'; 
        if (input[i] == '[') stack[++top] = i, temp_ans[i] = ']'; 
        if (input[i] == ')' || input[i] == ']') {
            if (top == 0 || temp_ans[stack[top]] != input[i]) {
                if (input[i] == ')') temp_ans[i] = '(';
                else temp_ans[i] = '[';
            }
            else temp_ans[stack[top--]] = ' ';
        }
    }
    for (int i = 0; i < len; i++){
        if (temp_ans[i] == '(' || temp_ans[i] == '[') putchar(temp_ans[i]);
        putchar(input[i]);
        if (temp_ans[i] == ')' || temp_ans[i] == ']') putchar(temp_ans[i]);
    }
    return 0;
}

题目8：验证栈序列

数据范围较小，直接使用STL模拟栈即可。注意题目是有可能，所以处理方式有点小变化

#include<iostream>
#include<stack>
using namespace std;
int stack_seq[100050], check_seq[100050];
stack<int> s;
int main(){
    int q, n;
    cin >> q;
    while (q--){
        cin >> n;
        int pos = 1;
        for (int i = 1; i <= n; i++) cin >> stack_seq[i];
        for (int i = 1; i <= n; i++) cin >> check_seq[i];
        for (int i = 1; i <= n; i++){
            s.push(stack_seq[i]);
            while ((s.top()) == check_seq[pos]){
                s.pop();
                pos++;
                if (s.empty()) break;
            }
        }
        if (s.empty()) cout << "Yes" << endl;
        else cout << "No" << endl;
        while (!s.empty()) s.pop();
    }
    return 0;
}

题目9：营业额统计（蓝题警告）

等我组织好语言再发出来（T.T）

文章作者: AleXandrite
文章链接: https://astrojoke.github.io/2020/05/02/luo-gu-guan-fang-ti-dan-xian-xing-biao-ti-jie/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 AleXandrite !
编程算法题解 洛谷 线性表
赏
  目录