假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单 选题：

n必须小于1000,否则程序可能会发生运行错误。()

假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：

第9行的“x”的数值范围是L+1到R.即[L+l, R]。()

（分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。

他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是（l-a）v。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如n=3, B=8，三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份，一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。

输入的数据范围为：1≤n≤1000,1≤B≤10^5;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=6，给出长度为n的整数序列a₁,a₂，……a_n（0 ≤ a_i<2^m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b₁，b₂，…，b_k，定 义其子序列分值S为w（b₁㊉b₂）+w（b₂㊉b₃）+w（b₃㊉b₄）+……+w（b_k-1㊉b_k）。其中㊉表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数n(1 ≤ n ≤  40000).接下来一行包含n个整数 a₁，a₂，……，a_n。

提示：考虑优化朴素的动态规划算法，将前位和后位分开计算。

Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。

试补全程序。

①处应填（）