这套题居然是noip模拟题。。吓尿了
怎么看都是前几年noi难度
1.连通期望
将每种状况的各个连通块大小hash一下，记忆化搜索。
状态数显然不会很多。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
// <t1.cpp> - 05/21/16 08:20:33 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #include <ctime> using namespace std; typedef long long lol; typedef unsigned long long ull; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=31; const int INF=1e9; const int seed=11,MOD=2001019; int f[MAXN]; int gf(int x){if(f[x]!=f[f[x]])f[x]=gf(f[x]);return f[x];} int b[MAXN],size[MAXN]; ull ha[MOD+1]; int all; int HASH(int b[],ull x){ int res=0; for(int i=1;i<=b[0];i++)res=(res*seed+b[i])%MOD; while(ha[res]&&ha[res]!=x)res++; ha[res]=x; return res; } ull HASH2(int b[]){ ull res=0; for(int i=b[0];i>=1;i--)res=res*seed+b[i]; return res; } double res[MOD+1]; double dfs(int b[]){ if(b[0]==1)return 0; int now[MAXN]; int ard=0; for(int i=1;i<=b[0];i++)ard+=b[i]*(b[i]-1)>>1; double g=0.0; for(int i=1;i<=b[0];i++) for(int j=i+1;j<=b[0];j++){ now[0]=0; for(int k=1;k<i;k++)now[++now[0]]=b[k]; for(int k=i+1;k<j;k++)now[++now[0]]=b[k]; for(int k=j+1;k<=b[0];k++)now[++now[0]]=b[k]; now[++now[0]]=b[i]+b[j]; sort(now+1,now+now[0]+1); int h=HASH(now,HASH2(now)); if(!res[h])res[h]=dfs(now); g+=res[h]*b[i]*b[j]/all; } return (g+1)/(1-double(ard)/all); } int main(){ freopen("t1.in","r",stdin); freopen("t1.out","w",stdout); int n=gi(),m=gi();all=n*(n-1)>>1; for(int i=1;i<=n;i++)f[i]=i; while(m--)f[gf(gi())]=gf(gi()); for(int i=1;i<=n;i++){ if(f[i]==i)b[++b[0]]=i; size[gf(i)]++; } for(int i=1;i<=b[0];i++)b[i]=size[b[i]]; sort(b+1,b+b[0]+1); printf("%.6lf",dfs(b)); return 0; } |
2.树的重构
用dp[i][j]表示序列[i,j]的答案
然后xjb dp就可以了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
// <t2.cpp> - 05/21/16 08:20:33 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=400; const int INF=1e9; char s[MAXN]; lol dp[MAXN][MAXN]; int main(){ freopen("t2.in","r",stdin); freopen("t2.out","w",stdout); scanf("%s",s+1); int n=strlen(s+1); for(int i=1;i<=n;i++)dp[i][i]=1; for(int l=n-2;l;l--) for(int r=l+2;r<=n;r+=2){ if(s[l]!=s[r])continue; dp[l][r]=dp[l+1][r-1]; for(int i=l+2;i<=r-1;i+=2) dp[l][r]+=dp[l+1][i-1]*dp[i][r]; } printf("%lld",dp[1][n]); return 0; } |
3.扭曲的排序[Ural 1568 Train Car Sorting]
就一结论题 没意思【
如果i的位置在i+1前面，可以把i和i+1合成一起一定最优
那么每次把1-n分成若干块，然后把偶数块提前
证明要看论文。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// <t3.cpp> - 05/21/16 08:20:33 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=10001; const int INF=1e9; int n,a[MAXN],b[MAXN],c[MAXN][2],cnt[2]; bool check(){for(int i=1;i<n;i++)if(a[i]!=i)return 0;return 1;} int main(){ freopen("t3.in","r",stdin); freopen("t3.out","w",stdout); n=gi(); for(int i=1;i<=n;i++)a[gi()]=i; int ans=0; while(!check()){ ans++; cnt[0]=cnt[1]=0; bool f=0; c[++cnt[f]][f]=1; for(int i=2;i<=n;i++){ if(a[i]<a[i-1])f=!f; c[++cnt[f]][f]=i; } for(int i=1;i<=cnt[0];i++)a[c[i][0]]=i; for(int i=1;i<=cnt[1];i++)a[c[i][1]]=cnt[0]+i; } printf("%d",ans); return 0; } |
4.括号化简
和斗地主一样的傻逼题 都放最后一题了
这么看来和noip还是有点相似之处的
每个括号判断拆不拆以及里面符号变不变即可
数据是n<=3000，暴力就行。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
// <t4.cpp> - 05/21/16 08:20:33 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=5020; const int INF=1e9; int n; char s[MAXN]; int st[MAXN]; int tot,l[MAXN],r[MAXN]; int p[MAXN],q[MAXN]; int main(){ freopen("t4.in","r",stdin); freopen("t4.out","w",stdout); scanf("%s",s+1); int n=strlen(s+1); int top=0; p[0]=1;q[n+1]=n; for(int i=1;i<=n;i++){ q[i]=i-1;p[i]=i+1; if(s[i]=='(')st[++top]=l[++tot]=i; if(s[i]==')')r[st[top--]]=i; } for(int i=1;i<=tot;i++){ int ll=l[i],rr=r[l[i]]; bool jj=0; int sb=0; for(int i=p[ll];i!=rr;i=p[i]){ if(s[i]=='(')sb++; else if(s[i]==')')sb--; else if(!sb) if(s[i]=='+'||s[i]=='-'){jj=1;break;} } if(jj){ if(s[q[ll]]=='*'||s[q[ll]]=='/')continue; if(s[p[rr]]=='*'||s[p[rr]]=='/')continue; if(s[q[ll]]=='-') for(int i=p[ll];i!=rr;i=p[i]){ if(s[i]=='(')sb++; else if(s[i]==')')sb--; else if(!sb) if(s[i]=='+')s[i]='-'; else if(s[i]=='-')s[i]='+'; } p[q[ll]]=p[ll];q[p[ll]]=q[ll]; p[q[rr]]=p[rr];q[p[rr]]=q[rr]; }else{ if(s[q[ll]]=='/'){ for(int i=p[ll];i!=rr;i=p[i]){ if(s[i]=='(')sb++; else if(s[i]==')')sb--; else if(!sb) if(s[i]=='*')s[i]='/'; else if(s[i]=='/')s[i]='*'; } } p[q[ll]]=p[ll];q[p[ll]]=q[ll]; p[q[rr]]=p[rr];q[p[rr]]=q[rr]; } } for(int i=p[0];i!=n+1;i=p[i])putchar(s[i]); return 0; } |
吓尿了
吓尿了