A. 验证栈序列
时空限制：1s，512MB
题目描述：
给出 pushed 和 poped 两个序列，其取值从 1 到 n(n≤100000)。
已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。
每个测试点有多组数据。
输入格式：
第一行输入一个正整数 T，表示数据组数。
对于每组数据，第一行输入一个正整数 n；
第二行输入 n 个正整数，表示入栈序列；
第三行输入 n 个正整数，表示出栈序列。
输出格式：
对于每组数据单独输出一行 Yes 或 No。
样例输入：
2 5 1 2 3 4 5 4 5 3 2 1 5 1 2 3 4 5 3 5 2 4 1
样例输出：
Yes No
数据规模：
n ≤ 100000
ptr1=1,ptr2=1,flag=true;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i][1]);
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i][2]);
}
while(ptr2<=n){
while(s.empty()||s.top()!=a[ptr2][2]&&ptr1<=n){
s.push(a[ptr1++][1]);
}
if(!s.empty()&&s.top()==a[ptr2][2]){
s.pop();
ptr2++;
}
else{
cout<<"No"<<endl;
flag=false;
break;
}
}
if(flag)cout<<"Yes"<<endl;
B. 合并果子
时间限制：1s 空间限制：128M
题目描述：
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了 n 堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有 3 种果子，数目依次为 1 ， 2 ， 9 。可以先将 1 、 2 堆合并，新堆数目为 3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 3+12=15 。可以证明 15 为最小的体力耗费值。
输入格式：
第一行是一个整数 n(1≤n≤1e5)，表示果子的种类数。
第二行包含 n 个整数，用空格分隔，第 i 个整数 ai(1≤ai≤1e9) 是第 i 种果子的数目。
输出格式：
一个整数，也就是最小的体力耗费值。
样例输入：
3 1 2 9
样例输出：
15
while(q.size()!=1){
now1=q.top();
q.pop();
now2=q.top();
q.pop();
q.push(now1+now2);
ans+=(now1+now2);
}
新做法（误
C. 矩阵
时间限制：1s 空间限制：512M
题目描述：
给定一个 n×m 的矩阵，给定 q 组询问，每组询问输入两个数 x 和 y，表示查询矩阵 x 行 y 列的元素是什么。
输入格式：
第一行三个正整数 n, m, q；
接下来 n 行，每行 m 个正整数，表示矩阵中的元素。其中第 i 行第 j 列的元素表示 ai−1,j−1。
接下来 q 行，每行两个正整数 x, y，表示询问第 x 行第 y 列的元素是什么。保证 0≤x
样例输入：
3 4 2 1 2 3 4 5 6 7 8 9 10 11 12 1 3 0 2
样例输出：
8 3
数据规模：
1≤n,m,q≤10^5，0<ai,j<10^9
vector<int> v[114514];
D. 模板库应用2-模板题3
题目描述
现在有10个集合（元素不可重），编号为0~9，现在有6种操作：
- 给一个集合x插入一个数y。
- 给一个集合x删除一个数y（如果没有就不删）。
- 给两个集合x，y，将集合x=x∪y（集合求并），并将y清空。
- 给两个集合x，y，将集合x=x∩y（集合求交），并将y清空。
- 给一个集合x和一个数y，询问集合x中是否出现了y。
- 给一个集合x，问集合x中有多少个数。
不保证所有数不相同。
注意操作3与操作4：当x=y时，操作后将y清空，由于x=y，所以集合x是空集。
输入描述
输入一个n，表示接下来有n次操作，
接下来n行每行一个数op，
若op=1~5，则之后再跟两个数x，y。
若op=6，则之后再跟一个数x。
输出描述
对于每个操作5,6各输出一行表示答案
样例输入
15
1 3 62201
4 1 4
6 3
2 4 42881
2 9 90161
5 4 11649
3 8 3
4 9 5
1 6 54033
6 0
2 3 60171
1 7 84681
3 5 4
1 1 98337
5 0 24497
样例输出
1
No
0
No
数据范围
n=100000,集合编号小于10，数字小于等于100000
时空限制
1s，512M
if(op==2){
if(s[x].count(y)){
set<int>::iterator it=s[x].find(y);
s[x].erase(it);
}
}
if(op==3){
for(auto it : s[y]){
s[x].insert(it);
}
s[y].clear();
}
if(op==4){
set<int> tmp;
for(auto it : s[y]){
if(s[x].count(it)){
tmp.insert(it);
}
}
s[x]=tmp;
s[y].clear();
}
if(op==5){
if(s[x].count(y)){
printf("Yes\n");
}
else printf("No\n");
}
E. 【模板】map
时间：1s 空间：256M
题目描述：
有一个数组a，下标范围是[−109,109]，初始值是0，q次操作，
操作1是修改操作，操作2是查询操作：
- 1 x y 修改 ax += y，y 范围是[−109,109]。
- 2 x 查询 ax 有没被修改过，如果有，则输出 “YES”，否则输出 “NO”
q 次操作后，输出所有被操作过的下标以及它们对应的值，每行两个整数
输入格式：
第一行包含一个整数 q，表示操作次数。
每次操作的输入格式如题面所示。
输出格式：
对于每次操作 2 输出一行 “YES” 或 “NO”
操作完后，输出若干行，每行两个整数代表所有被操作过的下标以及它们对应的值。按照被操作过的下标从小到大输出。
样例1输入：
5 2 -1 1 -1 1 2 -1 1 1000000000 1000000000 1 -1 -1
样例1输出：
NO YES -1 0 1000000000 1000000000
约定与提示：
1≤q≤3·10^5
if(op==1){
scanf("%lld", &y);
mp[x] += y;
}
if(op==2){
if(mp.count(x)){
printf("YES\n");
}
else{
printf("NO\n");
}
}
F. 模板库应用2-模板题2
题目描述
有两种操作：
- 给一个名字为s的人标号x，
- 查询名字为s的人的标号。
不保证所有数不相同，不保证操作2所查询的人一定存在。
输入描述
输入一个n，表示接下来有n种操作，
接下来n行每行一个数op，一个字符串s，
若op=1，则之后再跟一个数x，表示你要将名字为s的人标号为x，
若op=2，则你需要输出名字为s的人的标号。
输出描述
对于每个操作2输出一行，
如果不存在这个人，输出”Not found.”（不含双引号），
如果存在，则输出这个人的标号。
样例输入
10 2 cqszhwgywo 1 uqhlayolko 286241036 2 gdielmpguw 2 uqhlayolko 1 lturzllzrj 241550001 1 zkbvujvncb 674852961 1 wogdltbior 236413121 1 bccgbnbzzm 622686621 1 uckgjjyume 415730509 2 lturzllzrj
样例输出
Not found. Not found. 286241036 241550001
数据范围
|s|为字符串s的长度
n=100000, |s|=10, 1 ≤ x ≤ 1000000000
时空限制
1s, 512M
if(op==1){
cin>>x;
mp[s]=x;
}
if(op==2){
if(mp[s]){
printf("%lld\n",mp[s]);
}
else{
printf("Not found.\n",mp[s]);
}
}
G. 爱排队的史莱姆
时间：1s 空间：512M
题目描述：
史莱姆学校最近出了一个排队的活动，所有的史莱姆都很喜欢，
排队的规则是这样的，我们有一个很长的队伍，有n个史莱姆，
每个史莱姆都有自己的一个身高。每次我们选择前m个史莱姆组成新的小队伍，只有当新的小队伍为m个史莱姆时候，
我们把会把小队伍中最高的史莱姆输出，然后此时还剩下m-1个史莱姆，我们继续从大队伍中的最前面的一个史莱姆加入到小队伍中，
此时小队伍中又有m个史莱姆了，我们继续选取该小队伍中的最高的史莱姆输出。
然后继续执行以上操作，直到最后大队伍和小队伍的史莱姆总和不到m个史莱姆，活动结束。
题目输入：
输入一个整数n,输入一个整数m
第二行，输入n个整数A[i]
题目输出：
输出一行整数
样例输入：
3 1 1 2 3
样例输出：
1 2 3
数据范围：
m<=n<=1000
1<=A[i]<=1e9
while(qu.size()+qe.size()>=m){
while(qe.size()<m){
qe.push(qu.front());
qu.pop();
}
printf("%d ",qe.top());
qe.pop();
}
H. 排队
时间：1s 空间：256M
题目描述：
幼儿园里的小朋友在玩排队游戏，他们会根据老师的要求排队。
老师共进行 n 次操作，操作分为以下三种：
1 x: 将一名身高为 x 的小朋友加入队尾2: 输出队列最前面的小朋友的身高，并让他出队列，保证进行该操作时队列非空3: 将队列里的小朋友按照身高升序排序
输入格式：
第一行，包含一个正整数 n，表示操作次数。
加下来n行按照以下格式之一输入操作：
1 x
2
3
输出格式：
对应操作进行输出。
样例1输入：
9 1 1 1 3 1 2 3 2 2 1 0 3 2
样例1输出：
1 2 0
约定与解释：
对于100%的数据，1≤n≤2×105;0≤x≤109。
样例1解释：
第1个操作后，队列为 [1]；
第2个操作后，队列为 [1,3]；
第3个操作后，队列为 [1,3,2]；
第4个操作后，队列为 [1,2,3]；
第5个操作后，队列为 [2,3]；
第6个操作后，队列为 [3]；
第7个操作后，队列为 [3,0]；
第8个操作后，队列为 [0,3]；
第9个操作后，队列为 [3]。
if (op == 1) {
int x;
scanf("%d", &x);
qu.push(x);
}
if (op == 2) {
if (!qe.empty()) {
printf("%d\n", qe.top());
qe.pop();
} else {
printf("%d\n", qu.front());
qu.pop();
}
}
if(op==3) {
while (!qu.empty()) {
qe.push(qu.front());
qu.pop();
}
}
I. 查询数集
时间限制：1s 空间限制：512M
题目描述：
大数学家高斯小时候偶然间发现一种有趣的自然数集合 B，对于以 a 为基的集合 B 定义如下：
- a 是集合 B 的基，且 a 是 B 的第一个元素；
- 如果 x 在集合 B 中，则 2x+1 和 3x+1 也都在集合 B 中；
- 没有其他元素在集合 B 中了。
现在小高斯想知道如果将集合 B 中元素按照升序排列，第 n 个元素会是多少？
输入格式：
输入若干行，每行输入包括两个数字，集合的基 a(1≤a≤50) 以及所求元素序号 n(1≤n≤1000000)
输出格式：
对于每个输入，输出集合 B 的第 n 个元素值，以单个空格隔开。
样例输入：
1 100 28 5437
样例输出：
418 900585
#include<bits/stdc++.h>
using namespace std;
int p[1145141],a,n;
void blah(){
p[1]=a;
int t=1,t1=1,t2=1;
while(t<n){
int x = p[t1]*2+1;
int y = p[t2]*3+1;
if(x>y){
p[++t]=y;
t2++;
}else if(y>x){
p[++t]=x;
t1++;
}else{
p[++t]=x;
t1++;
t2++;
}
}
cout<<p[t]<<endl;
}
int main(){
while(cin>>a>>n){
blah();
}
return 0;
}