题解

1.Coin

大意:一个数列,两个人随机从两端取走数。求先手期望取走多少数。
60分:考场上俺就是这么打的。如果用f[i][j]表示数列[i…j]先手期望取走的数。

f[i][j]=

(f[i+2][j]+w[i]

+f[i][j-2]+w[j]

+f[i+1][j-1]+w[i]

+f[i+1][j-1]+w[j])/4

O(n^2*T);
100分:考虑到对于出现的一定长度的数列,每个位置上的数被取到的概率是不变的。所以如果f[i][j]表示出现了长度为i的数列,第j个数被取到的概率。则:

f[i][j]=

(1-f[i-1][j]+

1-f[i-1][j-1])/2

(其中前者表示取走最后一个数,后者表示取走前一个数。)
这样就可以O(n^2+n*T);

#include <cstdio>
#define MX 1001
using namespace std;
double f[MX][MX],a,ans;
int t,n;
int main()
{
    freopen("coin.in","r",stdin),freopen("coin.out","w",stdout);
    scanf("%d",&t);
    for(int i=1;i<MX;i++)for(int j=1;j<=i;j++)f[i][j]=1-(f[i-1][j]+f[i-1][j-1])/2;
    for(int i=1;i<=t;i++,ans=0){
        scanf("%d",&n);
        for(int j=1;j<=n;j++){
            scanf("%lf",&a);
            ans+=f[n][j]*a;
        }
        printf("%.3f\n",ans);
    }
    return 0;
}

2.Triangle

大意:求一个图中三元环的个数及不图中三元环的个数。
30分:枚举每个点暴力判边。
72分:前30分用30分做法,后42分只输出原图三元环个数,用后文的O(M)算法。
100分:令图中有的边为黑边,没有边为白边。则要求的是全为白边和全为黑边的三元环的个数。令B表示全黑三角形,W为全白三角形,A表示彩色三角形。则

B+W+A=N(N-1)(N-2)/6

其中A可以用O(N)求出:设black[i]表示与i点相连的点数,white[i]表示与i点不相邻的点数,则A=(Σ(black[i]*white[i]))/2 (i∈V).
由于白边数量较多,所以考虑求出B再推出W。
如果枚举每个点i,设book[j]=1((i,j)∈E),再枚举每个点j((i,j)∈E),枚举每个点w((j,w)∈E),如果book[w]==1,则B自加1。由于这样求出的每个三角形被枚举了6次(A(3,3)=3!),所以

W=N(N-1)(N-2)/6 – (Σ(black[i]*white[i]))/2 – (Σi,j,k∈V且(i,j),(i,k),(j,k)∈E1)

这样均摊复杂度为O(M).
至此,B,W已经求出。

#include <bits/stdc++.h>
#define MX 100001
#define MD 4323333
using namespace std;
template<typename T>
void in(T &x){
    x = 0;char ch = getchar();
    while(ch >'9' || ch <'0') ch = getchar();
    while(ch<='9' && ch >='0') x = x*10+ch-'0',ch = getchar();
}

long long pbl[MX],pwt[MX],n,m;
long long fst[MX*2],nxt[MX*2],lnum=-1,u[MX*2],v[MX*2];
long long tot,have;

int book[MX];

inline void addeg(int nu,int nv)
{
    lnum++;
    u[lnum]=nu;
    v[lnum]=nv;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
}

void work()
{
    long long yuan=0;
    for(register int i=1;i<=n;i++)
    {
        for(register int w=fst[i];w!=-1;w=nxt[w])book[v[w]]=i;
        for(register int w=fst[i];w!=-1;w=nxt[w])
            if(v[w]>i)
                for(register int p=fst[v[w]];p!=-1;p=nxt[p])
                    if(book[v[p]]==i&&v[p]>v[w])yuan++;
    }
    printf("%I64d %I64d\n",yuan,tot-have-yuan);
}

int main()
{
    memset(fst,0xff,sizeof(fst));
    freopen("triangle.in","r",stdin),freopen("triangle.out","w",stdout);
    in(n);in(m);
    for(long long i=1,a,b;i<=m;i++)
    {
        in(a);in(b);
        addeg(a,b),addeg(b,a);
        pbl[a]++,pbl[b]++;
    }
    for(int i=1;i<=n;i++)pwt[i]=n-1-pbl[i];
    tot=n*(n-1)*(n-2)/6;
    for(int i=1;i<=n;i++)have+=pbl[i]*pwt[i];
    have/=2;
    work();
    return 0;
}

3.Aqnum
大意:求1到upto中有几个数满足:每个质因数小于等于maxprime且每种质因数个数为奇数。
30分:暴力搜索,用f(x,k)当前的数为x,在处理第k个质数,则:继续搜索f(x,k+1), f(xp[k],k+1), f(xp[k]*p[k]2a,k+1). 复杂度约为∏(upto/p[k])

60分:如果当前的xp[k]<=upto且xp[k]2>upto,则找到最后一个满足上述条件的k2, ans+=k2-k+2;大约可以剪枝2k以上的状态数。

#include <bits/stdc++.h>

#define MX 1000001

using namespace std;

long long prm[80000];
long long tab[MX];
long long mp,upto,pnum;

typedef long long ll;

void makep(ll top)
{
    ll now=2;
    pnum++;
    prm[pnum]=2;
    for(;;)
    {
        for(ll i=1;i*now<=top;i++)
        {
            tab[i*now]=1;
        }
        for(ll i=now;i<=top;i++)
        {
            if(tab[i]==0)
            {
                now=i;
                prm[++pnum]=i;
                break;
            }
            if(i==top)return ;
        }
    }
}

ll sch(ll l,ll k)
{
    ll r=pnum,mid;
    while(mid=(l+r+1)>>1,l!=r)if(k*prm[mid]<=upto)l=mid;else r=mid-1;
    return l;
}

ll ans;

void get(ll x,ll now)
{
    if(now>pnum||x*prm[now]>upto){ans++;return;}
    if(x*prm[now]*prm[now]>upto){ans+=sch(now,x)-now+2;return;}
    get(x,now+1);
    x*=prm[now];
    get(x,now+1);
    while(x*prm[now]*prm[now]<=upto)
    {
        x*=prm[now]*prm[now];
        get(x,now+1);
    }
}

int main()
{
    freopen("aqnum.in","r",stdin),freopen("aqnum.out","w",stdout);
    scanf("%I64d%I64d",&upto,&mp);
    makep(mp);
    get(1,1);
    cout<<ans<<endl;
    return 0;
}
分类: 文章

发表评论

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

你是机器人吗? =。= *