首页 > 其他分享 >洛谷 【数据结构1-1】线性表

洛谷 【数据结构1-1】线性表

时间：2024-02-22 12:11:26浏览次数：20  
标签：洛谷 线性表 int cin long const tie 数据结构 cout

P3156 【深基15.例1】询问学号 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m;
map<int,int> mp;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int id;
        cin>>id;
        mp[i]=id;
    }
    for(int i=1;i<=m;i++){
        int quiry;
        cin>>quiry;
        cout<<mp[quiry]<<endl;
    }

    return 0;
}
View Code P3613 【深基15.例2】寄包柜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,q;
map<ll,int> mp;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    mp.clear();
    cin>>n>>q;
    while(q--){
        int op,i,j,k;
        cin>>op;
        if(op&1){
            cin>>i>>j>>k;
            mp[i*100000+j]=k;
        }else{
            cin>>i>>j;
            cout<<mp[i*100000+j]<<endl;
        }    
    }
    return 0;
}
View Code

P1449 后缀表达式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    stack<int> s;
    char c;
    int left,res=0,right=0;
    cin>>c;
    while(c!='@'){
        left=0;
        if(c>='0' && c<='9'){
            while(c>='0' && c<='9'){
                res=c-'0';
                left=left*10+res;
                cin>>c;
            }
        }
        if(c=='.') s.push(left);
        else{
            right=s.top();
            s.pop();
            left=s.top();
            s.pop();
            if(c=='+') s.push(left+right);
            if(c=='-') s.push(left-right);
            if(c=='*') s.push(left*right);
            if(c=='/') s.push(left/right);
        }
        cin>>c;
    }
    cout<<s.top();
    
    
    return 0;
}
View Code

P1996 约瑟夫问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m;
vector<int> a;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) a.push_back(i);
    int pos=0;
    for(int i=1;i<=n;i++){
        pos=(pos+m-1)%a.size();
        cout<<a[pos]<<" ";
        a.erase(a.begin()+pos);
    }
    return 0;
}
View Code

附赠：Problem - 4841 (hdu.edu.cn)

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    vector<int> a;
    while(cin>>n>>m){
        a.clear();
        for(int i=0;i<2*n;i++) a.push_back(i);
        int pos=0;
        for(int i=0;i<n;i++){
            pos=(pos+m-1)%a.size();
            a.erase(a.begin()+pos);
        }
        int j=0;
        for(int i=0;i<2*n;i++){
            if(!(i%50) && i) cout<<endl;
            if(j<a.size()&&i==a[j]){
                ++j;
                cout<<"G";
            }else cout<<"B";
        }
        cout<<endl<<endl;
    }
    return 0;
}
View Code

P1160 队列安排 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
int n,m;
struct node{
    int pre,next,id;
}a[N]={0};
void insert_(int i,int k,int p){
    //i插入k的哪一边 
    if(!p){ //左 
        a[i].next=k;
         a[a[k].pre].next=i;
        a[i].pre=a[k].pre;
        a[k].pre=i;
    }else{ //右 
        a[i].pre=k;
        a[a[k].next].pre=i;
        a[i].next=a[k].next;
        a[k].next=i;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    a[0].pre=1,a[0].next=1;
    a[1].pre=0;a[1].next=0;
    for(int i=2;i<=n;i++){
        int k,q;
        cin>>k>>q;
        insert_(i,k,q);
    }    
    cin>>m;
    while(m--){
        int x;
        cin>>x;
        a[x].id=1;
    }
    for(int i=a[0].next;i;i=a[i].next){
        if(a[i].id==0) cout<<i<<" ";
    }
    
    return 0;
}
View Code

P1540 [NOIP2010 提高组] 机器翻译 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int M,N,ans=0;
bool vis[1010];
queue<int> q;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>M>>N;
    for(int i=1;i<=N;i++){
        int x;
        cin>>x;
        if(vis[x]) continue;
        else{
            if(q.size()>=M){
                vis[q.front()]=false;
                q.pop();
            }
            q.push(x);
            vis[x]=true;
            ans++;
        }
    }
    cout<<ans<<endl;
    
    return 0;
}
View Code

