Educational Codeforces Round 36 (Rated for Div. 2) 题解

时间:2022-08-27 13:50:40

Educational Codeforces Round 36 (Rated for Div. 2)

题目的质量很不错(不看题解做不出来,笑

Codeforces 920C

题意

给定一个\(1\)\(n\)组成的数组,只可以交换某些相邻的位置,问是否可以将数组调整为升序的

解题思路

首先如果每个数都能通过交换到它应该到的位置,那么就可以调整为升序的。

但实际上交换是对称的,如果应该在的位置在当前位置前方的数都交换完成,那么整体就是排好序的,因为不可能所有不在相应位置的数都在相应位置的后方。

所以我们从\(1\)\(n\)扫一遍,在扫描的过程中维护当前位置能向前交换的位置的最小值,这样就可以判断了

AC代码

#include <bits/stdc++.h>
using namespace std;
int n,pos[300020],num[300020];
string str;
bool judge()
{
    int maxpre=1;
    for (int i=1;i<=n;i++)
    {
        if(i>=2)
            if(str[i-2]=='0')   maxpre=i;
        if(pos[i]>=i)   continue;
        if(maxpre>pos[i])   return false;
    }
    return true;
}
int main(int argc, char const *argv[])
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        pos[num[i]]=i;
    }
    cin>>str;
    if(judge())
        puts("YES");
    else
        puts("NO");
    return 0;
}

Codeforces 920E

题意

给定一个无向图,求补图的连通分量数和每个连通分量的大小

点数\(n \le 200000\) ,边数\(m \le 200000\)

(原题?:bzoj1098)

解题思路

虽然直接对补图用\(BFS\)求连通分量数复杂度是\(O(n)\)的,但光建图复杂度就要\(O(n^2)\)了,所以直接建补图肯定是不行的

这里用到一个神奇的方法,在对原图\(BFS\)最开始维护一个所有未分配在连通分量中的点的集合,当前点不能到达的点就是补图能到达的点,将补图能到达的点加入队列继续\(BFS\),对于已经判断在某个连通分量的点,需要在集合中删去。

这个集合可以直接使用std::set<int>,也可以使用链表,在这里我使用链表

这样只需要建原图就可以对补图进行\(BFS\)了,复杂度\(O(n+m)\)

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=200010;
vector <int> G[maxn];
int scc[maxn],scccnt;
int pre[maxn],nxt[maxn],vis[maxn],deled[maxn];
int n,m;
void del(int u)
{
    nxt[pre[u]]=nxt[u];
    pre[nxt[u]]=pre[u];
}
void bfs(int s)
{
    queue<int> Q;
    Q.push(s);
    del(s);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        if(vis[u])  continue;
        vis[u]=true;
        scc[scccnt]++;
        for (int v:G[u])
            deled[v]=true;
        for (int i=nxt[0];i<=n;i=nxt[i])
            if(!deled[i])
            {
                del(i);Q.push(i);
            }
        for (int v:G[u])
            deled[v]=false;
    }
    scccnt++;
}
int main(int argc, char const *argv[])
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n+1;i++)    pre[i]=i-1;
    for (int i=0;i<=n;i++)  nxt[i]=i+1;
    for (int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for (int i=nxt[0];i<=n;i=nxt[i])
        if(!vis[i])
            bfs(i);

    sort(scc,scc+scccnt);
    printf("%d\n",scccnt);
    for (int i=0;i<scccnt;i++)
        printf("%d ",scc[i]);
    puts("");
    return 0;
}

Codeforces 920F

题意

定义\(D(x)= Card\{k:k| x,k \in N^+\}\)

给定数组\(a\),做如下操作:

replace l r:将\(a_l\)\(a_r\)替换为\(D(a_i)\)

sum l r:输出\(a_l\)\(a_r\)的和

点数\(n \le 300000\),操作数\(m \le 300000\)\(a_i \le 1000000\)

解题思路

\(D(x)\)可以直接用筛法求出,复杂度\(O(MAXN \log MAXN)\)

首先显然要用线段树进行维护,但是直接套线段树对区间的每个点都单点更新显然是过不了的

注意到对\(D(x)\)迭代收敛很快,根据官方题解,在数据范围内迭代不超过\(6\)次就可以收敛到\(2\)\(1\)

