PAT (Basic Level) 1005 继续(3n+1)猜想
题意
作者：xavier_cai
（3n+1）猜想详见 link。给定一组数字，问最少需要多少个数，使得（这些数和他们使用上述猜想推导过程所包含的所有数字）这个集合，能囊括原数组。
思路对所有数字进行一次猜想，对推导过程中的数打上标记，若该数最后未被标记，证明只能被自己覆盖，则计入答案。模拟即可。
代码#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector a(n);
for (int& e : a)
cin >> e;
const int MAXN = 100005;
vector vis(MAXN, -1);
for (int e : a) {
int id = e;
while (id != 1) {
if (id & 1) id = 3 * id + 1;
id = id / 2;
vis[id] = e;
}
}
vector ans;
for (int e : a)
if (vis[e] == -1) ans.push_back(e);
sort(ans.begin(), ans.end(), greater());
for (int i = 0; i < ans.size(); ++i)
cout << ans[i] << (i == ans.size() - 1 ? '\n' : ' ');
return 0;
}
HINT
不定时更新更多题解，Basic Level 全部AC代码，详见 link ! ! !
作者：xavier_cai
