算法进阶指南：第二章练习题

迪丽瓦拉

2025-05-31 02:37:43

0次

1.括号画家

150. 括号画家 - AcWing题库

牛客竞赛-括号画家

遇到左括号就入栈，右括号需要栈顶的同类左括号对应。

用一个vis数组记录配对合法的下标为1，做完后求最大连续的1即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1e5+10;
int mp[226];
int st[N],sz;
bool vis[N];
void solve()
{string s;cin>>s;mp[']']='[',mp[')']='(',mp['}']='{';rep(i,0,s.size()){if(s[i]=='['||s[i]=='{'||s[i]=='(') st[++sz]=i;else{if(sz==0) continue;int t=st[sz--];if(s[t]!=mp[s[i]]) sz=0;else vis[t]=vis[i]=1;}}int res=0;rep(i,0,s.size()){int tot=0;while(i>_;while(_--){solve();}return 0;
}

2.表达式计算4

牛客竞赛-表达式计算4

151. 表达式计算4 - AcWing题库

转换为后缀表达式计算，注意数据中右括号多余的情况，可以在字符串前提前补上左括号。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=110;
int num[N],op[N];
int sz1,sz2;
int qp(int a,int b)
{int res=1;while(b){if(b&1) res*=a;a*=a;b>>=1;}return res;
}
void cal()
{int a=num[sz1--],b=num[sz1--],c=op[sz2--];int res;if(c=='+') res=a+b;else if(c=='-') res=b-a;else if(c=='*') res=a*b;else if(c=='/') res=b/a;else res=qp(b,a);num[++sz1]=res;
}
void solve()
{string s;cin>>s;int cnt=0;for(auto i:s) if(i==')') ++cnt;s=string(s.size(),'(')+s+')';rep(i,0,s.size()){if(isdigit(s[i])){int j=i,tot=0;while(j>_;while(_--){solve();}return 0;
}

python:

将括号补全，直接调用eval()。

s=input().replace('^','**').replace('/','//')
cnt=0
res=s
for i in s:if i=='(':cnt+=1elif i==')':if cnt:cnt-=1else:res='('+res
while cnt:res+=')'cnt-=1
print(eval(res))

3.City Game

152. 城市游戏 - AcWing题库

牛客竞赛-City Game

玉蟾宫 - 洛谷

枚举行作为矩形的底边，预处理出每个点往上连续'F'的高度，问题转化成求直方图中最大矩形问题，单调队列维护第i个位置的高度向两边扩展的最大距离。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1010;
int n,m,h[N][N];
char g[N][N];
int q[N],l[N],r[N];
int cal(int a[])
{int tt=0;q[0]=0,a[0]=-1;rep(i,1,m+1){while(a[q[tt]]>=a[i]) --tt;l[i]=q[tt]+1;q[++tt]=i;}tt=0;q[0]=m+1,a[m+1]=-1;per(i,m,0){while(a[q[tt]]>=a[i]) --tt;r[i]=q[tt]-1;q[++tt]=i;}int res=0;rep(i,1,m+1) res=max(res,a[i]*(r[i]-l[i]+1));return res;
}
void solve()
{cin>>n>>m;rep(i,1,n+1) rep(j,1,m+1){cin>>g[i][j];if(g[i][j]=='F') h[i][j]=h[i-1][j]+1;}int ans=0;rep(i,1,n+1) ans=max(ans,cal(h[i]));cout<>_; while(_--){solve();}return 0;
}

4.双栈排序

153. 双栈排序 - AcWing题库

牛客竞赛-双栈排序

[NOIP2008 提高组] 双栈排序 - 洛谷

双栈排序题解

hack数据：

5
2 3 1 4 5

要入第一个栈时，要先检查是否会使这个栈不合法，不合法的时候需要先 pop。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1010,M=2010;
int a[N],f[N],col[N],n;
bool v[N][N];
int sk1[2*N],sk2[2*N],sz1,sz2;
bool dfs(int u,int c)
{col[u]=c;rep(i,1,n+1) if(v[u][i]){if(col[i]==c) return false;if(col[i]==-1&&!dfs(i,!c)) return false;}return true;
}
void solve()
{scanf("%d",&n);rep(i,1,n+1) scanf("%d",&a[i]),col[i]=-1;f[n+1]=n+1;per(i,n,0) f[i]=min(f[i+1],a[i]);rep(i,1,n+1) rep(j,i+1,n+1) if(a[i]sk1[sz1]){if(sz1&&sk1[sz1]==nw){--sz1;putchar('b'),putchar(' ');++nw;}else if(sz2&&sk2[sz2]==nw){--sz2;putchar('d'),putchar(' ');++nw;}else break;}sk1[++sz1]=a[i];putchar('a'),putchar(' ');}else{while(1){if(sz1&&sk1[sz1]==nw){--sz1;putchar('b'),putchar(' ');++nw;}else if(sz2&&sk2[sz2]==nw){--sz2;putchar('d'),putchar(' ');++nw;}else break;}sk2[++sz2]=a[i];putchar('c'),putchar(' ');}}while(1){if(sz1&&sk1[sz1]==nw){--sz1;putchar('b'),putchar(' ');++nw;}else if(sz2&&sk2[sz2]==nw){--sz2;putchar('d'),putchar(' ');++nw;}else break;}
}
int main()
{
//	#ifndef ONLINE_JUDGE
//		freopen("1.in","r",stdin);
//		freopen("1.out","w",stdout);
//	#endif//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){solve();}return 0;
}

5.Sliding Window

牛客竞赛-Sliding Window

单调队列模板题。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1e6+10;
int a[N],q[N];
void solve()
{int n,m;cin>>n>>m;rep(i,1,n+1) cin>>a[i];int hh=0,tt=-1;rep(i,1,n+1){while(hh<=tt&&a[q[tt]]>=a[i]) --tt;if(hh<=tt&&i-m>=q[hh]) ++hh;q[++tt]=i;if(i>=m) cout<=q[hh]) ++hh;q[++tt]=i;if(i>=m) cout<>_; while(_--){solve();}return 0;
}

6.内存分配

155. 内存分配 - AcWing题库

牛客竞赛-内存分配

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=26,M=2010;
int n;
queueq; //等待队列进程<空间,时间> 
sets1; //内存使用<下标,长度> 
sets2; //<结束时间,下标>
int ans,cnt;
bool cal(int t,int m,int p) //分配进程 
{auto it=s1.begin();++it;while(it!=s1.end()){auto pre=it;--pre;if(m<=it->fi-(pre->fi+pre->se)){s1.insert({pre->fi+pre->se,m});s2.insert({t+p,pre->fi+pre->se});return true;}++it;}return false;
}
void fre(int t) //释放进程 
{while(s2.size()){auto it=s2.begin();int tt=it->fi;if(tt>t) break;ans=tt;while(s2.size()&&it->fi==tt){s1.erase(s1.lower_bound({it->se,-1}));it=s2.erase(it);}while(q.size()){pii tp=q.front();if(!cal(tt,tp.fi,tp.se)) break;else q.pop();}}
}
void solve()
{int t,m,p;cin>>n;s1.insert({-1,1}),s1.insert({n,0});while(cin>>t>>m>>p){if(!t&&!m&&!p) break;fre(t);if(!cal(t,m,p)) q.push({m,p}),++cnt;}fre(1e9);cout<>_;while(_--){solve();}return 0;
}

7.Matrix

156. 矩阵 - AcWing题库

牛客竞赛-Matrix

将原矩阵所有的矩形存入哈希表中，询问只需要判断值是否出现。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1010;
char s[N];
ULL g[N][N],p[N*N];
int h=131;
ULL cal(ULL f[],int l,int r)
{return f[r]-f[l-1]*p[r-l+1];
}
void solve()
{int n,m,a,b,_;cin>>n>>m>>a>>b;p[0]=1;rep(i,1,n*m+1) p[i]=p[i-1]*h;rep(i,1,n+1){cin>>s+1;rep(j,1,m+1) g[i][j]=g[i][j-1]*h+s[j]-'0'+1;}setst;for(int i=1;i+b-1<=m;++i){ULL tot=0;rep(j,1,n+1){tot=tot*p[b]+cal(g[j],i,i+b-1);if(j-a>=1) tot-=cal(g[j-a],i,i+b-1)*p[a*b];if(j>=a) st.insert(tot);}}cin>>_;while(_--){ULL ans=0;rep(i,1,a+1){cin>>s+1;rep(j,1,b+1) ans=ans*h+s[j]-'0'+1;}cout<>_;while(_--){solve();}return 0;
}

牛客oj上空间限制缩小了一半，换用vector可以过。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1010,M=1e5+10;
char s[N];
ULL g[N][N],p[M];
vectorv;
int h=131;
ULL cal(ULL f[],int l,int r)
{return f[r]-f[l-1]*p[r-l+1];
}
void solve()
{int n,m,a,b,_;cin>>n>>m>>a>>b;p[0]=1;rep(i,1,M) p[i]=p[i-1]*h;rep(i,1,n+1){cin>>s+1;rep(j,1,m+1) g[i][j]=g[i][j-1]*h+s[j]-'0'+1;}for(int i=1;i+b-1<=m;++i){ULL tot=0;rep(j,1,n+1){tot=tot*p[b]+cal(g[j],i,i+b-1);if(j-a>=1) tot-=cal(g[j-a],i,i+b-1)*p[a*b];if(j>=a) v.push_back(tot);}}sort(all(v));cin>>_;while(_--){ULL ans=0;rep(i,1,a+1){cin>>s+1;rep(j,1,b+1) ans=ans*h+s[j]-'0'+1;}int pos=lower_bound(all(v),ans)-v.begin();if(pos!=v.size()&&v[pos]==ans) cout<<1<>_;while(_--){solve();}return 0;
}

8.Subway tree systems

牛客竞赛-Subway tree systems

157. 树形地铁系统 - AcWing题库

给定的序列是树的dfs序列，0表示递归下一层，1表示回溯到上一层。根据序列可以确定一个树，问题就转化为判断两个树是否同构即可。

两个树同构，dfs序列中子树序列顺序会不同，但是子树是对应相等的，把子树按照字典序排序得到的结果，同构的情况一定是相同的。（树的最小表示定义，可以用来判断同构树）。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=5010;
string cal(string s)
{if(s.size()==0) return "";vectorv;rep(i,0,s.size()){int tot=1,j=i+1;while(j>a>>b;if(cal(a)==cal(b)) cout<<"same"<>_;while(_--){solve();}return 0;
}

9.Necklace

牛客竞赛-Necklace

158. 项链 - AcWing题库

将第一个串的所有同构串的哈希值算出来，计算第二个串的哈希值，看是否存在相等的。

如果存在，求最小字串：在比较两个字串时二分出最长前缀的长度，找到不同的后一位。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e6+10;
char s1[2*N],s2[N];
ULL f[2*N],p[2*N];
int h=131,n;
ULL cal(int l,int r)
{return f[r]-f[l-1]*p[r-l+1];
}
int cmp(int i,int j)
{int l=0,r=n;while(l>1;if(cal(i,i+m-1)==cal(j,j+m-1)) l=m;else r=m-1;}if(l==n) return 0;if(s1[i+l]>s1[j+l]) return 1;else return -1;
}
void solve()
{cin>>s1+1>>s2+1;n=strlen(s1+1);rep(i,1,n+1) s1[i+n]=s1[i];p[0]=1;ULL g=0;rep(i,1,2*n+1){f[i]=f[i-1]*h+s1[i]-'a'+1,p[i]=p[i-1]*h;if(i<=n) g=g*h+s2[i]-'a'+1;}int mx=1;bool fl=0;rep(i,1,n+1){if(cal(i,i+n-1)==g) fl=1;if(i!=1&&cmp(i,mx)<0) mx=i; }if(fl){cout<<"Yes"<>_;while(_--){solve();}return 0;
}

10.Milking Grid

牛客竞赛-Milking Grid

159. 奶牛矩阵 - AcWing题库

直接枚举覆盖矩阵的列的大小C，满足对于所有行字符C都是它们的一个循环节。对于C求覆盖矩阵的R，相当于把每一行看作一个整体，用kmp求出最短循环节，求ne数组比较时改为字符串比较，值为n-ne[n]。

最后答案是满足条件最小的C和它对应求出的R。如果C更大会使比较时更不容易相等，ne数组变小，R值更大。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1e4+10,M=80;
bool st[M]; //记录最小矩阵列宽是否合法 
char s[N][M];
int ne[N];
void solve()
{MEM(st,1);int n,m;cin>>n>>m;rep(i,1,n+1){cin>>s[i];rep(j,1,m+1){if(!st[j]) continue;rep(k,0,j){for(int z=k+j;z>_;while(_--){solve();}return 0;
}

11.匹配统计

牛客竞赛-匹配统计

160. 匹配统计 - AcWing题库

先预处理出a串哈希值，对于每一个后缀用二分法求出与b匹配的最大长度。把长度个数记录下来，后面查询复杂度都是O(1)。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=2e5+10;
ULL f[N],p[N],g[N];
int n,m,h=131;
int cnt[N];
char a[N],b[N];
ULL cal(ULL f[],int l,int r)
{return f[r]-f[l-1]*p[r-l+1];
}
void solve()
{int q,x;cin>>n>>m>>q>>a+1>>b+1;p[0]=1;rep(i,1,max(n,m)+1) p[i]=p[i-1]*h;rep(i,1,n+1) f[i]=f[i-1]*h+a[i]-'a'+1;rep(i,1,m+1) g[i]=g[i-1]*h+b[i]-'a'+1;rep(i,1,n+1){int l=0,r=min(n-i+1,m);while(l>1;if(cal(f,i,i+mid-1)==cal(g,1,mid)) l=mid;else r=mid-1;}++cnt[l];}while(q--){cin>>x;cout<>_;while(_--){solve();}return 0;
}

12.Phone List

牛客竞赛-Phone List

161. 电话列表 - AcWing题库

用trie树维护单词列表，一个单词结束用st数组记录。如果有前缀在插入的时候有两种情况：1.如果插入的是已经插入的前缀，则插入到末尾一定有tr[p][ch]不为0。2.如果插入的过程中某个已插入的是他的前缀，中途判断st[p]为1.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=998244353;
const int N=1e5+10;
string s;
int tr[N][10],tot;
bool st[N],fl;
void ins()
{int p=1;rep(i,0,s.size()){int ch=s[i]-'0';if(st[p]) fl=0;if(i==s.size()-1&&tr[p][ch]) fl=0;if(tr[p][ch]==0) tr[p][ch]=++tot;p=tr[p][ch];}if(st[p]) fl=0;st[p]=1;
}
void solve()
{int n;cin>>n;fl=1,tot=1,MEM(tr,0),MEM(st,0);rep(i,0,n){cin>>s;ins();}if(fl) cout<<"YES"<>_;while(_--){solve();}return 0;
}

13.Black Box

牛客竞赛-Black Box

162. 黑盒子 - AcWing题库

堆可以用stl中的multiset代替模拟，指针指向下次查询的排位。如果插入的值比指针指向的值小，将指针前移。这样每次查询就是指针所指向的值。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=30010;
int a[N],b[N];
void solve()
{int n,m;cin>>n>>m;rep(i,1,n+1) cin>>a[i];rep(i,1,m+1) cin>>b[i];multisetst;multiset::iterator it;int j=1;rep(i,1,n+1){st.insert(a[i]);if(i==1) it=st.begin();if(i>1&&a[i]<*it) --it;while(j<=m&&b[j]==i){cout<<*it<m) break;}
}
int main()
{
//	#ifndef ONLINE_JUDGE
//		freopen("in.txt","r",stdin);
//		freopen("out.txt","w",stdout);
//	#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){solve();}return 0;
}

上面代码并不完全正确，但是因为牛客数据比较水可以过。有一种特殊情况是下一次的GET超过当前长度，此时迭代器会指向end，为了避免需要加上哨兵。

下面代码可以通过洛谷所有数据：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=9901;
const int N=2e5+10;
int a[N],b[N];
void solve()
{int n,m;cin>>n>>m;rep(i,1,n+1) cin>>a[i];rep(i,1,m+1) cin>>b[i];multisetst;st.insert(2e9+1);multiset::iterator it;int j=1;rep(i,1,n+1){st.insert(a[i]);if(i==1) it=st.begin();if(i>1&&a[i]<*it) --it;while(j<=m&&b[j]==i){cout<<*it<m) break;}
}
int main()
{
//	#ifndef ONLINE_JUDGE
//		freopen("in.txt","r",stdin);
//		freopen("out.txt","w",stdout);
//	#endifios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--){solve();}return 0;
}

14.生日礼物

牛客竞赛-生日礼物

163. 生日礼物 - AcWing题库

将连续的正数，负数作为连续的一段一起选，整个数组就被划分为了一段正数一段负数相间的序列。如果正数段的个数小于等于m，直接选所有的正数段。否则考虑减小一些正数段，并且要使得减少的值尽量的小。

减少一段可以删除一个正数段，减少的代价就是这个正数段的值；或者将两个正数间的负数一起选上，减少的待见就是负数段的绝对值，现在要使得代价最小，将负数段取绝对值，就相当于是选取cnt-m个不连续的（cnt为正数段的个数）段，使得和最小。这个问题和本书85页例题的问题是一样的：现将段插入小根堆中，并且段之间关系用双链表维护，每次取出堆顶并于两侧合并（减去两边的值）插入堆中。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;ib;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define all(x) (x).begin(),(x).end()
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const int N=1e5+10;
int a[N],sz,cnt;
int l[N],r[N];
void del(int u)
{l[r[u]]=l[u];r[l[u]]=r[u];
}
void solve()
{int n,m,x,ans=0;cin>>n>>m;rep(i,0,n){cin>>x;if(!x) continue;if(!sz) a[++sz]=x;else if(1ll*a[sz]*x>0) a[sz]+=x;else a[++sz]=x;}setst;rep(i,1,sz+1){l[i]=i-1,r[i]=i+1;st.insert({abs(a[i]),i});if(a[i]>0) ++cnt,ans+=a[i];}if(cnt<=m){cout<0){ans-=t.fi;int ll=l[t.se],rr=r[t.se];st.erase({abs(a[ll]),ll}),st.erase({abs(a[rr]),rr});a[t.se]+=a[ll]+a[rr];st.insert({abs(a[t.se]),t.se});del(ll),del(rr);--k;}else del(t.se);}cout<>_;while(_--){solve();}return 0;
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Hive

下一篇：k8s笔记