洛谷-数据结构1-1-线性表1
P3156 【深基15.例1】询问学号
题目描述
有 n(n≤2×106) 名同学陆陆续续进入教室。我们知道每名同学的学号（在 1 到 109 之间），按进教室的顺序给出。上课了，老师想知道第 i 个进入教室的同学的学号是什么（最先进入教室的同学 i=1），询问次数不超过 105 次。
输入格式
第一行 2 个整数 n 和 m，表示学生个数和询问次数。
第二行 n 个整数，表示按顺序进入教室的学号。
第三行 m 个整数，表示询问第几个进入教室的同学。
输出格式
输出 m 个整数表示答案，用换行隔开。
输入输出样例
输入 #1复制
10 3 1 9 2 60 8 17 11 4 5 14 1 5 9
输出 #1复制
1 8 5
实现代码：
#include<cstdio> int a[2000001]; int main() { int n,m,sum; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) { scanf("%d",&sum); printf("%d\n",a[sum]); } }P3613 【深基15.例2】寄包柜
题目描述
超市里有 n(1≤n≤105) 个寄包柜。每个寄包柜格子数量不一，第 i 个寄包柜有 ai(0≤ai≤105) 个格子，不过我们并不知道各个 ai 的值。对于每个寄包柜，格子编号从 1 开始，一直到 ai。现在有 q(1≤q≤105) 次操作：
1 i j k：在第 i 个柜子的第 j 个格子存入物品 k(0≤k≤109)。当 k=0 时说明清空该格子。2 i j：查询第 i 个柜子的第 j 个格子中的物品是什么，保证查询的柜子有存过东西。
已知超市里共计不会超过 107 个寄包格子，ai 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。
输入格式
第一行 2 个整数 n 和 q，寄包柜个数和询问次数。
接下来 q 个行，每行有若干个整数，表示一次操作。
输出格式
对于查询操作时，输出答案，以换行隔开。
输入输出样例
输入 #1复制
5 4 1 3 10000 118014 1 1 1 1 2 3 10000 2 1 1
输出 #1复制
118014 1
说明/提示
upd 2022.7.26：新增加一组 Hack 数据。
实现代码：
#include <bits/stdc++.h> using namespace std; vector<int> a[100010]; int main(){ int n,q; cin>>n>>q; int x,y,z,op; while(q--){ cin>>op; if(op==1){ cin>>x>>y>>z; if(a[x].size()<y+1) { a[x].resize(y+1); } a[x][y]=z; } else{ cin>>x>>y; cout<<a[x][y]<<endl; } } return 0; }P1449 后缀表达式
题目描述
所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。
本题中运算符仅包含 +-*/。保证对于 / 运算除数不为 0。特别地，其中 / 运算的结果需要向 0 取整（即与 C++/运算的规则一致）。
如：3*(5-2)+7 对应的后缀表达式为：3.5.2.-*7.+@。在该式中，@为表达式的结束符号。.为操作数的结束符号。
输入格式
输入一行一个字符串 s，表示后缀表达式。
输出格式
输出一个整数，表示表达式的值。
输入输出样例
输入 #1复制
3.5.2.-*7.+@
输出 #1复制
16
输入 #2复制
10.28.30./*7.-@
输出 #2复制
-7
说明/提示
数据保证，1≤∣s∣≤50，答案和计算过程中的每一个值的绝对值不超过 109。
实现代码：
#include<iostream> #include<cstdio> using namespace std; long long stk[1000]; int main(){ long long i=0,now=0; char op; while((op=getchar())!='@'){ if(op>='0'&&op<='9') now*=10,now+=op-'0'; else if(op=='.'){ stk[++i]=now; now=0; } else if(op=='+'){ stk[i-1]=stk[i-1]+stk[i]; stk[i]=0; i--; } else if(op=='-'){ stk[i-1]=stk[i-1]-stk[i]; stk[i]=0; i--; } else if(op=='*'){ stk[i-1]=stk[i-1]*stk[i]; stk[i]=0; i--; } else if(op=='/'){ stk[i-1]=stk[i-1]/stk[i]; stk[i]=0; i--; } } cout<<stk[1]; return 0; }P1996 约瑟夫问题
题目描述
n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1 名小朋友，而该题是全部出圈。
输入格式
输入两个整数 n,m。
输出格式
输出一行 n 个整数，按顺序输出每个出圈人的编号。
输入输出样例
输入 #1复制
10 3
输出 #1复制
3 6 9 2 7 1 8 5 10 4
说明/提示
1≤m,n≤100
实现代码：
#include <bits/stdc++.h> using namespace std; int a[110]; int main(){ int cnt=0,k=0,i=0,n,m,b=0; cin>>n>>m; while(cnt!=n){ i++; if(i>n){ i=1; } if(a[i]==0){ k++; if(k%m==0){ cnt++; a[i]=1; cout<<i<<" "; } } } return 0; }P1160 队列安排
题目描述
一个学校里老师要将班上 N 个同学排成一列，同学被编号为 1∼N，他采取如下的方法：
先将 1 号同学安排进队列，这时队列中只有他一个人；
2∼N 号同学依次入列，编号为 i 的同学入列方式为：老师指定编号为 i 的同学站在编号为 1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；
从队列中去掉 M 个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。
输入格式
第一行一个整数 N，表示了有 N 个同学。
第 2∼N 行，第 i 行包含两个整数 k,p，其中 k 为小于 i 的正整数，p 为 0 或者 1。若 p 为 0，则表示将 i 号同学插入到 k 号同学的左边，p 为 1 则表示插入到右边。
第 N+1 行为一个整数 M，表示去掉的同学数目。
接下来 M 行，每行一个正整数 x，表示将 x 号同学从队列中移去，如果 x 号同学已经不在队列中则忽略这一条指令。
输出格式
一行，包含最多 N 个空格隔开的整数，表示了队列从左到右所有同学的编号。
输入输出样例
输入 #1复制
4 1 0 2 1 1 0 2 3 3
输出 #1复制
2 4 1
说明/提示
【样例解释】
将同学 2 插入至同学 1 左边，此时队列为：
2 1
将同学 3 插入至同学 2 右边，此时队列为：
2 3 1
将同学 4 插入至同学 1 左边，此时队列为：
2 3 4 1
将同学 3 从队列中移出，此时队列为：
2 4 1
同学 3 已经不在队列中，忽略最后一条指令
最终队列：
2 4 1
【数据范围】
对于 20% 的数据，1≤N≤10。
对于 40% 的数据，1≤N≤1000。
对于 100% 的数据，1<M≤N≤105。
实现代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; const int mx=1e5+10; int n,m; struct T{ int l,r; int d; }t[mx]={0}; void add(int i,int k,int f) { if(f==1) { t[k].r=t[i].r; t[k].l=i; t[i].r=k; t[t[k].r].l=k; } else { t[k].r=i; t[k].l=t[i].l; t[i].l=k; t[t[k].l].r=k; } } int main() { int x,k,f; cin>>n; t[0].r=0,t[0].l=0; add(0,1,1); for (int i=2;i<=n;i++) { cin>>x>>f; add(x,i,f); } cin>>m; while(m--) { cin>>x; t[x].d=1; } for (int i=t[0].r;i;i=t[i].r) { if (t[i].d==0) cout<<i<<" "; } return 0; }