Hướng dẫn giải của Thứ tự dãy con
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <vector> using namespace std; long long c[66][66],s; int a[66],n,k,b[66]; void decode(long long s) { int l=1,d[66]; for (int i=k-1;i>=0;i--) { for (int j=l;j+i<=n;j++) d[j]=0; while (1) { int r=-1,mn=1000111; for (int j=l;j+i<=n;j++) if (!d[j] && a[j]<mn) mn=a[j], r=j; d[r]=1; if (s<=c[n-r][i]) { cout << a[r] << " "; l=r+1; break; } else s-=c[n-r][i]; } } puts(""); } void encode(int b[]) { long long ans=0; int l=1; for (int i=k-1;i>=0;i--) { for (int j=l;j<=n;j++) if (a[j]<b[i]) ans+=c[n-j][i]; while (a[l]!=b[i]) l++; l++; } cout << ans+1 << endl; } int main() { for (int i=0;i<=60;i++) for (int j=0;j<=i;j++) c[i][j]=(j?c[i-1][j]+c[i-1][j-1]:1); cin >> n >> k; for (int i=1;i<=n;i++) cin >> a[i]; cin >> s; decode(s); for (int i=k-1;i>=0;i--) cin >> b[i]; encode(b); }
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> const int N = 66; using namespace std; int a[N], sub[N], val[N]; bool was[N]; long long f[N][N]; int n, k; long long m; void DP_PreProcess() { int i, j, t; ii b[N]; for(i=1; i<=n; i++) b[i] = ii(a[i], i); sort(b+1, b+1+n); for(i=1; i<=n; i++) val[i] = a[i]; for(i=1; i<=n; i++) { for(j=1; j<=k; j++) if (sub[j] == a[b[i].second]) sub[j] = i; a[b[i].second] = i; } for(i=1; i<=n; i++) f[1][i] = 1; for(i=2; i<=k; i++) for(j=1; j<=n; j++) for(t=n; t>j; t--) f[i][a[j]] += f[i-1][a[t]]; } void AnsNumber() { int i, j; long long ord = 0; for(i=1; i<=n; i++) was[i] = false; for(i=1; i<=k; i++) { for(j=1; j < sub[i]; j++) if (!was[j]) ord += f[k - i + 1][j]; for(j=1; j<=n; j++) if (a[j] != sub[i]) was[a[j]] = true; else {was[a[j]] = true; break;} } cout << ord + 1 << endl; } void AnsSeq() { int i, j, t; int ans[N]; long long v; for(i=1; i<=n; i++) was[i] = false; for(i=1; i<=k; i++) { for(j=n; j>0; j--) { v = 0; for(t=1; t<j; t++) if (!was[t]) v += f[k-i+1][t]; if (v < m) { ans[i] = j; m -= v; break; } } for(j=1; j<=n; j++) if (a[j] != ans[i]) was[a[j]] = true; else {was[a[j]] = true; break;} } for(i=1; i<=k; i++) { for(j=1; j<=n; j++) if (a[j] == ans[i]) { cout << val[j] << " "; break; } } printf("\n"); } int main() { scanf("%d %d", &n, &k); int i, j; for(i=1; i<=n; i++) scanf("%d", &a[i]); scanf("%lld", &m); for(i=1; i<=k; i++) scanf("%d", &sub[i]); DP_PreProcess(); AnsSeq(); AnsNumber(); return 0; }
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); int n, k, a[66], c[66]; long long f[66][66][66]; vector<int> need, cur; vector<int> get(long long m) { int i = 1; vector<int> res; res.clear(); FORD(p,k,1) { FOR(cur,1,n) if (f[i][p][cur] >= m) { res.PB(c[cur]); while (a[i] != cur) ++i; ++i; break; } else m -= f[i][p][cur]; } return res; } int main() { scanf("%d%d", &n, &k); FOR(i,1,n) { scanf("%d", &a[i]); c[i] = a[i]; } sort(c+1, c+n+1); FOR(i,1,n) a[i] = lower_bound(c+1, c+n+1, a[i]) - c; memset(f, 0, sizeof f); f[n+1][0][1] = 1; FORD(i,n,1) FOR(len,0,n-i+1) FOR(start,1,n) { if (len == 0) { if (start == 1) f[i][len][start] = 1; else f[i][len][start] = 0; } else { // Don't use i f[i][len][start] += f[i+1][len][start]; if (start == a[i]) FOR(next,1,n) f[i][len][start] += f[i+1][len-1][next]; } } long long m; cin >> m; cur = get(m); REP(i,cur.size()) cout << cur[i] << ' '; cout << endl; REP(i,k) { int u; cin >> u; need.PB(u); } long long l = 1, r = 0; FOR(start,1,60) r += f[1][k][start]; long long res = r; while (l <= r) { long long mid = (l + r) >> 1; cur = get(mid); if (cur >= need) { res = mid; r = mid - 1; } else l = mid + 1; } cout << res << endl; return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> //#include<conio.h> #define ep 0.000000001 #define maxn 10011 #define oo 1111111111 #define modunlo 111539786 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) double const PI=4*atan(1); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; int n,k,a[66],b[66]; vector<int> kq,V; long long m,C[66][66]; void tim(int vitri,long long tinh,int sochuso){ if(sochuso == 0) return; V.clear(); for(int i = vitri;i<=n;i++) V.push_back(a[i]); sort(V.begin(),V.end()); for(int i = 0;i<V.size();i++){ for(int j = vitri;j<=n;j++) if(a[j]==V[i] && n-j+1>=sochuso){ if(tinh<=C[sochuso-1][n-j]){ kq.push_back(V[i]); tim(j+1,tinh,sochuso-1); return; } else{ tinh -= C[sochuso-1][n-j]; } break; } } } long long tinh(int vitri,int thutu){ if(thutu == k+1) return 1; long long res = 0; V.clear(); for(int i = vitri;i<=n;i++) V.push_back(a[i]); sort(V.begin(),V.end()); for(int i = 0;i<V.size();i++){ for(int j = vitri;j<=n;j++){ if(a[j]==V[i] && n-j>=k-thutu){ if(a[j]==b[thutu]){ return res+tinh(j+1,thutu+1); } else{ res+=C[k-thutu][n-j]; break; } } } } } int main(){ // freopen("input.in","r",stdin); // freopen("output.out","w",stdout); cin>>n>>k; for(int i = 1;i<=n;i++) cin>>a[i]; cin>>m; for(int i = 1;i<=k;i++) cin>>b[i]; memset(C,0,sizeof(C)); for(int i = 0;i<=60;i++) C[0][i] = 1; for(int i = 1;i<=60;i++) for(int j = 1;j<=i;j++) C[j][i] = C[j][i-1]+C[j-1][i-1]; tim(1,m,k); for(int i = 0;i<k;i++) printf("%d ",kq[i]); //long long KQ = tinh(1,1); cout<<endl<<tinh(1,1); }
Bình luận