2017/10/10模拟赛总结

题目来自NOIP2016十连测第8场

T1 神炎皇

打表找规律可以发现
每碰上一个数是平方数(x^2)的倍数就会加
加上最大的x-1
比如36 是2 3 6共同的平方倍数
36的答案就会比35多加5(6-1)
现在的问题就是如何判断最大平方数因子为x^2
前面2和3共加了3 6只用加2
不妨用小因子的数更新他的倍数的因子要加的数
类似筛法 O(n√∗log2log2n√)
这样只有80分因为不能用线性筛来替代
再分析原来的式子

设 gcd(a,b)=d,a′d=a,b′d=b ，那么 (a′+b′)d∣a′b′d2 ，即 (a′+b′)∣a′b′d
由于 a′ 和 b′ 互质， (a′+b′)∤a′b′ ，于是 (a′+b′)|d
具体可以用反证法推一下
而 (a′+b′)d≤n ，所以 (a′+b′)<n√
考虑枚举 k=(a′+b′) ，对于每个 k ，合法的 d 有 nk2 个， (a′,b′) 则有 φ(k) 对
(因为如果假设 a′ 是质数，那么 a′ 的取值共有 φ(k) 个，每一种都一定有一个不互质的 b′ 对应)
所以 ans=∑i=2n√φ(i)∗ni2
线性筛的同时求解即可
O(n√)

#include<bits/stdc++.h>
using namespace std;
#define N 10000010
bool mark[N];
int phi[N],pri[N];
int main(){
    long long n,ans=0;
    scanf("%lld",&n);
    int P=sqrt(n),h=0;
    register int i,j;
    for (i=2;i<=P;i++){
        if (!mark[i]) pri[++h]=i,phi[i]=i-1;
        for (j=1;j<=h;j++){
            int t=i*pri[j];
            if (t>P) break;
            mark[t]=1;
            if (!(i%pri[j])){
                phi[t]=phi[i]*pri[j];
                break;
            }
            phi[t]=phi[i]*phi[pri[j]];
        }
        ans+=n/i/i*phi[i];
    }
    printf("%lld\n",ans);
    return 0;
}

T2 降雷皇

BIT优化LIS裸题..
在BIT中多存一个方案数即可
O(n∗log2n)

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define mo 123456789
int a[N],n,type;
inline void cmp(int &x,int &y,int p,int q){
    if (p>x) x=p,y=q;
    else if (p==x) y=(y+q)%mo;
}
struct Binary_Indexed_Tree{
    int bit[N],num[N];
    void add(int i,int x,int y){
        while (i<N){
            cmp(bit[i],num[i],x,y);
            i+=i&-i;
        }
    }
    void query(int i,int &x,int &y){
        while (i){
            cmp(x,y,bit[i],num[i]);
            i-=i&-i;
        }
    }
}BIT;
int main(){
    scanf("%d%d",&n,&type);
    int i;
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    int ans=0,ans1=0;
    for (i=1;i<=n;i++){
        int x=0,y=1;
        BIT.query(a[i]-1,x,y);
        cmp(ans,ans1,x+1,y);
        BIT.add(a[i],x+1,y);
    }
    printf("%d\n",ans);
    if (type) printf("%d\n",ans1);
    return 0;
}

T3 幻魔皇

点数构成斐波那契数列
首先可以把所有点建出来枚举+dfs
n=20 时有 1.7∗104 个点勉强几秒可以跑过去
n=30 时有 2∗106 个点用树形DP也可以在 O(点数) 范围内求出
n=400 时点就很多了显然要把所有点在深度的层次上考虑
其实一棵大树是由小树延展过来每一层只需要知道白点和黑点个数就可以了
相同颜色的点下面构造也是相同的

设 Wi 表示第 i 层有多少个白色节点 dpwi 表示下一层的一个白点下面共有几个白点
Bi 和 dpbi 同理
然后就可以枚举深度更新答案了

struct P3{
    static const int N3=510;
    int ans[N3<<1],A[N3],B[N3],W[N3],dpw[N3],dpb[N3],f[N3];
    void solve(){
        int i,j,k;
        A[1]=1; A[2]=1;
        for (i=3;i<=n;i++) A[i]=(A[i-1]+A[i-2])%mo;
        for (i=1;i<=n;i++){
            B[i]=A[i-1];
            W[i]=(A[i]-A[i-1]+mo)%mo;
        }
        dpw[n]=1;
        dpb[n]=0;
        for (i=n-1;i;i--){
            for (j=i+1;j<=n;j++)
                for (k=i+1;k<=n;k++)
                    ans[j+k-i*2]=(ans[j+k-i*2]+1LL*B[i]*dpw[j]%mo*dpb[k])%mo;
            for (j=i+1;j<=n;j++) ans[j-i]=(ans[j-i]+1LL*W[i]*dpb[j])%mo;
            for (j=i+1;j<=n;j++) f[j]=dpb[j];
            for (j=i+1;j<=n;j++) dpb[j]=(dpw[j]+dpb[j])%mo;
            for (j=i+1;j<=n;j++) dpw[j]=f[j];
            dpw[i]=1;
        }
        for (i=1;i<=2*n;i++) printf("%d ",ans[i]);
    }
}P80;

其实发现在 i 深度的 dpwj 的值就是 Wj−i dpb 也一样
可以这样把 dpw 和 dpb 数组去掉
然后看到更新 ans 时用到 j+k 可以每次根据新加的点更新 sumi 表示 j+k=i 有多少对点
而每次新加的点是 Bn−i 和 Wn−i
而由于 i 减少了之前求出的都向前平移了两格
处理一下即可

#include<bits/stdc++.h>
using namespace std;
#define mo 123456789
#define N 5010
int n;
int ans[N<<1],A[N],B[N],W[N],sum[N<<1];
int main(){
    int n;
    register int i,j;
    scanf("%d",&n);
    A[1]=1; A[2]=1;
    for (i=3;i<=n;i++) A[i]=(A[i-1]+A[i-2])%mo;
    for (i=1;i<=n;i++){
        B[i]=A[i-1];
        W[i]=(A[i]-A[i-1]+mo)%mo;
    }
    for (i=n;i;i--){
        for (j=1;j<=2*n;j++) sum[j]=sum[j+2];
        for (j=i+1;j<n;j++) sum[n+j]=(sum[n+j]+1LL*W[n-i]*B[j-i]+1LL*W[j-i]*B[n-i])%mo;
        sum[n*2]=(sum[n*2]+1LL*W[n-i]*B[n-i])%mo;
        for (j=i*2+1;j<=n*2;j++) ans[j-i*2]=(ans[j-i*2]+1LL*B[i]*sum[j])%mo;
        for (j=i+1;j<=n;j++) ans[j-i]=(ans[j-i]+1LL*W[i]*B[j-i])%mo;
    }
    for (i=1;i<=2*n;i++) printf("%d ",ans[i]);
    return 0;
}

Date:2017/10/11
By CalvinJin

秒客网

2017/10/10模拟赛总结

相关文章