考试的时候cy走进来说:今天提高组模拟,题目很水,请认真对待。
然后……
tm还真信了

T1

题目:有一排硬币堆,两个人轮流取硬币。每个选手随机取最左边或者最右边的一堆硬币。求先手期
望取得的硬币数。
硬币堆数<=1000,数据组数<=1000
60分算法:用f[i][j]表示从i到j的先手期望取硬币数,那么对于一段区间,先手要么取最左边的,要么取最右边的嘛,用s[i][j]表示i到j区间的硬币数和,所以很容易得到状态转移方程f[i][j]=(a[i]+s[i+1][j]-f[i+1][j])×0.5+(a[j]+s[i][j-1]-f[i][j-1])×0.5,其中s[i][j]的功能可以通过前缀和实现,复杂度O(Tn^2),但是T有1000组,超时。
100分算法:容易发现其实对于同样硬币堆数的情况,处于相同位置的硬币堆无论硬币数多少,被取到的期望值是一样的,比如说2堆硬币,左右都是0.5。我们可以预处理出来。用f[i][j]表示i堆硬币的情况下第j堆硬币被取到的期望值,因为先手要么拿最左边要么拿最右边,所以f[i][j]=1-(f[i-1][j]+f[i-1][j-1])×0.5。分别表示后手拿最右边和后手拿最左边的情况。预处理O(n^2),查询O(n)可以过。
代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
using namespace std;
int read(){
    int w=1,q=0;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return w*q;
}
double f[1005][1005];//在有i堆的情况下搞到第j堆的概率
int T;
int main()
{
    freopen("coin.in","r",stdin);
    freopen("coin.out","w",stdout);
    int i,j,n,x;
    double ans;
    T=read();
    for(i=1;i<=1000;i++)
        for(j=1;j<=i;j++)
            f[i][j]=1.0-(f[i-1][j]+f[i-1][j-1])*0.5;
    //就是先手取了第一个的期望和先手取了最后一个的期望对半分
    while(T--){
        n=read();ans=0;
        for(i=1;i<=n;i++){
            x=read();ans+=f[n][i]*x*1.0;
        }
        printf("%.3lf\n",ans);
    }
    return 0;
}

T2

题目:给定一个无自环重边的无向图,求这个图的三元环 1 的个数以及补图 2 的三元环个数。
m<=1000000,n<=1000000
30分算法:枚举三个点然后判断是否相连。
100分算法:看一看部分分的得法,补图和原图的和有些玄机。假如两点之间有边或者没有边可以看作是两种不同的颜色,那么对两边答案都没有贡献的是不同色三角形。一个点上任何一个“有”的边和一个“无”的边组合,无论第三边是什么,都会组成不同色三角形,而这样的三角形三条边中一定有一条边和其他两边的颜色都不同,这条边会被顶点重复计算。du[i]表示i点的度数,因此我们得到了一下算法:
pos=∑du[i]×(n-1-du[i])/2。
原图和补图的三角形和就是C(n,3)-pos。
而算原图三角形个数很简单,枚举每一条边,然后取边连接的度数少的那个点,枚举这个点相连的每一条边,链表哈希判断能否构成三角形,最后答案除以3
代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
using namespace std;
#define ll long long
int read(){
    int w=1,q=0;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return w*q;
}
int h[1000005],go[2000005],ne[2000005],du[1000005];
int he[1000005],xia[2000005],zo[2000005],yo[2000005];
ll zhe[2000005];
int n,m,tot,tot2,mod=999983;
ll kll,ans;
void add(int x,int y){tot++;go[tot]=y;ne[tot]=h[x];h[x]=tot;}
ll has(int x,int y){
    if(x>y)swap(x,y);
    return (ll)x*n+y;
}
void ah(ll tk){
    ll kl=tk%mod+1;
    tot2++;zhe[tot2]=tk;xia[tot2]=he[kl];he[kl]=tot2;
}
bool find(ll tk){
    ll kl=tk%mod+1;int i=he[kl];
    while(i){
        if(zhe[i]==tk)return 1;
        i=xia[i];
    }
    return 0;
}
int main()
{
    freopen("triangle.in","r",stdin);
    freopen("triangle.out","w",stdout);
    int i,j;
    bool da;
    n=read();m=read();
    for(i=1;i<=m;i++){
        zo[i]=read();yo[i]=read();add(zo[i],yo[i]);add(yo[i],zo[i]);
        du[zo[i]]++;du[yo[i]]++;ah(has(zo[i],yo[i]));
    }
    if(n==1||n==2){printf("0 0");return 0;}
    for(i=1;i<=n;i++)
        kll+=(long long)du[i]*(n-1-du[i]);
    kll=(long long)(n-2)*(n-1)*n/6-kll/2;
    for(i=1;i<=m;i++){
        if(du[zo[i]]>du[yo[i]])swap(zo[i],yo[i]);
        for(j=h[zo[i]];j;j=ne[j])
            if(find(has(yo[i],go[j])))  ans++;
    }
    ans=ans/3;
    printf("%lld %lld",ans,kll-ans);
    return 0;
}

