编程考试试卷

最新题目 更多

•    (最大值之和)给定整数序列ao,a₁,a₂……an,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤10⁵和1≤ai≤108。一个序列的非空连续子序列可以用两个下标I和r(其中0≤l≤r≤n)表示，对应的序列为ai,ai+1,……ar。两个非空连续子序列不同，当且仅当下标不同。例如，当原序列为[1,2,1,2]  时，   要计算子序 列[1],[2],[1],[2],[1,2],[2,1],[1,2],[1,2,1],[2,1,2],[1,2,1,2]的最大值之和，答案为18。注意[1,1]和[2,2]虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法，时间复杂度O(n log n).尝试补全程序#include <iostream> #include <algorithm> #include <vector>04 const int MAXN = 100000; int n; int a[MAXN]; long long ans; void solve(int l, int r){ if(1+ 1 == r){  ans += a[1];  return; } int mid =(1+ r)>>1; std::vector<int> pre(a + mid, a +r); for(int i =1; i<r - mid;++i)①; std::vector<long long> sum(r - mid + 1); for(int i =0; i<r -mid;++i)sum[i+1]= sum[i]+pre[i]; for(int i = mid - 1,j = mid,max =0; i >=l;--i){  while(j<r &&②)++j;  max = std::max(max,a[i]);  ans +=③;  ans +=④; } solve(1,mid); solve(mid,r); } int main(){32 std::cin >> n; for(int i =0; i<n;++i)std::cin >> a[i]; ⑤;  std::cout << ans << std::endl;  return o; }⑤处应填()
•    (最大值之和)给定整数序列ao,a₁,a₂……an,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤10⁵和1≤ai≤108。一个序列的非空连续子序列可以用两个下标I和r(其中0≤l≤r≤n)表示，对应的序列为ai,ai+1,……ar。两个非空连续子序列不同，当且仅当下标不同。例如，当原序列为[1,2,1,2]  时，   要计算子序 列[1],[2],[1],[2],[1,2],[2,1],[1,2],[1,2,1],[2,1,2],[1,2,1,2]的最大值之和，答案为18。注意[1,1]和[2,2]虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法，时间复杂度O(n log n).尝试补全程序#include <iostream> #include <algorithm> #include <vector>04 const int MAXN = 100000; int n; int a[MAXN]; long long ans; void solve(int l, int r){ if(1+ 1 == r){  ans += a[1];  return; } int mid =(1+ r)>>1; std::vector<int> pre(a + mid, a +r); for(int i =1; i<r - mid;++i)①; std::vector<long long> sum(r - mid + 1); for(int i =0; i<r -mid;++i)sum[i+1]= sum[i]+pre[i]; for(int i = mid - 1,j = mid,max =0; i >=l;--i){  while(j<r &&②)++j;  max = std::max(max,a[i]);  ans +=③;  ans +=④; } solve(1,mid); solve(mid,r); } int main(){32 std::cin >> n; for(int i =0; i<n;++i)std::cin >> a[i]; ⑤;  std::cout << ans << std::endl;  return o; }④处应填()
•    (最大值之和)给定整数序列ao,a₁,a₂……an,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤10⁵和1≤ai≤108。一个序列的非空连续子序列可以用两个下标I和r(其中0≤l≤r≤n)表示，对应的序列为ai,ai+1,……ar。两个非空连续子序列不同，当且仅当下标不同。例如，当原序列为[1,2,1,2]  时，   要计算子序 列[1],[2],[1],[2],[1,2],[2,1],[1,2],[1,2,1],[2,1,2],[1,2,1,2]的最大值之和，答案为18。注意[1,1]和[2,2]虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法，时间复杂度O(n log n).尝试补全程序#include <iostream> #include <algorithm> #include <vector>04 const int MAXN = 100000; int n; int a[MAXN]; long long ans; void solve(int l, int r){ if(1+ 1 == r){  ans += a[1];  return; } int mid =(1+ r)>>1; std::vector<int> pre(a + mid, a +r); for(int i =1; i<r - mid;++i)①; std::vector<long long> sum(r - mid + 1); for(int i =0; i<r -mid;++i)sum[i+1]= sum[i]+pre[i]; for(int i = mid - 1,j = mid,max =0; i >=l;--i){  while(j<r &&②)++j;  max = std::max(max,a[i]);  ans +=③;  ans +=④; } solve(1,mid); solve(mid,r); } int main(){32 std::cin >> n; for(int i =0; i<n;++i)std::cin >> a[i]; ⑤;  std::cout << ans << std::endl;  return o; }③处应填()
•    (最大值之和)给定整数序列ao,a₁,a₂……an,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤10⁵和1≤ai≤108。一个序列的非空连续子序列可以用两个下标I和r(其中0≤l≤r≤n)表示，对应的序列为ai,ai+1,……ar。两个非空连续子序列不同，当且仅当下标不同。例如，当原序列为[1,2,1,2]  时，   要计算子序 列[1],[2],[1],[2],[1,2],[2,1],[1,2],[1,2,1],[2,1,2],[1,2,1,2]的最大值之和，答案为18。注意[1,1]和[2,2]虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法，时间复杂度O(n log n).尝试补全程序#include <iostream> #include <algorithm> #include <vector>04 const int MAXN = 100000; int n; int a[MAXN]; long long ans; void solve(int l, int r){ if(1+ 1 == r){  ans += a[1];  return; } int mid =(1+ r)>>1; std::vector<int> pre(a + mid, a +r); for(int i =1; i<r - mid;++i)①; std::vector<long long> sum(r - mid + 1); for(int i =0; i<r -mid;++i)sum[i+1]= sum[i]+pre[i]; for(int i = mid - 1,j = mid,max =0; i >=l;--i){  while(j<r &&②)++j;  max = std::max(max,a[i]);  ans +=③;  ans +=④; } solve(1,mid); solve(mid,r); } int main(){32 std::cin >> n; for(int i =0; i<n;++i)std::cin >> a[i]; ⑤;  std::cout << ans << std::endl;  return o; }②处应填（）
•    (最大值之和)给定整数序列ao,a₁,a₂……an,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤10⁵和1≤ai≤108。一个序列的非空连续子序列可以用两个下标I和r(其中0≤l≤r≤n)表示，对应的序列为ai,ai+1,……ar。两个非空连续子序列不同，当且仅当下标不同。例如，当原序列为[1,2,1,2]  时，   要计算子序 列[1],[2],[1],[2],[1,2],[2,1],[1,2],[1,2,1],[2,1,2],[1,2,1,2]的最大值之和，答案为18。注意[1,1]和[2,2]虽然是原序列的子序列，但不是连续子序列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子序列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法，时间复杂度O(n log n).尝试补全程序#include <iostream> #include <algorithm> #include <vector>04 const int MAXN = 100000; int n; int a[MAXN]; long long ans; void solve(int l, int r){ if(1+ 1 == r){  ans += a[1];  return; } int mid =(1+ r)>>1; std::vector<int> pre(a + mid, a +r); for(int i =1; i<r - mid;++i)①; std::vector<long long> sum(r - mid + 1); for(int i =0; i<r -mid;++i)sum[i+1]= sum[i]+pre[i]; for(int i = mid - 1,j = mid,max =0; i >=l;--i){  while(j<r &&②)++j;  max = std::max(max,a[i]);  ans +=③;  ans +=④; } solve(1,mid); solve(mid,r); } int main(){32 std::cin >> n; for(int i =0; i<n;++i)std::cin >> a[i]; ⑤;  std::cout << ans << std::endl;  return o; }①处应填（）
•    (第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。试补全程序。#include <iostream> #include <algorithm> #include <vector> const int MAXN = 100000; constlonglongLIM=100000000000000000011; int n,m,deg[MAXN]; std::vector<int> E[MAXN]; long long k,f[MAXN]; int next(std::vector<int>cand,long long &k){ std::sort(cand.begin(),cand.end()); for(int u : cand){   if (①)return u;   k -= f[u]; }  return -1; } int main(){ std::cin>>n>>m>>k; for(inti=0;i<m;++i){  int u, v;  std::cin >>u >> v;//一条从u到v的边  E[u].push_back(v);  ++deg[v]; }  std::vector<int> Q; for(inti=0;i<n;++i)  if (!deg[i])Q.push_back(i); for(inti=0;i<n;++i){  int u = Q[i];  for (int v : E[u]){  if (②)Q.push_back(v);  --deg[v];  } }  std::reverse(Q.begin(), Q.end());  for(int u : Q){  f[u]= 1;  for(int v:E[u])f[u]=③; }  int u = next(Q,k);  std::cout << u << std::endl; while(④){  ⑤;  u = next(E[u],k);  std::cout << u << std::endl; }  return 0; }⑤处应填(   )
•    (第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。试补全程序。#include <iostream> #include <algorithm> #include <vector> const int MAXN = 100000; constlonglongLIM=100000000000000000011; int n,m,deg[MAXN]; std::vector<int> E[MAXN]; long long k,f[MAXN]; int next(std::vector<int>cand,long long &k){ std::sort(cand.begin(),cand.end()); for(int u : cand){   if (①)return u;   k -= f[u]; }  return -1; } int main(){ std::cin>>n>>m>>k; for(inti=0;i<m;++i){  int u, v;  std::cin >>u >> v;//一条从u到v的边  E[u].push_back(v);  ++deg[v]; }  std::vector<int> Q; for(inti=0;i<n;++i)  if (!deg[i])Q.push_back(i); for(inti=0;i<n;++i){  int u = Q[i];  for (int v : E[u]){  if (②)Q.push_back(v);  --deg[v];  } }  std::reverse(Q.begin(), Q.end());  for(int u : Q){  f[u]= 1;  for(int v:E[u])f[u]=③; }  int u = next(Q,k);  std::cout << u << std::endl; while(④){  ⑤;  u = next(E[u],k);  std::cout << u << std::endl; }  return 0; }④处应填(    )
•    (第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。试补全程序。#include <iostream> #include <algorithm> #include <vector> const int MAXN = 100000; constlonglongLIM=100000000000000000011; int n,m,deg[MAXN]; std::vector<int> E[MAXN]; long long k,f[MAXN]; int next(std::vector<int>cand,long long &k){ std::sort(cand.begin(),cand.end()); for(int u : cand){   if (①)return u;   k -= f[u]; }  return -1; } int main(){ std::cin>>n>>m>>k; for(inti=0;i<m;++i){  int u, v;  std::cin >>u >> v;//一条从u到v的边  E[u].push_back(v);  ++deg[v]; }  std::vector<int> Q; for(inti=0;i<n;++i)  if (!deg[i])Q.push_back(i); for(inti=0;i<n;++i){  int u = Q[i];  for (int v : E[u]){  if (②)Q.push_back(v);  --deg[v];  } }  std::reverse(Q.begin(), Q.end());  for(int u : Q){  f[u]= 1;  for(int v:E[u])f[u]=③; }  int u = next(Q,k);  std::cout << u << std::endl; while(④){  ⑤;  u = next(E[u],k);  std::cout << u << std::endl; }  return 0; }③处应填(  )
•    (第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。试补全程序。#include <iostream> #include <algorithm> #include <vector> const int MAXN = 100000; constlonglongLIM=100000000000000000011; int n,m,deg[MAXN]; std::vector<int> E[MAXN]; long long k,f[MAXN]; int next(std::vector<int>cand,long long &k){ std::sort(cand.begin(),cand.end()); for(int u : cand){   if (①)return u;   k -= f[u]; }  return -1; } int main(){ std::cin>>n>>m>>k; for(inti=0;i<m;++i){  int u, v;  std::cin >>u >> v;//一条从u到v的边  E[u].push_back(v);  ++deg[v]; }  std::vector<int> Q; for(inti=0;i<n;++i)  if (!deg[i])Q.push_back(i); for(inti=0;i<n;++i){  int u = Q[i];  for (int v : E[u]){  if (②)Q.push_back(v);  --deg[v];  } }  std::reverse(Q.begin(), Q.end());  for(int u : Q){  f[u]= 1;  for(int v:E[u])f[u]=③; }  int u = next(Q,k);  std::cout << u << std::endl; while(④){  ⑤;  u = next(E[u],k);  std::cout << u << std::endl; }  return 0; }②处应填(   )
•    (第k小路径)给定一张.个点.条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列"字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n.m≤105和1≤k≤1018。在程序中，我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。试补全程序。#include <iostream> #include <algorithm> #include <vector> const int MAXN = 100000; constlonglongLIM=100000000000000000011; int n,m,deg[MAXN]; std::vector<int> E[MAXN]; long long k,f[MAXN]; int next(std::vector<int>cand,long long &k){ std::sort(cand.begin(),cand.end()); for(int u : cand){   if (①)return u;   k -= f[u]; }  return -1; } int main(){ std::cin>>n>>m>>k; for(inti=0;i<m;++i){  int u, v;  std::cin >>u >> v;//一条从u到v的边  E[u].push_back(v);  ++deg[v]; }  std::vector<int> Q; for(inti=0;i<n;++i)  if (!deg[i])Q.push_back(i); for(inti=0;i<n;++i){  int u = Q[i];  for (int v : E[u]){  if (②)Q.push_back(v);  --deg[v];  } }  std::reverse(Q.begin(), Q.end());  for(int u : Q){  f[u]= 1;  for(int v:E[u])f[u]=③; }  int u = next(Q,k);  std::cout << u << std::endl; while(④){  ⑤;  u = next(E[u],k);  std::cout << u << std::endl; }  return 0; }①处应填(    )
•    2023年CSP-S1阅读程序题3：#include <vector> #include <algorithm> #include <iostream> using namespace std; bool fo(vector<int>& a, int m, int k){  int s =0; for(int i =0,j =0; i<a.size(); i++){  while (a[i]- a[j]>m)j++;  s += i -j; }  return s >= k; } int f(vector<int>& a, int k){  sort(a.begin(), a.end());1  int g =0;  int h = a.back()- a[0]; while(g< h){   int m = g+(h -g)/ 2; if(fo(a,m, k)){  h = m; } else {  g = m+1;27 }28 }29  return g;31}32  int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){  cin >> a[i];  }  cout<< f(a,k)<< endl;  return 0 }假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：当输入为“582-538-12”时，输出为（）。
•    2023年CSP-S1阅读程序题3：#include <vector> #include <algorithm> #include <iostream> using namespace std; bool fo(vector<int>& a, int m, int k){  int s =0; for(int i =0,j =0; i<a.size(); i++){  while (a[i]- a[j]>m)j++;  s += i -j; }  return s >= k; } int f(vector<int>& a, int k){  sort(a.begin(), a.end());1  int g =0;  int h = a.back()- a[0]; while(g< h){   int m = g+(h -g)/ 2; if(fo(a,m, k)){  h = m; } else {  g = m+1;27 }28 }29  return g;31}32  int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){  cin >> a[i];  }  cout<< f(a,k)<< endl;  return 0 }假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：将第10行中的“>”替换为“>=”，那么原输出与现输出的大小关系为（）。
•    2023年CSP-S1阅读程序题3：#include <vector> #include <algorithm> #include <iostream> using namespace std; bool fo(vector<int>& a, int m, int k){  int s =0; for(int i =0,j =0; i<a.size(); i++){  while (a[i]- a[j]>m)j++;  s += i -j; }  return s >= k; } int f(vector<int>& a, int k){  sort(a.begin(), a.end());1  int g =0;  int h = a.back()- a[0]; while(g< h){   int m = g+(h -g)/ 2; if(fo(a,m, k)){  h = m; } else {  g = m+1;27 }28 }29  return g;31}32  int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){  cin >> a[i];  }  cout<< f(a,k)<< endl;  return 0 }假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（）。
•    2023年CSP-S1阅读程序题3：#include <vector> #include <algorithm> #include <iostream> using namespace std; bool fo(vector<int>& a, int m, int k){  int s =0; for(int i =0,j =0; i<a.size(); i++){  while (a[i]- a[j]>m)j++;  s += i -j; }  return s >= k; } int f(vector<int>& a, int k){  sort(a.begin(), a.end());1  int g =0;  int h = a.back()- a[0]; while(g< h){   int m = g+(h -g)/ 2; if(fo(a,m, k)){  h = m; } else {  g = m+1;27 }28 }29  return g;31}32  int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){  cin >> a[i];  }  cout<< f(a,k)<< endl;  return 0 }假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：当输入为“572-451-3”，输出为“5”。（）
•    2023年CSP-S1阅读程序题3：#include <vector> #include <algorithm> #include <iostream> using namespace std; bool fo(vector<int>& a, int m, int k){  int s =0; for(int i =0,j =0; i<a.size(); i++){  while (a[i]- a[j]>m)j++;  s += i -j; }  return s >= k; } int f(vector<int>& a, int k){  sort(a.begin(), a.end());1  int g =0;  int h = a.back()- a[0]; while(g< h){   int m = g+(h -g)/ 2; if(fo(a,m, k)){  h = m; } else {  g = m+1;27 }28 }29  return g;31}32  int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){  cin >> a[i];  }  cout<< f(a,k)<< endl;  return 0 }假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：将第22行的“g+(h-g)/2”改为“(h+g)>>1”，输出不变。（）
•    2023年CSP-S1阅读程序题3：#include <vector> #include <algorithm> #include <iostream> using namespace std; bool fo(vector<int>& a, int m, int k){  int s =0; for(int i =0,j =0; i<a.size(); i++){  while (a[i]- a[j]>m)j++;  s += i -j; }  return s >= k; } int f(vector<int>& a, int k){  sort(a.begin(), a.end());1  int g =0;  int h = a.back()- a[0]; while(g< h){   int m = g+(h -g)/ 2; if(fo(a,m, k)){  h = m; } else {  g = m+1;27 }28 }29  return g;31}32  int main(){34 int n,k;35 cin >> n >> k;36 vector<int> a(n,0);37 for(int i =o; i<n; i++){  cin >> a[i];  }  cout<< f(a,k)<< endl;  return 0 }假设输入总是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判断题和单选题：将第24行的“m”改为“m-1”输出有可能不变，而剩下情况为少1。（）
•    2023年CSP-S1阅读程序题2：#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; long long solve1(int n){   vector<bool> p(n+1, true);   vector<long long> f(n+1,0),g(n+1,0);   f[1]= 1;   for (int i = 2; i*i <= n; i++){     if (p[i]){     vector<int> d;     for(int k = i;k <=n; k *= i)d.push_back(k);     reverse(d.begin(),d.end());     for (int k:d){for (int j =k; j<=n;j += k){ 　　　　　　if (p[j]){ 　　　　　　p[j]= false; 　　　　　　f[j]= i; 　　　　　　g[j]= k; 　　　　　　} 　　　　　} 　　　　}　　 　　} }  for (int i = sqrt(n)+ 1; i <= n; i++){   if (p[i]){   f[i]= i;   g[i]= i;   } }  long long sum = 1;   for(int i = 2; i <= n; i++){    f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);     sum += f[i];    }    return sum; }  long long solve2(int n){   long long sum = 0;   for(int i= 1; i <= n; i++){    sum += i*(n / i);   }    return sum; } int main(){    int n;    cin >> n;    cout << solve1(n)<< endl;    cout << solve2(n)<< endl;    return 0; }假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：输入为“5”时，输出的第二行为（）。
•    2023年CSP-S1阅读程序题2：#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; long long solve1(int n){   vector<bool> p(n+1, true);   vector<long long> f(n+1,0),g(n+1,0);   f[1]= 1;   for (int i = 2; i*i <= n; i++){     if (p[i]){     vector<int> d;     for(int k = i;k <=n; k *= i)d.push_back(k);     reverse(d.begin(),d.end());     for (int k:d){for (int j =k; j<=n;j += k){ 　　　　　　if (p[j]){ 　　　　　　p[j]= false; 　　　　　　f[j]= i; 　　　　　　g[j]= k; 　　　　　　} 　　　　　} 　　　　}　　 　　} }  for (int i = sqrt(n)+ 1; i <= n; i++){   if (p[i]){   f[i]= i;   g[i]= i;   } }  long long sum = 1;   for(int i = 2; i <= n; i++){    f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);     sum += f[i];    }    return sum; }  long long solve2(int n){   long long sum = 0;   for(int i= 1; i <= n; i++){    sum += i*(n / i);   }    return sum; } int main(){    int n;    cin >> n;    cout << solve1(n)<< endl;    cout << solve2(n)<< endl;    return 0; }假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：solve(2)的时间复杂度为（）。
•    2023年CSP-S1阅读程序题2：#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; long long solve1(int n){   vector<bool> p(n+1, true);   vector<long long> f(n+1,0),g(n+1,0);   f[1]= 1;   for (int i = 2; i*i <= n; i++){     if (p[i]){     vector<int> d;     for(int k = i;k <=n; k *= i)d.push_back(k);     reverse(d.begin(),d.end());     for (int k:d){for (int j =k; j<=n;j += k){ 　　　　　　if (p[j]){ 　　　　　　p[j]= false; 　　　　　　f[j]= i; 　　　　　　g[j]= k; 　　　　　　} 　　　　　} 　　　　}　　 　　} }  for (int i = sqrt(n)+ 1; i <= n; i++){   if (p[i]){   f[i]= i;   g[i]= i;   } }  long long sum = 1;   for(int i = 2; i <= n; i++){    f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);     sum += f[i];    }    return sum; }  long long solve2(int n){   long long sum = 0;   for(int i= 1; i <= n; i++){    sum += i*(n / i);   }    return sum; } int main(){    int n;    cin >> n;    cout << solve1(n)<< endl;    cout << solve2(n)<< endl;    return 0; }假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：solve1(n)的时间复杂度为(）。
•    2023年CSP-S1阅读程序题2：#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; long long solve1(int n){   vector<bool> p(n+1, true);   vector<long long> f(n+1,0),g(n+1,0);   f[1]= 1;   for (int i = 2; i*i <= n; i++){     if (p[i]){     vector<int> d;     for(int k = i;k <=n; k *= i)d.push_back(k);     reverse(d.begin(),d.end());     for (int k:d){for (int j =k; j<=n;j += k){ 　　　　　　if (p[j]){ 　　　　　　p[j]= false; 　　　　　　f[j]= i; 　　　　　　g[j]= k; 　　　　　　} 　　　　　} 　　　　}　　 　　} }  for (int i = sqrt(n)+ 1; i <= n; i++){   if (p[i]){   f[i]= i;   g[i]= i;   } }  long long sum = 1;   for(int i = 2; i <= n; i++){    f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);     sum += f[i];    }    return sum; }  long long solve2(int n){   long long sum = 0;   for(int i= 1; i <= n; i++){    sum += i*(n / i);   }    return sum; } int main(){    int n;    cin >> n;    cout << solve1(n)<< endl;    cout << solve2(n)<< endl;    return 0; }假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：当输入为“1000”时，输出的第一行与第二行相等。（）
•    2023年CSP-S1阅读程序题2：#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; long long solve1(int n){   vector<bool> p(n+1, true);   vector<long long> f(n+1,0),g(n+1,0);   f[1]= 1;   for (int i = 2; i*i <= n; i++){     if (p[i]){     vector<int> d;     for(int k = i;k <=n; k *= i)d.push_back(k);     reverse(d.begin(),d.end());     for (int k:d){for (int j =k; j<=n;j += k){ 　　　　　　if (p[j]){ 　　　　　　p[j]= false; 　　　　　　f[j]= i; 　　　　　　g[j]= k; 　　　　　　} 　　　　　} 　　　　}　　 　　} }  for (int i = sqrt(n)+ 1; i <= n; i++){   if (p[i]){   f[i]= i;   g[i]= i;   } }  long long sum = 1;   for(int i = 2; i <= n; i++){    f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);     sum += f[i];    }    return sum; }  long long solve2(int n){   long long sum = 0;   for(int i= 1; i <= n; i++){    sum += i*(n / i);   }    return sum; } int main(){    int n;    cin >> n;    cout << solve1(n)<< endl;    cout << solve2(n)<< endl;    return 0; }假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：当输入为“10”时，输出的第一行大于第二行。（）
•    2023年CSP-S1阅读程序题2：#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; long long solve1(int n){   vector<bool> p(n+1, true);   vector<long long> f(n+1,0),g(n+1,0);   f[1]= 1;   for (int i = 2; i*i <= n; i++){     if (p[i]){     vector<int> d;     for(int k = i;k <=n; k *= i)d.push_back(k);     reverse(d.begin(),d.end());     for (int k:d){for (int j =k; j<=n;j += k){ 　　　　　　if (p[j]){ 　　　　　　p[j]= false; 　　　　　　f[j]= i; 　　　　　　g[j]= k; 　　　　　　} 　　　　　} 　　　　}　　 　　} }  for (int i = sqrt(n)+ 1; i <= n; i++){   if (p[i]){   f[i]= i;   g[i]= i;   } }  long long sum = 1;   for(int i = 2; i <= n; i++){    f[i]= f[i / g[i]]*(g[i]* f[i]- 1)/(f[i]- 1);     sum += f[i];    }    return sum; }  long long solve2(int n){   long long sum = 0;   for(int i= 1; i <= n; i++){    sum += i*(n / i);   }    return sum; } int main(){    int n;    cin >> n;    cout << solve1(n)<< endl;    cout << solve2(n)<< endl;    return 0; }假设输入的n是不超过1000000的自然数，完成下面的判断题和单选题：将第15行删去，输出不变。（）
•    2023年CSP-S1阅读程序题1：#include <iostream> using namespace std; unsigned short f(unsigned short x){  x ^= x << 6;  x ^= x >>8;  return x; } int main(){  unsigned short x;  cin >> x;  unsigned short y = f(x);  cout << y <<endl;  return 0; }假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：当输入为“64”时，执行完第5行后x的值为(）。
•    2023年CSP-S1阅读程序题1：#include <iostream> using namespace std; unsigned short f(unsigned short x){  x ^= x << 6;  x ^= x >>8;  return x; } int main(){  unsigned short x;  cin >> x;  unsigned short y = f(x);  cout << y <<endl;  return 0; }假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：当输入为“512”时，输出为()。
•    2023年CSP-S1阅读程序题1：#include <iostream> using namespace std; unsigned short f(unsigned short x){  x ^= x << 6;  x ^= x >>8;  return x; } int main(){  unsigned short x;  cin >> x;  unsigned short y = f(x);  cout << y <<endl;  return 0; }假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：当输入为“1”时，输出为“64”。（）
•    2023年CSP-S1阅读程序题1：#include <iostream> using namespace std; unsigned short f(unsigned short x){  x ^= x << 6;  x ^= x >>8;  return x; } int main(){  unsigned short x;  cin >> x;  unsigned short y = f(x);  cout << y <<endl;  return 0; }假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：当输入为“65535”时，输出为“63”。（）
•    2023年CSP-S1阅读程序题1：#include <iostream> using namespace std; unsigned short f(unsigned short x){  x ^= x << 6;  x ^= x >>8;  return x; } int main(){  unsigned short x;  cin >> x;  unsigned short y = f(x);  cout << y <<endl;  return 0; }假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：将f函数的输入参数的类型改为 unsigned int，程序的输出不变。（）
•    2023年CSP-S1阅读程序题1：#include <iostream> using namespace std; unsigned short f(unsigned short x){  x ^= x << 6;  x ^= x >>8;  return x; } int main(){  unsigned short x;  cin >> x;  unsigned short y = f(x);  cout << y <<endl;  return 0; }假设输入的x是不超过65535的自然数，完成下面的判断题和单选题：当输入非零时，输出一定不为零。（）
•    现在用如下代码来计算xn,其时间复杂度为（）。double quick_power(double x, unsigned n){ 　　　if(n == 0)return 1; 　　　if(n == 1)return x; 　　　return quick_power(x, n / 2) 　　　　　　　* quick_power(x, n / 2) 　　　　　　　*((n&1)?x:1); }
•    若，定义；其中对于给定自然数n0，存在序列n0,n1,n2,...,nm,其中对于都有ni=f(ni-1)且nm=nm-1，称nm为n0关于f的不动点，问在10016至1A016中，关于f的不动点为9的自然数个数为（  ）。