T263、T264 关于set、priority_queue容器、动态规划、丑数

题目内容

• 丑数，就是只包含质因数 2、3 和/或 5 的正整数
• T263 判断是否为丑数，注意特判0。不赘述
• T264 输出第n个丑数

利用c++容器解T264

• “第n个”涉及排序和不重复
• priority_queue解决排序；unordered_set解决不重复

声明

unordered_set<long long> myset;
priority_queue<long long, vector<long long>, greater<long long> > pq;

容器的方法

• priority_queue套：push(), pop(), top(), empty()
• unordered_set套：add(), erase()
  • if(myset.find(x)!=myset.end()) 则x不在myset内

利用动态规划解T264

• \(dp[1]=1\)
• 定义三个指针 p2, p3, p5（px为使得dp[px] * x > dp[i-1]的最小值）。初始时，三个指针的值都是 1
• 当 2 ≤ i ≤ n 时，令 \(dp[i]=min\{dp[p2]*2,dp[p3]*3,dp[p5]*5\}\)，然后分别比较\(dp[i]\)和\(dp[p2]*2,dp[p3]*3,dp[p5]*5\)是否相等，如果相等则将对应的指针加1。