全部知识点
（分数背包）小 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;
}③ 处应填（ ）
（最优子序列）取 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;
}⑤处应填（ ）
设循环队列的存储空间为Q(1：35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为( )。
下列关于栈的叙述中正确的是( )。
下列链表中，其逻辑结构属于非线性结构的是( )
在关系数据库中，用来表示实体间联系的是( )。
公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员。则实体部门和职员间的联系是( )。
右两个关系R和S如下， 则由关系R得到关系S的操作是( )。
数据字典(DD)所定义的对象都包含于( )。
软件需求规格说明书的作用不包括( )。
下面属于黑盒测试方法的是( )。
下面不属于软件设计阶段任务的是( )。
以下叙述中正确的是( )。
C语言中的标识符分为关键字、预定义标识符和用户标识符，以下叙述正确的是( )。
以下选项中表示一个合法的常量是(说明，符号口表示空格)( )。
