Codeforces Educational Round 83 题解

· · 个人记录

也许更好的阅读体验

CF1312A Two Regular Polygons

这题是道数学题没错，不过是道特别简单的数学题。

很明显只要 n\ mod\ m=0 答案就是 YES，否则就是 NO 。

代码如下：

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, m;
        cin >> n >> m;
        if(n % m == 0)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

这道题好像真的没有什么可说的……

时间复杂度 O(1)

CF1312B Bogosort

这道题和CF1305A Kuroni and the gifts有相似之处。

为了让任何一组 i,j(i<j) 满足 i-a_i \neq j-a_j （这里利用不等式的对称性把原题目中的条件稍作调整），我们只要倒着排序就可以了。

这样的话 i 递增， a_i 递减，一定能满足题目条件。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int a[105];
bool cmp(int x, int y)
{
    return x > y;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1, cmp);
        for(int i = 1; i <= n; i++)
            cout << a[i] << ' ';
        cout << endl; 
    }
    return 0;
}

完事！

时间复杂度 O(nlogn)

CF1312C Adding Powers

这题还是有点数学题的味道。

我们要把一个数拆成若干个 k 的自然数次幂。(k^a+k^b+k^c+\dots) ，于是不难想到转进制。

我们把 a_i 转换成 k 进制，只要有任何一位大于1，答案就是NO。

其次，因为我们每一步最多只能操作一个数，所以一旦某一个 a_i 中的某一位是1，其它所有的 a_j 的相同位上就不能是1，否则答案就是NO。

剩下的情况答案就是YES了。

代码如下：

#include<iostream>
#include<cstring>
using namespace std;
long long a[35];
int trans[35][105], cnt[35];
int n, k;

void divide(int i, long long x, int m)
{
    if(x == 0)
        return;
    trans[i][++cnt[i]] = x % m;
    divide(i, x / m, m);
    return;
}

bool judge()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= cnt[i]; j++)
            if(trans[i][j] == 1)
                for(int k = 1; k <= n; k++)
                    if(k != i && trans[k][j] == 1)
                        return false;
    return true;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(trans, 0, sizeof(trans));
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
            cnt[i] = 0;
            divide(i, a[i], k);
        }
        bool flag = true;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= cnt[i]; j++)
                if(trans[i][j] > 1)
                {
                    flag = false;
                    break;
                }
        if(!flag)
        {
            cout << "NO" << endl;
            continue;
        }
        flag = judge();
        if(!flag)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}

因为数据范围比较小，所以不用担心TLE。

特别说明

由于本人本次时间有限，题解只写到C。