F. 3SUM

原创于 2023-08-27 16:45:11 发布 · 粉丝可见 · 132 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132524970

题目：

样例：

`cobol<br/>6<br/>4<br/>20 22 19 84<br/>4<br/>1 11 1 2022<br/>4<br/>1100 1100 1100 1111<br/>5<br/>12 34 56 78 90<br/>4<br/>1 9 8 4<br/>6<br/>16 38 94 25 18 99<br/>`

YES YES NO NO YES YES

解题思路：

这道题很好玩，找出任意三个元素，相加有没有结果个位数为 3 的三个元素

这里我们三重循环个位数 0~9相加即可，输入的时候统计每个元素的相应的个位数，该个位数共有多少个，然后暴力枚举一遍可以了

代码详解如下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

int n, sum;
umap<int, int>r;	// 用于记录我们数组元素中个位数出现的次数

inline void solve()
{
	//清空之前的记录
	r.clear();

	cin >> n;
	for (int i = 0, x; i < n; ++i)
	{
		cin >> x;

		// 由于结果只要个位数是 3，所以只有个位数有关系
		// 取出个位数
		x %= 10;

		// 记录好该数值有多少个
		r[x]++;

		// 这里来个小优化，记录所有个位数的总和
		sum += x;
	}

	// 如果所有个数都不可能超过 3 说明是 NO
	if (sum < 3)
	{
		NO;
		return ;
	}

	sum = 0;	// 初始化所有总和


	// 暴力枚举所有可能的个位数
	for (int i = 0; i < 10; ++i)
	{
		for (int j = i; j < 10; ++j)
		{
			for (int k = j; k < 10; ++k)
			{
				r[i]--, r[j]--, r[k]--;	// 取出我们枚举的数值
				if ((i + j + k) % 10 == 3 && r[i] >= 0 && r[j] >= 0 && r[k] >= 0)
				{
					YES;
					return ;
				}

				// 由于不符合，所以放回去，恢复我们取出来
				r[i]++, r[j]++, r[k]++;
			}
		}
	}
	NO;
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}