【水题合集】5.21考试 – 徐亦轲的博客

这套题居然是noip模拟题。。吓尿了

怎么看都是前几年noi难度

1.连通期望

将每种状况的各个连通块大小hash一下，记忆化搜索。

状态数显然不会很多。

// <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;
}

// <t1.cpp> - 05/21/16 08:20:33

// This file is created by XuYike's black technology automatically.

// 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就可以了

// <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;
}

// <t2.cpp> - 05/21/16 08:20:33

// This file is created by XuYike's black technology automatically.

// 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分成若干块，然后把偶数块提前

证明要看论文。。

// <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;
}

// <t3.cpp> - 05/21/16 08:20:33

// This file is created by XuYike's black technology automatically.

// 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，暴力就行。

// <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;
}

// <t4.cpp> - 05/21/16 08:20:33

// This file is created by XuYike's black technology automatically.

// 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;

}

2 评论

最旧