Educational Codeforces Round 141 A-B题解

2023/1/9 C++ Codeforces 算法竞赛 题解

被B题橄榄了🥺,菜枯

A. Make it Beautiful

题面

一开始竟然没看到 😥.

令 .

如果a是ugly的，那么

即

只需要使数列保证降序即可.

但是最大的两项可能相等，这样就会出现排完序后 .

需要将 与后面一项小于 的项交换，易证这时满足题意.

如果后面找不到比 小的项，那么这时候整个数列每个元素都相等，那这个数列不可能变成beautiful.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55;
int a[N],sum[N];
bool cmp(int a,int b)
{
    return a>b;
}
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        sum[0]=0;
        bool flag=false;
        bool flag1=false;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
            if(sum[i]==2*sum[i-1])
                flag=true;
        }
        for(int i=2;i<=n;i++)
        {
            if(a[i]!=a[i-1])
                flag1=true;
        }
        if(!flag1)
            cout<<"NO"<<'\n';
        else
        {
            cout<<"YES"<<'\n';
            if(!flag)
            {
                for(int i=1;i<=n;i++)
                    cout<<a[i]<<' ';
                cout<<'\n';
            }
            else
            {
                sort(a+1,a+1+n,cmp);
                int j=2;
                while(a[j]==a[j-1])
                    j++;
                swap(a[j],a[2]);
                for(int i=1;i<=n;i++)
                    cout<<a[i]<<' ';
                cout<<'\n';
            }
        }
    }
    return 0;
}

B. Matrix of Differences

题面

直觉上相邻格子的数的差肯定是可以遍历 ，，， 的，毕竟差有 种，而相邻格子的差有 个，苹果数远大于抽屉数，很大概率是可以遍历 ，，， 的.

然后就是痛苦的构造了，我是这么构造的：

用两个指针，一个从1递增(记为p)，一个从n递减(记为q)；
奇数行从左向右构造，偶数行从右向左构造；
p和q交替出现.

如 时

下面证明这样的构造可以遍历所有差

将每一行的相邻两数差写出来，构成一个 的矩阵
第行

距离完全遍历还差
计算第一列的纵向相邻差，观察第 行和第 行的首位数的差
时，

时，

综上，这样构造可以使相邻方格的差遍历

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55;
int a[N][N];
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int u=1,v=n*n;
        int x=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i%2==1)
                {
                    if(x)
                        a[i][j]=u++;
                    else
                        a[i][j]=v--;
                }
                else
                {
                    if(x)
                        a[i][n+1-j]=u++;
                    else
                        a[i][n+1-j]=v--;
                }
                x^=1;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                cout<<a[i][j]<<' ';
            cout<<'\n';
        }
    }
    return 0;
}
img_show