P2058 [NOIP2016 普及组] 海港 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,t,k,ans,x,c[100010];
struct node{
    int s,t;
};
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    queue<node> q;
    node now;
    for(int i=1;i<=n;i++){
        cin>>t>>k;
        while(!q.empty()){
            now=q.front();
            if(now.t+86400<=t){
                c[now.s]--;
                if(!c[now.s]) --ans;
                q.pop();
                continue;
            }
            break;
        }
        for(int i=1;i<=k;i++){
            cin>>x;
            now.s=x,now.t=t;
            c[x]++;
            q.push(now);
            if(c[x]==1) ++ans;
        }
        cout<<ans<<endl;
    }
    return 0;
}
View Code

P1241 括号序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int top=0,w[110];
char s[110],c[110];
string a; 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>a;
    int n=a.size();
    for(int i=0;i<n;i++){
        if(a[i]=='(' || a[i]=='['){
            s[++top]=a[i];
            w[top]=i;
            if(a[i]=='(') c[i]=')';
            else c[i]=']';
        }
        if(a[i]==')'){
            if(top && s[top]=='('){
                c[w[top]]=' ';
                top--;
            }else c[i]='(';
        }
        if(a[i]==']'){
            if(top && s[top]=='['){
                c[w[top]]=' ';
                top--;
            }else c[i]='[';
        }
    }
    for(int i=0;i<n;i++){
        if(c[i]=='(' || c[i]=='[') cout<<c[i]<<a[i];
        else if(c[i]==')' || c[i]==']') cout<<a[i]<<c[i];
        else cout<<a[i];
    }
    
    return 0;
}
View Code

赠送：小苯的IDE括号问题（easy） (nowcoder.com) & 小苯的IDE括号问题（hard） (nowcoder.com)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
int n,m,a[N],b[N];
char str[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    cin>>str+1;
    int top1=0,top2=0;
    for(int i=1;i<=n;i++){
        if(str[i]=='(') a[++top1]=0;
        if(str[i]==')') a[++top1]=1;
        if(str[i]=='I') break;
    }
    for(int i=n;i>=1;i--){
        if(str[i]=='(') b[++top2]=0;
        if(str[i]==')') b[++top2]=1;
        if(str[i]=='I') break;
    }
    while(m--){
        cin>>str+1;
        if(str[1]=='<'){
            if(top1) b[++top2]=a[top1--];
        }
        if(str[1]=='-'){
            if(top2) a[++top1]=b[top2--];
        }
        if(str[1]=='b'){
            if(top1){
                if(a[top1]==0 && top2 && b[top2]==1) top2--;
                top1--;
            }
        }
        if(str[1]=='d'){
            if(top2) top2--;
        }
    }
    for(int i=1;i<=top1;i++){
        if(a[i]==0) cout<<"(";
        else cout<<")";
    } 
    cout<<"I";
    for(int i=top2;i>=1;i--){
        if(b[i]==0)cout<<"(";
        else cout<<")";
    }
    
    return 0;
}
View Code

