常用技巧（二）

作者: 云中翻月 | 来源:发表于2019-09-29 17:20 被阅读0次

栈

POJ 3250: Bad Hair Day
题意：统计每个数字右边第一个比它大的数字与它的下标差的和。
单调栈模板题。（相当于只从一头进出的单调严格递减栈）
然后反过来思考，统计每头牛被多少头牛看到，作为这头牛对答案的贡献即可。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题意：统计每个数字右边第一个比它大的数字与它的下标差的和。
单调栈模板题。（相当于只从一头进出的单调严格递减栈） 
然后反过来思考，统计每头牛被多少头牛看到，作为这头牛对答案的贡献即可。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=80000+5;
const int INF=0x3f3f3f3f;
int q[maxn],n,h[maxn];
ll ans=0ll;
void solve(){
    int head=1,tail=1;
    q[head]=1;
    for(int i=2;i<=n+1;i++){
        while(head<=tail&&h[q[tail]]<=h[i]) tail--;
        ans+=(ll)(tail-head+1); //此时栈中的元素都能看到i 即i的贡献就是栈中元素的数量tail-head+1 
        q[++tail]=i;
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Bad Hair Day.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    h[n+1]=INF;
    solve();
    printf("%lld",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 2082: Terrible Sets
预处理出l[i]和r[i]为i号矩形向左/右能够达到的最远小标距离，可以用两个严格单调增的单调栈实现。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
预处理出l[i]和r[i]为i号矩形向左/右能够达到的最远小标距离，可以用两个严格单调增的单调栈实现。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
int w[maxn],h[maxn],n;
int ans;
int q[maxn],l[maxn],r[maxn];
void init(){
    ans=0;
}
void solve(){
    int head=1,tail=1;
    q[head]=0;
    h[0]=-INF;
    for(int i=1;i<=n;i++){
        while(head<=tail&&h[i]<=h[q[tail]]) tail--;
        l[i]=w[i]-w[q[tail]];
        q[++tail]=i;
    }
//  for(int i=1;i<=n;i++) D(l[i]);
//  E;
    head=1,tail=1;
    q[head]=n+1;
    h[n+1]=-INF;
    for(int i=n;i>=1;i--){
        while(head<=tail&&h[i]<=h[q[tail]]) tail--;
        r[i]=w[q[tail]-1]-w[i-1];
        q[++tail]=i;
    }
//  for(int i=1;i<=n;i++) D(r[i]);
//  E;
    for(int i=1;i<=n;i++) ans=max((l[i]+r[i]-w[i]+w[i-1])*h[i],ans);
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Terrible Sets.in","r",stdin);
    while(scanf("%d",&n)){
        if(n==-1) break;
        init();
        for(int i=1;i<=n;i++){
            scanf("%d%d",&w[i],&h[i]);
            w[i]+=w[i-1];
        }
        solve();
        printf("%d\n",ans);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3494: Largest Submatrix of All 1’s
悬线法裸题，不再赘述。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
悬线法裸题，不再赘述。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000+5;
const int INF=0x3f3f3f3f;
int n,m,a[maxn][maxn],q[maxn],h[maxn],l[maxn],r[maxn],ans;
void init(){
    ans=0;
}
int calc(){ //计算h[i]表示的最大矩形 
    int res=0;
//  for(int i=1;i<=m;i++) D(h[i]);
//  E;
    int head=1,tail=1;
    q[head]=0;
    h[0]=-INF;
    for(int i=1;i<=m;i++){
        while(head<=tail&&h[i]<=h[q[tail]]) tail--;
        l[i]=i-q[tail];
        q[++tail]=i;
    }
//  for(int i=1;i<=m;i++) D(l[i]);
//  E;
    head=1,tail=1;
    q[head]=m+1;
    h[m+1]=-INF;
    for(int i=m;i>=1;i--){
        while(head<=tail&&h[i]<=h[q[tail]]) tail--;
        r[i]=q[tail]-i;
        q[++tail]=i;
    }
//  for(int i=1;i<=m;i++) D(r[i]);
//  E;
    for(int i=1;i<=m;i++) res=max((l[i]+r[i]-1)*h[i],res);
    return res;
}
void solve(){
    for(int i=1;i<=n;i++){
        memcpy(h,a[i],sizeof(a[i]));
        ans=max(calc(),ans);
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Largest Submatrix of All 1’s.in","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF) {
        init(); 
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) {
                scanf("%d",&a[i][j]);
                if(a[i][j]!=0) a[i][j]+=a[i-1][j];
            }
        /*
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                cout<<a[i][j]<<" ";
            }
            E;
        }
        */
        solve();
        printf("%d\n",ans);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

双端队列

POJ 2823: Sliding Window
单调队列模板题，不再赘述。
注意k=1的情况。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
单调队列模板题，不再赘述。
注意k=1的情况。  
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e6+5;
const int INF=0x3f3f3f3f;
int n,k,a[maxn];
int q[maxn];
int mn[maxn],mx[maxn]; //最小值 最大值 
void solve(){
    int head=1,tail=1;
    q[head]=1;
    mn[1]=mx[1]=a[1]; //注意k=1的情况 
    //1 3 -1 -3 5 3 6 7
    for(int i=2;i<=n;i++){
        while(head<=tail&&i-q[head]+1>k) head++; //i-q[head]+1为单调队列中的元素数量 
        while(head<=tail&&a[i]<=a[q[tail]]) tail--;
        q[++tail]=i;
//      for(int j=head;j<=tail;j++) D(a[q[j]]);
//      E;
        mn[i]=a[q[head]];
    }
    head=1,tail=1;
    q[head]=1;
    for(int i=2;i<=n;i++){
        while(head<=tail&&i-q[head]+1>k) head++; 
        while(head<=tail&&a[i]>=a[q[tail]]) tail--;
        q[++tail]=i;
//      for(int j=head;j<=tail;j++) D(a[q[j]]);
//      E;
        mx[i]=a[q[head]];
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Sliding Window.in","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    solve();
    for(int i=k;i<=n;i++) printf("%d ",mn[i]);
    printf("\n");
    for(int i=k;i<=n;i++) printf("%d ",mx[i]);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 3260: The Fewest Coins
题解链接 https://blog.csdn.net/u013480600/article/details/40617083
以为需要单调队列来优化多重背包的，结果竟然直接过了。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题解链接 https://blog.csdn.net/u013480600/article/details/40617083
以为需要单调队列来优化多重背包的，结果竟然直接过了。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxm=10000+120*120+5; //maxt+maxv*maxv
const int INF=0x3f3f3f3f;
int n,t,v[maxn],c[maxn];
int m,maxv=0,ans=INF;
int d[maxm],f[maxm]; //d 支付 f 找零 
void init(){
    memset(f,INF,sizeof(f));
    memset(d,INF,sizeof(d));
    f[0]=d[0]=0;
}
void dp1(){
    for(int i=1;i<=n;i++){
        if(v[i]*c[i]>=m) for(int j=v[i];j<=m;j++) d[j]=min(d[j],d[j-v[i]]+1);
        else{
            for(int j=m;j>=v[i];j--) for(int k=1;k<=c[i]&&j-k*v[i]>=0;k++) d[j]=min(d[j],d[j-k*v[i]]+k);
        }
    }
}
void dp2(){
    for(int i=1;i<=n;i++) for(int j=v[i];j<=m;j++) f[j]=min(f[j],f[j-v[i]]+1);
}
void solve(){
    for(int i=t;i<=m;i++) ans=min(ans,d[i]+f[i-t]);
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("The Fewest Coins.in","r",stdin);
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%d",&v[i]),maxv=max(maxv,v[i]);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    m=t+maxv*maxv;
    init();
    dp1();
    dp2();
    solve();
    if(ans==INF) printf("-1");
    else printf("%d",ans);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ 1180: Batch Scheduling
题解链接 https://www.jianshu.com/p/fdb41c13d11f
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题解链接 https://www.jianshu.com/p/fdb41c13d11f 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int INF=0x3f3f3f3f;
int n,s,t[maxn],c[maxn];
int q[maxn],f[maxn];
void solve(){
    int l=1,r=1;
    f[0]=0;
    q[l]=0;
    for(int i=1;i<=n;i++){
        while(l<r&&(s+t[i])*(c[q[l+1]]-c[q[l]])>=f[q[l+1]]-f[q[l]]) l++;
        f[i]=f[q[l]]-(s+t[i])*c[q[l]]+t[i]*c[i]+s*c[n];//要使f[i]最小 就要f[j]最小 在截距一定的情况下 队首的斜率最小 所以结构也最小 
        while(l<r&&(f[i]-f[q[r]])*(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r]])) r--;
        q[++r]=i;
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Batch Scheduling.in","r",stdin);
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++) scanf("%d%d",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
    solve();
    printf("%d",f[n]);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

常用技巧（二）

栈

双端队列

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读