洛谷P1059解题报告

link

题目大意

给定 \(n\) 个整数 \(a_1,a_2,a_3,\cdots ,a_n\)，将 \(n\) 个整数去重，并且排序，输出操作后数组的大小，再输出这个数组。

数据范围

\(1\leq n \leq 100\)

\(1\leq a_1,a_2,a_3,\cdots ,a_n\leq1000\)

解题思路

这个数据范围，emm……，2006年的NOIP真是水。

解法1

使用STL大法中的 set ，它本身就具有排序和去重的功能，可以无伤A掉这道题。

Code:

#include <bits/stdc++.h>
using namespace std;
#define debug cerr<<"The code runs successfully.\n";
#define endl '\n'
#define TRACE 1
#define tcout TRACE && cout
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
const int P = 998244353; 
const int Base = 3221225477;
const int INF = 0x3f3f3f3f3f3f3f3f; 
const int N = 1e6 + 10, M = 2e6 + 10;
signed main()
{
	fst;
	int n;
	cin>>n;
	set<int> s;
	for(int i=0;i<n;i++)
	{
		int t;
		cin>>t;
		s.insert(t);
	}
	cout<<s.size()<<endl;
	for(auto e:s)
	{
		cout<<e<<' ';
	}
	return 0;
}

解法2

由于数据范围，可以暴力，用 map<int,bool> ，unordered_map<int,bool> 或者 bitset<1010> 来解决，存储每个数是否在数组里，遍历并统计个数，最后遍历输出。

Code:

#include <bits/stdc++.h>
using namespace std;
#define debug cerr<<"The code runs successfully.\n";
#define endl '\n'
#define TRACE 1
#define tcout TRACE && cout
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
const int P = 998244353; 
const int Base = 3221225477;
const int INF = 0x3f3f3f3f3f3f3f3f; 
const int N = 1e3 + 10, M = 2e6 + 10;
int n,tmp;
bitset<N> vis;//内存上的优势
//map<int,bool> vis;
//unordered_map<int,bool> vis;
signed main()
{
	fst;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>tmp;
		vis[tmp]=1;
	}
	int ans=0;
	for(int i=1;i<=1000;i++)
	{
		ans+=vis[i];
	}
	cout<<ans<<endl;
	for(int i=1;i<=1000;i++)
	{
		if(vis[i])
		{
			cout<<i<<' ';
		}
	}
	return 0;
}

done.