P4387 【深基15.习9】验证栈序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=100010;
int q,n,a[N],b[N];
stack<int> s;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>q;
    while(q--){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        int pos=1;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int j=1;j<=n;j++) cin>>b[j];
        for(int i=1;i<=n;i++){
            s.push(a[i]);
            while(s.top()==b[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;
}
View Code

P2234 [HNOI2002] 营业额统计 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,x;
ll ans=0;
set<int> s;
set<int>::iterator l,r;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    s.insert(INF);s.insert(-INF);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(s.size()==2){
            ans+=x;
            s.insert(x);
        }else{
            l=s.lower_bound(x);
            if(*l!=x){
                r=l;
                --r;
                ans+=min(abs(*l-x),abs(*r-x));    
                s.insert(x);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
View Code

 

标签：洛谷,线性表,int,cin,long,const,tie,数据结构,cout
From： https://www.cnblogs.com/accbulb/p/18027040

相关文章

  • 洛谷题单指南-递推与递归-P1498 南蛮图腾
    原题链接：https://www.luogu.com.cn/problem/P1498题意解读：观察样例，可以发现，当n=1时，得到最基础的图案：/\/__\当n=2时，将基础图案向下复制两个，并排，然后将之前的图案移到居中的位置/\/__\/\/\/__\/__\当n=3时，再将n=2时的图案向下复制两个，并排，然后将之前的图......
  • [洛谷P3503][POI2010][BZOI2086]Blocks
    先看数据范围，n≤1e7，k≤1e9，暴力显然行不通，只能考虑单调栈；首先题目中说每一个数都要大于k，那么我们可以在初始化时就将每一个数都减去k，将问题转化为从正数中取出数加到负数里；然后维护一个前缀和，来判断一个区间是否符合要求；显然，当sum[j]-sum[i]≥0时，区间[i+1,j]符合题意，......
  • 洛谷 P6610 [Code+#7] 同余方程
    题目描述给出若干组正整数\(p\)和\(x\)，求方程\(a^2+b^2\equivx\pmodp\)关于\(a\)和\(b\)在模\(p\)意义下解的组数，其中\(p\)是奇数，且不包含平方因子题解来整一个更注重于观察结构而不是计算的题解（首先使用CRT将问题转化为模奇质数的结果相乘是显然的......
  • #根号分治，分块#洛谷 5309 [Ynoi2011] 初始化
    题目传送门分析如果\(x\)比较大那么可以暴力修改，\(x\)比较小的话可以用数组打标记查询的时候对于暴力修改的部分可以分块，暴力修改的同时需要给块打标记如果\(x\)比较小的情况，一段区间相当于是中间很多段周期加上前后缀（当然可以直接区间减但是我被卡常了）我调的块长是160......
  • 洛谷P4447题解
    md这篇反正不交题解的，随便写，不管它格式题意简化下，给你N个数，求出连续值分组人数最小的那组的人数最大值。这个题目还挺经典的，原本23年8月份过了到现在来又不会了（划掉，bushi对于这种，很容易想到的是输入，之后排序，然后分组这种模板就不多说了，就在我24年2月份重温这道题再打一遍代码......
  • 洛谷题单指南-递推与递归-P1228 地毯填补问题
    原题链接：https://www.luogu.com.cn/problem/P1228题意解读：用4种毯子铺满2^k*2^k的区域，留出一个公主位置，输出所有毯子拐角的坐标以及哪种毯子，看起来有点无从下手，可以从k=1，k=2，k=3入手去依次考虑，找到规律，用分治法解决。解题思路：1、当k=1时，即2*2的区域，对于任意一个位置是公主，都......
  • Python数据结构与算法05——插入排序 shell排序
    插入排序 definsrt_sort(aimlist):n=len(aimlist)forcurinrange(1,n):i=curwhilei>0:ifaimlist[i]<aimlist[i-1]:aimlist[i],aimlist[i-1]=aimlist[i-1],aimlist[i]i-=1e......
  • 洛谷题单指南-递推与递归-P1010 [NOIP1998 普及组] 幂次方
    原题链接：https://www.luogu.com.cn/problem/P1010题意解读：输出一个正整数的2的幂次方表示，需要用到二进制数学知识，将整数拆解成2的次幂之和，幂次方也要进行拆解，因此容易想到通过递归处理。解题思路：先看样例，给定整数137，要拆解成2的幂次方之和，先考虑i使得刚好137>=2^i时，i取7，因此2......
  • Python数据结构与算法04——栈与队列
    栈的实现：classStack(object):def__init__(self):self.__list=[]defpush(self,item):self.__list.append(item)defpop(self):returnself.__list.pop()defpeek(self):ifself.__list:returnself._......
  • Python数据结构与算法05——查找与排序
    冒泡排序：defbible_sort(aimlist):n=len(aimlist)j=len(aimlist)whilej>0:foriinrange(n-1):ifaimlist[i]>aimlist[i+1]:aimlist[i],aimlist[i+1]=aimlist[i+1],aimlist[i]n-=1j-=1r......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99