Loading...

Codeforces Round #538 (Div. 2)题解

check评论:0 条 remove_red_eye浏览量:583 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-02-11

$A$

很简单,按照题意模拟即可,靠前的两个人优先取即可

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,x,y,z;
    cin>>a>>b>>c>>x>>y>>z;
    if(a>x)
    {
        cout<<"NO";
        return 0;
    }
    x-=a;
    y+=x;
    if(b>y)
    {
        cout<<"NO";
        return 0;
    } 
    y-=b;
    z+=y;
    if(c>z)
    {
        cout<<"NO";
        return 0;
    }
    cout<<"YES";
}

$B$

看到数据范围,考虑贪心,既然每一块都取最大的$m$个,我们就将答案设置为最大的$k\times m$个之和,然后从头到尾扫一遍,如果一块中已经出现了$m$个要取的数,划开即可

#include <bits/stdc++.h>
using namespace std;
int n,k,m;
int a[200010],b[200010];
map<int,int> mp;
int main()
{
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    long long ans=0;
    for(int i=n,j=1;j<=(k*m);i--,j++)
    {
        mp[b[i]]++;
        ans+=b[i];
    }
    cout<<ans<<endl;
    for(int i=1,now=0,qaq=0;i<=n;i++)
    {
        if(mp[a[i]])
        {
            now++;
            mp[a[i]]--;
        }
        if(now>=k)
        {
            printf("%d ",i);
            qaq++;
            now=0;
        }
        if(qaq==m-1)
        {
            return 0;
        }
    }
}

$C$

在$k$进制下末尾为$0$代表了这个数包含了$k$的所有因子,将$k$质因数分解后,找出所以$n!$中$k$的质因数的个数除以$k$需要的个数的最小值即可(见代码)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,b;
inline ll mycalculate(ll a,ll b)
{
    ll num=0;
    for(ll i=a;i<=n;i*=a)
    {
         num+=n/i;
         if(n/i<a) 
         {
             break;
         }
     }
    return num/b;
} 
int main()
{
    cin>>n>>b;
    ll ans=1e18;
    for(ll i=2;i*i<=b;i++)
    {
        if(b%i==0)
        {
            ll a=0;
            while(b%i==0) 
            {
                b/=i,a++;
            }
            ans=min(ans,mycalculate(i,a));
        }
    } 
    if(b>1) 
    {
        ans=min(ans,mycalculate(b,1));
    }
    cout<<ans;
    return 0;
}

$D$

看到数据范围,考虑区间$dp$

两个区间合并的转移方程是$dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+1);$(两边不同)

但是这样是$O(n^3)$的,考虑优化

容易想到直接枚举长度,然后和左右合并即可

复杂度$O(n^2)$

#include <bits/stdc++.h>
using namespace std;
int dp[5005][5005],n,a[5005],tot,b[5005];
int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        if(a[i]==a[i-1]) 
        {
            continue;
        }
        else 
        {
            b[++tot]=a[i];
        }
    } 
    n=tot;
    for(int len=1;len<n;len++) 
    {
        for(int l=1;l+len<=n;l++) 
        {
            int r=l+len;
            if(b[l]==b[r]) 
            {
                dp[l][r]=dp[l+1][r-1]+1;
            }
            else 
            {
                dp[l][r]=min(dp[l+1][r]+1,dp[l][r-1]+1);
            }
        }
    }
    cout<<dp[1][n];
}

$E$

一道交互题,思路比较简单

先二分找出序列最大值,大概需要$30$次

剩下的$30$次随机询问某个位置,将$30$个数存入数组中,排序后,求出两两间差值的$gcd$即可得到公差

不能用$rand$,$windows$里$rand$最大为$32767$,要改成$rand()<<15|rand()%n$

#include <bits/stdc++.h>
using namespace std;
int now[37],cnt,p[4000010];
int gcd(int a,int b)
{
    return a==0?b:gcd(b%a,a);
}
int main()
{
    srand(19260817);
    int n;
    cin>>n;
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=(l+r)>>1;
        cout<<"> "<<mid<<endl;fflush(stdout);
        int x;
        cin>>x;
        if(x==0)
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    } 
    cout<<"> "<<l<<endl;fflush(stdout);
    int x;
    cin>>x;
    if(x==0)
    {
        l--;
    } 
    for(int i=1;i<=min(29,n);i++)
    {
        int x=(rand()<<15|rand())%n+1;
        while(p[x])
        {
            x=(rand()<<15|rand())%n+1;
        }
        p[x]=1;
        cout<<"? "<<x<<endl;fflush(stdout);
        int pwp;
        cin>>pwp;
        now[++cnt]=pwp;
    }
    sort(now+1,now+cnt+1);
    int d=now[2]-now[1];
    for(int i=3;i<=cnt;i++)
    {
        d=gcd(d,abs(now[i]-now[i-1]));
    }
    l=l-(n-1)*d;
    cout<<"! "<<l+1<<" "<<d<<endl;fflush(stdout);
}

