P3156 【深基15.例1】询问学号

链接 : 【深基15.例1】询问学号 - 洛谷

直接输入，然后输出a[i]即可;

代码 : 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int main(){int  n, q ; cin >> n >> q;vector<int> a(n+1);for(int i=1;i<=n;i++) cin >> a[i];while(q--){int x ;cin >> x;cout << a[x] << endl;}	return 0;
}

P3613 【深基15.例2】寄包柜

链接 : 【深基15.例2】寄包柜 - 洛谷

这题直接套用stl中的map解决就行了 : 

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main(){int n , q ; cin >> n >> q;int op,i,j,k;map<int,map<int,int>> a; // 下标 while(q--){cin >> op;if(op == 1){cin >> i >> j >> k;a[i][j] = k;}else{cin >> i >> j;cout << a[i][j] << endl;}}return 0;
}

或者用数组模拟 : 

#include<cstdio>
#include<map>
using namespace std;
int n,q,p,k;
map<long long,int>b;
long long i,j;
int main()
{scanf("%d%d",&n,&q);while(q--){scanf("%d%d%d",&p,&i,&j);if(p==1){scanf("%d",&k);b[i*1000000+j]=k;}else printf("%d\n",b[i*1000000+j]);}return 0;
}

P1449 后缀表达式

链接 : 后缀表达式 - 洛谷

栈的模板题，直接用stack来模拟栈，或者用数组来模拟stack也行；

// 后缀表达式;
// 可以用栈stack模拟
// 也可以用数组模拟 #include<cstring>
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
stack<int> st;
char ch = '0';
int s = 0;
int x , y ;
int main(){while(ch != '@'){ch = getchar();if(ch=='+'){x = st.top() ; st.pop();y = st.top() ; st.pop();st.push(x+y) ; }else if(ch == '-'){x = st.top() ; st.pop();y = st.top() ; st.pop();st.push(y - x);}else if(ch == '*'){x = st.top() ; st.pop();y = st.top() ; st.pop();st.push(x * y);}else if(ch == '/'){x = st.top() ; st.pop();y = st.top() ; st.pop();st.push(y / x);}else if(ch == '.') {st.push(s);s = 0;}else{s = s* 10 + (int)(ch-'0');}}cout << st.top() << endl;return 0;
}

P1996 约瑟夫问题

链接 : 约瑟夫问题 - 洛谷

直接暴力模拟就行

// 暴力模拟 
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int main(){int n , m ; cin >> n >> m;int cnt = 0 , k = 0 , s = 0;vector<int> a(n+1,0);while(cnt != n){k++;if(k>n) k = 1;// 标号 if(a[k]==0){s++;//人数 if(s==m){cnt ++;s = 0;a[k] = 1;cout << k << " ";}	}}	return 0;
}

用队列来操作 : 

用cnt来统计当前报数的人数，如果cnt == m,那么输出队头，且队头出队；

否则将队头放入最后面，以此来实现模拟；

// 用队列模拟 : 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int main(){int n , m ;  cin >> n >> m ;queue<int> q;for(int i=1;i<=n;i++) q.push(i);int cnt = 1 ; // 表示当前数的人数 while(!q.empty()){if(cnt == m){cout << q.front() << " ";q.pop();cnt = 1;}else{q.push(q.front());q.pop();cnt ++;}}cout << endl;
}

P1160 队列安排

链接 : 队列安排 - 洛谷

这题是一道静态双链表的好题 : 用结构体数组去模拟双链表 ， 结构体中定义l,r分别表示t[i]的左节点 和 右节点 ， 用 tag 表示 是否被删除；

具体可以参考luogu第一篇题解，要注意的是，要设置t[0].l=0.t[0].r=0,然后add(1,0,1),这样就可以避免循环而出现死循环的问题；

代码 : 

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;struct Node{int l,r;int tag;//标记是否要用到 
}t[N]={0};void add(int i,int k,int p){if(p==1) { // i放到k右 t[i].r = t[k].r;t[i].l = k;t[k].r = i;t[t[i].r].l = i;} else { // i放到k左边 t[i].l = t[k].l;t[k].l = i;t[i].r = k;t[t[i].l].r = i;}
}int main(){int n ; cin >> n;t[0].l = 1 ; t[0].r = 0;add(1,0,1);for(int i=2;i<=n;i++){int k,p;cin >> k >> p;// k 表示 k 号同学 // p 表示左右add(i,k,p);	}int m ; cin >> m;int mx = m;while(m--){int x ; cin >> x;t[x].tag = 1; }for(int i=t[0].r;i;i=t[i].r){if(t[i].tag==0){cout << i << " ";}}return 0;
}

P1540 [NOIP2010 提高组] 机器翻译

链接 : [NOIP2010 提高组] 机器翻译 - 洛谷

这个题最先想到的就是用vector来模拟队列，代码如下 : 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int main(){int  m, n ; cin >> m >> n;vector<int> a;int ans = 0;while(n--){int x ; cin >> x;if(find(a.begin(),a.end(),x) == a.end()){ // 找不到 a.push_back(x);ans ++;}if(a.size() > m)a.erase(a.begin());}cout << ans << endl;return 0;
}

那用队列(queue)怎么写呢?代码如下 :(这里有个小trick : 用一个tag数组记录x是否出现过) 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int tag[1010] = {0};
int main(){int  m, n ; cin >> m >> n;queue<int> a;int ans = 0;while(n--){int x ; cin >> x;if(!tag[x]){ // 找不到 a.push(x);ans ++;tag[x] = true;}if(a.size() > m){int y = a.front();if(x != y) tag[y] = 0;a.pop();}}cout << ans << endl;return 0;
}

P1739 表达式括号匹配

链接 : 表达式括号匹配 - 洛谷

这题应该是栈来模拟，但是用不到，只用设置一个cnt变量，遇到(减一，遇到)加一，如果cnt>0，直接返回false,为true当且仅当最后cnt==0,请看代码 : 

#include<bits/stdc++.h>
using namespace std;
int main(){string s ;cin >> s;int t = 0 ;for(char& c : s){if(c=='(') t--;else if(c==')') t++;if(t>0 ){cout << "NO" << endl;return 0;}}if(t==0) cout << "YES" << endl;else cout << "NO" << endl;
}

 P4387 【深基15.习9】验证栈序列

链接 : 【深基15.习9】验证栈序列 - 洛谷

用栈模拟

代码如下 : 

#include<iostream>
#include<stack>
using namespace std;
stack<int>q;//栈q 
int p,n;//p组数据，n为序列长度 
int main()
{cin>>p;while(p--){cin>>n;int a[n+1],b[n+1],sum=1;//入栈队列a，待检验队列b，计数器sum for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++){q.push(a[i]);//入栈 while((q.top())==b[sum]) {q.pop(),sum++;//sum++到b下一个元素 if(q.empty())break;//注意这里，第一次RE就因为当栈空时还用了出栈操作，所以要手动结束循环 }}if(q.empty()) cout<<"Yes"<<endl;//如果栈为空说明出栈序列b正确 else cout<<"No"<<endl;while(!q.empty())q.pop();//清空栈 }return 0; 
}