抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

上杉九月的博客

你好,我的朋友,很高兴在这里遇见你。

前言

要填的坑挺多的,精力有限,目前先集中更新本篇文章。

本篇文章参考书籍为《洛谷-深入浅出程序设计竞赛》

2021.09.24

1. P3156 【深基15.例1】询问学号 - 洛谷 - 入门

题目描述

有 $n(n \le 2 \times 10^6)$ 名同学陆陆续续进入教室。我们知道每名同学的学号(在 1 到 $10^9$ 之间),按进教室的顺序给出。上课了,老师想知道第 $i$ 个进入教室的同学的学号是什么(最先进入教室的同学 $i=1$),询问次数不超过 $10^5$ 次。

输入格式

第一行 2 个整数 n 和 m,表示学生个数和询问次数。

第二行 n 个整数,表示按顺序进入教室的学号。

第三行 m 个整数,表示询问第几个进入教室的同学。

输出格式

m 个整数表示答案,用换行隔开。

样例

输入:
10 3
1 9 2 60 8 17 11 4 5 14
1 5 9
输出:
1
8
5

思路和知识点

vector基本用法
1. vector <int> array (N, i); 新建一个初始长度为N,N个数据为i的vector数组
2. array.push_back(a); 将a元素添加到数组array的末尾,并增加数组长度
3. array.size(); 返回数组的长度
4. array.resize(n, m); 重新将数组长度设置为n,若原数组比n长,则删除多余元素,若短,新增加的数组初始化为m
5. array.begin(); 返回array数组的首元素,也就是array[0]的指针
6. array.end(); 返回array数组末尾下一个元素的指针

AC代码

#include <iostream>
#include <vector> 
using namespace std;
int main()
{
    int n, m;
    vector <int> student; // 创建vector数组
    int temp = 0;
    cin>>n>>m;
    for(int i = 0; i < n; i++)
    {
        cin>>temp;
        student.push_back(temp); // 将temp压入动态vector数组的末尾,并且vector数组的长度+1
    }
    for(int i = 0; i < m; i++)
    {
        cin>>temp;
        cout<<student[temp - 1]<<"\n";// 数组一般是从0开始存储数据,而我们询问学号是从1开始寻找
    }
    return 0;
}

2. P3613 【深基15.例2】寄包柜 - 洛谷 - 普及

题目描述

超市里有 $n(n\le10^5)$ 个寄包柜。每个寄包柜格子数量不一,第 $i$ 个寄包柜有 $a_i(a_i\le10^5)$ 个格子,不过我们并不知道各个 $a_i$ 的值。对于每个寄包柜,格子编号从 1 开始,一直到 $a_i$。现在有 $q(q\le10^5)$ 次操作:

  • 1 i j k:在第 $i$ 个柜子的第 $j$ 个格子存入物品 $k(0\le k\le 10^9)$。当 $k=0$ 时说明清空该格子。
  • 2 i j:查询第 $i$ 个柜子的第 $j$ 个格子中的物品是什么,保证查询的柜子有存过东西。

已知超市里共计不会超过 $10^7$ 个寄包格子,$a_i$ 是确定然而未知的,但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 n 和 q,寄包柜个数和询问次数。

接下来 q 个整数,表示一次操作。

输出格式

对于查询操作时,输出答案。

样例

输入:
5 4
1 3 10000 114514
1 1 1 1
2 3 10000
2 1 1
输出:
114514
1

思路和知识点

vector相关操作

注意 此题的数据范围是$10^5$,如果开一个$10^5$ * $10^5$ 的二维数组,空间占用将会十分离谱

所以此类题目使用vector便可以最大程度的减少空间的占用

AC代码

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
    int n, q, op;
    int i, j, k;
    cin>>n>>q;
    vector < vector <int> > block (n + 1);// 此时仅仅是开了一个长度为n的一维数组
    for(int count = 0; count < q; count++)
    {
        cin>>op;
        if(op == 1)
        {
            cin>>i>>j>>k;
            if(block[i].size() < j + 1)// 如果柜子里格子不足,那么就扩展第i个柜子的格子到j + 1
            {
                block[i].resize(j + 1);
            }
            block[i][j] = k;
        }
        else
        {
            cin>>i>>j;
            cout<<block[i][j]<<"\n";
        }
    }
    return 0;
}

3. 手写栈的操作

题目描述

栈作为一个先进先出的数据结构,尽管头文件已经提供了现成的关于栈的操作

但是在STL里面,使用这些操作而不使用O2优化

会导致程序有一点点慢

思路和知识点

C语言提供了栈的相关快捷操作<stack>
1. stack <int> s; 新建一个栈
2. s.push(a); 将元素a压入栈
3. s.pop(); 将s的栈顶元素弹出
4. s.top(); 查询s的栈顶元素
5. s.size(); 查询s的元素个数
6. s.empty(); 查询s是否为空

手写栈模板(请根据实际情况进行修改)

int stack[10000];
int p = 0;// 指针,指向的是下一个栈元素
void push(int x)// 压栈操作
{
    stack[p++] = x;
}
void pop()// 弹出栈顶元素
{
    stack[--p] = 0;
}
int top()// 查询栈顶元素
{
    return stack[p - 1];
}

4. UVA673 平衡的括号 Parentheses Balance - 洛谷 - 普及

题目描述

输入一个包含“()”和“[]”的括号序列,判断是否合法。
具体规则:

  1. 空串合法;
  2. 如果A和B合法,那么AB合法;
  3. 如果A合法(A)和[A]都合法

感谢 @陶文祥 提供的翻译。

样例

输入:
3
([])
(([()])))
([()[]()])()
输出:
Yes
No
Yes

思路和知识点

你可以将含有括号的这一个字符串人为的分为左右两边。

出栈判定是右边的括号可以将左边正处于栈顶的括号匹配消除

入栈判定是栈为空或者是没有对应的括号可以匹配

AC代码

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int stack[1000];
int p = 0;// 栈顶指针,指的是下一个待插入的数组位置
void push(int x)// 压栈操作
{
    stack[p++] = x;
}
void pop()
{
    stack[--p] = 0;
}
int top()
{
    return stack[p - 1];

}
char judge(char a)// 因为要让右边的括号匹配左边的括号,所以说对于每一种右括号都应该返回相对应的左括号形式
{
    if(a == ')')
    {
        return '(';
    }
    if(a == ']')
    {
        return '[';
    }
    if(a == '}')
    {
        return '{';
    }
    return '/0';
}
int main()
{
    int num;
    cin>>num;
    string str;
    getline(cin, str);// C++在使用cin输入时,光标停留在数字行的末尾,如果此时用getline读取一行,那么将读取到空行
    while(num--)
    {
        while(p != 0)
        {
            pop();
        }
        getline(cin, str);// 这里才是真正的去读入字符串
        for(int i = 0; i < str.size(); i++)
        {
            if(p == 0)
            {
                push(str[i]);// 栈空则压入数据
                continue;
            }
            if(judge(str[i]) == top())// 栈顶左括号与右括号匹配
            {
                pop();
            }
            else
            {
                push(str[i]);
            }
        }
        if(p == 0)
        {
            cout<<"Yes\n";
        }
        else
        {
            cout<<"No\n";
        }
    }
    return 0;
}

2021.09.26

5. P1449 后缀表达式 - 洛谷 - 普及

题目描述

所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。

如:3*(5–2)+7对应的后缀表达式为:3.5.2.-*7.+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。

样例

输入:
3.5.2.-*7.+@
输出:
16  

思路和知识点

首先注意一点,运算符号前面的两位数字便是进行运算的两位数。

当在字符串读取到运算符号的时候,便从栈顶的顶部取两个数,然后进行运算,运算后的结果仍然放在栈顶。

AC代码

#include <iostream>
#include <cstdio>
using namespace std;
int stack[1000];
int p = 0;
void push(int x)
{
    stack[p++] = x;
}
void pop()
{
    stack[--p] = 0;
}
int top()
{
    return stack[p - 1];
}
int main()
{
    int x, y; // x, y是用于存放两个算数的临时变量
    int sum = 0;
    char ch;
    do
    {
        ch = getchar();
        if(ch <= '9' && ch >= '0')
        {
            sum = sum * 10 + (ch - '0');
        }
        else if(ch == '.')
        {
            push(sum);
            sum = 0;
        }
        else if(ch != '@')
        {
            x = top();
            pop();
            y = top();
            pop();
            switch (ch)
            {
                case '+':
                    push(x + y);
                    break;
                case '-':
                    push(y - x);
                    break;
                case '*':
                    push(x * y);
                    break;
                case '/':
                    push(y / x);
                    break;            
                //default:
                    //break;
            }
        }
    } while (ch != '@');
    printf("%d", top());
    return 0;
}