$F$

考虑到数字都在$300$以内,即质因数最多$62$个,那么只需要线段树维护区间出现的质数即可,$\varphi (p)=p\times \prod\limits_{i=1}^k(1-\frac{1}{p_i})$

注意到内存开不下,用$long long$状压一下出现了的质数即可

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int mod=1e9+7;
#define mymaxn 400400
int fpow(int a,int b)
{
    int s=1;if(a==1)return 1;
    while(b)
    {
        if(b&1)
        {
            s=1ll*s*a%mod;
        }
        a=1ll*a*a%mod;
        b>>=1;
    }
    return s;
}
ll qaqaq[mymaxn];
bool vis[mymaxn];int prime[mymaxn],cnt;
int n,Q,a[mymaxn];
int t[mymaxn<<2];
ll qwqwqwqwqwq[mymaxn<<2];
int tagt[mymaxn<<2];
ll pwpwpw[mymaxn<<2];
void Build(int now,int l,int r)
{
    t[now]=1;
    qwqwqwqwqwq[now]=0;
    tagt[now]=1;
    if(l==r)
    {
        t[now]=a[l];
        qwqwqwqwqwq[now]=qaqaq[a[l]];
        return;
    }
    int mid=(l+r)>>1;
    Build((now<<1),l,mid);
    Build((now<<1|1),mid+1,r);
    t[now]=1ll*t[(now<<1)]*t[(now<<1|1)]%mod;
    qwqwqwqwqwq[now]=qwqwqwqwqwq[(now<<1)]|qwqwqwqwqwq[(now<<1|1)];
}
void modify(int now,int l,int r,int L,int R,int w,ll W)
{
    if(L==l&&r==R)
    {
        tagt[now]=1ll*tagt[now]*w%mod;pwpwpw[now]|=W;
        return;
    }
    int mid=(l+r)>>1;
    if(L>mid)
    {
        modify((now<<1|1),mid+1,r,L,R,w,W);
    }
    else if(R<=mid)
    {
        modify((now<<1),l,mid,L,R,w,W);
    }
    else 
    {
        modify((now<<1),l,mid,L,mid,w,W);
        modify((now<<1|1),mid+1,r,mid+1,R,w,W);
    }
    qwqwqwqwqwq[now]|=W;
    t[now]=1ll*t[now]*fpow(w,R-L+1)%mod;
}
int queryqwq(int now,int l,int r,int L,int R)
{
    if(L==l&&r==R)
    {
        return 1ll*t[now]*fpow(tagt[now],r-l+1)%mod;
    }
    int mid=(l+r)>>1;
    if(R<=mid)
    {
        return 1ll*queryqwq((now<<1),l,mid,L,R)*fpow(tagt[now],R-L+1)%mod;
    }
    if(L>mid)
    {
        return 1ll*queryqwq((now<<1|1),mid+1,r,L,R)*fpow(tagt[now],R-L+1)%mod;
    }
    return 1ll*queryqwq((now<<1),l,mid,L,mid)*queryqwq((now<<1|1),mid+1,r,mid+1,R)%mod*fpow(tagt[now],R-L+1)%mod;
}
ll queryqaq(int now,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        return qwqwqwqwqwq[now]|pwpwpw[now];
    }
    ll ret=pwpwpw[now];
    int mid=(l+r)>>1;
    if(L<=mid)
    {
        ret|=queryqaq((now<<1),l,mid,L,R);
    }
    if(R>mid)
    {
        ret|=queryqaq((now<<1|1),mid+1,r,L,R);
    }
    return ret;
}
int inv[500];
int main()
{
    cin>>n>>Q;
    for(int i=2;i<=300;++i)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            inv[cnt]=fpow(i,mod-2);
        }
        for(int j=i+i;j<=300;j+=i)
        {
            vis[j]=true;
        }
    }
    for(int i=2;i<=300;++i)
    {
        for(int j=1;j<=cnt;++j)
        {
            if(i%prime[j]==0)
            {
                qaqaq[i]|=1ll<<(j-1);
            }
        }
    }
        
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    Build(1,1,n);
    char ch[50];
    while(Q--)
    {
        scanf("%s",ch);
        int l,r;
        scanf("%d%d",&l,&r);
        if(ch[0]=='M')
        {
            int x;
            scanf("%d",&x);
            modify(1,1,n,l,r,x,qaqaq[x]);
        }
        else
        {
            ll S=queryqaq(1,1,n,l,r);
            int v=queryqwq(1,1,n,l,r);
            for(int i=0;i<cnt;++i)
            {
                if(S&(1ll<<i))
                {
                    v=1ll*v*inv[i+1]%mod*(prime[i+1]-1)%mod;
                }    
            }        
            printf("%d\n",v);
        }
    }
    return 0;
}

chevron_left (EX)bsgs 学习笔记
FWT (伪)学习笔记 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名