8.6 mx 训练赛记录

__S08577__ · 2024-08-06 21:20:54 · 个人记录

A

题意

P1516

思路

设青蛙出发点为 m1 和 n1 ，分别能跳 m 米和 n 米，周长为 l，不难发现：

移项得：

不妨设 a=m-n，b=l，c=m1-n1

得：

若该方程有解，则 \gcd(a,b) \mid c 是必要条件。

可以用exgcd求解。(注意要处理负数的情况)

代码

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    d=exgcd(b,a%b,x,y);

    int xx=x;
    x=y;
    y=xx-(a/b)*y;
    return d;
}

signed main(){

//    freopen("road.in","r",stdin);
//    freopen("road.out","w",stdout);

    int x,y,m,n,l;
    cin>>x>>y>>m>>n>>l;
    if(n<m){
        swap(n,m);
        swap(x,y);
    }
    int a=x-y;
    int b=n-m;
    int t=exgcd(b,l,x,y);
   // cout<<a<<' '<<b<<' '<<c<<' '<<t<<endl;
    if(a%t){
        cout<<"Impossible";
        return 0;
    }

    int md=l/t;
    x=(x*(a/d)%md+md)%md;
    cout<<x;
    return 0;
}

B

题意

P3868

思路

比较板子。

由题意得：

移项得：

中国剩余定理板子。

注意这道题要预处理负数的情况并且使用快速乘。

代码

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    d=exgcd(b,a%b,x,y);

    int xx=x;
    x=y;
    y=xx-(a/b)*y;
    return d;
}

long long ksm(long long a,long long b){
    long long res=0;
    while(b>0){
        if(b&1)
            res=(res+a+lcm)%lcm;
        a=(a+a)%lcm;
        b>>=1;
    }
    return res%lcm;
}

int crt(){
    int ans=0,mi,x,y,d;
    for(int i=1;i<=n;i++){
        mi=lcm/b[i];
        exgcd(mi,b[i],x,y);
        x=(x%b[i]+b[i])%b[i];
        ans=((ans+ksm(mi,ksm(x,a[i])))%lcm+lcm)%lcm;
       // ans=(ans+(mi*x*b[i])%lcm+lcm%lcm)%lcm;
    }
    return (ans+lcm)%lcm;
}

signed main(){

//    freopen("road.in","r",stdin);
//    freopen("road.out","w",stdout);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        lcm*=b[i];
    }
    for(int i=1;i<=n;i++){
        a[i]=(a[i]%b[i]+b[i])%b[i];
    }
    cout<<crt();

    return 0;
}

C

题意

P2398加强版。

思路

此题与P2398只相差一点，即求和时求的是 \sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^2。

因为P2398中，我们钦定 \gcd=i，所以此题仅需将 i 更改为 i^2。

代码

void Pr(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(st[i]==0){
            cnt++;
            prime[cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
            st[prime[j]*i]=1;
            if(i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}

signed main(){
//   freopen("inq.in","r",stdin);
//   freopen("inq.out","w",stdout);

    cin>>n;

    Pr();
    for(int i=1;i<=n;i++){
        s[i]=(s[i-1]+phi[i])%mod;
        //cout<<s[i]<<' ';
    }
    //Endl
    int ans=0;
    for(int i=1;i<=n;i++){

        ans+=(2*s[n/i]-1)*i*i%mod;
    }
    cout<<ans%mod;
    return 0;
//    fclose(stdin);
//    fclose(stdout);
}

D

题意

P9007

E

题意

CF988D

思路

不难发现，选出的集合的大小不会大于3。

证：

当 x=1 时，答案显然。

当 x=2 时，答案显然。

当 x=3 时，设三个数分别为 x1，x2，x3。

设 x1-x2=2^{k1}，x2-x3=2^{k2}，则x1-x3=2^{k1}+2^{k2}。

显然，当 k1=k2 时，2^{k1}+2^{k2}=2^{k3}。

当 x=4 时，设四个数分别为 x1，x2，x3，x4。

设 x1-x2=2^{k1}，x2-x3=2^{k2}，x3-x4=2^{k3}。

根据上述结论不难发现，k1=k2=k3。

那么，x1-x4=3*2^{k1}，显然不是 2^k。

当 x>4 时，该集合定有一个子集长度为4。

根据上述结论，当x \le 3 时，集合可能符合要求。

可以分讨+二分。

具体见代码。

代码

signed main(){
//   freopen("inq.in","r",stdin);
//   freopen("inq.out","w",stdout);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=2;i<n;i++){//枚举第二个数
        for(int j=0;j<=30;j++){
            int l=lower_bound(a+1,a+i,a[i]-(1<<j))-a;//二分查找
            int r=lower_bound(a+i+1,a+1+n,a[i]+(1<<j))-a;
            if(a[l]+(1<<j)==a[i]&&a[i]+(1<<j)==a[r]){//如果查找出来的数符合要求
                cout<<3<<endl;
                cout<<a[l]<<' '<<a[i]<<' '<<a[r];
                return 0;
            }
        }
    }
    for(int i=2;i<=n;i++){//同上
        for(int j=0;j<=30;j++){
            int l=lower_bound(a+1,a+i,a[i]-(1<<j))-a;

            if(a[l]+(1<<j)==a[i]){
                cout<<2<<endl;
                cout<<a[l]<<' '<<a[i];
                return 0;
            }
        }
    }
    cout<<1<<endl<<a[1];
    return 0;
//    fclose(stdin);
//    fclose(stdout);
}

F

题意

用 n 张纸币（1,5,10,50）能组成多少种不同的面值和？

思路

纯诈骗。

先DFS出 n\le11 的情况，n>11 时，进行差分，不难发现差分均为49.

代码

signed main(){
//   freopen("inq.in","r",stdin);
//   freopen("inq.out","w",stdout);
    cin>>n;
    if(n<=11) cout<<mny[n];//自己算
    else  cout<<mny[11]+49*(n-11);
    return 0;
//    fclose(stdin);
//    fclose(stdout);
}

G

题意

AGC001C

思路

对 k 进行分讨。

当 k 为偶数，则枚举直径的中间点，以该点为起点查找其他点与该点距离 \le k/2 的点。

当 k 为奇数，则枚举直径的中间边，以该边的两个端点分别为起点查找其他点与该点距离 \le k/2 的点。

代码

void dfs(int x,int len,int fa){
    vis[x]=1;
    cnt++;
    if(len==0) return ;
    for(int i=0;i<ve[x].size();i++){
        int v=ve[x][i];
        if(v==fa) continue;
        if(vis[v]) continue;
        dfs(v,len-1,x);
    }
}
signed main(){
//   freopen("inq.in","r",stdin);
//   freopen("inq.out","w",stdout);

    int maxx=0;
    cin>>n>>len;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    if(len%2==0){
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            cnt=0;
            dfs(i,len/2,0);
            maxx=max(maxx,cnt);
        }
    }
    else{
        for(int i=1;i<=n;i++){
            for(int j=0;j<ve[i].size();j++){
                memset(vis,0,sizeof(vis));
                int v=ve[i][j];
                cnt=0;
                dfs(i,len/2,v);
                dfs(v,len/2,i);
                maxx=max(maxx,cnt);
            }
        }
    }
    cout<<maxx;
    return 0;
//    fclose(stdin);
//    fclose(stdout);
}