头像

well188




离线:1天前


新鲜事 原文

well188
1个月前
AcWing《每日一题·春季》拼团优惠!https://www.acwing.com/activity/content/introduction/40/group_buy/12132/


新鲜事 原文

well188
1个月前
AcWing《每日一题·春季》拼团优惠!https://www.acwing.com/activity/content/introduction/40/group_buy/12132/



well188
1个月前

y老师在 最长连续不重复子序列 这道题中详细讲解了“双指针算法”并举例说明。抄录。
双指针核心思想及例题.png




well188
1个月前

分析:

阅读一个后缀表达式,从左往右读,一旦遇到运算符就往前取2个数(弹出栈),在用获得的运算符进行运算,并把结果压栈。需要注意的是,弹出时,后进的先出,所以第1个得到的操作数是操作符右侧的,第2个是操作符左侧的数字。

#include <cstdio>
#include <stack>
using namespace std;
stack<int> stk;
int s,x,y;//s由字符串转换得到的数字,x,y是由栈弹出的操作数
int main(){
    char ch;
    do{
        ch=getchar();
        if(ch>='0'&&ch<='9'){
            s=s*10+ch-48;
        }
        else if(ch=='.'){
            stk.push(s),s=0;
        }
        else if(ch!='@'){//不是@即是+-*/这几个操作符
//弹出时是倒序,故第1个是y,第2个是x
            y=stk.top();stk.pop();x=stk.top();stk.pop();
            switch(ch){//根据ch计算结果并压回栈内
                case '+':stk.push(x+y);break;
                case '-':stk.push(x-y);break;
                case '*':stk.push(x*y);break;
                case '/':stk.push(x/y);break;
            }
        }
    }while(ch!='@');//不是@就循环
    printf("%d\n",stk.top());//这时栈内应该只剩一个数了
    return 0;
}



well188
1个月前

vector在算法竞赛中主要当作可变数组来用

询问学号

分析:直接建立一个数组按照顺序记录按顺序到达的同学的学号,之后在数组中查询即可

#include <cstdio>
#include <vector>
using namespace std;
int n,m,tmp;
int main(){
    vector<int> v;//定义一个变长数组
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&tmp);
        v.push_back(tmp);//按进入顺序存入vector
    }
    for(int i=0;i<m;i++){
        scanf("%d",&tmp);
        printf("%d\n",v[tmp-1]);
    }
    return 0;
}

寄包柜

分析:第一个想到的肯定是二维数组,但是看下数据范围:$4 \cdot 10^5 \cdot 10^5 \approx 40G$ ,显然超出内存限制。
但后面特别说明:已知超市里共计不会超过 $10^7$ 个柜子,$\log_{2}^{4*10^7} \approx 25.2535 $ 也就是说其实总的空间 $4 \cdot 10^7 \approx 2^{25.2535} < 64M $ 就可以满足需要,但由于每个柜子中的格子数是未知的,这种情况正是变长数组 vector 的用武之地啊。

#include <cstdio>
#include <vector>
using namespace std;
int n,q,opt,i,j,k;
int main(){
    scanf("%d%d",&n,&q);
    vector<vector<int> >locker(n+1);//编号从1到n,0号没用
    while(q--){//q次询问
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&i,&j,&k);
            if(locker[i].size()<j+1){//要有1号到j号共j+1个盒子(算上0号)
                locker[i].resize(j+1);//不够就扩展
            }
            locker[i][j]=k;//够的话就存入
        }
        else{
            scanf("%d%d",&i,&j);
            printf("%d\n",locker[i][j]);//查询直接输出
        }
    }
    return 0;
}



well188
1个月前

仅用于练习二叉搜索树

构造一个二叉搜索树,编号从1开始,空节点用0表示。
允许有重复数字,用num数字记录重复。
本程序可以用插入方式构造一个简单的二叉搜素树,并用中序遍历输出。
即从小到大输出二叉树的权值。

#include <cstdio>
using namespace std;
const int N=1e5+10;
int l[N],r[N],val[N],num[N];//左右子树、节点权值、次数
int n,idx,root,x;//idx表待分配编号,root表当前节点,x表当前权值
//二叉搜索树的编号从1开始,0表示空节点,保证权值均不同。
inline add(int x){//构造一个节点并返回该节点的编号
    l[++idx]=0,r[idx]=0,val[idx]=x,num[idx]=1;//分配一个新编号,并初始化各个值
    return idx;//返回编号
}
void insert(int x,int root){//往二叉搜索树内插入一个权值为x的节点
    if(x==val[root]) {
        num[root]++;
        return;
    }
    if(x<val[root]){//若x小于根的权值
        if(l[root]==0) l[root]=add(x);//若根的左子树空,则构造一个值为x的节点挂到上面
        else insert(x,l[root]);//否则就继续递归
    }
    if(x>val[root]){//若x大于根的权值
        if(r[root]==0) r[root]=add(x);//若根右子树空,则构造值为x的节点挂上
        else insert(x,r[root]);//否则就继续递归
    }
}
void in(int root){//中序遍历
    if(root==0) return;
    if(l[root]!=0) in(l[root]);
    for(int i=0;i<num[root];i++) printf("%d",val[root]);
    if(r[root]!=0) in(r[root]);
}
int main(){
    scanf("%d%d",&n,&x);//接受n个节点和一个值x初始化根
    root=add(x);//初始化根
    for(int i=1;i<n;i++){//插入剩余的n-1个根
        scanf("%d",&x);
        insert(x,root);
    }
    in(root);//打印中序遍历
    return 0;
}

样例:

//输入
6
5 3 6 2 4 3
//输出:
233456


活动打卡代码 AcWing 787. 归并排序

well188
1个月前
#include <cstdio>
using namespace std;
const int N=1e5+10;
int n,a[N],tmp[N];
void merge_sort(int l,int r){
    if(l>=r) return;//如果区间到1就停止(停在叶节点,从第一层非叶节点开始上升)
    int mid=(l+r)/2;//设置中间值
    merge_sort(l,mid);
    merge_sort(mid+1,r);//递归左右区间
    int k=0,i=l,j=mid+1;//k:tmp的游标,i:左区间游标,j:右区间游标
    while(i<=mid && j<=r){//归并两区间
        if(a[i]<=a[j]) tmp[k++]=a[i++];
        else tmp[k++]=a[j++];
    }
    while(i<=mid) tmp[k++]=a[i++];
    while(j<=r) tmp[k++]=a[j++];
    for(int i=l,j=0;i<=r;i++,j++){
        a[i]=tmp[j];//把排序后的数据放进a数组
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    merge_sort(0,n-1);
    for(int i=0;i<n;i++) printf("%d ",a[i]);
    printf("\n");
    return 0;
}



well188
1个月前
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int l[N],r[N],n;//l数组左子树,r数组右子树
int dfs(int root){
    if(root==0) return 0;//节点为0时,深度为0
    int left=dfs(l[root]);//接受左子树的深度
    int right=dfs(r[root]);//接受右子树的深度
    return max(left,right)+1;//最大深度是左右子树最大值加1
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    printf("%d\n",dfs(1));
    return 0;
}



well188
1个月前

思路

已知2种遍历方法,先构造出来二叉树,再用遍历函数遍历即可。
一次构造并打印需要的遍历,难度较高,不如分拆简单。

后序遍历从后往前遍历,“根右左”的顺序

2个不同的root

在build函数中,第一个root是从post或pre中获得。第2个root是作为返回值的root。这2个root的区别是,第1个root是第2个root的父节点。

已知中序,前序构造二叉树,输出后序

#include <cstdio>
#include <map>
using namespace std;
const int N=1e6+10;
int pre[N],in[N],n;
int l[N],r[N],p=1;
map<int,int> mp;
void post(int root){
    if(!root) return;
    if(l[root]) post(l[root]);
    if(r[root]) post(r[root]);
    printf("%d",root);
}
int build(int left,int right){
    if(left>right) return 0;
    int root=pre[p++];//第1个root
    int i=mp[root];
    l[root]=build(left,i-1);
    r[root]=build(i+1,right);
    return root;//第2个root作为第1个root的子节点返回
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){//中序
        scanf("%d",&in[i]);
    }
    for(int i=1;i<=n;i++){//前序
        scanf("%d",&pre[i]);
    }
    for(int i=1;i<=n;i++){//映射
        mp[in[i]]=i;
    }
    build(1,n);//构造
    post(1);//后序打印
    return 0;
}

已知中序,后序构造二叉树,输出前序

#include <cstdio>
#include <map>
using namespace std;
const int N=1e6+10;
int in[N],post[N],n;//存入中序,前序
int l[N],r[N],p;//构造二叉树
map<int,int> mp;
void pre(int root){//前序遍历
    if(root==0) return;
    printf("%d",root);
    if(l[root]!=0) pre(l[root]);
    if(r[root]!=0) pre(r[root]);
}
//构造出二叉树,再用pre输出一遍
int build(int left,int right){
    if(left>right) return 0;
    int root=post[p];
    int i=mp[root];
    p--;
    //递归的目的是把当前root放到正确的位置上
    r[root]=build(i+1,right);
    l[root]=build(left,i-1);
    return root;
}
int main(){
    scanf("%d",&n);
    p=n;
    for(int i=1;i<=n;i++){
        scanf("%d",&in[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&post[i]);
    }
    for(int i=1;i<=n;i++){
        mp[in[i]]=i;
    }
    build(1,n);
    pre(1);
    printf("\n");

    return 0;
}

样例输入输出

输入:
9
4 2 5 1 6 3 8 7 9 //中序
4 5 2 6 8 9 7 3 1 //后序
输出:
124536789 //前序

构造二叉树.png




well188
1个月前

当x是布尔值,指针类型,整数时:
if(x) x 是:bool:真,指针:不空,整数:不等于0

if(!x) x 是:bool:假,指针:空,整数:等于0

当x是队列,栈等stl库类型时:
x.empty();

if(!x.empty()) x不空的情况下执行