6 条题解
-
0
#include<bits/stdc++.h> using namespace std; int read() { char s; int k=0,base=1; while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9')); if(s==EOF)exit(0); if(s=='-')base=-1,s=getchar(); while(s>='0'&&s<='9') { k=k*10+(s-'0'); s=getchar(); } return k*base; } void write(int x) { if(x<0) { putchar('-'); write(-x); } else { if(x/10)write(x/10); putchar(x%10+'0'); } } int n,A,B; struct node { int x,y; } a[1010]; bool cmp(node aa,node bb) { if (aa.x*aa.y==bb.x*bb.y) return aa.y<bb.y; return (aa.x*aa.y)<(bb.x*bb.y); } int sum[1010]; int ans[1010],ls; int p[1010],lp; int m;//sum长度 int P; bool Max()//比大小,ans>p: true { int i=1; while (p[i]==0&&i<=lp) i++;//去掉前面的0 int j=1; while (ans[j]==0&&j<=ls) j++; if (lp-i+1>ls-j+1) return false;//p的位数>ans的位数 if (lp-i+1<ls-j+1) return true; while (i<=lp&&j<=ls)//一位一位的比较 { if (p[i]<ans[j]) return true; if (p[i]>ans[j]) return false; i++; j++; } return false; } void cheng(int d) { for (int i=1;i<=m;i++) sum[i]*=a[d].x;//高精度乘法 for (int i=1;i<=m;i++)//进位 { sum[i+1]+=sum[i]/10000; sum[i]%=10000; } if (sum[m+1]!=0) m++; } void div(int d) { memset(ans,0,sizeof(ans)); ls=1; while (m>0&&sum[m]==0) m--;//去掉前导0 P=0; int flag=0; for (int i=m;i>=1;i--)//高精度除法(模拟竖式) { P=P*10000+sum[i]; ans[++ls]=P/a[d].y; if (ans[ls]==0&&!flag) ls--; else flag=1; P%=a[d].y; } } int main() { n=read(); A=read(); B=read(); for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(); sort(a+1,a+n+1,cmp); m=1; sum[1]=A; for (int i=1;i<=n;i++) { div(i); if (Max()) { lp=ls; memcpy(p,ans,sizeof(ans)); } cheng(i); } int i=0; while (i<=lp&&p[i]==0) i++; printf("%d",p[i]);i++; for (;i<=lp;i++)//输出 { if (0<=p[i]&&p[i]<=9) printf("000%d",p[i]);else if (10<=p[i]&&p[i]<=99) printf("00%d",p[i]);else if (100<=p[i]&&p[i]<=999) printf("0%d",p[i]);else printf("%d",p[i]); } return 0; } -
0
#include #include #include #include using namespace std; const int MAXN = 1e5 + 10;
int n,lens = 1,lenm = 1,lena = 1; int sum[MAXN] = {0,1}, Max[10010] = {0, 1}, ans[MAXN]; struct node{ long long l, r, all; void read(){ cin >> l >> r; all = l * r; } }coin[MAXN]; bool operator< (node a,node b){ return a.all < b.all; } void mul(long long x){ int tmp = 0; for(int i = 1;i <= lens; i++){ sum[i] *= x; } for(int i = 1;i <= lens; i++){ tmp += sum[i]; sum[i] = tmp % 10; tmp /= 10; } while(tmp != 0){ lens++; sum[lens] = tmp % 10; tmp /= 10; } } void work(long long x){ memset(ans, 0, sizeof(ans)); lena = lens; int tmp = 0; for(int i = lena; i >= 1; i--){ tmp *= 10; tmp += sum[i]; if(tmp >= x){ ans[i] = tmp / x; tmp %= x; } } while(ans[lena] == 0){ if(lena == 1){ break; } lena--; } } void chose(){ if(lena > lenm) { for(int i = 1;i <= lena; i++){ Max[i] = ans[i]; } lenm = lena; } else if(lena == lenm){ for(int i = lena;i >= 1; i--){ if(Max[i] < ans[i]){ for(int j = 1;j <= lena; j++){ Max[j] = ans[j]; } lenm = lena; break; } } } } int main(){ cin >> n; cin >> coin[0].l >> coin[0].r; for(int i = 1;i <= n; i++){ coin[i].read(); } sort(coin + 1, coin + n + 1); for(int i = 1;i <= n; i++){ mul(coin[i - 1].l); work(coin[i].r); chose(); } for(int i = lenm; i >= 1; i--){ cout << Max[i]; } return 0; }
-
0
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int MAXN = 1e5 + 10; int n,lens = 1,lenm = 1,lena = 1; int sum[MAXN] = {0,1}, Max[10010] = {0, 1}, ans[MAXN]; struct node{ long long l, r, all; void read(){ cin >> l >> r; all = l * r; } }coin[MAXN]; bool operator< (node a,node b){ return a.all < b.all; } void mul(long long x){ int tmp = 0; for(int i = 1;i <= lens; i++){ sum[i] *= x; } for(int i = 1;i <= lens; i++){ tmp += sum[i]; sum[i] = tmp % 10; tmp /= 10; } while(tmp != 0){ lens++; sum[lens] = tmp % 10; tmp /= 10; } } void work(long long x){ memset(ans, 0, sizeof(ans)); lena = lens; int tmp = 0; for(int i = lena; i >= 1; i--){ tmp *= 10; tmp += sum[i]; if(tmp >= x){ ans[i] = tmp / x; tmp %= x; } } while(ans[lena] == 0){ if(lena == 1){ break; } lena--; } } void chose(){ if(lena > lenm) { for(int i = 1;i <= lena; i++){ Max[i] = ans[i]; } lenm = lena; } else if(lena == lenm){ for(int i = lena;i >= 1; i--){ if(Max[i] < ans[i]){ for(int j = 1;j <= lena; j++){ Max[j] = ans[j]; } lenm = lena; break; } } } } int main(){ cin >> n; cin >> coin[0].l >> coin[0].r; for(int i = 1;i <= n; i++){ coin[i].read(); } sort(coin + 1, coin + n + 1); for(int i = 1;i <= n; i++){ mul(coin[i - 1].l); work(coin[i].r); chose(); } for(int i = lenm; i >= 1; i--){ cout << Max[i]; } return 0; } -
0
C++ :
#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef pair<int, int>PII; const int N = 1010; int n; PII ps[N]; vector<int> mul(vector<int> a, int b) //高精度乘法 { vector<int> c; int t = 0; for(int i = 0; i < a.size(); i++) { t += a[i] * b; c.push_back(t % 10); //取出余数 t /= 10; //进位 } while(t) c.push_back(t % 10), t /= 10; return c; } vector<int> div(vector<int> a, int b) { vector<int> c; bool is_first = false; // 避免输出前面位的0 for(int i = a.size() - 1, t = 0; i >= 0; i--) //从高位往低位 { t = t * 10 + a[i]; //竖式后位的值 int x = t / b; if(x || is_first) { is_first = true; c.push_back(x); } t %= b; } return vector<int>(c.rbegin(), c.rend()); //逆序遍历 } vector<int> max_vec(vector<int>a, vector<int> b) // 返回vector { if(a.size() > b.size()) return a; if(a.size() < b.size()) return b; if(vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend()))//构造新的vector，是a的逆序 return a; return b; } void output(vector<int> a) { for(int i = a.size() - 1; i >= 0; i--) cout << a[i]; //高精度存，小位在前，高位在后,因为增加一位只能在后面增加 cout << endl; } int main() { cin >> n; for(int i = 0; i <= n; i++) // 0位国王，1...n+1为大臣 { int a, b; cin >> a >> b; ps[i] = {a * b, a}; } sort(ps + 1, ps + n + 1); vector<int>product(1, 1); //乘积长度为1，初始为1 vector<int>res(1,0); // 结果长度为1，初始为0 for(int i = 0; i <= n; i++) { if(i) res = max_vec(res, div(product, ps[i].first / ps[i].second)); product = mul(product, ps[i].second); } output(res); return 0; } -
-1
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int MAXN = 1e5 + 10; int n,lens = 1,lenm = 1,lena = 1; int sum[MAXN] = {0,1}, Max[10010] = {0, 1}, ans[MAXN]; struct node{ long long l, r, all; void read(){ cin >> l >> r; all = l * r; } }coin[MAXN]; bool operator< (node a,node b){ return a.all < b.all; } void mul(long long x){ int tmp = 0; for(int i = 1;i <= lens; i++){ sum[i] *= x; } for(int i = 1;i <= lens; i++){ tmp += sum[i]; sum[i] = tmp % 10; tmp /= 10; } while(tmp != 0){ lens++; sum[lens] = tmp % 10; tmp /= 10; } } void work(long long x){ memset(ans, 0, sizeof(ans)); lena = lens; int tmp = 0; for(int i = lena; i >= 1; i--){ tmp *= 10; tmp += sum[i]; if(tmp >= x){ ans[i] = tmp / x; tmp %= x; } } while(ans[lena] == 0){ if(lena == 1){ break; } lena--; } } void chose(){ if(lena > lenm) { for(int i = 1;i <= lena; i++){ Max[i] = ans[i]; } lenm = lena; } else if(lena == lenm){ for(int i = lena;i >= 1; i--){ if(Max[i] < ans[i]){ for(int j = 1;j <= lena; j++){ Max[j] = ans[j]; } lenm = lena; break; } } } } int main(){ cin >> n; cin >> coin[0].l >> coin[0].r; for(int i = 1;i <= n; i++){ coin[i].read(); } sort(coin + 1, coin + n + 1); for(int i = 1;i <= n; i++){ mul(coin[i - 1].l); work(coin[i].r); chose(); } for(int i = lenm; i >= 1; i--){ cout << Max[i]; } return 0; }
2024sng28
LV 10
@ 2025-2-22 11:36:48
- 1