[7.11] 纪中C组

本文主要是介绍[7.11] 纪中C组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题
算个成绩而已嘛，我当时就码了一波快排然后没看数据于是你懂得。。
位数在30位以内
去你[哔——]的！这long long都装不下嘛！
于是一个古老而神秘，呸呸呸，一个久远的算法——高精度从我脑海里浮现……
然而浮现有个[哔——]用，我要打出来而且对才行
恩，唠叨的够多了
其实说白了就一个字符串（数组）快排加上高精减罢了

#include <fstream> 
#include <string>
#include <memory.h>
#include <cstdlib>
using namespace std;
string c[10001],m[10001],e[10001],x,y,z;
int n,i,sc[101],p;
void qsc(int l,int h)
{int i=l,j=h;string mid=c[(l+h)/2],t;if (l>=h) return;do{while (c[i].length()>mid.length()||c[i].length()==mid.length()&&c[i]>mid) i++;while (c[j].length()<mid.length()||c[j].length()==mid.length()&&c[j]<mid) j--;if (i<=j){t=c[i];c[i]=c[j];c[j]=t;i++;j--;}}while (i<=j);qsc(i,h);qsc(l,j);
} 
void qsm(int l,int h)
{int i=l,j=h;string mid=m[(l+h)/2],t;if (l>=h) return;do{while (m[i].length()>mid.length()||m[i].length()==mid.length()&&m[i]>mid) i++;while (m[j].length()<mid.length()||m[j].length()==mid.length()&&m[j]<mid) j--;if (i<=j){t=m[i];m[i]=m[j];m[j]=t;i++;j--;}}while (i<=j);qsm(i,h);qsm(l,j);
}
void qse(int l,int h)
{int i=l,j=h;string mid=e[(l+h)/2],t;if (l>=h) return;do{while (e[i].length()>mid.length()||e[i].length()==mid.length()&&e[i]>mid) i++;while (e[j].length()<mid.length()||e[j].length()==mid.length()&&e[j]<mid) j--;if (i<=j){t=e[i];e[i]=e[j];e[j]=t;i++;j--;}}while (i<=j);qse(i,h);qse(l,j);
}
void g(string s1,string s2)
{int i,l,a[101],b[101];memset(sc,0,sizeof(sc));memset(a,0,sizeof(a));memset(b,0,sizeof(b));l=s2.length();for (i=1;i<=l;i++)b[i]=s2[l-i]-'0';l=s1.length();for (i=1;i<=l;i++)a[i]=s1[l-i]-'0';for (i=1;i<=l;i++){sc[i]=a[i]-b[i]+sc[i];if (sc[i]<0){sc[i+1]=sc[i+1]-1;sc[i]+=10;}}for (i=l;i>=2;i--)if (sc[i]!=0)break;p=i;
}
int main()
{ifstream fin("score.in",ios::in);ofstream fout("score.out",ios::out);fin>>c[0]>>m[0]>>e[0];x=c[0];y=m[0];z=e[0];fin>>n;for (i=1;i<=n;i++)fin>>c[i]>>m[i]>>e[i];qsc(0,n);qsm(0,n);qse(0,n);g(c[0],x);for (i=p;i>=1;i--)fout<<sc[i];fout<<' ';g(m[0],y);for (i=p;i>=1;i--)fout<<sc[i];fout<<' ';g(e[0],z);for (i=p;i>=1;i--)fout<<sc[i];fout<<' ';
}

第三题
1. 每个人的背包能装无限多的物品，每种物品有一个价值，但只能装一件；
2. 每个人都很有个性，所以每个人的背包不会完全相同。
DaA 的团队中有M 个人，那么对于整个团队，背包价值和最大是多少呢？
这道题真的很水很水个屁
很容易看得出来，就是个组合，选最大而已
然而时间复杂度不允许。。。
那我能干吗？
撸……呸，当然是码代码啊
首先DP，f[i]为价值为i时的的方案数
我不想说啦啊啊啊

#include <iostream>
#include <cstdio>
using namespace std;
int m,n;
long long s,f[25001],su,a[1000001],i,j;
int main()
{freopen("team.in","r",stdin);freopen("team.out","w",stdout);scanf("%d%d",&m,&n);for (i=1;i<=n;i++){scanf("%d",&a[i]);su+=a[i];}f[0]=1;for (i=1;i<=n;i++)for (j=su;j>=a[i];j--)f[j]+=f[j-a[i]];for (i=su;i>=1;i--)if (f[i]>0){if (f[i]>m){s+=m*i;m=0;}elseif (f[i]<=m){s+=f[i]*i;m-=f[i];}if (m==0) break;}printf("%lld",s);
}

这篇关于[7.11] 纪中C组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---