CF1692F 题解

__vector__ · 2022-06-16 15:10:49 · 题解

题目翻译

给你一个 n 个元素的数列 a。
问是否可以选择 3 个不同的下标 i,j,k，使得 a_i+a_j + a_k 的个位是 3。

解法

换一种思路，可以枚举所有的数字组合，对于每一种组合判断是否在 a 数组中出现过。
虽然运算次数达到了 10^{27}，但是可以进行优化。
可以发现最终答案的个位只和 a_i,a_j,a_k 的个位有关。
也就是说只需要枚举所有的个位组合，然后判断这样的组合在数列 a 的有没有出现就行了。
直接看代码应该更清楚

代码：

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=2e5+5;
    int t,n;
    int im[10];//一个桶，im[i] 代表有 im[i] 个元素的个位等于 i
    int a[maxn];
    void main()
    {
        scanf("%d",&t);
        while(t--)
        {
            memset(im,0,sizeof(im));
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                im[a[i]%10]++;//a[i]的个位出现次数++
            }
            bool flag=0;
            for(int i=0;i<=9;i++)
            {
                if(!im[i])continue;
                for(int j=0;j<=9;j++)
                {
                    if(i==j)
                    {
                        if(im[j]<2)continue;
                    }
                    else
                    {
                        if(!im[j])continue;
                    }//a 中没出现过，跳过该组合
                    for(int k=0;k<=9;k++)
                    {
                        if(i==j&&j==k)
                        {
                            if(im[k]<3)continue;
                        }
                        if(i==k||j==k)
                        {
                            if(im[k]<2)continue;
                        }
                        else
                        {
                            if(!im[k])continue;
                        }//a 中没出现过，跳过该组合
                        if((i+j+k)%10==3)
                        {//该组合是否合法
                            printf("Yes\n");
                            flag=1;
                            break;
                        }
                    }
                    if(flag)break;
                }
                if(flag)break;
            }
            if(!flag)
            {
                printf("No\n");
            }
        }
    }
}
int main()
{
    Main::main();   
    return 0;
}