ZJOI2011 Day1 ( bzoj2227~2229 ) 题解

2018-06-27 10:00:38来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

bzoj2227 看电影:

先打个暴力,然后找规律。得到答案:ans=(k+1)n-1*(k-n+1)/kn

正解:http://blog.lightning34.cn/?p=166

注意到答案很大,又由于n,k<=200,将k+1,k-n+1,k分解质因数,然后高精乘就可以了

 

暴力代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 #define ll long long
 7 #define N 210
 8 ll x,y,g;
 9 int i,j,k,n,m,T;
10 bool b[N];
11 inline ll Gcd(ll x,ll y){
12     if(y==0)return x;
13     return Gcd(y,x%y);
14 }
15 inline ll Pow(int x,int y){
16     if(y==0)return 1;
17     ll Ans=Pow(x,y>>1);
18     Ans*=Ans;
19     if(y&1)return Ans*x;return Ans;
20 }
21 inline ll Dfs(int x){
22     if(x==n+1)return 1;
23     ll Ans=0;
24     int j=0;
25     for(int i=1;i<=k;i++)
26     if(!b[i]){
27         b[i]=1;
28         Ans+=Dfs(x+1)*(i-j);
29         b[j=i]=0;
30     }
31     return Ans;
32 }
33 int main()
34 {
35     for(n=1;n<=9;n++)
36     for(k=n;k<=9;k++){
37         cout<<n<<" "<<k<<" ";
38         memset(b,0,sizeof(b));
39         x=Dfs(1);y=Pow(k,n);
40         printf("%lld %lld\n",x,y);
41     } 
42 }
43 
44 bzoj2227(暴力)
bzoj2227(暴力)

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 #define N 210
 7 #define M 510
 8 int i,T,j,k,n,m,p[N][N],P[N],Num,ans[N],a2[N],s,a[M],l,x;
 9 inline void C(int x){
10     if(l==0){
11         a[l=1]=x;
12         for(l++;a[l];)a[l+1]+=a[l]/10,a[l++]%=10;l--;
13         return;
14     }
15     for(int i=1;i<=l;i++)a[i]*=x;
16     for(int i=1;i<=l;i++)a[i+1]+=a[i]/10,a[i]%=10;
17     for(l++;a[l];)a[l+1]+=a[l]/10,a[l++]%=10;l--;
18 }
19 int main()
20 {
21     for(i=2;i<N;i++){
22         s=sqrt((double)i);
23         for(j=2;j<=s;j++)
24         if(i%j==0)break;
25         if(j>s)P[++Num]=i;
26     }
27     for(i=1;i<N;i++){
28         x=i;
29         for(j=1;j<=Num;j++)
30         while(x%P[j]==0)p[i][P[j]]++,x/=P[j];
31     }
32     scanf("%d",&T);
33     while(T--){
34         scanf("%d%d",&n,&k);
35         if(n>k){puts("0 1");continue;}
36         memset(a,0,sizeof(a));l=0;
37         memset(ans,0,sizeof(ans));
38         memset(a2,0,sizeof(a2));
39         for(i=1;i<=k+1;i++)ans[i]=p[k+1][i]*(n-1);
40         if(k-n)for(i=1;i<=k-n+1;i++)ans[i]+=p[k-n+1][i];
41         if(k>1)for(i=1;i<=k;i++)
42         a2[i]=p[k][i]*n-ans[i],ans[i]-=p[k][i]*n;
43         for(i=1;i<N;i++)
44         for(i=1;i<N;i++)
45         for(j=1;j<=ans[i];j++)C(i);                
46         if(!l)putchar('1');
47         for(i=l;i;i--)putchar(a[i]+48);putchar(' ');
48         memset(a,0,sizeof(a));l=0;
49         for(i=1;i<N;i++)
50         for(j=1;j<=a2[i];j++)C(i);
51         if(!l)putchar('1');
52         for(i=l;i;i--)putchar(a[i]+48);putchar('\n');
53     }
54     return 0;
55 }
bzoj2227

 

bzoj2228 礼物:

枚举将哪一面作为底面。枚举每一层,令f[i][j][k]表示在第k层右下角在(i,j)时最大的正方形边长,得到:

f[i][j][k]=min(f[i][j-1][k],f[i-1][j][k],f[i-1][j-1][k])+1

枚举i,j,那么问题就转化为求序列的区间最小值*区间长度的最大值

枚举每个数,用单调栈求出它作为最小值时向左、右最多延伸的长度即可。

时间复杂度O(n3)

 

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 #define N 160
 6 int i,j,k,n,m,f[N][N][N],p,q,r,b[N],Q[N],t,Ans;
 7 bool a[N][N][N],A[N][N][N];
 8 char c[N];
 9 inline int _Max(int x,int y){return x>y?x:y;}
10 inline int _Min(int x,int y){return x<y?x:y;}
11 inline void Work(){
12     for(k=1;k<=r;k++)
13     for(i=1;i<=p;i++)
14     for(j=1;j<=q;j++)
15     if(a[i][j][k])f[i][j][k]=0;else f[i][j][k]=_Min(_Min(f[i-1][j][k],f[i][j-1][k]),f[i-1][j-1][k])+1;
16     for(i=1;i<=p;i++)
17     for(j=1;j<=q;j++){
18         f[i][j][0]=f[i][j][r+1]=-1;
19         for(Q[t=1]=0,k=1;k<=r;k++){
20             while(f[i][j][Q[t]]>=f[i][j][k])t--;
21             b[k]=Q[t]+1;Q[++t]=k;
22         }
23         for(Q[t=1]=r+1,k=r;k>=1;k--){
24             while(f[i][j][Q[t]]>=f[i][j][k])t--;
25             Ans=_Max(Ans,f[i][j][k]*(Q[t]-b[k]));Q[++t]=k;
26         }
27     }
28 }
29 int main()
30 {
31     scanf("%d%d%d",&p,&q,&r);
32     for(i=1;i<=q;i++)
33     for(j=1;j<=p;j++){
34         scanf("%s",c+1);
35         for(k=1;k<=r;k++)if(c[k]=='P')A[j][i][k]=a[j][i][k]=1;
36     }
37     for(Work(),i=1;i<=p;i++)
38     for(j=1;j<=q;j++)
39     for(k=1;k<=r;k++)
40     a[i][r-k+1][j]=A[i][j][k];
41     for(swap(q,r),Work(),swap(q,r),i=1;i<=p;i++)    
42     for(j=1;j<=q;j++)
43     for(k=1;k<=r;k++)
44     a[k][j][p-i+1]=A[i][j][k];
45     swap(p,r);Work();
46     printf("%d",Ans<<2);
47     return 0;
48 }
bzoj2228

 

bzoj2229 最小割:

有一个结论:一个n个点的图最多只有n-1个最小割。

那么我们先求出(s,t)的最小割(X,Y),对于i∈X,j∈Y,更新ans[i][j],再对X,Y中的点分别进行前面的步骤就可以了。

 

代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 160
 6 #define M 3010
 7 #define INF 2147483647
 8 struct Edge{
 9     int c,t,nx;
10 }e[M<<1];
11 int Num,i,h[N],Cur[N],j,k,S[N],q[N],l,r,n,m,a[N],A[N],Ans[N][N],x,y,z,_Ans,T,Q;
12 bool b[N],B[N];
13 inline int _Min(int x,int y){return x<y?x:y;}
14 inline void Add(int x,int y,int z){e[++Num].t=y;e[Num].c=z;e[Num].nx=h[x];h[x]=Num;}
15 inline bool Bfs(int s,int t){
16     memset(b,0,sizeof(b));
17     b[s]=1;l=0;q[r=1]=s;S[s]=0;
18     while(++l<=r){
19         for(int i=h[q[l]];i;i=e[i].nx)
20         if(e[i].c&&!b[e[i].t])q[++r]=e[i].t,S[e[i].t]=S[q[l]]+1,b[e[i].t]=1;
21     }
22     return b[t];
23 }
24 inline int Dfs(int x,int a,int t){
25     if(a==0||x==t)return a;
26     int f,F=0;
27     for(int& i=Cur[x];i;i=e[i].nx)
28     if(S[e[i].t]==S[x]+1&&e[i].c&&(f=Dfs(e[i].t,_Min(a-F,e[i].c),t))){
29         e[i].c-=f;e[i^1].c+=f;F+=f;
30         if(a==F)break;
31     }
32     return F;
33 }
34 inline int Max_flow(int s,int t){
35     int Ans=0;
36     while(Bfs(s,t)){
37         for(int i=1;i<=n;i++)Cur[i]=h[i];
38         Ans+=Dfs(s,INF,t);
39     }
40     return Ans;
41 }
42 inline void Dfs(int x){
43     B[x]=1;
44     for(int i=h[x];i;i=e[i].nx)
45     if(e[i].c&&!B[e[i].t])Dfs(e[i].t);
46 }
47 inline void Divide(int l,int r){
48     if(l==r)return;
49     for(int i=2;i<=Num;i+=2)e[i].c=e[i+1].c=(e[i].c+e[i+1].c)>>1;
50     int Mf=Max_flow(a[l],a[r]);
51     memset(B,0,sizeof(B));
52     Dfs(a[l]);
53     for(int i=1;i<=n;i++)
54     if(B[i])for(int j=1;j<=n;j++)
55     if(!B[j])Ans[i][j]=Ans[j][i]=_Min(Ans[i][j],Mf);
56     int l1=l,l2=r;
57     for(int i=l;i<=r;i++)
58     if(B[a[i]])A[l1++]=a[i];else A[l2--]=a[i];
59     for(int i=1;i<=n;i++)a[i]=A[i];
60     Divide(l,l1-1);Divide(l2+1,r);
61 }
62 int main()
63 {
64     scanf("%d",&T);
65     while(T--){
66         scanf("%d%d",&n,&m);
67         for(Num=1,memset(h,0,sizeof(h)),i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),Add(x,y,z),Add(y,x,z);
68         for(i=1;i<=n;i++)a[i]=i;
69         memset(Ans,127,sizeof(Ans));
70         Divide(1,n);
71         scanf("%d",&Q);
72         while(Q--){
73             scanf("%d",&x);
74             for(_Ans=0,i=1;i<=n;i++)
75             for(j=i+1;j<=n;j++)
76             if(Ans[i][j]<=x)_Ans++;
77             printf("%d\n",_Ans);
78         }
79         putchar('\n');
80     }
81 }
bzoj2229

 

概率就是可行方案除以所有方案。

所有方案就是 knkn

考虑可行方案,如果加上一个座位使得所有的位置连成环的话,方案数就是 (k+1)n(k+1)n,另外由于是环,有重复的情况,所以要除以 k+1k+1

然后再断开,只要是空位的都可以断开,所以断开的方案数为 k?n+1k?n+1

所以最后的可行方案数为 (k?n+1)(k+1)n?1(k?n+1)(k+1)n?1

答案可以质因数分解之后高精度求。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:事物的五种配置方式(转载)

下一篇:1729 单词查找树 2000年NOI全国竞赛