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

P3156 【深基15.例1】询问学号题目描述有 n(n≤2×106) 名同学陆陆续续进入教室。我们知道每名同学的学号在 1 到 109 之间按进教室的顺序给出。上课了老师想知道第 i 个进入教室的同学的学号是什么最先进入教室的同学 i1询问次数不超过 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实现代码#includecstdio int a[2000001]; int main() { int n,m,sum; scanf(%d %d,n,m); for(int i1;in;i) scanf(%d,a[i]); for(int i1;im;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)。当 k0 时说明清空该格子。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; vectorint a[100010]; int main(){ int n,q; cinnq; int x,y,z,op; while(q--){ cinop; if(op1){ cinxyz; if(a[x].size()y1) { a[x].resize(y1); } a[x][y]z; } else{ cinxy; couta[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。实现代码#includeiostream #includecstdio using namespace std; long long stk[1000]; int main(){ long long i0,now0; char op; while((opgetchar())!){ if(op0op9) now*10,nowop-0; else if(op.){ stk[i]now; now0; } 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--; } } coutstk[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 cnt0,k0,i0,n,m,b0; cinnm; while(cnt!n){ i; if(in){ i1; } if(a[i]0){ k; if(k%m0){ cnt; a[i]1; couti ; } } } 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 则表示插入到右边。第 N1 行为一个整数 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% 的数据1M≤N≤105。实现代码#includeiostream #includecstdio #includecstdlib #includecstring using namespace std; const int mx1e510; int n,m; struct T{ int l,r; int d; }t[mx]{0}; void add(int i,int k,int f) { if(f1) { t[k].rt[i].r; t[k].li; t[i].rk; t[t[k].r].lk; } else { t[k].ri; t[k].lt[i].l; t[i].lk; t[t[k].l].rk; } } int main() { int x,k,f; cinn; t[0].r0,t[0].l0; add(0,1,1); for (int i2;in;i) { cinxf; add(x,i,f); } cinm; while(m--) { cinx; t[x].d1; } for (int it[0].r;i;it[i].r) { if (t[i].d0) couti ; } return 0; }