Three_C 比赛解题报告–by litble

考试的时候 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;
}