P3156 [深基15.例1] 询问学号
#include <cstdio>
const int MAXN = 2000005;
int a[MAXN];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
while (m--) {
int q;
scanf("%d", &q);
printf("%d\n", a[q - 1]);
}
return 0;
}
P3613 [深基15.例2] 寄包柜
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 100005;
vector<int> v[MAXN];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
while (q--) {
int op, i, j;
scanf("%d%d%d", &op, &i, &j);
if (op == 1) {
int k; scanf("%d", &k);
if (v[i].size() <= j) v[i].resize(j + 1);
v[i][j] = k;
} else {
printf("%d\n", v[i][j]);
}
}
return 0;
}
UVA673 平衡的括号 Parentheses Balance
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 150;
char stk[MAXN], paren[MAXN];
int p;
int main()
{
paren['['] = ']'; paren['('] = ')';
int n;
scanf("%d\n", &n);
while (n--) {
p = 0;
string seq;
getline(cin, seq);
bool ok = true;
for (int i = 0; i < seq.length(); i++) {
if (seq[i] == '(' || seq[i] == '[') {
// 入栈
stk[p] = seq[i]; p++;
} else {
// stk[p-1] seq[i]
if (p > 0 && paren[stk[p-1]] == seq[i]) p--;
else {
ok = false; break;
}
}
}
if (p != 0) ok = false;
printf("%s\n", ok ? "Yes" : "No");
}
return 0;
}
P1449 后缀表达式
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
char expr[1005];
stack<int> s;
int main()
{
scanf("%s", expr);
int len = strlen(expr);
int i = 0;
while (i < len) {
char ch = expr[i];
if (ch == '@') break;
if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
int n2 = s.top();
s.pop();
int n1 = s.top();
s.pop();
if (ch == '+') s.push(n1 + n2);
else if (ch == '-') s.push(n1 - n2);
else if (ch == '*') s.push(n1 * n2);
else s.push(n1 / n2);
} else {
int n = 0;
while (ch >= '0' && ch <= '9') {
n = n * 10 + ch - '0';
++i;
ch = expr[i];
}
s.push(n);
}
++i;
}
printf("%d\n", s.top());
return 0;
}
P1996 约瑟夫问题
#include <cstdio>
const int MAXN = 15000;
int q[MAXN], head, tail;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
q[tail] = i; tail++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
q[tail] = q[head]; tail++;
head++;
}
printf("%d ", q[head]);
head++;
}
return 0;
}
P1540 [NOIP2010 提高组] 机器翻译
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN = 1005;
bool used[MAXN];
queue<int> que;
int main()
{
int m, n;
scanf("%d%d", &m, &n);
int sz = 0, ans = 0;
for (int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
if (!used[x]) {
++ans;
if (sz == m) {
int cur = que.front();
que.pop();
used[cur] = false;
} else ++sz;
que.push(x);
used[x] = true;
}
}
printf("%d\n", ans);
return 0;
}
P1160 队列安排
#include <cstdio>
const int MAXN = 100005;
int l[MAXN], r[MAXN];
bool del[MAXN];
int main()
{
int n;
scanf("%d", &n);
r[0] = 1;
l[1] = 0;
r[1] = n + 1;
l[n + 1] = 1;
for (int i = 2; i <= n; ++i) {
int k, p;
scanf("%d%d", &k, &p);
if (p == 0) {
int pre = l[k];
r[pre] = i;
l[i] = pre;
r[i] = k;
l[k] = i;
} else {
int suf = r[k];
r[k] = i;
l[i] = k;
r[i] = suf;
l[suf] = i;
}
}
int m;
scanf("%d", &m);
while (m--) {
int x;
scanf("%d", &x);
if (!del[x]) {
del[x] = true;
int pre = l[x];
int suf = r[x];
r[pre] = suf;
l[suf] = pre;
}
}
int cur = r[0];
while (cur != n + 1) {
printf("%d ", cur);
cur = r[cur];
}
return 0;
}
P2058 [NOIP2016 普及组] 海港
#include <cstdio>
int t[100005], k[100005];
int x[300005], xlen;
int cnt[100005]; // cnt记录每个国家对应的乘客人数
int main()
{
int n;
scanf("%d", &n);
int tp = 0, xp = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
scanf("%d%d", &t[i], &k[i]);
for (int j = 0; j < k[i]; j++) {
scanf("%d", &x[xlen]);
if (cnt[x[xlen]] == 0) ans++;
cnt[x[xlen]]++;
xlen++;
}
// 删除到达时间小于等于Ti-86400的乘客
while (t[tp] <= t[i] - 86400) {
for (int j = 0; j < k[tp]; j++) {
--cnt[x[xp]];
if (cnt[x[xp]] == 0) ans--;
xp++;
}
tp++;
}
printf("%d\n", ans);
}
return 0;
}
P4387 [深基15.习9] 验证栈序列
#include <cstdio>
#include <stack>
using namespace std;
const int MAXN = 100005;
int in[MAXN], out[MAXN];
stack<int> s;
int main()
{
int q;
scanf("%d", &q);
while (q--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &in[i]);
for (int i = 1; i <= n; i++) scanf("%d", &out[i]);
while (!s.empty()) s.pop();
int p = 1;
for (int i = 1; i <= n; i++) {
s.push(in[i]);
while (!s.empty() && p <= n && s.top() == out[p]) {
s.pop(); p++;
}
}
printf("%s\n", s.empty() && p > n ? "Yes" : "No");
}
return 0;
}
P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10005;
int a[MAXN], b[MAXN];
int p, q, r, n;
int getmin() {
int res;
if (q > r || (p <= n && a[p] < b[q])) {
res = a[p]; p++;
} else {
res = b[q]; q++;
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
int ans = 0;
p = 1; q = 1; r = 0;
for (int i = 1; i < n; i++) {
int cur = 0;
cur += getmin(); cur += getmin();
ans += cur;
r++; b[r] = cur;
}
printf("%d\n", ans);
return 0;
}
P2201 数列编辑器
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1000005;
char op[5];
stack<int> s1, s2;
int sum[MAXN], ans[MAXN];
int main()
{
int n;
scanf("%d", &n);
int len = 0;
ans[0] = -1e9;
for (int i = 0; i < n; i++) {
scanf("%s", op);
if (op[0] == 'I') {
int x;
scanf("%d", &x);
s1.push(x);
++len;
sum[len] = sum[len - 1] + x;
ans[len] = max(ans[len - 1], sum[len]);
} else if (op[0] == 'D') {
s1.pop();
len--;
} else if (op[0] == 'L') {
if (!s1.empty()) {
s2.push(s1.top());
s1.pop();
len--;
}
} else if (op[0] == 'R') {
if (!s2.empty()) {
s1.push(s2.top());
s2.pop();
len++;
sum[len] = sum[len - 1] + s1.top();
ans[len] = max(ans[len - 1], sum[len]);
}
} else {
int k;
scanf("%d", &k);
printf("%d\n", ans[k]);
}
}
return 0;
}
P5788 [模板] 单调栈
#include <cstdio>
#include <stack>
using namespace std;
const int MAXN = 3e6 + 5;
int h[MAXN], ans[MAXN];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
stack<int> s;
for (int i = 1; i <= n; i++) {
while (!s.empty() && h[s.top()] < h[i]) {
ans[s.top()] = i;
s.pop();
}
s.push(i);
}
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
return 0;
}
P2866 [USACO06NOV] Bad Hair Day S
#include <cstdio>
#include <stack>
using namespace std;
typedef long long LL;
const int MAXN = 80005;
int h[MAXN];
stack<int> s; // s存牛的编号而不是牛的身高
int main()
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
LL ans = 0;
for (int i = 1; i <= n; i++) {
// 淘汰掉栈中之前<=h[i]的牛
while (!s.empty() && h[s.top()] <= h[i]) {
ans += i - s.top() - 1;
s.pop();
}
s.push(i);
}
while (!s.empty()) { // 假设了h[n+1]是一头很高很高的牛
ans += n - s.top();
s.pop();
}
// 整体复杂度O(n)
printf("%lld\n", ans);
return 0;
}
P1106 删数问题
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
const int MAXN = 255;
char num[MAXN];
bool del[MAXN];
int main()
{
int k;
scanf("%s%d", num, &k);
stack<char> s;
int len = strlen(num);
for (int i = 0; i < len; i++) {
while (!s.empty() && k > 0 && num[s.top()] > num[i]) {
del[s.top()] = true; s.pop(); k--;
}
s.push(i);
}
while (!s.empty() && k > 0) {
del[s.top()] = true; s.pop(); k--;
}
bool flag = false;
for (int i = 0; i < len; i++) {
if (!del[i] && (num[i] != '0' || flag)) {
printf("%c", num[i]);
flag = true;
}
}
if (!flag) printf("0");
return 0;
}
P1901 发射站
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1000005;
int h[MAXN], v[MAXN];
LL sum[MAXN];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &h[i], &v[i]);
stack<int> s;
LL ans = 0;
for (int i = 1; i <= n; i++) {
while (!s.empty() && h[s.top()] < h[i]) {
sum[i] += v[s.top()]; ans = max(ans, sum[i]);
s.pop();
}
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n; i >= 1; i--) {
while (!s.empty() && h[s.top()] < h[i]) {
sum[i] += v[s.top()]; ans = max(ans, sum[i]);
s.pop();
}
s.push(i);
}
printf("%lld\n", ans);
return 0;
}
P1886 滑动窗口 / [模板] 单调队列
#include <cstdio>
const int MAXN = 1000005;
int a[MAXN];
struct Queue {
int q[MAXN], head, tail;
bool empty() { return head == tail; }
int front() { return q[head]; }
int back() { return q[tail - 1]; }
void pop_front() { head++; }
void pop_back() { tail--; }
void push(int x) { q[tail++] = x; }
};
Queue qmax, qmin;
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
while (!qmin.empty() && qmin.front() <= i - k) qmin.pop_front();
while (!qmin.empty() && a[qmin.back()] > a[i]) qmin.pop_back();
qmin.push(i);
if (i >= k) printf("%d ", a[qmin.front()]);
}
printf("\n");
for (int i = 1; i <= n; i++) {
while (!qmax.empty() && qmax.front() <= i - k) qmax.pop_front();
while (!qmax.empty() && a[qmax.back()] < a[i]) qmax.pop_back();
qmax.push(i);
if (i >= k) printf("%d ", a[qmax.front()]);
}
printf("\n");
return 0;
}
标签:include,int,代码,len,++,MAXN,线性,数据结构,scanf
From: https://www.cnblogs.com/ronchen/p/17588836.html