6. P1739 表达式括号匹配 - 洛谷 - 入门

题目描述

假设一个表达式有英文字母(小写)、运算符(+,—,*,/)和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则返回“YES”;否则返回“NO”。表达式长度小于255,左圆括号少于20个。

样例

输入:
2*(x+y)/(1-x)@
输出:
YES
输入:
(25+x)*(a*(a+b+b)@
输出
NO

思路和知识点

这个相比于前面那道括号匹配题更加简单。

只要程序读取到左括号就压入栈顶,读入右括号就将栈顶弹出。

如果到最后栈非空,输出NO,反之,输出YES。

AC代码

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int stack[1000];
int p = 0;
void push(int x)
{
    stack[p++] = x;
}
void pop()
{
    stack[--p] = 0;
}
int top()
{
    return stack[p - 1];
}
int main()
{
    string s;
    getline(cin, s);
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] == '(')
        {
            push(s[i]);
        }
        else if(s[i] == ')')
        {
            if(top() == '(')
            {
                pop();
            }
            else
            {
                push(s[i]);
            }
        }
    }
    if(p != 0)
    {
        printf("NO");
    }
    else
    {
        printf("YES");
    }
    return 0;
}

7. P1044 (NOIP2003 普及组)栈 - 洛谷 - 普及

题目描述

栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。

栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。

宁宁考虑的是这样一个问题:一个操作数序列,$1,2,\ldots ,n$(图示为 1 到 3 的情况),栈 A 的深度大于 $n$。

现在可以进行两种操作,

  1. 将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的 push 操作)
  2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的 pop 操作)

使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由 1 2 3 生成序列 2 3 1 的过程。

(原始状态如上图所示)

你的程序将对给定的 $n$,计算并输出由操作数序列 $1,2,\ldots,n$ 经过操作可能得到的输出序列的总数。

样例

输入:
3
输出:
5

思路和知识点

本题我暂时也没搞得太明白,只是推算出了数学规律为卡特兰数。

至于卡特兰数怎么推导的,我再看看吧。

AC代码

#include <iostream>
#include <cstdio>
using namespace std;
int k[100];
int main()
{
    int n;
    cin>>n;
    k[0] = 1; k[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            k[i] += k[j] * k[i - j - 1];
        }
    }
    cout<<k[n];
    return 0;
}

P1996 约瑟夫问题 - 洛谷 - 普及

题目描述

$n$ 个人围成一圈,从第一个人开始报数,数到 $m$ 的人出列,再由下一个人重新从 $1$ 开始报数,数到 $m$ 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n-1 名小朋友,而该题是全部出圈。

样例

输入:
10 3
输出:
3 6 9 2 7 1 8 5 10 4

思路和知识点

典型的队列问题。

这里我们先将$n$个数按照从小到大的顺序以此加入队列,此时我们再每次将$m-1$个数从队前迁移到队尾,那么此时在队伍最前的便是要淘汰的数,输出后直接弹出。

直到$head == tail$结束。

AC代码

#include <iostream>
#include <cstdio>
using namespace std;
int queue[100000];
int head = 0, tail = 0;
void push(int x)
{
    queue[tail++] = x;
}
void pop()
{
    queue[head++] = 0;
}
int front()
{
    return queue[head];
}
int main()
{
    int n, m;
    cin>>n>>m;
    if(n == 0 && m == 0)
    {
        cout<<"1";
        return 0;
    }
    for(int i = 1; i <= n; i++)
    {
        push(i);
    }
    while(head != tail)
    {
        for(int i = 1; i < m; i++)
        {
            push(front());
            pop();
        }
        cout<<front()<<" ";
        pop();
    }
    return 0;
}

about_me

评论