我们可以用\(2\)棵线段树,一棵维护和,一棵维护最大值,当区间更新时对整个区间进行递归地更新,如果当前子树的最大值$ \le 2$, 那么可以直接返回,这样对于每个点最多不更新超过\(6\)

复杂度\(O(m \log n+MAN \log MAXN)\)

我看其他的题解说是套路题……难受

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxnum=1e6+6;
const int maxn=3e5+7;
int D[maxnum],a[maxn];
int n,m;
long long sumv[(maxn<<2)+5];
int maxv[(maxn<<2)+5];
void build(int now,int l,int r)
{
    if(l==r)
    {
        maxv[now]=sumv[now]=a[l];
        return;
    }
    int mid=l+((r-l)>>1);
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    sumv[now]=sumv[now<<1]+sumv[now<<1|1];
    maxv[now]=max(maxv[now<<1],maxv[now<<1|1]);
}
void update(int now,int l,int r,int ul,int ur)
{
    if(maxv[now]<=2)    return; //关键
    if(l==r)
    {
        maxv[now]=sumv[now]=D[sumv[now]];
        return;
    }
    int mid=l+((r-l)>>1);
    if(ul<=mid) update(now<<1,l,mid,ul,ur);
    if(ur>mid) update(now<<1|1,mid+1,r,ul,ur);
    sumv[now]=sumv[now<<1]+sumv[now<<1|1];
    maxv[now]=max(maxv[now<<1],maxv[now<<1|1]);
}
long long query_sum(int now,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)    return sumv[now];
    int mid=l+((r-l)>>1);
    long long ans=0;
    if(ql<=mid) ans+=query_sum(now<<1,l,mid,ql,qr);
    if(qr>mid)  ans+=query_sum(now<<1|1,mid+1,r,ql,qr);
    return ans;
}

void pre_solve()
{
    for (int i=1;i<=1e6;i++)
    {
        for (int j=i;j<=1e6;j+=i)
            D[j]++;
    }
}

int main(int argc, char const *argv[])
{
    pre_solve();
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int t,l,r;scanf("%d%d%d",&t,&l,&r);
        if(t==1)
            update(1,1,n,l,r);
        else
            printf("%I64d\n",query_sum(1,1,n,l,r));
    }
    return 0;
}

Codeforces 920G

题意

定义\(L(x,p)\)为数列\(\{ y > x, gcd(y,p)=1\}\)

输入\(x,p,k\),求数列\(L(x,p)\)的第\(k\)

输入数目\(t \le 30000\)\(x,p,k \le 1000000\)

解题思路

我们记\(A(x,p)= Card\ L(x,p)\),可以考虑求\(L\)的补集,用枚举\(p,y\)\(gcd\)含有的素因子利用容斥原理求解,由于 \(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17=510510\),所以数据范围内的数素因子个数不超过\(7\)个,子集不超过\(2^7\)

那么答案求的就是\(A(ans,p)=A(x,p)+k\),转化后我们可以利用二分法求解答案\(ans\)

复杂度\(O(t \log MAXANS)\)

经试验,答案的上界不超过\(1e10\)

AC代码

#include <bits/stdc++.h>
using namespace std;
vector <long long> factor;

long long solve(long long x)
{
    int num=factor.size();
    long long ans=0;
    for (int i=0;i<(1<<num);i++)
    {
        long long flag=1,gcdf=1;
        for (int j=0;j<num;j++)
        {
            if((i>>j)&1)
            {
                gcdf*=factor[j];
                flag*=-1;
            }
        }
        ans+=flag*(x/gcdf);
    }
    return ans;
}

long long p,x,k;
int main(int argc, char const *argv[])
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        factor.clear();
        scanf("%I64d%I64d%I64d",&x,&p,&k);
        for (int i=2;i*i<=p;i++)
        {
            if(p%i) continue;
            else
                factor.push_back(i);
            while(p%i==0)   p/=i;
        }
        if(p>1) factor.push_back(p);
        k+=solve(x);
        long long l=1,r=1e10,mid,ans;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(solve(mid)>=k)
            {
                ans=mid;
                r=mid-1;
            }           
            else l=mid+1;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}