提交记录 12928


用户 题目 状态 得分 用时 内存 语言 代码长度
lrw04 noip18b. 【NOIP2018】货币系统 Accepted 100 17.106 ms 184 KB C++11 1.91 KB
提交时间 评测时间
2020-07-04 23:12:33 2020-08-01 03:01:34
#include <bits/stdc++.h>
using namespace std;

#define MAXN 120
#define MAXV 25050
int a[MAXN], n, ans, ri[MAXV];
bool e[MAXN], isc[MAXV], v[MAXV];

//void euclid(int a, int b, int& d, int& x, int& y) {
//	if (b) {
//		euclid(b, a % b, d, y, x);
//		y -= x * (a / b);
//	} else {
//		d = a; x = 1; y = 0;
//	}
//}

//// returns if equation mx + ny = l has nonnegative integer solution
//bool iscomposed(int m, int n, int l) {
//	int d, x, y;
//	euclid(m, n, d, x, y);
//	if (l % d) return false;
//	x *= l / d; y *= l / d;
////	cout << m << " * " << x << " + " << n << " * " << y << " = " << l << endl;
////	cout << -x * d / n << " <= k <= " << y * d / m << endl;
////	return x * m + y * n >= 0;
//	return y * d / m > -x * d / n;
//}

bool iscg(int val, int ind) {
//	cout << "(" << val << ", " << ind << ")" << endl;
	if (val < a[0]) return false;
	if (ri[val] != -1 && ri[val] < ind) return true;
	if (v[val]) return isc[val];
	v[val] = true;
	for (int i = 0; i < ind; i++)
		if (/*val - a[i] >= a[0] && */iscg(val - a[i], ind)) return isc[val] = true;
	return isc[val] = false;
}

int main() {
	int t; cin >> t;
	while (t--) {
		memset(e, -1, sizeof(e));
		memset(v, 0, sizeof(v));
		memset(ri, -1, sizeof(ri));
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		sort(a, a + n);	
		
		for (int i = 0; i < n; i++) {
			ri[a[i]] = i;
		}
			
		ans = n;
//		for (int i = 0; i < n; i++)
//			for (int j = 0; j < n; j++)
//				for (int k = 0; k < n; k++)
//					if (k != i && k != j && e[k] && e[i] && e[j] && iscomposed(a[i], a[j], a[k])) {
////						cout << a[i] << ", " << a[j] << " -> " << a[k] << endl;
//						e[k] = false;
//						ans--;
//					}

		v[a[0]] = true;
		isc[a[0]] = false;
		
		for (int i = 1; i < n; i++) {
			if (iscg(a[i], i)) //{
//				cout << "isc[" << a[i] << "] = " << 1 << endl;
				ans--;
//			} else
//				cout << "isc[" << a[i] << "] = " << isc[i] << endl;
		}
					
		cout << ans << endl;
	}
	
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1112.23 us164 KBAcceptedScore: 5

Testcase #2114.01 us168 KBAcceptedScore: 5

Testcase #3116.58 us164 KBAcceptedScore: 5

Testcase #4110.45 us168 KBAcceptedScore: 5

Testcase #5113.48 us172 KBAcceptedScore: 5

Testcase #6110.97 us168 KBAcceptedScore: 5

Testcase #7125.41 us176 KBAcceptedScore: 5

Testcase #8122.18 us164 KBAcceptedScore: 5

Testcase #9133.42 us176 KBAcceptedScore: 5

Testcase #10156.58 us168 KBAcceptedScore: 5

Testcase #11125.74 us164 KBAcceptedScore: 5

Testcase #12140.95 us164 KBAcceptedScore: 5

Testcase #13134.22 us164 KBAcceptedScore: 5

Testcase #14166.45 us164 KBAcceptedScore: 5

Testcase #15154.53 us164 KBAcceptedScore: 5

Testcase #16187.35 us164 KBAcceptedScore: 5

Testcase #1715.718 ms184 KBAcceptedScore: 5

Testcase #1817.106 ms184 KBAcceptedScore: 5

Testcase #1915.525 ms184 KBAcceptedScore: 5

Testcase #2013.342 ms184 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2020-08-05 16:01:49 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用