Codeforces Round #845 (Div. 2) and ByteRace 2023 A-D

A. Everybody Likes Good Arrays!

题意：对给定数组进行操作：删除相邻两项，替换为两项的乘积，使得该数组奇偶相间。　

题解：从前向后遍历模拟

代码：

void solve(){

    int n=read(),ans=0;

    for(int i=1;i<=n;i++)    a[i]=read()%2;

    for(int i=1;i<n;i++){

        if(a[i]&&a[i+1])   ans++;

        else  if(!a[i]&&!a[i+1]) ans++;

    }

    cout<<ans<<endl;

}

B. Emordnilap

题意：对n个数的每个全排列拼接上其逆序排列后的逆序对总数

题解：找规律对于n个数有如下性质：

　　　　1.有n!个排列

　　　　2.每个排列拼接上自己的逆序后有n*(n-1)个逆序对

　　　　由此：逆序对总和即为n!*n*(n-1)个

代码：

void solve(){

    int n=read(),ans=1;

    for(int i=1;i<=n;i++){

        ans*=i;

        ans%=mod;

    }

    ans*=n;

    ans%=mod;

    ans*=(n-1);

    ans%=mod;

}

C. Quiz Master

题意：在给定的数组中选择其中几个使1~m的每个数是至少是一个选择的数字的因子若选不出这样的几个数则输出-1 否则输出选择的最大数与最小值的差

题解：朴素的双指针思想在对给定数组排序后指向最大数与最小数的指针(分别记为R,L)有如下性质：

　　　　　　1.取上两个指针间所有数对最后答案无影响

　　　　　　2.对于目前不能构成选择区间的L,R指针，若L指针不动，只有R指针向后移动才可能重新构成满足题意的区间

　　　　所以采用双指针算法 R向后移动时记录新R的因子 L向后移动时去掉原L的因子以此维护双指针区间

代码：

int a[N],cnt[N],n,m;

bool check(){

    for(int i=1;i<=m;i++){

        if(cnt[i]<=0) return false;

    }

    return true;

}

void solve(){

    n=read(),m=read();

    for(int i=1;i<=n;i++) a[i]=read();

    for(int i=1;i<=m;i++) cnt[i]=0;

    sort(a+1,a+n+1);

    int ans=inf;

    for (int i = 1, j = 1; i <=n; i ++ ){

        for(int h=1;h*h<=a[i];h++){

            if(a[i]%h==0){

                cnt[h]++;

                cnt[a[i]/h]++;

            }

        }

        while (j <= i && check()){

            ans=min(ans,a[i]-a[j]);

            j++;

            for(int h=1;h*h<=a[j-1];h++){

                if(a[j-1]%h==0){

                    cnt[h]--;

                    cnt[a[j-1]/h]--;

                }

            }

        }

    }

    if(ans<inf)cout<<ans<<endl;

    else cout<<-1<<endl;

}

D. Score of a Tree

题意：现有一棵根为1的树，其中初始点权是0或1。每一秒，一个点的点权变为其所有子节点的值的异或值。求在所有时间下，所有01配置的树节点的总值。

题解：对每一结点，有如下性质：

　　　　1.每个初始时刻值的期望为1/2　　　　

　　　　2.每个节点都存在一个时间点 tx ，在 tx 后该节点值始终为0。且 tx 等于该节点的子树最大深度　　　　

　　　　3.每个节点在tx之前，其值的期望仍为1/2　　（对于性质3，可采用数学归纳法证明这一点）　　　

　　　所以对于整颗树，要求的值即为每个节点的最大子树深度*2^(n-1).

巴特西

Codeforces Round #845 (Div. 2) and ByteRace 2023 A-D

Codeforces Round #845 (Div. 2) and ByteRace 2023 A-D

最新文章

热门文章