FDU 2020 | 2.斗牛

1. 题目描述

给定五个 0 ~ 9 范围内的整数 a1, a2, a3, a4, a5。如果能从五个整数中选出三个并且这三个整数的和为10 的倍数（包括 0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对 10 取余的结果，显然如果有多个三元组满⾜和是 10 的倍数，剩下两个数之和对 10 取余的结果都是相同的；如果选不出这样三个整数，则这五个整数的权值为 -1。现在给定 T 组数据，每组数据包含五个 0~9 范围内的整数，分别求这 T 组数据中五个整数的权值。

输入描述

第一行一个整数 T (1<=T<=1000)，表示数据组数。 接下来T行，
每行5 个 0~9 的整数，表示一组数据。

输出描述

第二行输入n个整数

输入样例

4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8

输出样例

2
-1
-1
0

2. 我的尝试

对于每组数据，记五数之和对10取模的结果为mod，只需穷举该组数据中所有的二元组，若存在某个二元组两数之和对10取模后的结果等于mod，则该组数据权重即为mod。若没有任意一个二元组匹配成功，则权重为-1。

每组数据只需穷举 $C_5^2=10$ 次，总的时间复杂度为线性的。

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	int a[5];
	bool flag = false;
	int mod;
	
	cin >> n;
	for (int i = 0; i < n; i ++){
	    flag = false;
	    mod = 0;
	    
	    for (int j = 0; j < 5; j ++){
	        scanf("%d", &a[j]);
	        mod = (mod + a[j]) % 10;
	    }
	        
	    for (int j = 0; j < 5; j ++)
	        for (int k = 0; k < j; k ++)
	            if ((a[j] + a[k]) % 10 == mod) \
	                flag = true;
	   
	   if (flag) printf("%d\n", mod);
	   else printf("-1\n");
	}
	    
	return 0;
}