11月22日星期六18:30-21:30
高精度加法
代码
高精度乘单精度
描述
输入描述
输出描述
用例输入 1
111111111111111111111111111111111111
10用例输出 1
1111111111111111111111111111111111110代码
1.
2.
3.
4.
#include<bits/stdc++.h>
using namespace std;
int a[1000],b[1000];
int main(){
string str;
int n,count=0,jishu=0;
cin>>str>>n;
for(int i=str.size()-1;i>=0;i--){
a[count++] = str[i]-'0';
}
for(int i=0;i<count;i++){
a[i] = a[i]*n;
}
for(int i=0;i<count-1;i++){//count位没有存放数据 不用计算到这 最后一位的数据直接输出就行了
if(a[i]>=10){
a[i+1] = a[i]/10 + a[i+1];
a[i] = a[i]%10;
}
}
for(int i=count-1;i>=0;i--){
if(a[i]!=0){
jishu=1;
}
if(jishu||i==0){
cout<<a[i];
}
}
return 0;
}高精度相乘
描述
输入描述
输出描述
用例输入 1
1111111111111111111111111
2222222222222222222222222用例输出 1
2469135802469135802469135308641975308641975308642代码
#include<bits/stdc++.h>
using namespace std;
int num1[10000],num2[10000],num[10000],jishu;
int main(){
string s1,s2;
cin>>s1>>s2;
for(int i=0;i<s1.size();i++){
num1[i] = s1[s1.size()-1-i]-'0';
}
for(int i=0;i<s2.size();i++){
num2[i] = s2[s2.size()-1-i]-'0';
}
for(int i=0;i<s2.size();i++){
for(int j=0;j<s1.size();j++){
int n = num2[i]*num1[j];
num[i+j] = num[i+j]+n;
if(num[i+j]>=10){//进位
num[i+j+1] = num[i+j+1]+num[i+j]/10;//计算下一位的值
num[i+j] = num[i+j]%10;//计算当前位的值
}
}
}
for(int i=s1.size()+s2.size()-1;i>=0;i--){
if(num[i]!=0){
jishu=1;
}
if(jishu||i==0){
cout<<num[i];
}
}
return 0;
}高精度整数除法
描述
输入描述
输出描述
用例输入 1
97 61 50用例输出 1
1.59016393442622950819672131147540983606557377049180代码
#include<bits/stdc++.h>
using namespace std;
int a,b,n;
int main(){
cin>>a>>b>>n;
//输出整数和小数点
cout<<a/b;
if(n==0) return 0;
else cout<<".";
int q = a%b;
for(int i=0;i<n;i++){
cout<<q*10/b;//余数*10/除数
q = q*10%b;//更新余数
}
return 0;
}简单背包问题
描述
输入描述
输出描述
用例输入 1
10 3
4 5
3 4
6 9用例输出 1
14#include<bits/stdc++.h>
using namespace std;
int maxw,n,wi,pi,dp[100][100];
int main(){
cin>>maxw>>n;
for(int i=1;i<=n;i++){
cin>>wi>>pi;
for(int j=1;j<=maxw;j++){
if(j>=wi){
dp[i][j] = max(pi+dp[i-1][j-wi],dp[i-1][j]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<dp[n][maxw];
return 0;
}
//优化
#include<bits/stdc++.h>
using namespace std;
int maxw,n,wi,pi,dp[21000];
int main(){
cin>>maxw>>n;
for(int i=1;i<=n;i++){
cin>>wi>>pi;
for(int j=maxw;j>=wi;j--){
dp[j] = max(dp[j],pi+dp[j-wi]);
}
}
cout<<dp[maxw];
return 0;
}
}T1268 完全背包问题
描述
输入描述
输出描述
用例输入 1
10 4
2 1
3 3
4 5
7 9用例输出 1
max=12#include<bits/stdc++.h>
using namespace std;
int maxw,n,wi,pi,dp[110][21000];
int main(){
cin>>maxw>>n;
for(int i=1;i<=n;i++){
cin>>wi>>pi;
for(int j=1;j<=maxw;j++){
if(j>=wi){
dp[i][j] = max(dp[i-1][j],pi+dp[i][j-wi]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
cout<<"max="<<dp[n][maxw];
return 0;
}
//优化
#include<bits/stdc++.h>
using namespace std;
int maxw,n,wi,pi,dp[21000];
int main(){
cin>>maxw>>n;
for(int i=1;i<=n;i++){
cin>>wi>>pi;
for(int j=wi;j<=maxw;j++){
dp[j] = max(dp[j],pi+dp[j-wi]);
}
}
cout<<"max="<<dp[maxw];
return 0;
}修改于 2025-11-23 10:22:50