Orzz(j)yf、kb都太强啦比我不知道高到哪里去了Orz。。。

T1 币(coin)

每次询问跑一次$O(n^2)$得60分。
所以此题需要预处理。
设$f[i][j]$表示在$n=i$的情况下,第$j$个位置的权重(一个小于1的实数,也就是设$j$这个位置的数为1时,最后先手对这个位置的期望)。
我们不难得到递推式:
$f[i][j]=1.0-(f[i-1][j]+f[i-1][j-1])/2$

所以$O(n^2)$预处理,$O(n)$询问。

代码:

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

T2 △(triangle)

其实这题解法真的很暴力。。。
如果要算出原图符合条件的三元组个数,就暴力算。
枚举一个点$i$,再枚举与它有边链接的点$j$,再枚举与$j$有边链接的点$k$,再判断$k$与$i$是否有边链接,如果有则ans++。
但在这里我们需要保证:$i<j<k$,不然会重复计算,这个在读入边的时候就可以处理掉。

怎么解补图中符合条件的三元组个数呢?
看评分标准,其实是个提示。我们如果求出原图、补图的符合条件的三元组个数之和不就行了嘛。。。

显然如果整个图任意两个点之间都有一条边,那么三元组个数之和为$C(n,3)=n×(n-1)×(n-2)/6$
所以我们要找出不能组成符合条件的三元组的个数。

这就很简单了。对于点$i$,它的出度为$ocnt[i]$,那么与它不相邻的点的个数为$n-1-a[i]$(-1是因为与它相邻的还包括它自己)。
所以组成的不符合的三元组个数就是:$ocnt[i]*(n-1-ocnt[i])/2$
所以总共不符合条件的三元组个数为:
http://www.k-xzy.xyz/wp-content/uploads/2017/05/bufuhetiaojiandesanyuanzu.png

所以就AC
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
static const LL maxs=100100;
LL n,m,tot,ans,ocnt[maxs+5],to[maxs+5],nxt[maxs+5],head[maxs+5],size;
queue<LL> que;
bool book[maxs+5];
void push(LL u,LL v){to[size]=v,nxt[size]=head[u],head[u]=size,size++;}
int main()
{
    freopen("triangle.in","r",stdin),freopen("triangle.out","w",stdout);
    scanf("%lld%lld",&n,&m),memset(head,-1,sizeof(head));
    for(LL i=1,u,v;i<=m;i++)
    {
        scanf("%lld%lld",&u,&v);
        if(u>v)swap(u,v);
        push(u,v),ocnt[u]++,ocnt[v]++;
    }
    for(LL i=1;i<=n;i++)
    {
        tot+=ocnt[i]*(n-1-ocnt[i]);
        for(LL j=head[i];j!=-1;j=nxt[j])que.push(to[j]),book[to[j]]=1;
        while(!que.empty())
        {
            LL f=que.front();que.pop();
            for(LL j=head[f];j!=-1;j=nxt[j])ans+=book[to[j]];
        }
        for(LL j=head[i];j!=-1;j=nxt[j])book[to[j]]=0;
    }
    tot=n*(n-1)*(n-2)/6-tot/2;
    printf("%lld %lld\n",ans,tot-ans);
    return 0;
}

T3 数(aqnum)

题意很难理解吧。
其实可以转化为:
当一个数字$i$质因数分解以后,每种因数的个数为奇数的时候,$i$为农数。
解法:搜索+优化
首先素数筛,筛出区间[2,maxprime]中的素数。
然后设$dfs(i,j)$表示当前确定了$i$为一个农数,当前搜索到了第$j$个质数(因为我们只会找$j$后面的质数)。
设$p[i]$为第$i$个质数。
因为i是个农数,所以$i×p[j]$也是农数(因为$p[j]$在之前没有被搜索过),$i×p[j]^3$也是,$i×p[j]$的$(2×k+1)$次方都是。
所以我们就可以暴力搜索了。
然后我们需要优化。
1. 当$i×p[j]$大于upto,ans++,然后减掉。
2. 当$j$大于[1,maxprime]中的质数个数时,ans++,然后减掉。
3. 当$i×2×p[j]$大于upto,但$i×p[j]$小于等于upto,直接二分找出满足条件的最大的$j$设为k,然后$ans+=k-j+2$,然后减掉。

于是就能AC了。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,ans,p[1000005],psize;
bool book[1000005];
LL serch(LL k,LL l)
{
    LL r=psize-1,mid;
    while(mid=(l+r+1)>>1,l!=r)if(k*p[mid]<=n)l=mid;else r=mid-1;
    return l;
}
void dfs(LL k,LL x)
{
    if(x>=psize|k*p[x]>n){ans++;return;}
    if(k*p[x]*p[x]>n){ans+=serch(k,x)-x+2;return;}
    dfs(k,x+1),k*=p[x],dfs(k,x+1);
    while(k*=p[x]*p[x],k<=n)dfs(k,x+1);
}
int main()
{
    freopen("aqnum.in","r",stdin),freopen("aqnum.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(LL i=2;i<=m;i++)
        if(!book[i]){p[psize++]=i;for(LL j=(LL)i*i;j<=m;j+=i)book[j]=1;}
    dfs(1,0),printf("%lld\n",ans);
    return 0;
}

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *