51nod 1158

Type:悬线法,单调栈(未学,用悬线法做的)

提示

蓝书P51,最大子矩阵 O(mn)

Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=510;
int m,n;
int mat[maxn][maxn],up[maxn][maxn],left[maxn][maxn],right[maxn][maxn];

void print(){
    printf("Up:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",up[i][j]);
        }
        puts("");
    }
    printf("Left:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",left[i][j]);
        }
        puts("");
    }
    printf("Right:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",right[i][j]);
        }
        puts("");
    }
}

int main(){
    while(~scanf("%d%d",&m,&n)){
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                scanf("%d",&mat[i][j]);
            }
        }
        int ans=0;
        for(int i=1;i<=m;++i){
            int lo=0,ro=n;
            for(int j=1;j<=n;++j){///从右往左扫描,维护up和left
                if(!mat[i][j]){
                    up[i][j]=left[i][j]=0;lo=j;
                }else{
                    up[i][j]=up[i-1][j]+1;
                    left[i][j]=max(left[i-1][j],lo+1);
                }
            }
            for(int j=n;j>=1;--j){///维护right
                if(!mat[i][j]){
                    right[i][j]=n+1;ro=j-1;
                }else{
                    right[i][j]=i==1?ro:min(right[i-1][j],ro);
                    ans=max(ans,up[i][j]*(right[i][j]-left[i][j]+1));
                }
            }
        }
        //print();
        printf("%d\n",ans);
    }
    return 0;
}

第14届浙江省赛By Tusimple

【网赛链接】

第14届浙江省赛By Tusimple

【A】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int N,a1,T;
int Kobayashi[4]={1,0,1,-1},Kscore;
int Tohru[4]={0,1,1,-1},Tscore;
int main(){
    while(~SI(N)){
        while(N–){
            SI(T);
            Kscore=0;
            Tscore=0;
            rep(i,T){
                SI(a1);
                Kscore+=Kobayashi[a1-1];
                Tscore+=Tohru[a1-1];
            }
            if(Kscore>Tscore)
                puts(“Kobayashi”);
            else if(Tscore>Kscore)
                puts(“Tohru”);
            else
                puts(“Draw”);
        }
    }
    return 0;
}

【B】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
const int maxn=20000+10;
int T,N,fk,Orz,flag,cnt;
int score[maxn],scomp[maxn];
int main(){
    while(~SI(T)){
        while(T–){
            fill(score,score+4000,0);
            Orz=flag=0;
            SI(N);
            if(N>13 || N<10){
                rep(i,N){
                    SI(fk);
                }
                puts(“No”);continue;
            }
            rep(i,N){
                SI(fk);
                if(fk<=0){
                    flag=1;
                }else{
                    score[fk]++;
                }
                scomp[i]=fk;
            }
            if(flag){
                puts(“No”);
            }else{
                if(score[1]<2){
                    puts(“No”);
                    continue;
                }else{
                    sort(scomp,scomp+N);
                    rez(i,1,N-2){
                        if(scomp[i]-scomp[i-1]>2){
                            puts(“No”);
                            flag=1;
                            break;
                        }
                    }
                    if(!flag) puts(“Yes”);
                }
            }
        }
    }
    return 0;
}

【C】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int T,n,q,c;
map<string,int> mp;
map<string,int>::iterator ite;
map<int,vector<string> > res;
string st;

inline int readt(int N){
    int ans=0,tit;
    rep(i,N){
        SI(tit);
        ans+=(1<<N-i-1) & (tit<<N-i-1);
    }
    return ans;
}

