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; 
}