全部知识点
（匠人的自我修养）一个匠人决定要学习 n 个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数 n(1≤n≤103)，以及已有经验值(≤107)。
接下来 n 行。第 i 行的两个整数，分别表示学习第 i 个技术所需的最低经验值 (≤107)，以及学会第 i 个技术后可获得的经验值 (≤104)。
接下来 n 行。第 i 行的第一个数 mi(0≤mi 下面的程序已 O(n2)的时间复杂完成这个问题，试补全程序。 ④ 处应填（ ）#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
bool find(){
int target=-1;
for (int i = 1;i<=n;++i)
if(① && ②){
target = i;
break;
}
if(target==-1)
return false;
unlock[target]=-1;
③
for (int i=0;i<cnt[target];++i)
④
return true;
}
int main(){
scanf("%d%d",&n, &points);
for (int i =1; i<=n;++i){
cnt [i]=0;
scanf("%d%d",&threshold[i],&bonus[i]);
}
for (int i=1;i<=n;++i){
int m;
scanf("%d",&m);
⑤
for (int j=0; j<m ;++j){
int fa;
scanf("%d", &fa);
child [fa][cnt[fa]]=i;
++cnt[fa];
}
}
int ans = 0;
while(find())
++ans;
printf("%d
", ans);
return 0;
}
（匠人的自我修养）一个匠人决定要学习 n 个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数 n(1≤n≤103)，以及已有经验值(≤107)。
接下来 n 行。第 i 行的两个整数，分别表示学习第 i 个技术所需的最低经验值 (≤107)，以及学会第 i 个技术后可获得的经验值 (≤104)。
接下来 n 行。第 i 行的第一个数 mi(0≤mi 下面的程序已 O(n2)的时间复杂完成这个问题，试补全程序。 ⑤处应填（ ）#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
bool find(){
int target=-1;
for (int i = 1;i<=n;++i)
if(① && ②){
target = i;
break;
}
if(target==-1)
return false;
unlock[target]=-1;
③
for (int i=0;i<cnt[target];++i)
④
return true;
}
int main(){
scanf("%d%d",&n, &points);
for (int i =1; i<=n;++i){
cnt [i]=0;
scanf("%d%d",&threshold[i],&bonus[i]);
}
for (int i=1;i<=n;++i){
int m;
scanf("%d",&m);
⑤
for (int j=0; j<m ;++j){
int fa;
scanf("%d", &fa);
child [fa][cnt[fa]]=i;
++cnt[fa];
}
}
int ans = 0;
while(find())
++ans;
printf("%d
", ans);
return 0;
}
（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 n 条取石子的规则，第 i 条规则为：如果剩余的石子个数大于等于 a[i] 且大于等于 b[i]，那么她们可以取走 b[i] 个石子。他们轮流取石子。如果轮到某个人取石子，而她们无法按照任何规则取走石子，那么他就输了，一开始石子有 m 个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数 n(1≤n≤64),以及石子个数 m(≤107)。
接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i] 不超过 64，所以可以使用位无符号整数去压缩必要的状态。
Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。
代码说明：
“~”表示二进制补码运算符，它将每个二进制位的 0 变成 1、1 变为 0；
而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0，反之为 1。
ull 标识符表示它前面的数字是 unsigned long long 类型。
#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
scanf(“%d%d”,＆n, ＆m);
for (int i = 0; i < n; ++i)
scanf(“%d%d”, ＆a[i], ＆b[i]);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (aa[i] > a[j]) {
swap(a[i], a[j]);
swap(b[i], b[j]);
}
status = ①;
trans = 0;
for (int i = 1, j = 0; i <= m; ++i) {
while (j < n && ②) {
③;
++j;
}
win = ④;
⑤;
}
puts(win ? “Win” : “Loss”)；
return 0;
}② 处应填（ ）
（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 n 条取石子的规则，第 i 条规则为：如果剩余的石子个数大于等于 a[i] 且大于等于 b[i]，那么她们可以取走 b[i] 个石子。他们轮流取石子。如果轮到某个人取石子，而她们无法按照任何规则取走石子，那么他就输了，一开始石子有 m 个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数 n(1≤n≤64),以及石子个数 m(≤107)。
接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i] 不超过 64，所以可以使用位无符号整数去压缩必要的状态。
Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。
代码说明：
“~”表示二进制补码运算符，它将每个二进制位的 0 变成 1、1 变为 0；
而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0，反之为 1。
ull 标识符表示它前面的数字是 unsigned long long 类型。
试补全程序
#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
scanf(“%d%d”,＆n, ＆m);
for (int i = 0; i < n; ++i)
scanf(“%d%d”, ＆a[i], ＆b[i]);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (aa[i] > a[j]) {
swap(a[i], a[j]);
swap(b[i], b[j]);
}
status = ①;
trans = 0;
for (int i = 1, j = 0; i <= m; ++i) {
while (j < n && ②) {
③;
++j;
}
win = ④;
⑤;
}
puts(win ? “Win” : “Loss”)；
return 0;
}③ 处应填（ ）
（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 n 条取石子的规则，第 i 条规则为：如果剩余的石子个数大于等于 a[i] 且大于等于 b[i]，那么她们可以取走 b[i] 个石子。他们轮流取石子。如果轮到某个人取石子，而她们无法按照任何规则取走石子，那么他就输了，一开始石子有 m 个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数 n(1≤n≤64),以及石子个数 m(≤107)。
接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i] 不超过 64，所以可以使用位无符号整数去压缩必要的状态。
Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。
代码说明：
“~”表示二进制补码运算符，它将每个二进制位的 0 变成 1、1 变为 0；
而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0，反之为 1。
ull 标识符表示它前面的数字是 unsigned long long 类型。
试补全程序
#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
scanf(“%d%d”,＆n, ＆m);
for (int i = 0; i < n; ++i)
scanf(“%d%d”, ＆a[i], ＆b[i]);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (aa[i] > a[j]) {
swap(a[i], a[j]);
swap(b[i], b[j]);
}
status = ①;
trans = 0;
for (int i = 1, j = 0; i <= m; ++i) {
while (j < n && ②) {
③;
++j;
}
win = ④;
⑤;
}
puts(win ? “Win” : “Loss”)；
return 0;
}④ 处应填（ ）
（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 n 条取石子的规则，第 i 条规则为：如果剩余的石子个数大于等于 a[i] 且大于等于 b[i]，那么她们可以取走 b[i] 个石子。他们轮流取石子。如果轮到某个人取石子，而她们无法按照任何规则取走石子，那么他就输了，一开始石子有 m 个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数 n(1≤n≤64),以及石子个数 m(≤107)。
接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i] 不超过 64，所以可以使用位无符号整数去压缩必要的状态。
Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。
代码说明：
“~”表示二进制补码运算符，它将每个二进制位的 0 变成 1、1 变为 0；
而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0，反之为 1。
ull 标识符表示它前面的数字是 unsigned long long 类型。
试补全程序
#include <cstdio>
#include<algorithm>
using namespace std ;
const int maxn =64;
int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；
int main() {
scanf(“%d%d”,＆n, ＆m);
for (int i = 0; i < n; ++i)
scanf(“%d%d”, ＆a[i], ＆b[i]);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (aa[i] > a[j]) {
swap(a[i], a[j]);
swap(b[i], b[j]);
}
status = ①;
trans = 0;
for (int i = 1, j = 0; i <= m; ++i) {
while (j < n && ②) {
③;
++j;
}
win = ④;
⑤;
}
puts(win ? “Win” : “Loss”)；
return 0;
}⑤处应填（ ）
（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。
例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤109。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for (i = ①; ② <= n; i ++) {
③ {
printf("%d ", i);
n = n / i;
}
}
if (④) {
printf("%d ", ⑤);
}
return 0;
}② 处应填（ ）
（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。
例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤109。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for (i = ①; ② <= n; i ++) {
③ {
printf("%d ", i);
n = n / i;
}
}
if (④) {
printf("%d ", ⑤);
}
return 0;
}③ 处应填（ ）
（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。
例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤109。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for (i = ①; ② <= n; i ++) {
③ {
printf("%d ", i);
n = n / i;
}
}
if (④) {
printf("%d ", ⑤);
}
return 0;
}④ 处应填（ ）
（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。
例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤109。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for (i = ①; ② <= n; i ++) {
③ {
printf("%d ", i);
n = n / i;
}
}
if (④) {
printf("%d ", ⑤);
}
return 0;
}⑤处应填（ ）
（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间 [0,m][0,m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数 n 和 m（1≤n≤5000, 1≤m≤109）。
接下来 n 行，每行两个证书 ai，bi（0≤ai，bi≤m）。
提示：使用贪心法解决这个问题。先用 Θ(n^2) 的时间复杂度排序，然后贪心选择这些区间。
试补全程序。
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans = 0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}② 处应填（ ）
（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间 [0,m][0,m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数 n 和 m（1≤n≤5000, 1≤m≤109）。
接下来 n 行，每行两个证书 ai，bi（0≤ai，bi≤m）。
提示：使用贪心法解决这个问题。先用 Θ(n^2) 的时间复杂度排序，然后贪心选择这些区间。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for (i = ①; ② <= n; i ++) {
③ {
printf("%d ", i);
n = n / i;
}
}
if (④) {
printf("%d ", ⑤);
}
return 0;
}③ 处应填（ ）
（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间 [0,m][0,m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数 n 和 m（1≤n≤5000, 1≤m≤109）。
接下来 n 行，每行两个证书 ai，bi（0≤ai，bi≤m）。
提示：使用贪心法解决这个问题。先用 Θ(n^2) 的时间复杂度排序，然后贪心选择这些区间。
试补全程序。
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans = 0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}④ 处应填（ ）
（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是[ai,bi]。现在要在这些区间中选出若干个，使得区间 [0,m][0,m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数 n 和 m（1≤n≤5000, 1≤m≤109）。
接下来 n 行，每行两个证书 ai，bi（0≤ai，bi≤m）。
提示：使用贪心法解决这个问题。先用 Θ(n^2) 的时间复杂度排序，然后贪心选择这些区间。
试补全程序。
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans = 0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}⑤处应填（ ）
（分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 wi，体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 α(0<α<1)，并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 αw，体积是 αv，另一块的价值是 (1−α)w，体积是 (1−α)v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。
那么最优的方法就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.61，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。
输入的数据范围为：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比 wi/vi 从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, B, w[maxn], v[maxn];
int gcd(int u, int v) {
if (v == 0)
return u;
return gcd(v, u % v);
}
void print(int w, int v) {
int d = gcd(w, v);
w = w / d;
v = v / d;
if (v == 1)
printf("%d\n", w);
else
printf("%d/%d\n", w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("%d %d", &n, &B);
for (int i = 1; i <= n; i ++) {
scanf("%d%d", &w[i], &v[i]);
}
for (int i = 1; i < n; i ++)
for (int j = 1; j < n; j ++)
if ( ① ) {
swap(w[j], w[j + 1]);
swap(v[j], v[j + 1]);
}
int curV, curW;
if ( ② ) {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for (int i = 2; i <= n; i ++)
if (curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print( ④ );
return 0;
}
print( ⑤ );
return 0;
}② 处应填（ ）
（分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 wi，体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 α(0<α<1)，并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 αw，体积是 αv，另一块的价值是 (1−α)w，体积是 (1−α)v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。
那么最优的方法就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.61，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。
输入的数据范围为：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比 wi/vi 从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, B, w[maxn], v[maxn];
int gcd(int u, int v) {
if (v == 0)
return u;
return gcd(v, u % v);
}
void print(int w, int v) {
int d = gcd(w, v);
w = w / d;
v = v / d;
if (v == 1)
printf("%d\n", w);
else
printf("%d/%d\n", w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("%d %d", &n, &B);
for (int i = 1; i <= n; i ++) {
scanf("%d%d", &w[i], &v[i]);
}
for (int i = 1; i < n; i ++)
for (int j = 1; j < n; j ++)
if ( ① ) {
swap(w[j], w[j + 1]);
swap(v[j], v[j + 1]);
}
int curV, curW;
if ( ② ) {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for (int i = 2; i <= n; i ++)
if (curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print( ④ );
return 0;
}
print( ⑤ );
return 0;
}③ 处应填（ ）
（分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 wi，体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 α(0<α<1)，并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 αw，体积是 αv，另一块的价值是 (1−α)w，体积是 (1−α)v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。
那么最优的方法就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.61，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。
输入的数据范围为：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比 wi/vi 从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, B, w[maxn], v[maxn];
int gcd(int u, int v) {
if (v == 0)
return u;
return gcd(v, u % v);
}
void print(int w, int v) {
int d = gcd(w, v);
w = w / d;
v = v / d;
if (v == 1)
printf("%d\n", w);
else
printf("%d/%d\n", w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("%d %d", &n, &B);
for (int i = 1; i <= n; i ++) {
scanf("%d%d", &w[i], &v[i]);
}
for (int i = 1; i < n; i ++)
for (int j = 1; j < n; j ++)
if ( ① ) {
swap(w[j], w[j + 1]);
swap(v[j], v[j + 1]);
}
int curV, curW;
if ( ② ) {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for (int i = 2; i <= n; i ++)
if (curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print( ④ );
return 0;
}
print( ⑤ );
return 0;
}④ 处应填（ ）
（分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i 块蛋糕的价值是 wi，体积是 vi。他有一个大小为 B 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 α(0<α<1)，并将一块价值是 w，体积为 v 的蛋糕切割成两块，其中一块的价值是 αw，体积是 αv，另一块的价值是 (1−α)w，体积是 (1−α)v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如 n=3，B=8，三块蛋糕的价值分别是 4、4、2，体积分别是 5、3、2。
那么最优的方法就是将体积为 5 的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.61，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出 42/5。
输入的数据范围为：1≤n≤1000，1≤B≤105，1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比 wi/vi 从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n, B, w[maxn], v[maxn];
int gcd(int u, int v) {
if (v == 0)
return u;
return gcd(v, u % v);
}
void print(int w, int v) {
int d = gcd(w, v);
w = w / d;
v = v / d;
if (v == 1)
printf("%d\n", w);
else
printf("%d/%d\n", w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("%d %d", &n, &B);
for (int i = 1; i <= n; i ++) {
scanf("%d%d", &w[i], &v[i]);
}
for (int i = 1; i < n; i ++)
for (int j = 1; j < n; j ++)
if ( ① ) {
swap(w[j], w[j + 1]);
swap(v[j], v[j + 1]);
}
int curV, curW;
if ( ② ) {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for (int i = 2; i <= n; i ++)
if (curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print( ④ );
return 0;
}
print( ⑤ );
return 0;
}⑤处应填（ ）
（最优子序列）取 m = 16，给出长度为 n 的整数序列 a1,a2,…,an(0≤ai≤2m)。对于一个二进制数 x，定义其分值 w(x) 为x+popcnt(x)，其中 popcnt(x) 表示 x 二进制表示中 1 的个数。对于一个子序列 b1,b2,…,bk，定义其子序列分值 S 为 w(b1⨁b2)+w(b2⨁b3)+w(b3⨁b4)+…w(bk−1⨁bk)。其中⨁ 表示按位异或。对于空子序列，规定其子序列分值为 0。求一个子序列似的其子序列的分值最大，输出这个最大值。
输入第一行包含一个整数 n(1≤n≤40000)。接下来一行包含 n 个整数a1,a2,…,an。
提示：考虑优化朴素的动态规划算法，将前 m/2 位和后m /2位分开计算。
Max[x][y] 表示当前的子序列下一个位置的高 8 位是 x、最后一个位置的低 8 位是 y 时的最大价值。
试补全程序。
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];
int w(int x)
{
int s = x;
while (x)
{
①;
s++;
}
return s;
}
void to_max(LL &x, LL y)
{
if (x < y)
x = y;
}
int main()
{
int n;
LL ans = 0;
cin >> n;
for (int x = 0; x <= MS; x++)
for (int y = 0; y <= MS; y++)
Max[x][y] = -INF;
for (int i = 1; i <= n; i++)
{
LL a;
cin >> a;
int x = ②, y = a & MS;
LL v = ③;
for (int z = 0; z <= MS; z++)
to_max(v, ④);
for (int z = 0; z <= MS; z++)
⑤;
to_max(ans, v);
}
cout << ans << endl;
return 0;
}② 处应填（ ）
（最优子序列）取 m = 16，给出长度为 n 的整数序列 a1,a2,…,an(0≤ai≤2m)。对于一个二进制数 x，定义其分值 w(x) 为x+popcnt(x)，其中 popcnt(x) 表示 x 二进制表示中 1 的个数。对于一个子序列 b1,b2,…,bk，定义其子序列分值 S 为 w(b1⨁b2)+w(b2⨁b3)+w(b3⨁b4)+…w(bk−1⨁bk)。其中⨁ 表示按位异或。对于空子序列，规定其子序列分值为 0。求一个子序列似的其子序列的分值最大，输出这个最大值。
输入第一行包含一个整数 n(1≤n≤40000)。接下来一行包含 n 个整数a1,a2,…,an。
提示：考虑优化朴素的动态规划算法，将前 m/2 位和后m /2位分开计算。
Max[x][y] 表示当前的子序列下一个位置的高 8 位是 x、最后一个位置的低 8 位是 y 时的最大价值。
试补全程序。
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];
int w(int x)
{
int s = x;
while (x)
{
①;
s++;
}
return s;
}
void to_max(LL &x, LL y)
{
if (x < y)
x = y;
}
int main()
{
int n;
LL ans = 0;
cin >> n;
for (int x = 0; x <= MS; x++)
for (int y = 0; y <= MS; y++)
Max[x][y] = -INF;
for (int i = 1; i <= n; i++)
{
LL a;
cin >> a;
int x = ②, y = a & MS;
LL v = ③;
for (int z = 0; z <= MS; z++)
to_max(v, ④);
for (int z = 0; z <= MS; z++)
⑤;
to_max(ans, v);
}
cout << ans << endl;
return 0;
}③ 处应填（ ）