大学連合アルゴリズムウィンター学院第6回(スタック、キュー、インデックス)
52211 ワード
スタック
LIFO構造
後で入って初めて出てきます#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//cout.tie(nullptr);
cout << fixed;
cout.precision(2);
ll n = 0;
cin >> n;
string s;
cin >> s;
vector<double> a(n);
for (i = 0; i < n; ++i) {
cin >> a[i];
}
stack<double> st;
for (i = 0; i < s.length(); ++i) {
if (s[i] == '*' || s[i] == '/' || s[i] == '+' || s[i] == '-') {
double a = st.top();
st.pop();
double b = st.top();
st.pop();
if (s[i] == '*') {
st.push((1.0) * a * b );
}
else if (s[i] == '/') {
st.push((1.0) * b / a);
}
else if (s[i] == '+') {
st.push(a + b);
}
else if (s[i] == '-') {
st.push(b - a);
}
}
else {
st.push(a[s[i] - 'A']);
}
}
//printf("%.2f\n", st.top());
cout << st.top();
}
キュー
FIFO(First In First Out)
1158ジョセフス問題
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
queue<int> q;
for (int i = 1; i <= n; ++i) {
q.push(i);
}
int t = 0;
cout << '<';
while (!q.empty()) {
t++;
int temp = q.front();
q.pop();
if (t % k == 0) {
cout << temp;
if (!q.empty()) cout << ", ";
}
else q.push(temp);
}
cout << '>';
}
19591ユニークコンピューティング
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
//cin.tie(nullptr);
string s;
getline(cin, s);
bool flag = false;
while (s != ".") {
//cout << s << '\n';
flag = true;
stack<char> so;
for (i = 0; i < s.length(); ++i) {
if (s[i] == '(' || s[i]=='[') {
so.push(s[i]);
}
else if (s[i] == ')') {
if (!so.empty() and so.top() == '(') so.pop();
else { cout << "no" << '\n'; flag = false; break; }
} else if(s[i] == ']') {
if (!so.empty() and so.top() == '[') so.pop();
else { cout << "no" << '\n'; flag = false; break; }
}
}
if ((!so.empty()) and flag) {
cout << "no" << '\n';
while (!so.empty()) so.pop();
}
else if(flag){
cout << "yes" << '\n';
}
getline(cin, s);
//cin.ignore();
}
}
1966プリンタキュー
キューと優先キューの使用
数字でrankをあげて、探し続けます.#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int rank;
vector<pair<int, int>> a;
queue<pair<int, int>> q;
priority_queue<int> pq;
for (i = 0; i < n; ++i) {
cin >> rank;
q.push(make_pair(i,rank));
pq.push(rank);
}
int c = 1;
while (!q.empty()) {
int num = q.front().first;
int rank = q.front().second;
q.pop();
if (rank == pq.top()) {
if (num == m) {
cout << c << '\n';
break;
}
else {
c += 1;
pq.pop();
}
}
else {
q.push(make_pair(num, rank));
}
}
}
}
デッキ
1021回転キュー
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
deque<int> dq;
for (i = 1; i <= n; ++i) {
dq.push_back(i);
}
vector<int> a;
for (i = 0; i < m; ++i) {
int temp;
cin >> temp;
a.push_back(temp);
}
int ans = 0;
int c = 0;
for (i = 0; i < a.size(); ++i) {
int index = 0;
for (j = 0; j < dq.size(); ++j) {
if (a[i] == dq[j]) {
index = j;
break;
}
}
c = 0;
/* 뒤에서 빼기*/
if (index > dq.size() - index) {
while (1) {
if (dq.front() == a[i]) {
dq.pop_front();
break;
}
else {
dq.push_front(dq.back());
dq.pop_back();
ans += 1;
}
}
}
else {
while (1) {
if (dq.front() == a[i]) {
dq.pop_front();
break;
}
else {
dq.push_back(dq.front());
dq.pop_front();
ans += 1;
}
}
}
}
cout << ans << '\n';
}
Reference
この問題について(大学連合アルゴリズムウィンター学院第6回(スタック、キュー、インデックス)), 我々は、より多くの情報をここで見つけました
https://velog.io/@tonyhan18/대학-연합-알고리즘-윈터-스쿨-6회차스택-큐-덱
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//cout.tie(nullptr);
cout << fixed;
cout.precision(2);
ll n = 0;
cin >> n;
string s;
cin >> s;
vector<double> a(n);
for (i = 0; i < n; ++i) {
cin >> a[i];
}
stack<double> st;
for (i = 0; i < s.length(); ++i) {
if (s[i] == '*' || s[i] == '/' || s[i] == '+' || s[i] == '-') {
double a = st.top();
st.pop();
double b = st.top();
st.pop();
if (s[i] == '*') {
st.push((1.0) * a * b );
}
else if (s[i] == '/') {
st.push((1.0) * b / a);
}
else if (s[i] == '+') {
st.push(a + b);
}
else if (s[i] == '-') {
st.push(b - a);
}
}
else {
st.push(a[s[i] - 'A']);
}
}
//printf("%.2f\n", st.top());
cout << st.top();
}
FIFO(First In First Out)
1158ジョセフス問題
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
queue<int> q;
for (int i = 1; i <= n; ++i) {
q.push(i);
}
int t = 0;
cout << '<';
while (!q.empty()) {
t++;
int temp = q.front();
q.pop();
if (t % k == 0) {
cout << temp;
if (!q.empty()) cout << ", ";
}
else q.push(temp);
}
cout << '>';
}
19591ユニークコンピューティング
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
//cin.tie(nullptr);
string s;
getline(cin, s);
bool flag = false;
while (s != ".") {
//cout << s << '\n';
flag = true;
stack<char> so;
for (i = 0; i < s.length(); ++i) {
if (s[i] == '(' || s[i]=='[') {
so.push(s[i]);
}
else if (s[i] == ')') {
if (!so.empty() and so.top() == '(') so.pop();
else { cout << "no" << '\n'; flag = false; break; }
} else if(s[i] == ']') {
if (!so.empty() and so.top() == '[') so.pop();
else { cout << "no" << '\n'; flag = false; break; }
}
}
if ((!so.empty()) and flag) {
cout << "no" << '\n';
while (!so.empty()) so.pop();
}
else if(flag){
cout << "yes" << '\n';
}
getline(cin, s);
//cin.ignore();
}
}
1966プリンタキュー
キューと優先キューの使用
数字でrankをあげて、探し続けます.
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int rank;
vector<pair<int, int>> a;
queue<pair<int, int>> q;
priority_queue<int> pq;
for (i = 0; i < n; ++i) {
cin >> rank;
q.push(make_pair(i,rank));
pq.push(rank);
}
int c = 1;
while (!q.empty()) {
int num = q.front().first;
int rank = q.front().second;
q.pop();
if (rank == pq.top()) {
if (num == m) {
cout << c << '\n';
break;
}
else {
c += 1;
pq.pop();
}
}
else {
q.push(make_pair(num, rank));
}
}
}
}
デッキ
1021回転キュー
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
deque<int> dq;
for (i = 1; i <= n; ++i) {
dq.push_back(i);
}
vector<int> a;
for (i = 0; i < m; ++i) {
int temp;
cin >> temp;
a.push_back(temp);
}
int ans = 0;
int c = 0;
for (i = 0; i < a.size(); ++i) {
int index = 0;
for (j = 0; j < dq.size(); ++j) {
if (a[i] == dq[j]) {
index = j;
break;
}
}
c = 0;
/* 뒤에서 빼기*/
if (index > dq.size() - index) {
while (1) {
if (dq.front() == a[i]) {
dq.pop_front();
break;
}
else {
dq.push_front(dq.back());
dq.pop_back();
ans += 1;
}
}
}
else {
while (1) {
if (dq.front() == a[i]) {
dq.pop_front();
break;
}
else {
dq.push_back(dq.front());
dq.pop_front();
ans += 1;
}
}
}
}
cout << ans << '\n';
}
Reference
この問題について(大学連合アルゴリズムウィンター学院第6回(スタック、キュー、インデックス)), 我々は、より多くの情報をここで見つけました
https://velog.io/@tonyhan18/대학-연합-알고리즘-윈터-스쿨-6회차스택-큐-덱
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <functional>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#define ll long long
#define len 1001
using namespace std;
int ans, i, j, n, m;
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
deque<int> dq;
for (i = 1; i <= n; ++i) {
dq.push_back(i);
}
vector<int> a;
for (i = 0; i < m; ++i) {
int temp;
cin >> temp;
a.push_back(temp);
}
int ans = 0;
int c = 0;
for (i = 0; i < a.size(); ++i) {
int index = 0;
for (j = 0; j < dq.size(); ++j) {
if (a[i] == dq[j]) {
index = j;
break;
}
}
c = 0;
/* 뒤에서 빼기*/
if (index > dq.size() - index) {
while (1) {
if (dq.front() == a[i]) {
dq.pop_front();
break;
}
else {
dq.push_front(dq.back());
dq.pop_back();
ans += 1;
}
}
}
else {
while (1) {
if (dq.front() == a[i]) {
dq.pop_front();
break;
}
else {
dq.push_back(dq.front());
dq.pop_front();
ans += 1;
}
}
}
}
cout << ans << '\n';
}
Reference
この問題について(大学連合アルゴリズムウィンター学院第6回(スタック、キュー、インデックス)), 我々は、より多くの情報をここで見つけました https://velog.io/@tonyhan18/대학-연합-알고리즘-윈터-스쿨-6회차스택-큐-덱テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol