头像

晨曦时雨




离线:1天前


最近来访(25)
用户头像
whsstory
用户头像
思樊
用户头像
写bug大师
用户头像
我爱y总
用户头像
潮声两岸
用户头像
D.devil
用户头像
我要出去乱说
用户头像
故事
用户头像
qyzawa_phi
用户头像
𝓳𝓾𝓷
用户头像
齐天大仙
用户头像
12..
用户头像
Hatsune_Miku
用户头像
无名氏DU
用户头像
lghgha
用户头像
曦雨
用户头像
无心插柳柳橙汁
用户头像
李向前XingY
用户头像
隹隹隹隹隹
用户头像
hanwei6174


当当当……闪亮登场

- ->

(其实就等于- -)

while(m-->0)
{
    cout<<m<<' ';
}

(小声bb:没啥新鲜的卵用)



新鲜事 原文

安利一下 https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan



晨曦时雨
1个月前

题目描述

给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。

注意:

  • 数据保证给定的表达式合法。
  • 题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
  • 题目保证表达式中所有数字均为正整数。
  • 题目保证表达式在中间计算过程以及结果中,均不超过 $2^{31}−1$。
  • 题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 5/3=1,对于小于 0 的结果向上取整,例如 5/(1−4)=−1
  • C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。

输入格式

共一行,为给定表达式。

输出格式

共一行,为表达式的结果。

数据范围

表达式的长度不超过 $10^5$。

输入样例:

(2+2)*(1+1)

输出样例:

8

代码&思路

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<stack>
#include<string>
using namespace std;
stack<int> num;
stack<char> op;
void eval()
{
    auto b=num.top();num.pop();//第二个数
    auto a=num.top();num.pop();//第一个数
    //因为实在栈中取出的,所以在上面的是后面的数,即第二个数
    auto c=op.top();op.pop();//运算符号
    int x=0;
    //进行运算
    if(c=='+') x=a+b;
    else if(c=='-') x=a-b;
    else if(c=='*') x=a*b;
    else x=a/b;
    num.push(x);//放入num栈中
}
int main()
{
    unordered_map<char,int> pr={{'+',1},{'-',1},{'*',2},{'/',2}};//符号优先级
    string str;
    cin>>str;
    for(int i=0;i<str.size();i++)
    {
        auto c=str[i];
        if(isdigit(c))//数字
        {
            int x=0,j=i;
            while(j<str.size()&&isdigit(str[j])) x=x*10+str[j++]-'0';//把数字进行存储,如果是多位数的,要先进乘以10
            num.push(x);//放入num栈
            i=j-1;//更新i,改变i的位置
        }
        else if(c=='(') op.push(c);//把‘(’放入op栈
        else if(c==')')//‘)’
        {
            while(op.top()!='(') eval();//从左往右算,算到‘(’为止
            op.pop();
        }
        else
        {
            while(op.size()&&pr[op.top()]>=pr[c]) eval();//按符号的优先级顺序进行计算
            op.push(c);
        }
    }
    while(op.size()) eval();//将剩余的进行计算
    cout<<num.top()<<endl;
    return 0;
}


分享 getline函数

晨曦时雨
1个月前

格式

getline(cin,string类型)

注意事项

getlinecin共同使用时,因为getline\n极度敏感,所以在用完cin时的\n也会被getline吞掉,所以,要在cin后面加上cin.ignore();

getline可以连带空格一起读入,常用于把句子分裂成单词,所以,建议大家配合 stringstream用法食用(分成单词的用法在最后)




晨曦时雨
2个月前

有哪位大佬知道怎样理解KMP的吗啊喂QAQ

40分钟的视频硬让我看了3个小时

我裂开了啊……

现在已经懂了大概意思了(真不容易)

y总代码

我用的是下标从1开始的方法

可是现在还有一大堆的疑问点:

  1. 最后的j=ne[j]是什么意思???
  2. 为什么s[]p[]要错开一位???
  3. 如果第二层的for循环里面的要求都不满足,就会i++j不变,这种比较的意义什么???
  4. 只有一个输出是怎么输出两个数的???

(来自一位菜鸡的烦恼)

感谢大佬的回答○| ̄|_(哪怕只回答一个也十分感谢)




晨曦时雨
2个月前

题目描述

给定一个大小为$n≤10^6$ 的数组。

有一个大小为 $k$ 的滑动窗口,它从数组的最左边移动到最右边。

你只能在窗口中看到 $k$ 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为 [1 3 -1 -3 5 3 6 7],$k$ 为 $3$。

无标题.png

你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 $n$ 和 $k$,分别代表数组长度和滑动窗口的长度。

第二行有 $n$ 个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:

