一、单选题
1、若有定义：int a=7; float x=2.5, y=4.7；则表达式x+a%3*(int)(x+y)%2的值是：（ ）
A 0.000000
B 2.750000
C 2.500000
D 3.500000
2、下列属于图像文件格式的有（ ）
A WMV
B MPEG
C JPEG
D AVI
3、二进制数11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是（ ）
A 11 1111 1101
B 11 1111 1111 1101
C 10 1111 1111 1111
D 11 1111 1111 1111
4、编译器的功能是（ ）
A 将源程序重新组合
B 将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）
C 将低级语言翻译成高级语言
D 将一种编程语言翻译成自然语言
5、设变量x为float型且已赋值，则以下语句中能将x中的数值保留到小数点后两位，并将第三位四舍五入的是（ ）
A X=(x*100+0.5)/100.0
B x=(int)(x*100+0.5)/100.0
C x=(x/100+0.5)*100.0
D x=x*100+0.5/100.0
6、由数字1，1，2，4，8，8所组成的不同的4位数的个数是（ ）
A 104
B 102
C 98
D 100
7、排序的算法很多，若按排序的稳定性和不稳定性分类，则（ ）是不稳定排序。
A 冒泡排序
B 直接插入排序
C 快速排序
D 归并排序
8、G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有（ ）个顶点
A 10
B 9
C 11
D 8
9、一些数字可以颠倒过来看，例如0、1、8颠倒过来看还是本身，6颠倒过来是9，9颠倒过来看还是6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（ ）
A 40
B 25
C 30
D 20
10、一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（ ）
A 23
B 21
C 20
D 22
11、设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（ ）
A n2
B n log n
C 2n
D 2n-1
12、以下哪个结构可以用来存储图（ ）
A 栈
B 二叉树
C 队列
D 邻接矩阵
13、以下哪些算法不属于贪心算法？（ ）
A Di jkstra算法
B Floyd算法
C Prim算法
D Kruskal算法
14、有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098，中间一项是486，请问以下哪个数是可能的公比？（ ）
A 5
B 3
C 4
D 2
15、有正实数构成的数字三角形排列形式如图所示。第一行的数为a1,1;第二行的数从左到右依次为a2,1,a2,2，第n行的数为an,1，an,2，…，an,n。从a1,1开始，每一行的数ai,j只有两条边可以分别通向下一行的两个数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1，an,2，…，an,n中某个数的路径，使得该路径上的数之和最大。
令C[i][j]是从a1,1到ai,j的路径上的数的最大和，并且C[i][0]= C[0][j]=0，则C[i][j]=（ ）
A max{C[i-1][j-1],C[i-1][j]}+ ai,j
B C[i-1][j-1]+C[i-1][j]
C max{C[i-1][j-1],c[i-1][j]}+1
D max{C[i][j-1],C[i-1][j]}+ ai,j
二、判断题
#include <cstdio>
using namespace std;
int n;
int a[100];
int main( ) {
scanf(“%d”，&n);
for(int i = 1; i <= n; ++i) {
scanf(“%d”，&a[i])
int ans = 1
for (int i = 1; i <= n; ++i) {
if ( i > 1 && a[i] < a[i-1])
ans = i ;
while (ans < n && a[i] >= a[ans+1])
++ans;
printf(“%d/n”, ans);
}
return 0;
}
16、（1分）第16行输出ans时，ans的值一定大于i。（ ）
A 正确
B 错误
#include <cstdio>
using namespace std;
int n;
int a[100];
int main( ) {
scanf(“%d”，&n);
for(int i = 1; i <= n; ++i) {
scanf(“%d”，&a[i])
int ans = 1
for (int i = 1; i <= n; ++i) {
if ( i > 1 && a[i] < a[i-1])
ans = i ;
while (ans < n && a[i] >= a[ans+1])
++ans;
printf(“%d/n”, ans);
}
return 0;
}
17、（1分）程序输出的ans小于等于n。（ ）
A 正确
B 错误
#include <cstdio>
using namespace std;
int n;
int a[100];
int main( ) {
scanf(“%d”，&n);
for(int i = 1; i <= n; ++i) {
scanf(“%d”，&a[i])
int ans = 1
for (int i = 1; i <= n; ++i) {
if ( i > 1 && a[i] < a[i-1])
ans = i ;
while (ans < n && a[i] >= a[ans+1])
++ans;
printf(“%d/n”, ans);
}
return 0;
}
18、若将第12行的“<”改为“！=”，程序输出的结果不会改变。（ ）
A 正确
B 错误
#include <cstdio>
using namespace std;
int n;
int a[100];
int main( ) {
scanf(“%d”，&n);
for(int i = 1; i <= n; ++i) {
scanf(“%d”，&a[i])
int ans = 1
for (int i = 1; i <= n; ++i) {
if ( i > 1 && a[i] < a[i-1])
ans = i ;
while (ans < n && a[i] >= a[ans+1])
++ans;
printf(“%d/n”, ans);
}
return 0;
}
19、当程序执行到第16行时，若ans-i>2，则a[i+1]≦a[i]。（ ）
A 正确
B 错误
三、单选题
#include <cstdio>
using namespace std;
int n;
int a[100];
int main( ) {
scanf(“%d”，&n);
for(int i = 1; i <= n; ++i) {
scanf(“%d”，&a[i])
int ans = 1
for (int i = 1; i <= n; ++i) {
if ( i > 1 && a[i] < a[i-1])
ans = i ;
while (ans < n && a[i] >= a[ans+1])
++ans;
printf(“%d/n”, ans);
}
return 0;
}
20、（3分）若输入的a数组是一个严格单调递增的数列，此程序的时间复杂度是（ ）。
A 0(log n)
B 0(n2)
C 0(nlog n)
D 0(n)
#include <cstdio>
using namespace std;
int n;
int a[100];
int main( ) {
scanf(“%d”，&n);
for(int i = 1; i <= n; ++i) {
scanf(“%d”，&a[i])
int ans = 1
for (int i = 1; i <= n; ++i) {
if ( i > 1 && a[i] < a[i-1])
ans = i ;
while (ans < n && a[i] >= a[ans+1])
++ans;
printf(“%d/n”, ans);
}
return 0;
}
21、最坏情况下，此程序的时间复杂度是（ ）。
A 0（n2)
B 0(log n)
C 0(n)
D 0(nlog n)
四、判断题
#include <cstdio>
using namepace std ;
const int maxn =1000;
int n;
int fa[maxn],cnt [maxn];
int getroot(int v ) {
if (fa[v] == v) return v;
return getroot(fa[v]);
}
int main ( ) {
cin >> n;
for (int i =0;i<n;++i){
fa[i]=i;
cnt[i]=1;
}
int ans = 0 ;
for (int i=0; i<n - 1; ++i){
int a,b,x,y,;
cin >>a>>b
x=getRoot(a);
y=getRoot(b);
ans +=cnt[x]cnt[y];
fa[x]=y;
cnt[y] +=cnt[x];
}
cout<<ans<<endl;
return 0;
}
22、（1分）输入的a和b值应在[0，n-1]的范围内。（ ）
A 正确
B 错误
#include <cstdio>
using namepace std ;
const int maxn =1000;
int n;
int fa[maxn],cnt [maxn];
int getroot(int v ) {
if (fa[v] == v) return v;
return getroot(fa[v]);
}
int main ( ) {
cin >> n;
for (int i =0;i<n;++i){
fa[i]=i;
cnt[i]=1;
}
int ans = 0 ;
for (int i=0; i<n - 1; ++i){
int a,b,x,y,;
cin >>a>>b
x=getRoot(a);
y=getRoot(b);
ans +=cnt[x]cnt[y];
fa[x]=y;
cnt[y] +=cnt[x];
}
cout<<ans<<endl;
return 0;
}
23、(1分)第16行改成“fa[i]=0;”, 不影响程序运行结果。（ ）
A 正确
B 错误
#include <cstdio>
using namepace std ;
const int maxn =1000;
int n;
int fa[maxn],cnt [maxn];
int getroot(int v ) {
if (fa[v] == v) return v;
return getroot(fa[v]);
}
int main ( ) {
cin >> n;
for (int i =0;i<n;++i){
fa[i]=i;
cnt[i]=1;
}
int ans = 0 ;
for (int i=0; i<n - 1; ++i){
int a,b,x,y,;
cin >>a>>b
x=getRoot(a);
y=getRoot(b);
ans +=cnt[x]cnt[y];
fa[x]=y;
cnt[y] +=cnt[x];
}
cout<<ans<<endl;
return 0;
}
24、若输入的a和b值均在[0, n-1]的范围内，则对于任意0≤i＜n，都有0≤fa[i]＜n。（ ）
A 正确
B 错误
#include <cstdio>
using namepace std ;
const int maxn =1000;
int n;
int fa[maxn],cnt [maxn];
int getroot(int v ) {
if (fa[v] == v) return v;
return getroot(fa[v]);
}
int main ( ) {
cin >> n;
for (int i =0;i<n;++i){
fa[i]=i;
cnt[i]=1;
}
int ans = 0 ;
for (int i=0; i<n - 1; ++i){
int a,b,x,y,;
cin >>a>>b
x=getRoot(a);
y=getRoot(b);
ans +=cnt[x]cnt[y];
fa[x]=y;
cnt[y] +=cnt[x];
}
cout<<ans<<endl;
return 0;
}
25、若输入的a和b值均在[0,n-1]的范围内，则对于任意0≤i＜n，都有1≤cnt[i] ≤n。（ ）
A 正确
B 错误
五、单选题
#include <cstdio>
using namepace std ;
const int maxn =1000;
int n;
int fa[maxn],cnt [maxn];
int getroot(int v ) {
if (fa[v] == v) return v;
return getroot(fa[v]);
}
int main ( ) {
cin >> n;
for (int i =0;i<n;++i){
fa[i]=i;
cnt[i]=1;
}
int ans = 0 ;
for (int i=0; i<n - 1; ++i){
int a,b,x,y,;
cin >>a>>b
x=getRoot(a);
y=getRoot(b);
ans +=cnt[x]cnt[y];
fa[x]=y;
cnt[y] +=cnt[x];
}
cout<<ans<<endl;
return 0;
}
26、当n等于50时，若a、b的值都在[0,49]的范围内，且在第25行时x总是不等于y，那么输出为（ ）
A 1276
B 1176
C 1225
D 1250
#include <cstdio>
using namepace std ;
const int maxn =1000;
int n;
int fa[maxn],cnt [maxn];
int getroot(int v ) {
if (fa[v] == v) return v;
return getroot(fa[v]);
}
int main ( ) {
cin >> n;
for (int i =0;i<n;++i){
fa[i]=i;
cnt[i]=1;
}
int ans = 0 ;
for (int i=0; i<n - 1; ++i){
int a,b,x,y,;
cin >>a>>b
x=getRoot(a);
y=getRoot(b);
ans +=cnt[x]cnt[y];
fa[x]=y;
cnt[y] +=cnt[x];
}
cout<<ans<<endl;
return 0;
}
27、此程序的时间复杂度是（ ）
A O(n)
B O(log n)
C O(n^2)
D O(n log n)
六、判断题
本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。
S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x…y]是空串。t[x…y]同理。
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 202;
string s, t ;
int pre[max1], suf[max1]
int main() {
cin＞＞s＞＞t；
int slen =s. length(), tlen= t. length();
for (int I = 0 ,j = 0 ; i＜ slen; ++i) {
if (j＜ tlen&&s[i]t[j] ) ++j;
pre[i] = j;// t[0…j-1]是s[0…i]的子序列
}
for (int I = slen -1 ,j= tlen -1; I ＞=0；–i) {
if(j＞=0&& s[i] == t [j]) –j;
suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列
}
suf[slen] = tlen -1;
int ans = 0;
for （int i=0, j=0, tmp=o; i＜=slen; ++i）{
while（j＜=slen && tmp ＞=suf[j] + 1） ++j；
ans =max(ans, j – I – 1);
tmp = pre[i];
}
cout ＜＜ans ＜＜ end1;
return 0;
}
提示：
t[0…pre[i]-1]是s[0…i]的子序列；
t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。
28、（1分）程序输出时，suf数组满足：对任意0≤i＜slen，suf[i] ≤suf[i+1]。( )
A 正确
B 错误
本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。
S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x…y]是空串。t[x…y]同理。
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 202;
string s, t ;
int pre[max1], suf[max1]
int main() {
cin＞＞s＞＞t；
int slen =s. length(), tlen= t. length();
for (int I = 0 ,j = 0 ; i＜ slen; ++i) {
if (j＜ tlen&&s[i]t[j] ) ++j;
pre[i] = j;// t[0…j-1]是s[0…i]的子序列
}
for (int I = slen -1 ,j= tlen -1; I ＞=0；–i) {
if(j＞=0&& s[i] == t [j]) –j;
suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列
}
suf[slen] = tlen -1;
int ans = 0;
for （int i=0, j=0, tmp=o; i＜=slen; ++i）{
while（j＜=slen && tmp ＞=suf[j] + 1） ++j；
ans =max(ans, j – I – 1);
tmp = pre[i];
}
cout ＜＜ans ＜＜ end1;
return 0;
}
提示：
t[0…pre[i]-1]是s[0…i]的子序列；
t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。
29、 （2分）当t是s的子序列时，输出一定不为0。（ ）
A 正确
B 错误
本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。
S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x…y]是空串。t[x…y]同理。
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 202;
string s, t ;
int pre[max1], suf[max1]
int main() {
cin＞＞s＞＞t；
int slen =s. length(), tlen= t. length();
for (int I = 0 ,j = 0 ; i＜ slen; ++i) {
if (j＜ tlen&&s[i]t[j] ) ++j;
pre[i] = j;// t[0…j-1]是s[0…i]的子序列
}
for (int I = slen -1 ,j= tlen -1; I ＞=0；–i) {
if(j＞=0&& s[i] == t [j]) –j;
suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列
}
suf[slen] = tlen -1;
int ans = 0;
for （int i=0, j=0, tmp=o; i＜=slen; ++i）{
while（j＜=slen && tmp ＞=suf[j] + 1） ++j；
ans =max(ans, j – I – 1);
tmp = pre[i];
}
cout ＜＜ans ＜＜ end1;
return 0;
}
提示：
t[0…pre[i]-1]是s[0…i]的子序列；
t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。
30、 （2分）程序运行到第23行时，“j-i-1”一定不小于0。（ ）
A 正确
B 错误
本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。
S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x…y]是空串。t[x…y]同理。
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 202;
string s, t ;
int pre[max1], suf[max1]
int main() {
cin＞＞s＞＞t；
int slen =s. length(), tlen= t. length();
for (int I = 0 ,j = 0 ; i＜ slen; ++i) {
if (j＜ tlen&&s[i]t[j] ) ++j;
pre[i] = j;// t[0…j-1]是s[0…i]的子序列
}
for (int I = slen -1 ,j= tlen -1; I ＞=0；–i) {
if(j＞=0&& s[i] == t [j]) –j;
suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列
}
suf[slen] = tlen -1;
int ans = 0;
for （int i=0, j=0, tmp=o; i＜=slen; ++i）{
while（j＜=slen && tmp ＞=suf[j] + 1） ++j；
ans =max(ans, j – I – 1);
tmp = pre[i];
}
cout ＜＜ans ＜＜ end1;
return 0;
}
提示：
t[0…pre[i]-1]是s[0…i]的子序列；
t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。
31、 （2分）当t是s的子序列时，pre数组和suf数组满足：对任意0≤i＜slen，pre[i]＞suf[i+1]+1。( )
A 正确
B 错误
七、单选题
本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。
S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x…y]是空串。t[x…y]同理。
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 202;
string s, t ;
int pre[max1], suf[max1]
int main() {
cin＞＞s＞＞t；
int slen =s. length(), tlen= t. length();
for (int I = 0 ,j = 0 ; i＜ slen; ++i) {
if (j＜ tlen&&s[i]t[j] ) ++j;
pre[i] = j;// t[0…j-1]是s[0…i]的子序列
}
for (int I = slen -1 ,j= tlen -1; I ＞=0；–i) {
if(j＞=0&& s[i] == t [j]) –j;
suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列
}
suf[slen] = tlen -1;
int ans = 0;
for （int i=0, j=0, tmp=o; i＜=slen; ++i）{
while（j＜=slen && tmp ＞=suf[j] + 1） ++j；
ans =max(ans, j – I – 1);
tmp = pre[i];
}
cout ＜＜ans ＜＜ end1;
return 0;
}
提示：
t[0…pre[i]-1]是s[0…i]的子序列；
t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。
32、若tlen=10，输出为0，则slen最小为（ ）
A 10
B 12
C 0
D 1
本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。
S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x…y]是空串。t[x…y]同理。
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 202;
string s, t ;
int pre[max1], suf[max1]
int main() {
cin＞＞s＞＞t；
int slen =s. length(), tlen= t. length();
for (int I = 0 ,j = 0 ; i＜ slen; ++i) {
if (j＜ tlen&&s[i]t[j] ) ++j;
pre[i] = j;// t[0…j-1]是s[0…i]的子序列
}
for (int I = slen -1 ,j= tlen -1; I ＞=0；–i) {
if(j＞=0&& s[i] == t [j]) –j;
suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列
}
suf[slen] = tlen -1;
int ans = 0;
for （int i=0, j=0, tmp=o; i＜=slen; ++i）{
while（j＜=slen && tmp ＞=suf[j] + 1） ++j；
ans =max(ans, j – I – 1);
tmp = pre[i];
}
cout ＜＜ans ＜＜ end1;
return 0;
}
提示：
t[0…pre[i]-1]是s[0…i]的子序列；
t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。
33、若tlen=10，输出为2，则slen最小为（ ）
A 0
B 10
C 12
D 1
（匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数n（1≤n≤103），以及已有经验值（≤107）。
接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤107），以及学会第i个技术后可获得的经验值（≤104）。
接下来n行。第i行的第一个数mi（0≤mi＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。
下面的程序已O（n2）的时间复杂完成这个问题，试补全程序。
#inclde
using namesoace std；
const int maxn = 1001；
int n；
int cnt [maxn]
int child [maxn] [maxn]；
int unlock[maxn];
int unlock[maxn];
int threshold [maxn],bonus[maxn];
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＜cut[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\n”, ans);
return 0;
}
34、①处应填（ ）
A unlock[i]＜=0
B unlock[i]＞=0
C unlock[i]==0
D unlock[i]==-1
（匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数n（1≤n≤103），以及已有经验值（≤107）。
接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤107），以及学会第i个技术后可获得的经验值（≤104）。
接下来n行。第i行的第一个数mi（0≤mi＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。
下面的程序已O（n2）的时间复杂完成这个问题，试补全程序。
#inclde
using namesoace std；
const int maxn = 1001；
int n；
int cnt [maxn]
int child [maxn] [maxn]；
int unlock[maxn];
int unlock[maxn];
int threshold [maxn],bonus[maxn];
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＜cut[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\n”, ans);
return 0;
}
35、②处应填（ ）
A threshold[i]＞points
B threshold[i]＞=points
C points＞threshold[i]
D points＞=threshold[i]
（匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数n（1≤n≤103），以及已有经验值（≤107）。
接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤107），以及学会第i个技术后可获得的经验值（≤104）。
接下来n行。第i行的第一个数mi（0≤mi＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。
下面的程序已O（n2）的时间复杂完成这个问题，试补全程序。
#inclde
using namesoace std；
const int maxn = 1001；
int n；
int cnt [maxn]
int child [maxn] [maxn]；
int unlock[maxn];
int unlock[maxn];
int threshold [maxn],bonus[maxn];
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＜cut[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\n”, ans);
return 0;
}
36、③处应填（ ）
A、
target = -1
B、
- -cnt[target]
C、
bbonus[target]=0
D points += bonus[target]
（匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数n（1≤n≤103），以及已有经验值（≤107）。
接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤107），以及学会第i个技术后可获得的经验值（≤104）。
接下来n行。第i行的第一个数mi（0≤mi＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。
下面的程序已O（n2）的时间复杂完成这个问题，试补全程序。
#inclde
using namesoace std；
const int maxn = 1001；
int n；
int cnt [maxn]
int child [maxn] [maxn]；
int unlock[maxn];
int unlock[maxn];
int threshold [maxn],bonus[maxn];
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＜cut[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\n”, ans);
return 0;
}
37、④处应填（ ）
A cnt [child[target][i]] -=1
B cnt [child[target][i]] =0
C unlock[child[target][i]] -= 1
D unlock[child[target][i]] =0
（匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数n（1≤n≤103），以及已有经验值（≤107）。
接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤107），以及学会第i个技术后可获得的经验值（≤104）。
接下来n行。第i行的第一个数mi（0≤mi＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。
下面的程序已O（n2）的时间复杂完成这个问题，试补全程序。
#inclde
using namesoace std；
const int maxn = 1001；
int n；
int cnt [maxn]
int child [maxn] [maxn]；
int unlock[maxn];
int unlock[maxn];
int threshold [maxn],bonus[maxn];
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＜cut[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\n”, ans);
return 0;
}
38、⑤处应填（ ）
A unlock[i] = cnt[i]
B unlock[i] =m
C unlock[i] = 0
D unlock[i] =-1
(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则，第i条规则为：如果剩余石子的个数大于等于a[i]且大于等于b[il， 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子， 而他无法按照任何规则取走石子，那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数n（1≤n≤64），以及石子个数m（≤10^7）。
接下来n行。第i行有两个正整数a[i]和b[i]（1≤a[i]≤10^7，1≤b[i]≤64）
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i]不超过64，所以可以使用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 (a[i] > a[j]) {
swap(a[i],a[j]);
swap(b[i],b[j]);
}
status = ___(1)___;
trans = 0;
for(int i = 1, j = 0; i <= m; ++i) {
while (j < n && ___(2)___) {
___(3)___
++j;
}
win = ___(4)___;
___(5)___;
}
puts(win ? "Win" : "Loss");
return 0;
}
39、①处应填（）
A 0
B ~0u11
C ~0u11^1
D 1
(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则，第i条规则为：如果剩余石子的个数大于等于a[i]且大于等于b[il， 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子， 而他无法按照任何规则取走石子，那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数n（1≤n≤64），以及石子个数m（≤10^7）。
接下来n行。第i行有两个正整数a[i]和b[i]（1≤a[i]≤10^7，1≤b[i]≤64）
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i]不超过64，所以可以使用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 (a[i] > a[j]) {
swap(a[i],a[j]);
swap(b[i],b[j]);
}
status = ___(1)___;
trans = 0;
for(int i = 1, j = 0; i <= m; ++i) {
while (j < n && ___(2)___) {
___(3)___
++j;
}
win = ___(4)___;
___(5)___;
}
puts(win ? "Win" : "Loss");
return 0;
}
40、②处应填（）
A a[j]<i
B a[j]==i
C a[j]!=i
D a[j]>i
(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则，第i条规则为：如果剩余石子的个数大于等于a[i]且大于等于b[il， 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子， 而他无法按照任何规则取走石子，那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数n（1≤n≤64），以及石子个数m（≤10^7）。
接下来n行。第i行有两个正整数a[i]和b[i]（1≤a[i]≤10^7，1≤b[i]≤64）
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i]不超过64，所以可以使用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 (a[i] > a[j]) {
swap(a[i],a[j]);
swap(b[i],b[j]);
}
status = ___(1)___;
trans = 0;
for(int i = 1, j = 0; i <= m; ++i) {
while (j < n && ___(2)___) {
___(3)___
++j;
}
win = ___(4)___;
___(5)___;
}
puts(win ? "Win" : "Loss");
return 0;
}
41、③处应填（）
A 
B 
C 
D 
(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则，第i条规则为：如果剩余石子的个数大于等于a[i]且大于等于b[il， 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子， 而他无法按照任何规则取走石子，那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数n（1≤n≤64），以及石子个数m（≤10^7）。
接下来n行。第i行有两个正整数a[i]和b[i]（1≤a[i]≤10^7，1≤b[i]≤64）
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i]不超过64，所以可以使用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 (a[i] > a[j]) {
swap(a[i],a[j]);
swap(b[i],b[j]);
}
status = ___(1)___;
trans = 0;
for(int i = 1, j = 0; i <= m; ++i) {
while (j < n && ___(2)___) {
___(3)___
++j;
}
win = ___(4)___;
___(5)___;
}
puts(win ? "Win" : "Loss");
return 0;
}
42、④处应填（）
A 
B 
C 
D 
(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则，第i条规则为：如果剩余石子的个数大于等于a[i]且大于等于b[il， 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子， 而他无法按照任何规则取走石子，那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法？
输入第一行有两个正整数，分别为规则个数n（1≤n≤64），以及石子个数m（≤10^7）。
接下来n行。第i行有两个正整数a[i]和b[i]（1≤a[i]≤10^7，1≤b[i]≤64）
如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”
提示：
可以使用动态规划解决这个问题。由于b[i]不超过64，所以可以使用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 (a[i] > a[j]) {
swap(a[i],a[j]);
swap(b[i],b[j]);
}
status = ___(1)___;
trans = 0;
for(int i = 1, j = 0; i <= m; ++i) {
while (j < n && ___(2)___) {
___(3)___
++j;
}
win = ___(4)___;
___(5)___;
}
puts(win ? "Win" : "Loss");
return 0;
}
43、⑤处应填（）
A 
B 
C 
D 
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
