首页 > 代码库 > SDOI2017 Round1 Day2 题解
SDOI2017 Round1 Day2 题解
T2好厉害啊……AK不了啦……不过要是SCOI考这套题就好了240保底。
BZOJ4819 新生舞会
模板题，分数规划+二分图最大权匹配。费用流跑得过，可以不用KM。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef double flo;
const int inf=1e9;
const int N=205;
struct edge{
int v,c;
flo w;
}e[20400];
vector<int>h[N];
int l;
void ins(int u,int v,int c,flo w){
edge a={v,c,w};
h[u].pb(l);
e[l++]=a;
edge b={u,0,-w};
h[v].pb(l);
e[l++]=b;
}
flo d[N];
int s1,s2,q[N*N],vis[N],p[N];
bool spfa(){
flo c=0;
while(1){
fill(d,d+s2+1,-inf);
d[q[0]=s1]=0;
for(int a=0,b=0;a<=b;++a){
int u=q[a];
vis[u]=0;
for(int i=0;i<h[u].size();++i){
edge*j=e+h[u][i];
if(d[u]+j->w>d[j->v]&&j->c){
d[j->v]=d[u]+j->w;
p[j->v]=j-e;
if(!vis[j->v]++)q[++b]=j->v;
}
}
}
if(d[s2]==-inf)
return 1;
int f=inf;
for(int i=s2;i!=s1;i=e[p[i]^1].v)
f=min(f,e[p[i]].c);
c+=f*d[s2];
if(c<0)return 0;
for(int i=s2;i!=s1;i=e[p[i]^1].v){
e[p[i]].c-=f;
e[p[i]^1].c+=f;
}
}
}
int n,a[N][N],b[N][N];
bool jud(flo c){
for(int i=s2;~i;--i)
h[i].clear();
l=0;
for(int i=1;i<=n;++i){
ins(s1,i,1,0);
ins(i+n,s2,1,0);
for(int j=1;j<=n;++j)
ins(i,j+n,1,a[i][j]-c*b[i][j]);
}
return spfa();
}
int main(){
scanf("%d",&n);
s2=n*2+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",a[i]+j);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",b[i]+j);
flo l=1e-4,r=1e4;
while(r-l>1e-8){
flo j=(l+r)/2;
(jud(j)?l:r)=j;
}
printf("%.6f\n",l);
}
BZOJ4820 硬币游戏
设$f_i$为经过$i$的次数的期望。把所有非终止态记为一个状态$p$，考虑$p$加上一个人的串，可能直接到对应的终止态，也可能先到其他终止态（可能是自己），因此要减去其他终止态的贡献。比如终止态$x$、$y$的串分别为TTH、HTT，那么$p$+TTH可能是$y$+TH或$y$+H，因此$f_x=\frac18f_p-\frac34f_y$，因为$p$有$\frac18$的概率到$x$，其中到了$y$的话有$\frac34$的概率到$x$。可能先到其他终止态的情况也就是其他串的后缀匹配了当前串的前缀，可以用kmp计算。列出这些方程后高斯消元即可。
#include<bits/stdc++.h>
using std::swap;
typedef long double flo;
const int N=302;
int n,m,f[N];
char z[N][N];
flo c[N][N];
void piv(int i){
int j=i;
for(int k=i+1;k<=n;++k)
if(fabs(c[k][i])>fabs(c[j][i]))j=k;
for(int k=i;k<=n+1;++k)
swap(c[i][k],c[j][k]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
scanf("%s",z[i]);
f[0]=-1;
for(int i=0;i<n;++i){
int j=0,k=-1;
while(j<m){
while(~k&&z[i][j]!=z[i][k])k=f[k];
f[++j]=++k;
}
for(int l=0;l<n;++l){
j=k=0;
while(j<m){
while(~k&&z[l][j]!=z[i][k])k=f[k];
++j,++k;
}
for(;k;k=f[k])
c[i][l]+=pow(.5l,m-k);
}
c[i][n]=-pow(.5l,m);
c[n][i]=1;
}
c[n][n+1]=1;
for(int i=0;i<=n;++i){
piv(i);
for(int j=n+1;j>=i;--j)
c[i][j]/=c[i][i];
for(int j=0;j<=n;++j)
if(i!=j)
for(int k=n+1;k>=i;--k)
c[j][k]-=c[j][i]*c[i][k];
}
for(int i=0;i<n;++i)
printf("%.10f\n",double(c[i][n+1]));
}
BZOJ4821 相关分析
简单线段树，维护$\sum x$、$\sum y$、$\sum xy$、$\sum x^2$以及两种标记。
#include<cstdio>
#define P (k<<1)
#define S (P^1)
typedef long double flo;
const int N=1e5+5;
flo cal1(flo n){return n*(n-1)/2;}
flo cal2(flo n){return n*(n-1)*(n*2-1)/6;}
struct vec{flo a,b,c,d;};
vec operator+(vec a,vec b){
vec c={
a.a+b.a,a.b+b.b,a.c+b.c,a.d+b.d
};
return c;
}
struct node{
int i,j,n;
vec s;
flo xd,yd,xc,yc;
bool d,c;
void upd1(flo x,flo y){
if(!d)
xd=x,yd=y,d=1;
else
xd+=x,yd+=y;
s.c+=y*s.a+x*s.b+n*x*y;
s.d+=x*s.a*2+n*x*x;
s.a+=n*x;
s.b+=n*y;
}
void upd2(flo x,flo y){
xc=x,yc=y,c=1,d=0;
flo a=x+i,b=y+i;
s.a=n*a+cal1(n);
s.b=n*b+cal1(n);
s.c=n*a*b+cal1(n)*(a+b)+cal2(n);
s.d=n*a*a+cal1(n)*a*2+cal2(n);
}
}a[N*4];
void down(int k){
if(a[k].c){
a[P].upd2(a[k].xc,a[k].yc);
a[S].upd2(a[k].xc,a[k].yc);
a[k].c=0;
}
if(a[k].d){
a[P].upd1(a[k].xd,a[k].yd);
a[S].upd1(a[k].xd,a[k].yd);
a[k].d=0;
}
}
void upd1(int k){
a[k].s=a[P].s+a[S].s;
}
void upd2(int k){
a[k].i=a[P].i;
a[k].j=a[S].j;
a[k].n=a[P].n+a[S].n;
upd1(k);
}
int f[N],g[N];
void pre(int i,int j,int k){
if(i==j){
flo x=f[i],y=g[i];
a[k]=(node){i,j,1,x,y,x*y,x*x};
}else{
pre(i,i+j>>1,P);
pre((i+j>>1)+1,j,S);
upd2(k);
}
}
void inc(flo x,flo y,int s,int t,int k){
if(s<=a[k].i&&a[k].j<=t)
a[k].upd1(x,y);
else{
down(k);
if(s<a[S].i)inc(x,y,s,t,P);
if(t>a[P].j)inc(x,y,s,t,S);
upd1(k);
}
}
void cov(flo x,flo y,int s,int t,int k){
if(s<=a[k].i&&a[k].j<=t)
a[k].upd2(x,y);
else{
down(k);
if(s<a[S].i)cov(x,y,s,t,P);
if(t>a[P].j)cov(x,y,s,t,S);
upd1(k);
}
}
vec ask(int s,int t,int k){
if(s==a[k].i&&a[k].j==t)
return a[k].s;
down(k);
return t<a[S].i?ask(s,t,P):s>a[P].j?ask(s,t,S):ask(s,a[P].j,P)+ask(a[S].i,t,S);
}
int main(){
int n,m,o,s,t,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",f+i);
for(int i=1;i<=n;++i)scanf("%d",g+i);
pre(1,n,1);
while(m--){
scanf("%d%d%d",&o,&s,&t);
if(o==1){
vec v=ask(s,t,1);
int n=t-s+1;
printf("%.10f\n",double((v.c-v.a*v.b/n)/(v.d-v.a*v.a/n)));
}else{
scanf("%d%d",&x,&y);
(o==2?inc:cov)(x,y,s,t,1);
}
}
}
SDOI2017 Round1 Day2 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。