作者：德莉傻天下第一可爱
链接：https://blog.nowcoder.net/n/bd5694a397064c7fb6a7160f40d56171
来源：牛客网
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<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("%lldn", 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 #%dn",++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("%dn",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;
}
查看作者更多博客：https://blog.nowcoder.net/zhxu98
欢迎关注公众号：牛客NOIP竞赛学
版权声明：本文为weixin_39795065原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。