T3

题目:秋锅对数论很感兴趣,他特别喜欢一种数字。秋锅把这种数字命名为 农数 ,英文名为 AQ
number 。这种数字定义如下:
定义 1 一个数 n 是农数,当且仅当对于每个质数 p ,要么 p ∤ n ,要么 p ≤ maxP rime 且存在一个
正奇数 k 使得 p k | n 且 p k+1 ∤ n 。
秋锅想知道,给定 upto和maxPrime ,问 1 到 Upto 里面的农数有多少个呢?
Upto<=10000000000,maxPrime<=1000000
题目可以转化为求upto以内可以表示为小于等于maxprime的质数的奇数次方的积的数的个数。
30分算法:暴力
60分算法:打出素数表,每次在当前搜到的num的基础上继续搜num×pri[x],num×pri[x]×(pri[x])^2,num×pri[x]×(pri[x])^2×(pri[x])^2…
100分算法:剪个枝,如果当前num×pri[x]只能乘一次了,num×pri[x]×pri[x]就超出upto了,我们知道num×pri[x+1]×pri[x+1]也会超出upto…
我们可以二分出还满足num×pri[w]<n的最后一个w,然后ans直接加上w-x+2,+2是因为此时num也算一个。
代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
using namespace std;
#define ll long long
ll upto,mp,ans;
bool is[1000005];
ll pri[1000005];
int tot;
int find(ll num,int l){//二分
    int mid,td,r=tot;
    while(l<=r){
        mid=(l+r)/2;
        if((ll)num*pri[mid]>upto)r=mid-1;
        else {td=mid;l=mid+1;}
    }
    return td;
}
void dfs(int x,ll num){
    int kl;
    if(x>tot){ans++;return;}
    if((ll)num*pri[x]>upto){ans++;return;}
    if((ll)num*pri[x]*pri[x]>upto){
        kl=find(num,x);
        ans+=kl-x+2;return;//+2的原因:num本身要算一个
    }
    dfs(x+1,num);num*=pri[x];dfs(x+1,num);
    while((ll)pri[x]*pri[x]*num<=upto){num*=pri[x]*pri[x];dfs(x+1,num);}
}
int main()
{
    freopen("aqnum.in","r",stdin);
    freopen("aqnum.out","w",stdout);
    int i,j;
    scanf("%lld%lld",&upto,&mp);
    for(i=2;i<=mp;i++){//筛素数
        if(!is[i])pri[++tot]=i;
        for(j=1;j<=tot&&pri[j]*i<=mp;j++){
            is[pri[j]*i]=1;
            if(!(i%pri[j]))break;
        }
    }
    dfs(1,1);
    printf("%lld",ans);
    return 0;
}

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *