珠心算测验¹

题目信息

见链接

解题思路

首先，我要说一句：

STL大法好啊

既然题目说要去重，那不就是用个set吗？

创建一个查找用的set和一个去重的set。

由于这道题$n\le 100$，而STL的set插入与查找的时间复杂度均为$O(\log n)$，所以可以用$(n^2)$的暴力枚举来做。

所以这道题的时间复杂度是$O(n^2\log n)$。

$C++$代码如下。

#include <bits/stdc++.h> using namespace std; typedef set<int>::iterator setIt;//定义set<int>的迭代器别名 set <int> setFind;//查找用的set set <int> setUniq;//去重用的set int n, a[105]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", a + i);//等价于scanf("%d", &a[i]); setFind.insert(a[i]);//存入集合 } //----暴力枚举----// for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++){ int tmp = a[i] + a[j]; setIt iter = setFind.find(tmp); if (it != setFind.end()) {//存在 setUniq.insert(*it); delete it; } } cout << setUniq.size(); return 0; }

是的，set就是这么恶心好用！

---

2014年NOIP普及组第1题 ↩︎