3536 - 小软要变大软
阮麦琪(Maggie·Ruan)是普崔希德教授制造的一只萌萌的软泥怪。她爬呀爬呀爬，渴望爬出这座寒冷的城堡去外面玩。在旅行的路上她会碰到许多和她一样被制造的软泥怪。普崔希德教授赋予了麦琪特殊的能力。她可以吸收一个和她体型大小相同的软泥怪，在吸收之后，她的体型会翻倍。并且一旦遇到体型与她相同的其他软泥怪，她一定会吸收他们。
众所周知，前方路漫漫，在她游历的路上有许许多多的软泥怪。
现在，你，对阮麦琪的初始体积一无所知，但你已经知道她会依次遇到哪些软泥怪以及他们的体积，并且你非常清楚她一旦遇到与她体型相同的其他软泥怪，她一定会吸收他们，并且翻倍自己的体积。
假定正整数集合S表示麦琪最终可能的体型，请计算有多少正整数是不属于S的。
<br />
Input
多组输入数据
每组数据第一行为一个整数n(1<=n<=300)
第二行为n个整数，表示麦琪依次遇到的n个软泥怪的体型大小，其中每个整数都属于[1,1000000000]
<br />
Output
返回麦琪最终不可能达到的正整数体型个数。
Examples
Input
3 3 2 1 10 2 2 2 2 2 2 4 2 2 2
Output
2 2
Solution C++
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <sstream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <numeric> #include <cassert> #include <complex> #include <ctime> #define clr(x,a) memset(x,a,sizeof(x)) #define sz(x) (int)x.size() #define rep(i,n) for(int i=0;i<n;i++) #define repeat(i, a, b) for(int i=(a);i<=(b);i++) #define all(v) (v).begin(), (v).end() #define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin()) #define X first #define Y second using namespace std; const int N=1000+10; set<int>s; void work(int k,vector<int>x) { for (int i=0; i<x.size(); i++) { if (x[i]==k) k*=2; } s.erase(k); } int get(vector <int> x) { s.clear(); for (int i=0; i<x.size(); i++) s.insert(x[i]); for (int i=0; i<x.size(); i++) work(x[i],x); return (int)s.size(); } int main () { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //srand(time(NULL)); int n; while (scanf("%d",&n)!=EOF) { vector<int>v; for (int i=0;i<n;i++) { int k; scanf("%d",&k); v.push_back(k); } printf("%d\n",get(v)); } return 0; }