Codeforces Round #811 (Div. 3) E. Add Modulo 10

最新推荐文章于 2025-06-04 14:43:36 发布

309摸鱼巨人

最新推荐文章于 2025-06-04 14:43:36 发布

阅读量249

点赞数

文章标签： c++ 算法图论

本文链接：https://blog.csdn.net/MagicFromMe/article/details/126168384

版权

博客探讨了Codeforces Round #811 (Div. 3) E. Add Modulo 10问题的解决策略。通过分析个位数变化的规律，作者指出可以将数组中的奇数转化为偶数，使得个位数按2 4 8 6的顺序循环。特别地，个位为6的情况需要单独处理，因为它不影响其他位的奇偶性。最后，作者提出解决方案应针对个位数为0、2 4 8或6的三类情况。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

E. Add Modulo 10
题意
给你n个数，你现在可以执行一个操作，假如对a[i]执行操作：a[i] = a[i] + (a[i] % 10)，问你能不能够最后让所有的数都相等。
思路
首先我们来看两个图
在这里插入图片描述

上面这个图我是模拟只是个位累加的结果，我们可以发现除了第五行，其他的都会有一个规律，那就是每一次个位最后都会呈现2 4 8 6 的顺序展现，无论个位是奇还是偶，所以呢，在最开始的时候，我们可以通过一次操作将奇数变成偶数，这个时候数组里面的所有的数全都成为偶数，后面个位也只会出现2 4 8 6。
现在来看第二幅图，我们可以发现，对于个位是6的这些数字，无论怎么累计，只要个位出现了6，它的除去各位以外的位置，它的奇偶性是不改变的，就比如第二行，2 4 8 16……这一行，我们观察个位为6嗦出现的位置，36 56 76 96这些数字，它的是为都是奇数，而出现2 4 8 6的这些位置它们的十位都是偶数，那么我们会发现，个位为6是个特例，它累加后的结果与其他数字累加的结果的奇偶会不相同，那么个位为6的我们要单独考虑：
综上，我们一共分为了三类，第一类是个位为0，第二类是个位为2 4 8的，第三类是个位为6的，所以，要想最终得到一样的结果，给的数组里的数字只能满足上面三类中的一类结果

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 2e5 + 10;

int n;

void solve()
{
    cin >> n;

    int flag = 1;
    set<int> s;
    int cnt[2] = {0};

    for (int i = 1; i <= n; i ++)
    {
        int x; cin >> x;
        while (x & 1) x = x + x % 10;
        int t1 = x % 10, t2 = x / 10;

        if (t1 == 0) s.insert(x);
        else if (t1 == 6) cnt[t2 & 1] ++;
        else cnt[!(t2 & 1)] ++;
    }

    if (s.size())
    {
        if (s.size() == 1 && cnt[0] + cnt[1] == 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    else
    {
        if (cnt[0] == n || cnt[1] == n) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);

    int t; cin >> t;
    while (t --) solve();

    return 0;
}