题解一

A. Buns（多重背包/01背包）点击打开题目链接

题意：有n克面团，m种可以做不同馅饼的馅料，第i种馅料有ai克，可以用bi克馅料和ci克面团做一个价值为di的馅饼，也可以不用馅料只用c0克面团做价值为d0的饼。问用现有的面团可以做的面饼的价值最多是多少。因为是英文题所以可能读起来有一定难度，但是读懂了以后结合样例看一下就没问题了。

解法：简单的多重背包问题，背包容量为面团的重量，有m种可供选择的馅饼，第i种的数量为ai/bi，体积为ci,价值为di，还有一种数量无限，体积为c0，价值为d0的物品。简化为这种模型就很好理解了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn =11;
int dp[1010];
int w[maxn],v[maxn],num[maxn];
int main()
{int n,m,c0,d0;while(scanf("%d%d%d%d",&n,&m,&c0,&d0)!=EOF){int a,b,c,d;memset(dp,0,sizeof(dp));//不要求装满背包只求最大价值就可以全部初始化为0for(int i=1;i<=m;i++){scanf("%d%d%d%d",&a,&b,&c,&d);num[i]=a/b;//统计某一种模具有多少个v[i]=d;//它的体积w[i]=c;//它的价值}num[0]=n/c0;//不用模具的情况也要处理一下。v[0]=d0;w[0]=c0;for(int i=0;i<=m;i++){for(int j=n;j>=0;j--)for(int k=0;k<=num[i];k++){if(j>=k*w[i])dp[j]=max(dp[j],dp[j-k*w[i]]+v[i]*k);}}printf("%d\n",dp[n]);}
}

B. Round House（水题）点击打开题目链接

题意：一个圆环上有n个点，初始位置在a点，问移动b步后到达哪个点（b大于0顺时针，小于0逆时针）。

题解：简单的模拟题。具体的就不讲了，可以推数学式子找规律，也可以直接暴力模拟。

暴力做法：

#include<bits/stdc++.h>
using namespace std;
int aa[200];
int main()
{int n,a,b;while(scanf("%d%d%d",&n,&a,&b)!=EOF){for(int i=1; i<=n; i++)aa[i]=i;int ans=a;if(b>0){for(int i=1;i<=b;i++){ans++;if(ans>n)ans=1;}}else {int num=abs(b);for(int i=1;i<=num;i++){ans--;if(ans<1)ans=n;}}printf("%d\n",ans);}return 0;
}

找规律做法：

#include<bits/stdc++.h>
using namespace std;
int aa[200];
int main()
{int n,a,b;while(scanf("%d%d%d",&n,&a,&b)!=EOF){for(int i=1; i<=n; i++)aa[i]=i;int ans;if(b>=0){int num=abs(a+b)%n==0?n:abs(a+b)%n;ans=aa[num];}else{if(abs(b)<a)ans=aa[a-abs(b)];else {int num=abs(a+b)%n==0?n:abs(a+b)%n;if(num==n)ans=aa[n];elseans=aa[n-num];}}printf("%d\n",ans);}return 0;
}

C. Playing Cubes （找规律/思维题）点击打开题目链接

题意：两人轮流向已有序列后面放红蓝木块，一人想使相邻颜色相同多，另外一人想不同颜色多，问最后两人分别得了多少分。

对于想拿相同的木块分的人，他当前放与上一个木块相同最优，对于想拿不同木块分的人，他放与上一块木块不同颜色最优，第一个人放多的颜色木块更优，当前对自己有利就放，否则到后面就无利了，对于第一个想拿不同木块分的人，他放与上一块木块不同颜色最优，第一个人放多的颜色木块更优（当前对自己有利就放，否则到后面就无利了）

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{int m,n;scanf("%d%d",&m,&n);if (m<n) swap(n,m);printf("%d %d\n",m-1,n);
}

D. Xenia and Weights（记忆化搜索）点击打开题目链接

 题意：给定长度为10的01序列，第i个数字为0代表没有重量为i的砝码，否则就代表有。利用已有砝码轮流在天平两端共放置m个砝码，要求每次满足放砝码一端重量比不放砝码一端重。如果有可以满足要求的方案就输出YES+方案，否则输出NO。

题解：dfs记忆化搜索看每个砝码是否符合要求即可（注意连续两次放置的砝码重量不能相同）。

代码：

#include<bits/stdc++.h>
typedef long long ll;using namespace std;
const int maxn = 1100;
int ans[maxn],vis[maxn];
int pan[2],m;
char s[11];
ll a[maxn];
bool dfs(int p, int pos, int last)//当前为天平的p端，当前放置次数为pos,上一个放置的砝码重量为last
{if(pos > m)//已放置m个砝码return true;int t = last;for(int i = 1; i <= 10; i++)//遍历所有重量的砝码（如果这个重量的砝码有的话）看是否满足条件{if(!vis[i]) continue;if(pan[p] + i > pan[p ^ 1] && last != i)//当前天平端重量大于另一端且当前放置砝码与上一次放置的砝码重量不相同。{last = i;//标记此次放置的砝码重量pan[p] += i;//该端天平重量增加if(dfs(p^1, pos+1, last))//遍历下一步{ans[pos] = i;return true;}last = t;//记得要改回来看其他砝码是否满足条件。pan[p] -= i;}}return false;
}
int main()
{memset(ans, 0, sizeof(ans));memset(vis, 0, sizeof(vis));memset(pan, 0, sizeof(pan));scanf("%s",s);for(int i = 0; i < 10; i++){if(s[i] == '1') vis[i+1] = 1;//标记有无重量为i+1的砝码}scanf("%d",&m);if(!dfs(0, 1, -1)) printf("NO\n");else{printf("YES\n");for(int i = 1; i <= m; i++){if(i > 1) printf(" ");printf("%d",ans[i]);}printf("\n");}return 0;
}

E. Writing Code（完全背包）点击打开题目链接

题意： 有n个写代码的工程师，第i个人写一行代码就有ai个bug，现在要求写m行代码，每行代码选一个人来写，规定m行代码的bug总和不能超过b个，问有多少种满足要求的选人方案。

题解：完全背包问题，背包容量为m，有n种物品，每种的数量无限，体积为1，价值为ai，做一个完全背包，最后再统计所有不bug数超过b的方案共有多少种。dp[i][j][k] = n; 表示第i个人，写了j行代码，有k个bug的有方案数n。由于这个状态是由第i个人不写第j行和写第j行转移过来，所以第一维可以省略掉。

需要考虑如果有程序员每行代码bug = 0的情况，所以最后统计答案的时候应该从0~b遍历。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[550];
int dp[550][550];
int main()
{int n,m,b,mod;//n个人，m条程序，b个bugscanf("%d%d%d%d",&n,&m,&b,&mod);for(int i=1;i<=n;i++)scanf("%d",&a[i]);//每个程序员的一行代码有多少bugdp[0][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=a[i];k<=b;k++){dp[j][k]=(dp[j][k]%mod+dp[j-1][k-a[i]]%mod)%mod;}int ans=0;for(int i=0;i<=b;i++)ans=(ans+dp[m][i])%mod;printf("%d\n",ans);return 0;
}

F. Party（签到题）点击打开题目链接

 题意：老板会给来的最早的小组的每个人发奖金，问至少要准备多少钱才够发。

题解：当然满足条件的钱一定是分给任何一组的人都能够均分的，所以直接求所有数的最小公倍数就可以了。

代码：

#include
using namespace std;
int a[110];
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{int num=gcd(a,b);return a*b/num;
}
int main()
{int n;while(scanf("%d",&n)!=EOF&&n){for(int i=1;i<=n;i++)scanf("%d",&a[i]);int num=a[1];for(int i=2;i<=n;i++)num=lcm(num,a[i]);if(num>=1000000)printf("Too much money to pay!\n");else printf("The CEO must bring %d pounds.\n",num);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！