int main(){
    SI(T);
    while(T–){
        //测试数据可能出现重复的名字和情况,所以要初始化
        mp.clear();
        res.clear();
        SII(n,q);
        SI(c);
        rep(i,c){
            cin>>st;
            mp[st]=0;
        }
        rep(i,q){
            int nu;
            SI(nu);
            rep(j,nu){
                cin>>st;
                mp[st]+=(1<<q-i-1);
            }
        }
        for(ite=mp.begin();ite!=mp.end();ite++){
            res[ite->second].push_back(ite->first);
        }
        rep(i,n){
            int index=readt(q);
            if(res.find(index)==res.end()){
                puts(“Let’s go to the library!!”);
            }else{
                vector<string>& t=res[index];
                if(t.size()>1){
                    puts(“Let’s go to the library!!”);
                }else{
                    cout<<t[0]<<“\n”;
                }
            }
        }
    }
    return 0;
}

【D】

因为样例用的是m=3…所以我就一直卡在z>=3……然后比赛结束以后发现了…好亏啊

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;

struct Star{
    int left,right;
    bool operator<(const Star MM) const{
        return left<MM.left;
    }
}A[500],B[500];
int n,m,x,y,T,s,e;

int main(){
    SI(T);
    while(T–){
        SII(n,m);SII(x,y);
        rep(i,x){
            SII(s,e);
            A[i].left=s;
            A[i].right=e;
        }
        rep(i,y){
            SII(s,e);
            B[i].left=s;
            B[i].right=e;
        }
        sort(A,A+x);
        sort(B,B+y);
        int ans=0;
        rep(i,x){
            s=A[i].left;
            e=A[i].right;
            int z=0;
            rep(j,y){
                if(B[j].left>A[i].right) break;
                z+=(min(B[j].right,A[i].right)-max(A[i].left,B[j].left)+1);
                    if(z>=m){
                        ans+=z-m+1;
                        z=0;
                    }else{
                        z=0;
                    }
            }
        }
        printf(“%d\n”,ans);
    }
    return 0;
}

LA 3029

【类型】

扫描线,悬线法

【题解】

蓝书P50

扫描方程的解释

我对代码的理解放在代码里了.

如果为满:left[i][j]=0,right[i][j]=n,up[i][j]=0,这里是为了下一行的比较做准备。可以模拟试一试。

【Code】

#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=1000;
int mat[maxn][maxn],up[maxn][maxn],left[maxn][maxn],right[maxn][maxn];
int readchar(){
    int a=getchar();
    while(a!=’F’ && a!=’R’) a=getchar();
    return a;
}
int main(){
    int T;
    scanf(“%d”,&T);
    while(T–){
        int m,n;
        scanf(“%d%d”,&m,&n);
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j){
                int ch=getchar();
                while(ch!=’F’ && ch!=’R’) ch=getchar();
                mat[i][j]=ch==’F’?0:1;
            }

        int ans=0;
        for(int i=0;i<m;++i){//从上到下逐行处理
            int lo=-1,ro=n;
            for(int j=0;j<n;++j)//从左向右处理
                if(mat[i][j]==1){left[i][j]=up[i][j]=0;lo=j;}
                else{
                    up[i][j]=i==0?1:up[i-1][j]+1;
                    //lo存的是左边界的下标,而不是到左边将诶有多少空地
                    //这里,每次遇到障碍(1)时,lo就等于j(重新开始计算左边界)
                    //然后,left[i][j]存的是当前矩阵的右边界
                    //这里是lo+1,而不是lo++,所以lo的值在碰到障碍前一直不变
                    //因为受到上一行的影响,所以需要在上一行和本行中选取一个最大
                    //下标的左边界.
                    left[i][j]=i==0?lo+1:max(left[i-1][j],lo+1);
                }
            for(int j=n-1;j>=0;–j)//从右往左扫描,维护right并更新答案
                if(mat[i][j]==1){right[i][j]=n;ro=j;}
                //为啥等于n捏???
                //为了使其下一行若是空格,作比较的时候,会发现上一行的下标一定是最大的
                //从而不影响下一行右边界的计算
                else{
                    right[i][j]=i==0?ro-1:min(right[i-1][j],ro-1);
                    ans=max(ans,up[i][j]*(right[i][j]-left[i][j]+1));
                }
        }
        printf(“%d\n”,ans*3);
    }
    return 0;
}