0x11 栈
- 单调栈 栈的基本操作
class MinStack {
public:
/** initialize your data structure here. */
int a[5050];
int mi[5050];
int tops;
MinStack() {
tops=0;
}
void push(int x) {
a[++tops]=x;
if(tops==1){
mi[tops]=x;
}else{
mi[tops]=min(mi[tops-1],x);
}
}
void pop() {
tops--;
}
int top() {
return a[tops];
}
int getMin() {
return mi[tops];
}
};
- 编辑器
对顶栈 栈的应用 f数组存最大sum
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5 ;
const double pi = acos(-1.0);
int n, m;
int A[maxn], Atop;
int B[maxn], Btop;
int sum[maxn], f[maxn];
signed main() {
cin >> n;
string cmd;
f[0]=-0x3f3f3f3f;
while(n--) {
cin >> cmd;
if(cmd[0] == 'I') {
cin >> m;
A[++Atop] = m;
sum[Atop] = sum[Atop - 1] + A[Atop];
f[Atop] = max(sum[Atop], f[Atop - 1]);
} else if(cmd[0] == 'Q') {
cin >> m;
cout << f[m] << endl;
} else if(cmd[0] == 'D') {
if(Atop)
Atop--;
} else if(cmd[0] == 'R') {
if(Btop == 0)
continue;
A[++Atop] = B[Btop--];
sum[Atop] = sum[Atop - 1] + A[Atop];
f[Atop] = max(f[Atop - 1], sum[Atop]);
} else if(cmd[0] == 'L') {
if(Atop == 0)
continue;
B[++Btop] = A[Atop--];
}
}
return 0;
}
- 火车进出栈问题
当入栈 + 出栈火车达到n时 输出 出战的在把栈内pop出即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5 ;
const double pi = acos(-1.0);
int n, m;
int sta[maxn], top;
int que[maxn], head, tail;
int ans;
void dfs(int num) {
if(ans >= 20)
return ;
if(num == n + 1) {
for(int i = 1; i <= tail; i++) {
cout << que[i];
}
for(int i = top; i; i--) {
cout << sta[i];
}
cout << endl;
ans++;
return ;
}
if(top) {
que[++tail] = sta[top--];
dfs(num);
sta[++top] = que[tail--];
}
sta[++top] = num;
dfs(num + 1);
--top;
}
signed main() {
cin >> n;
dfs(1);
return 0;
}
- 进出站序列问题 卡特兰数 1 0 序列 一般 1 <= 0 但是最终数量上 0 == 1
DP 直接膜大数乘除 超时。。。。。。。。。。。orz
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn =2e5 + 5 ;
const int jz = 1e9;
int res[maxn], tt;
bool pr[maxn];
int p[maxn],cnt,chu[maxn];
void init(){
pr[1]=pr[0]=1;
for(int i = 2; i < maxn; i++ ){
if(!pr[i]){
p[cnt ++ ] = i;
for(int j = (i << 1); j < maxn; j += i){
pr[j] = 1;
}
}
}
}
int ges(int n, int ps){
int s = 0;
while(n){
s += n/ps;
n/=ps;
}
return s;
}
void mul(int b){
int r = 0;
for(int i = 0; i <= tt; i ++ ) {
res[i] = res[i] * b + r;
r = res[i] / jz;
res[i] %= jz;
}
while(r){
res[++tt] = r % jz;
r /= jz;
}
}
void div(int b){
int r = 0;
for(int i = tt; i >= 0; i -- ) {
res[i] += r * jz;
r = res[i] % b;
res[i] /= b;
}
while(!res[tt]) tt--;
}
void out(){
printf("%lld",res[tt]);
for(int i = tt - 1; i >= 0; i -- ){
printf("%09lld",res[i]);
}puts("");
}
signed main() {
int n;
cin >> n;
init();
for(int i = 0; i < cnt; i ++) {
chu[p[i]] = ges(n * 2, p[i]) - ges(n, p[i]) * 2;
}
int k = n + 1;
for(int i = 0;p[i]<=k; i++){
int s = 0;
while(k%p[i]==0){
s ++;
k/=p[i];
}
chu[p[i]] -= s;
}
res[0] = 1;
tt =0 ;
for(int i =2 ;i <= n*2; i++){
for(int j = 0; j <chu[i];j++){
mul(i);
}
}
out();
return 0;
}
以下重新整理到这里
单调栈
板子。
#include<cstdio>
#include<stack>
using namespace std;
#define ll long long
const int N = 1e5+5;
ll a[N];;
int L[N], R[N], st[N];
int main(){
int n;
while(~scanf("%d", &n) && n){
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
int top = 0;
for(int i = 1; i <= n; i++){
while(top && a[st[top-1]] >= a[i]) top--;
L[i] = (top==0) ? 0 : st[top-1];
st[top++] = i;
}
top = 0;
for(int i = n; i >= 1; i--){
while(top && a[st[top-1]] >= a[i]) top--;
R[i] = (top==0) ? (n+1) : st[top-1];
st[top++] = i;
}
ll ans = 0;
for(int i = 1; i <= n; i++)
ans = max(ans, (ll)(R[i]-L[i]-1)*a[i]);
printf("%lld\n", ans);
}
return 0;
}
队列
team queue
模拟队列
小组队列
开 2个队列A,B 在开个map什么的记录每个人属于什么队
第一个队列放map人对应属于什么
插入的时候 优先放到 B队列 如果A队列它不再了 插到A尾部 否在不管
pop 时候 如果这个第一队列空了 A弹出它 否在不管
#include <cstdio>
#include <string>
#include <iostream>
#include <map>
#include <queue>
using namespace std;
const int maxn = 1010;
int main (){
int kase=0,t;
queue<int> q,pq[maxn];
map<int,int> team;
char cmd[10];
while(scanf("%d",&t)!=EOF&&t){
while(!q.empty())q.pop();
team.clear();
printf("Scenario #%d\n",++kase);
for(int i=0;i<t;i++){
int n,x;
scanf("%d",&n);
while(n--){
scanf("%d",&x);
team[x]=i;
}
while(!pq[i].empty())pq[i].pop();
}
for(;;){
int x;
scanf("%s",cmd);
if(cmd[0]=='S') {break;}
if(cmd[0]=='E'){
scanf("%d",&x);
int t=team[x];
if(pq[t].empty()) q.push(t);
pq[t].push(x);
}
if(cmd[0]=='D'){
int t=q.front();
printf("%d\n",pq[t].front());
pq[t].pop();
if(pq[t].empty()) q.pop();
}
}
cout<<endl;
}
return 0;
}
蚯蚓
这题不太好想orz 首先是坎最长的 不需要考虑 但是每坎一次 其他都会长q 这样维护起来就变难了 所以 我们使用了一个detla
作为整体应该加的数据每次选出最长的+detla 然后坎了它 因为被砍出得 这轮不会 在涨 所以 p1-q，p2-q； 放回队列 detla+=q；
这样就处理了其他量在变得情况
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5 ;
const double pi = acos(-1.0);
int n, m, q, u, v, t;
priority_queue<int> que;
int a[maxn];
queue<int> q2, q3;
int rmax() {
int x = -0x3f3f3f3f3f3f3f;
if(!que.empty())
x = max(x, que.top());
if(!q2.empty())
x = max(x, q2.front());
if(!q3.empty())
x = max(x, q3.front());
if(!que.empty() && x == que.top())
que.pop() ;
else if(!q2.empty() && x == q2.front())
q2.pop() ;
else
q3.pop() ;
return x;
}
signed main() {
cin >> n >> m >> q >> u >> v >> t;
for(int i = 1; i <= n; i++)
cin >> a[i], \
que.push(a[i]);
int res = 0;
for(int i = 1; i <= m; i += 1) {
int ma = rmax();
ma += res;
if(i%t==0) cout << ma << " ";
int p1 = ma * u / v;
int p2 = ma - p1;
res += q;
q2.push(p1 - res);
q3.push(p2 - res);
}
cout << endl;
for(int i=1;i<=n+m;i++) {
int x = rmax();
if(i%t==0)
cout << x + res << " ";
}
cout << endl;
return 0;
}
双端队列 待续
单调队列 最大字段和 这玩意应用挺多的 贪心要用 DP要用。。 经常需要它
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5 + 5 ;
const double pi = acos(-1.0);
int n, m;
int a[maxn];
int sum[maxn];
int q[maxn], head, tail;
signed main() {
cin >> n >> m ;
for(int i = 1 ; i <= n ; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
q[1] = 0;
int l = 1, r = 1;
int ans = 0;
for(int i = 1; i <= n; i++) {
if(l <= r && q[l] < i - m)
l++; // 队列>M
ans = max(ans, sum[i] - sum[q[l]]);
while(l <= r && sum[q[r]] >= sum[i])
r--;
q[++r] = i;
}
cout << ans << endl;
return 0;
}
京公网安备 11010502036488号