8 3
1 3 -1 -3 5 3 6 7

输出样例:

-1 -3 -3 -3 3 3
3 3 5 5 6 7

代码&思路

1.png

#include<iostream>
using namespace std;
const int N = 1000010;
int q[N],a[N];
int hh,tt=-1,n,k;
int main()
{
    scanf("%d%d", &n, &k);//这里建议使用scanf/printf,会比cin/cout快好多!
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i ++ )
    {
        if ( hh <= tt && i - k + 1 > q[hh]) hh ++;
        //判断队列是否为空并且判断队列长度是否超过窗口长度
        //i-k+1这个公式你们可以试试,是对的,一个常用的公式
        while ( hh <= tt && a[q[tt]] >/*=*/ a[i] ) tt --;
        //这里主要判断对位的元素是否大于(等于)当前元素,如果大于(等于),就删除,直到删到小于(等于)当前数为止
        //这一步可以理解为:比当前数大的元素留着没什么用,因为求的是最小值,只要留着比较小的就行了
        q[++tt] = i;//注意先加入,因为这个数也可能是最小值
        if(i >= k - 1) printf("%d ",a[q[hh]]);
        //因为是一个一个放入队列的,所以一开始的时候并不是题目的位置,要特判一下
    }

    printf("\n");
    //下面就和上面一样的啦,只不过求的是最大值,过程你们按着上面的反着说吧,我就不写啦~
    hh = 0,tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if ( hh <= tt && i - k + 1 > q[hh]) hh ++;
        while ( hh <= tt && a[q[tt]] </*=*/ a[i] ) tt --;
        q[++tt] = i;
        if(i >= k - 1) printf("%d ",a[q[hh]]);
    }
}


活动打卡代码 AcWing 154. 滑动窗口

晨曦时雨
2个月前

题目描述

给定一个大小为$n≤10^6$ 的数组。

有一个大小为 $k$ 的滑动窗口,它从数组的最左边移动到最右边。

你只能在窗口中看到 $k$ 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为 [1 3 -1 -3 5 3 6 7],$k$ 为 $3$。

无标题.png

你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 $n$ 和 $k$,分别代表数组长度和滑动窗口的长度。

第二行有 $n$ 个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:

8 3
1 3 -1 -3 5 3 6 7

输出样例:

-1 -3 -3 -3 3 3
3 3 5 5 6 7

代码&思路

1.png

#include<iostream>
using namespace std;
const int N = 1000010;
int q[N],a[N];
int hh,tt=-1,n,k;
int main()
{
    scanf("%d%d", &n, &k);//这里建议使用scanf/printf,会比cin/cout快好多!
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i ++ )
    {
        if ( hh <= tt && i - k + 1 > q[hh]) hh ++;
        //判断队列是否为空并且判断队列长度是否超过窗口长度
        //i-k+1这个公式你们可以试试,是对的,一个常用的公式
        while ( hh <= tt && a[q[tt]] >/*=*/ a[i] ) tt --;
        //这里主要判断对位的元素是否大于(等于)当前元素,如果大于(等于),就删除,直到删到小于(等于)当前数为止
        //这一步可以理解为:比当前数大的元素留着没什么用,因为求的是最小值,只要留着比较小的就行了
        q[++tt] = i;//注意先加入,因为这个数也可能是最小值
        if(i >= k - 1) printf("%d ",a[q[hh]]);
        //因为是一个一个放入队列的,所以一开始的时候并不是题目的位置,要特判一下
    }

    printf("\n");
    //下面就和上面一样的啦,只不过求的是最大值,过程你们按着上面的反着说吧,我就不写啦~
    hh = 0,tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if ( hh <= tt && i - k + 1 > q[hh]) hh ++;
        while ( hh <= tt && a[q[tt]] </*=*/ a[i] ) tt --;
        q[++tt] = i;
        if(i >= k - 1) printf("%d ",a[q[hh]]);
    }
}



晨曦时雨
2个月前

题目描述

给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。

输入格式

第一行包含整数 N,表示数列长度。

第二行包含 N 个整数,表示整数数列。

输出格式

共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。

数据范围

$1≤N≤10^5$

$1≤数列中元素≤10^9$

输入样例:

5
3 4 2 7 5

输出样例:

-1 3 -1 2 2

思路

单调栈:单调递增或单调减的栈

这道题就是一道经典的运用这种性质的题

我们来证明一下:

设:x<y   a[x]>a[y]

当a[x]<a[i]时

a[y]是不是相对于a[i]更近一些?

且a[i]>a[x],a[x]>a[y],那么a[i]>a[y]对不对?

这样就得到了a[y]相对于a[x]是更优的答案

所以就可以把a[x]删掉(因为a[y]更优,所以用不到a[x])

由此可以构成单调栈

代码

#include<iostream>
using namespace std;
const int N = 10010;
int stk[N],tt;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        while(tt&&stk[tt]>=x) tt--;//进行筛选
        if(tt) cout<<stk[tt]<<' ';//如果有符合要求的就输出
        else cout<<-1<<' ';//否则输出-1
        stk[++tt]=x;//存入
    }
    return 0;
}


活动打卡代码 AcWing 830. 单调栈

晨曦时雨
2个月前

题目描述

给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。

输入格式

第一行包含整数 N,表示数列长度。

第二行包含 N 个整数,表示整数数列。

输出格式

共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。

数据范围

$1≤N≤10^5$

$1≤数列中元素≤10^9$

输入样例:

5
3 4 2 7 5

输出样例:

-1 3 -1 2 2

思路

单调栈:单调递增或单调减的栈

这道题就是一道经典的运用这种性质的题

我们来证明一下:

设:x<y   a[x]>a[y]

当a[x]<a[i]时

a[y]是不是相对于a[i]更近一些?

且a[i]>a[x],a[x]>a[y],那么a[i]>a[y]对不对?

这样就得到了a[y]相对于a[x]是更优的答案

所以就可以把a[x]删掉(因为a[y]更优,所以用不到a[x])

由此可以构成单调栈

代码

#include<iostream>
using namespace std;
const int N = 10010;
int stk[N],tt;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        while(tt&&stk[tt]>=x) tt--;//进行筛选
        if(tt) cout<<stk[tt]<<' ';//如果有符合要求的就输出
        else cout<<-1<<' ';//否则输出-1
        stk[++tt]=x;//存入
    }
    return 0;
}



晨曦时雨
2个月前

题目描述

实现一个队列,队列初始为空,支持四种操作:

  1. push x – 向队尾插入一个数$x$;
  2. pop – 从队头弹出一个数;
  3. empty – 判断队列是否为空;
  4. query – 查询队头元素。

现在要对队列进行 $M$ 个操作,其中的每个操作 $3$ 和操作 $4$ 都要输出相应的结果。

输入格式

第一行包含整数 $M$,表示操作次数。

接下来 $M$ 行,每行包含一个操作命令,操作命令为 push xpopemptyquery 中的一种。

输出格式

对于每个 emptyquery 操作都要输出一个查询结果,每个结果占一行。

其中,empty 操作的查询结果为 YESNOquery 操作的查询结果为一个整数,表示队头元素的值。

数据范围

$1≤M≤100000$

$1≤x≤10^9$

所有操作保证合法。

输入样例:

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例:

NO
6
YES
4

代码&思路

2.png

做法一
#include<iostream>
using namespace std;
const int N = 100010;
int q[N],hh,tt;//
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        string op;
        cin>>op;
        if(op=="push")
        {
            cin>>x;
            q[tt++]=x;//
        }
        if(op=="pop")
        {
            hh++;
        }
        if(op=="empty")
        {
            if(hh>=tt) cout<<"YES"<<endl;//
            else cout<<"NO"<<endl;
        }
        if(op=="query")
        {
            cout<<q[hh]<<endl;
        }
    }
    return 0;
}
做法二
#include<iostream>
using namespace std;
const int N = 100010;
int q[N],hh,tt=-1;//
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        string op;
        cin>>op;
        if(op=="push")
        {
            cin>>x;
            q[++tt]=x;//
        }
        if(op=="pop")
        {
            hh++;
        }
        if(op=="empty")
        {
            if(hh>tt) cout<<"YES"<<endl;//
            else cout<<"NO"<<endl;
        }
        if(op=="query")
        {
            cout<<q[hh]<<endl;
        }
    }
    return 0;
}

上面两种做法的区别我用//标了一下

主要的区别就是:

第一种是tt从0开始的(全局变量默认为0),而第二种从-1开始

而这一小小的区别就需要我们去注意许多细节

tt-1开始的时候,我们在进行插入的时候要写成q[++tt],反之写成q[tt++]

我个人认为这是因为数组的下标不能为-1

所以要先进行++

另外

hh都是从0开始的

所以当tt0开始的时候,tthh一开始是相等的,而一开始队列为空,这就说明当hh==tt的时候,队列为空

tt-1开始的时候,如果tt等于了0,tt加了一,就说明已经插入了一个元素,此时hh==tt的时候,队列不为空

总结一下:

tt可以从0开始也可以从-1开始,看个人的习惯

当tt从0开始的时候,hh==tt队列为空

当tt从-1开始的时候,要先++,hh==tt队列不为空