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 ",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 ",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 ",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,0); for(int i=1;i<=n;i++) printf("%d ",i); return 0; } printf("%d %d ",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 long using 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; }*/