首页 > 代码库 > 2016-11-15试题解题报告

2016-11-15试题解题报告

2016-11-15试题解题报告

By shenben

技术分享

技术分享

技术分享

 

T1代码:

#include<cstdio>#include<algorithm>using namespace std;inline int read(){    register int x=0;bool f=1;    register char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=0;ch=getchar();}    while(ch>=0&&ch<=9){x=(x<<3)+(x<<1)+ch-0;ch=getchar();}    return f?x:-x;}const int N=1e5+10;int lson[N],rson[N],a[N];int n,ans;int len,r,b[N],c[N];void dfs(int x){    if(lson[x]) dfs(lson[x]);    b[++len]=x;    if(rson[x]) dfs(rson[x]);}void LIS(){    for(int p,i=1;i<=len;i++){        int x=a[b[i]]-i;        if(x>=c[r]){            c[++r]=x;        }        else{            p=upper_bound(c+1,c+r+1,x)-c;            c[p]=x;        }    }}#define name "binary"int main(){    n=read();    for(int i=1;i<=n;i++) a[i]=read();    for(int i=2,fa,son;i<=n;i++){        fa=read();son=read();        if(!son) lson[fa]=i;        else rson[fa]=i;    }    dfs(1);    LIS();    printf("%d\n",len-r);    return 0;} 

T2代码:

//std既丑由慢~~~还是暴力快#include<cstdio>#include<algorithm>using namespace std;const int N=5e5+10;int n,len=-1,a[N],ans[N];#define name "pair"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",a+i);    for(int i=1;i<=n;i++){//枚举a[k]         int L=i,R=i;//枚举a[k]所能管辖的最远边界         while(L-1>=1&&a[L-1]%a[i]==0) L--;        while(R+1<=n&&a[R+1]%a[i]==0) R++;        if(R-L>len){            len=R-L;            ans[ans[0]=1]=L;        }        else if(R-L==len){            ans[++ans[0]]=L;        }    }    sort(ans+1,ans+ans[0]+1);    ans[0]=unique(ans+1,ans+ans[0]+1)-(ans+1);    printf("%d %d\n",ans[0],len);    for(int i=1;i<=ans[0];i++) printf("%d ",ans[i]);    fclose(stdin);    fclose(stdout);    return 0;}/*30分存档 #include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#include<queue>#include<stack>#include<vector>#include<map>using namespace std;inline int read(){    register int x=0;bool f=1;    register char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}    return f?x:-x;}const int N=1e3+10;const int M=9e6+10;int n,a[N],xmin[N][N];struct node{    int l,r,val;    node(int _l=0,int _r=0,int _val=0){        l=_l;r=_r;val=_val;    }    bool operator <(const node &b)const{        if(val==b.val) return l<b.l;        return val>b.val;    }}fs[M];int cnt,num,zmx;#define name "pair"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    n=read();    for(int i=1;i<=n;i++) a[i]=read();    for(int i=1;i<=n;i++){        xmin[i][i]=a[i];        for(int j=i+1;j<=n;j++){            xmin[i][j]=min(xmin[i][j-1],a[j]);        }    }    //for(int i=1;i<=n;i++){    //    for(int j=i;j<=n;j++){    //        printf("min[%d,%d]: %d\n",i,j,xmin[i][j]);    //    }    //}    for(int i=1;i<=n;i++){        for(int k,v,j=i+1;j<=n;j++){            for(k=i;k<=j;k++){                if(a[k]%xmin[i][j]) break;            }            if(k>j){                if((v=j-i)>=zmx){                    zmx=v;                    fs[++cnt]=node(i,j,v);                }            }        }    }    sort(fs+1,fs+cnt+1);    for(int i=1;i<=cnt;i++) if(fs[i].val!=zmx){num=i-1;break;}    if(!num||!zmx){        printf("%d %d\n",n,0);        for(int i=1;i<=n;i++) printf("%d ",i);        return 0;    }    printf("%d %d\n",num,zmx);    for(int i=1;i<num;i++) printf("%d ",fs[i].l);printf("%d",fs[num].l);    fclose(stdin);    fclose(stdout);    return 0;}*/

T3代码:

#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;inline int read(){    register int x=0,f=1;    register char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}const int N=55;const int mod=1e9+7;int n,p[N],C[N][N],dp[N][N];int dfs(int len,int low){    if(dp[len][low]!=-1) return dp[len][low];    if(len==1) return dp[len][low]=1;    int &res=dp[len][low];res=0;    int t[N],m=0;    for(int i=1;i<=n;i++){        if(p[i]>=low&&p[i]<len+low){            t[++m]=p[i];        }    }    for(int j,k,i=1;i<=m;i++){        swap(t[i],t[i+1]);        for(j=1;j<=i;j++) if(t[j]>=low+i) break;        for(k=i+1;k<=m;k++) if(t[k]<low+i) break;        if(j>i&&k>m){            ll tmp=((ll)dfs(i,low)*(ll)dfs(m-i,low+i))%mod;            tmp=tmp*C[m-2][i-1]%mod;            res=(res+tmp)%mod;        }        swap(t[i],t[i+1]);    }    return res;}#define name "swap"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    memset(dp,-1,sizeof dp);     n=read();    for(int i=1;i<=n;i++) p[i]=read();    for(int i=0;i<=n;i++){        C[i][0]=1;        for(int j=1;j<=i;j++){            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;        }    }    dfs(n,0);    printf("%d",dp[n][0]!=-1?dp[n][0]:0);    fclose(stdin);    fclose(stdout);    return 0;}/*//读懂题目后,暴力30分(改出来的) #include<cstdio>#include<algorithm>using namespace std;const int N=1e5+10;const int mod=1e9+7;int n,dn,a[N],b[N],c[N];int ans;bool judge(){    for(int i=0;i<n;i++) b[i]=i;    for(int i=0;i<dn;i++) swap(b[c[i]],b[c[i]+1]);    for(int i=0;i<n;i++) if(a[i]!=b[i]) return 0;    return 1;}#define name "swap"int main(){    freopen(name".in","r",stdin);    freopen(name".out","w",stdout);    scanf("%d",&n);    for(int i=0;i<n;i++) scanf("%d",&a[i]);    for(int i=0;i<n;i++) b[i]=i;    dn=n-1;    for(int i=0;i<dn;i++) c[i]=i;    do{        if(judge()) ans++;        if(ans>=mod) ans-=mod;    }while(next_permutation(c,c+dn));    printf("%d",ans);    fclose(stdin);    fclose(stdout);    return 0;}*/

 

 

 

2016-11-15试题解题报告