洛谷八月月赛Ⅱ总结

A.「EZEC-3」造房子

题目大意

给你 $a,b,c$ 三个数，满足 $a,b,c\leq 1e12$ ,求最大的 $x$ 满足 $f(x)=\sum_{i=1}^x<min(a,b)$ ,其中，$c$ 可以分配给 $a$ 和 $b$

题解

直接一个循环搞定，水题直接看代码

代码

signed main(void)
{
    for(register int i=1;i<=1000000;++i)sum[i]=sum[i-1]+i;
    cin>>a>>b>>c;
    ll ans=0;
    if(a>b)swap(a,b);
    if(c>b-a)
    {
        ans=b;
        c-=b-a;
        ans+=(c/2);
    }
    else ans=a+c;
    for(register int i=1;i<=1000000;++i)
        if(ans<sum[i])
        {
            cout<<i-1<<endl;
            break;
        }
    return 0;
}

B.「EZEC-3」排列

题目大意

给你一个数的集合，你需要选出若干个数排成一列，记为 $x_1,x_{2},\cdots,x_{p}$（ $p$ 为数的个数）。

这一列数合法当且仅当满足以下条件：

• $p \ge 2$。
• 令 $y_{i} = x_{i + 1} - x_{i}$（特别的，$y_{p}=x_{1}-x_{p}$），如果把 $y_{1}$ 到 $y_{p}$按 $y_1,y_2,\cdots,y_p$ 的顺序排成一圈，那么每两个相邻的数互为相反数且绝对值都为 $k$。$k$ 由输入给出。

求满足要求的 $x$ 数列的和的最大值
$$
k,n,x_i\le1e6
$$

题解

题目要求每相邻 $x_i-x_{i-1}=x_i-x_{i+1}$ 相等,即 $x_{i+1}=x_i-1$ ,显然的我们发现选出来的数列要么只含有一种不同的数（$k=0$），要么就只有两种，由于数据范围并不大，我们可以用一个桶来记录值为 $i$ ，的数的个数，从小到大枚举即可

代码

 signed main(void)
{
    n=read(),k=read();
    for(register int x,i=1;i<=n;++i)x=read(),cnt[x]+=read();
    ll ans=-1;
    if(!k)
    {
        for(register int i=0;i<=maxn-5;++i)
            if(cnt[i]>1)ans=max(cnt[i]*i,ans);
    }
    else
    {
        for(register int i=k;i<=maxn-5;++i)
            if(cnt[i]&&cnt[i-k])ans=max(min(cnt[i],cnt[i-k])*(2*i-k),ans);
    }
    if(ans==-1)printf("NO");
    else cout<<ans<<endl;
    return 0;
}

C.「SWTR-6」GCDs & LCMs

题目大意

[ 展开](javascript:void 0)

题目描述

给你一个长度为$n$ 的序列 $a_1,a_2,\cdots,a_n$。

你需要从这些数中选出一些数 $b_1,b_2,\cdots,b_k$ 满足：对于所有$ i\ (1\leq i\leq k$)，$b_i$ 要么是序列 $b$ 中的最大值，要么存在一个位置 $j$ 使得 $b_j>b_i$ 且$ b_i+b_j+\gcd(b_i,b_j)=\mathrm{lcm}(b_i,b_j)$。

求最大的$\sum_{i=1}^kb_i$，k为任意正整数
$$
1\le n\le3e5，1\le a_i\le1e9
$$

题解

对于题目给出的式子，我们考虑化简
$$
\begin{align}
&x+y+\gcd(x,y)=\mathrm{lcm}(x,y)\\
&t_1\cdot\gcd(x,y)+t_2\cdot\gcd(x,y)+\gcd(x,y)=\frac{xy}{\gcd(x,y)}\\
&t_1\cdot\gcd(x,y)^2+t_2\cdot\gcd(x,y)^2+\gcd(x,y)^2=t_1t_2\cdot\gcd(x,y)^2\\
&t_1+t_2+1=t_1t_2
\end{align}
$$
化简后，由于 $t_1,t_2$ ,是互质的，根据打表(玄学理解)可以得出满足条件的 $t_1,t_2$只有 $(2,3)$ 一组，我们考虑离散化后从小到大往上推过去，最后取最大值

代码

signed main(void)
{
    n=read();
    for(register int i=1;i<=n;++i)b[i]=a[i]=read();
    sort(b+1,b+1+n);
    ll m=unique(b+1,b+1+n)-b-1;
    for(register int i=1;i<=n;++i)
    {
        ll t=lower_bound(b+1,b+1+m,a[i])-b;
        f[t]+=a[i];
    }
    for(register int i=1;i<=m;++i)
    {
        ll x=b[i];
        if(!(x&1))
        {
            ll t=(x/2)*3;
            ll pt=lower_bound(b+1,b+1+m,t)-b;
            if(b[pt]==t)f[pt]+=f[i];
        }
    }
    ll ans=0;
    for(register int i=1;i<=m;++i)ans=max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}