https://www.luogu.org/problemnew/show/P2723

題解：

C++版本一

題解：STL+優化

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; struct node{int v;int i;bool operator < (const node &S)const{return v>S.v;} }; ll a[N]; priority_queue<node>heap; char str; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d%d",&k,&n);for(ll i=1;i<=k;i++){scanf("%lld",&a[i]);}heap.push({1,1});node humble;t=n;n++;while(n--){humble=heap.top();heap.pop();for(int i=humble.i;i<=k;i++){ll num=humble.v*a[i];if(num<=(1ll<<31)-1)heap.push({num,i});}}printf("%d\n",humble.v);//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

題解：貪心

#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;int i,j,n,m,k; long long a[150],s[100011],f[100011];int main(){cin>>k>>n;for(i=1;i<=k;i++) cin>>a[i];f[0]=1;for(i=1;i<=n;i++){m=2147483647;for(int j=1;j<=k;j++){while(a[j]*f[s[j]]<=f[i-1]) s[j]++;if(a[j]*f[s[j]]<m) m=a[j]*f[s[j]];}f[i]=m;}cout<<f[n]<<endl;return 0; }

C++版本三

題解：平衡樹

#include <iostream> #include <cstdio>using namespace std;const int S = 1 << 20; char frd[S], *hed = frd + S; const char *tal = hed;inline char nxtChar() {if (hed == tal)fread(frd, 1, S, stdin), hed = frd;return *hed++; }inline int get() {char ch; int res = 0;while (!isdigit(ch = nxtChar()));res = ch ^ 48;while (isdigit(ch = nxtChar()))res = res * 10 + ch - 48;return res; }typedef long long ll; const int N = 11e4 + 5; ll Int = 2147483647ll; int fa[N], lc[N], rc[N], sze[N], val[N]; int T, n, k, rt, top, stk[N], a[N];inline void Push(int x) {sze[x] = sze[lc[x]] + sze[rc[x]] + 1;}inline void Rotate(int x) {int y = fa[x], z = fa[y];int b = (lc[y] == x ? rc[x] : lc[x]);fa[y] = x; fa[x] = z;if (b) fa[b] = y;if (z) (lc[z] == y ? lc[z] : rc[z]) = x;if (lc[y] == x) rc[x] = y, lc[y] = b;else lc[x] = y, rc[y] = b;Push(y); }inline bool Which(int x) {return lc[fa[x]] == x;}inline void Splay(int x, int tar) {while (fa[x] != tar){if (fa[fa[x]] != tar)Which(fa[x]) == Which(x) ? Rotate(fa[x]) : Rotate(x);Rotate(x); }Push(x);if (!tar) rt = x; }inline void Insert(int vi) {int x = rt, y = 0, dir;while (x){y = x;if (val[x] == vi) return ;if (val[x] > vi) x = lc[x], dir = 0;else x = rc[x], dir = 1; }int w = y; if (y) ++sze[y];while (fa[w]) ++sze[w = fa[w]];x = top ? stk[top--] : ++T;fa[x] = y; val[x] = vi; sze[x] = 1;if (y) (dir ? rc[y] : lc[y]) = x; Splay(x, 0); }inline void Join(int x, int y) {int w = y;while (lc[w]) w = lc[w];lc[fa[x] = w] = x; fa[rt = y] = 0;Splay(w, 0); }inline void Delete(int x) {Splay(x, 0);stk[++top] = x;int L = lc[x], R = rc[x];lc[x] = rc[x] = 0;if (!L || !R) fa[rt = L + R] = 0;else Join(L, R); }inline int GetKth(int k) {int x = rt;while (x){if (k <= sze[lc[x]])x = lc[x];else {k -= sze[lc[x]] + 1;if (!k) return x;x = rc[x];}}return 0; }inline void Print(int x) {if (!x) return ;Print(lc[x]); Print(rc[x]); stk[++top] = x; fa[x] = lc[x] = rc[x] = 0; }inline int FindMin() {int x = rt; while (lc[x]) x = lc[x]; return x;}int main() {k = get(); n = get(); int x, cnt = 0; ll y;for (int i = 1; i <= k; ++i) Insert(a[i] = get());while (++cnt <= n){y = val[x = FindMin()]; Delete(x);for (int i = 1; i <= k; ++i) if (y * a[i] < Int) Insert(y * a[i]);else break;if (sze[rt] + cnt >= n) {Int = val[x = GetKth(n - cnt)]; Splay(x, 0); Print(rc[x]); rc[x] = 0; Push(x);}}cout << y << endl; }

?

總結

以上是生活随笔為你收集整理的丑数 Humble Numbers的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。