全部知识点
#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。
#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] 的范围内
本题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
（匠人的自我修养）一个匠人决定要学习 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;
}① 处应填（ ）
在内存储器中每个存储单元都被赋予一个唯一的序号，称为（ ）。
编译器的主要功能是（ ）。
设x = true，y = true，z = false，以下逻辑运算表达式值为真的是（ ）。
现有一张分辨率为 2048×1024 像素的 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（ ）
冒泡排序算法的伪代码如下：
输入：数组 L，n ≥ 1。输出：按非递减顺序排序的 L。 算法 BubbleSort： 1. FLAG ← n // 标记被交换的最后元素位置 2. while FLAG > 1 do 3. k ← FLAG - 1 4. FLAG ← 1 5. for j = 1 to k do 6. if L(j) > L(j+1) then do 7. L(j) ↔ L(j+1) 8. FLAG ← j
对 n 个数用以上冒泡排序算法进行排序，最少需要比较多少次？（ ）
设 A 是 n 个实数的数组，考虑下面的递归算法：
XYZ(A[1..n]) 1) if n=1 then return A[1] 2) else temp ← XYZ(A[1..n-1]) 3) if temp < A[n] 4) then return temp 5) else return A[n]
链表不具有的特点是（ ）。
有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
二进制数 1011 转换成十进制数是（ ）
五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法？
下图中所使用的数据结构是（ ）。
独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（ ）。
干支纪年法是中国传统的纪年方法，由 10 个天干和 12 个地支组合成 60 个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。
天干=（公历年份）除以 10 所的余数
地支=（公历年份）除以 12 所的余数
例如，今年是 2020 年，2020 除以 10 余数为 0，查表为“庚”；2020 除以 12，余数为 4，查表为“子”，所以今年是庚子年。
请问 1949 年的天干地支是（ ）
10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。
有五副不同颜色的手套（共 10 只手套，每副手套左右手各 1 只），一次性从中取 6 只手套，请问恰好能配成两副手套的不同取法有（ ）种。