第1题
若有定义 int a = 7, float x = 2.5, y = 4.7;,则表达式 x + a % 3 * (int) (x + y) % 2 的值是( )
第2题
下列属于图像文件格式的( )
第3题
下面哪个选项是11 1011 1001 0111 和 01 0110 1110 1011进行逻辑或运算的结果( )。
第4题
编译器的作用是 ( )。
第5题
设变量 x 为 float 型且已赋值,下列哪条语句能将 x 中的数值保留到小数点后两位,并将第三位四舍五入 ( )。
第6题
由数字 1, 1, 2, 4, 8, 8组成的不同的 4 位数的个数是 ( )。
第7题
排序的算法很多,若按排序的稳定性和不稳定性分裂,下面算法中 ( ) 是不稳定排序。
第8题
G 是一个非连通无向图(没有重边和自环),共有 28 条边,则该图至少有 ( )。
第9题
一些数字可以颠倒过来看,例如 0、1、8 颠倒过来还是本身,6 颠倒过来是 9,9 颠倒过来看还是 6,其他数字颠倒过来都不构成数字。类似的,一些多位数也可以颠倒过来看,比如 106 颠倒过来是 901。假设某个城市的车牌只由 5 位数字组成,每一位都可以取 0 到 9。请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌,并且车牌上的 5 位数能被 3 整除 ( )。
第10题
一次期末考试,某班有 15 人数学得满分,有 12 人语文得满分,共有 4 人语文、数学都是满分,那么这个班至少有一门满分的同学有多少人 ( )。
第11题
设 A 和 B 是两个长为 n 的有序数组,现在需要将 A 和 B 合并成一个排好序的数组,请问在归并算法中,在最坏情况下至少要做多少次比较( )。
第12题
以下哪个结构可以用来存图 ( )。
第13题
以下哪些算法不属于贪心算法 ( )。
第14题
有一个等比数列,共有奇数项,其中第一项和最后一项分别是 2 和 118098,中间一项是 486,请问以下那个数是可能的公比 ( )。
第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] = ( )
第16题
#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 ", ans); } return 0; }
1)第 16 行输出 ans 时,ans 的值一定大于 i。
第17题
#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 ", ans); } return 0; }
2)程序输出的 ans 小于等于 n。
第18题
#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 ", ans); } return 0; }
3)若将第 12 行的 “<” 改为 “!=” 程序输出的结果不会改变。
第19题
#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 ", ans); } return 0; }
4)当程序执行到第 16 行时,若 ans - i > 2,则 a[i+1]≤a[i]。
第20题
#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 ", ans); } return 0; }
5)若输入的 a 数组是一个严格单调递增的数列,此程序的时间复杂度是
第21题
#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 ", ans); } return 0; }
6)最坏情况下,此程序的时间复杂度为:
第22题
#include <iostream> using namespace 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; }
1)输入的 a 和 b 的值应在 [0,n−1] 的范围内
第23题
#include <iostream> using namespace 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; } 1)输入的 a
2)第 16 行改成 fa[i]=0;,不影响程序运行结果
第24题
#include <iostream> using namespace 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; }
3)若输入的 a 和 b 值均在 [0,n−1] 的范围内,则对于任意 0≤i<n,都有 0≤fa[i]<n。
第25题
#include <iostream> using namespace 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; }
4)若输入的 a 和 b 值均在 [0,n−1] 的范围内,则对于任意 0≤i<n,都有 1≤cnt[i]≤n。
第26题
#include <iostream> using namespace 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; }
5)当 n 等于 50 时,若 a、b 的值都在 [0,49] 的范围内,且在第 25 行时总是不等于 y,那么输出为 ( )
第27题
#include <iostream> using namespace 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; }
6)此程序的时间复杂度是( )
第28题
本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t。特别的,如果s == t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“acd”不是“abcde”的子序列。
S[x..y]表示s[x]…s[y]共 y-x+1y−x+1 个字符构成的字符串,若 x>yx>y 则s[x..y]是空串。t[x..y]同理。
#include <iostream> #include <string> 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= 0; i <= slen; ++i) { while (j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; }
提示:
t[0..pre[i]-1]是s[0..i]的子序列;
t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。
1)程序输出时,suf数组满足:对任意 0≤i<slen,suf[i]≤suf[i+1]。
第29题
本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t。特别的,如果s == t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“acd”不是“abcde”的子序列。
S[x..y]表示s[x]…s[y]共 y-x+1y−x+1 个字符构成的字符串,若 x>yx>y 则s[x..y]是空串。t[x..y]同理。
#include <iostream> #include <string> 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= 0; i <= slen; ++i) { while (j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; }
提示:
t[0..pre[i]-1]是s[0..i]的子序列;
t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。
2)当 t 是 s 的子序列时,输出一定不为 0。
第30题
本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t。特别的,如果s == t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“acd”不是“abcde”的子序列。
S[x..y]表示s[x]…s[y]共 y-x+1y−x+1 个字符构成的字符串,若 x>yx>y 则s[x..y]是空串。t[x..y]同理。
#include <iostream> #include <string> 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= 0; i <= slen; ++i) { while (j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; }
提示:
t[0..pre[i]-1]是s[0..i]的子序列;
t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。
3)程序运行到第 23行时,j - i- 1 一定不小于 0
第31题
本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t。特别的,如果s == t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“acd”不是“abcde”的子序列。
S[x..y]表示s[x]…s[y]共 y-x+1y−x+1 个字符构成的字符串,若 x>yx>y 则s[x..y]是空串。t[x..y]同理。
#include <iostream> #include <string> 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= 0; i <= slen; ++i) { while (j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; }
提示:
t[0..pre[i]-1]是s[0..i]的子序列;
t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。
4)当 t 是 s 的子序列时,pre 数组和 suf 数组满足:对任意 0≤i<slen,pre[i]>suf[i+1]。
第32题
本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t。特别的,如果s == t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“acd”不是“abcde”的子序列。
S[x..y]表示s[x]…s[y]共 y-x+1y−x+1 个字符构成的字符串,若 x>yx>y 则s[x..y]是空串。t[x..y]同理。
#include <iostream> #include <string> 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= 0; i <= slen; ++i) { while (j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; }
提示:
t[0..pre[i]-1]是s[0..i]的子序列;
t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。
5)若 tlen = 10,输出为 0 ,则 slen 最小为:
第33题
本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t。特别的,如果s == t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“acd”不是“abcde”的子序列。
S[x..y]表示s[x]…s[y]共 y-x+1y−x+1 个字符构成的字符串,若 x>yx>y 则s[x..y]是空串。t[x..y]同理。
#include <iostream> #include <string> 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= 0; i <= slen; ++i) { while (j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; }
提示:
t[0..pre[i]-1]是s[0..i]的子序列;
t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。
6)若 tlen = 10, 输出为 2,则 slen 最小为
第34题
(匠人的自我修养)一个匠人决定要学习 n 个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 n(1≤n≤103),以及已有经验值(≤107)。
接下来 n 行。第 i 行的两个整数,分别表示学习第 i 个技术所需的最低经验值 (≤107),以及学会第 i 个技术后可获得的经验值 (≤104)。
接下来 n 行。第 i 行的第一个数 mi(0≤mi<n),表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数,表示第 i 个技术的相关技术编号,输出最多能学会的新技术个数。
下面的程序已 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; }
① 处应填( )
第35题
(匠人的自我修养)一个匠人决定要学习 n 个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 n(1≤n≤103),以及已有经验值(≤107)。
接下来 n 行。第 i 行的两个整数,分别表示学习第 i 个技术所需的最低经验值 (≤107),以及学会第 i 个技术后可获得的经验值 (≤104)。
接下来 n 行。第 i 行的第一个数 mi(0≤mi<n),表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数,表示第 i 个技术的相关技术编号,输出最多能学会的新技术个数。
下面的程序已 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; }
② 处应填( )
第36题
(匠人的自我修养)一个匠人决定要学习 n 个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 n(1≤n≤103),以及已有经验值(≤107)。
接下来 n 行。第 i 行的两个整数,分别表示学习第 i 个技术所需的最低经验值 (≤107),以及学会第 i 个技术后可获得的经验值 (≤104)。
接下来 n 行。第 i 行的第一个数 mi(0≤mi<n),表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数,表示第 i 个技术的相关技术编号,输出最多能学会的新技术个数。
下面的程序已 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; }
③ 处应填( )
第37题
(匠人的自我修养)一个匠人决定要学习 n 个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 n(1≤n≤103),以及已有经验值(≤107)。
接下来 n 行。第 i 行的两个整数,分别表示学习第 i 个技术所需的最低经验值 (≤107),以及学会第 i 个技术后可获得的经验值 (≤104)。
接下来 n 行。第 i 行的第一个数 mi(0≤mi<n),表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数,表示第 i 个技术的相关技术编号,输出最多能学会的新技术个数。
下面的程序已 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; }
④ 处应填( )
第38题
(匠人的自我修养)一个匠人决定要学习 n 个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 n(1≤n≤103),以及已有经验值(≤107)。
接下来 n 行。第 i 行的两个整数,分别表示学习第 i 个技术所需的最低经验值 (≤107),以及学会第 i 个技术后可获得的经验值 (≤104)。
接下来 n 行。第 i 行的第一个数 mi(0≤mi<n),表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数,表示第 i 个技术的相关技术编号,输出最多能学会的新技术个数。
下面的程序已 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; }
⑤处应填( )
第39题
(取石子)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; }
① 处应填( )
第40题
(取石子)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; }
② 处应填( )
第41题
(取石子)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; }
③ 处应填( )
第42题
(取石子)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; }
④ 处应填( )
第43题
(取石子)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; }
⑤处应填( )