CSP-S1提高级初赛试卷[2023]

第1题

在linux 系统终端中，以下哪个命令用于创建一个新的目录?（）

第2题

0,1,2,3,4 中选取4个数字，能组成（）个不同四位数。(注: 最小的四位数是 1000最大的四位数是9999)

第3题

假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 m=O(n)的稀疏图而言，下面的四个选项，哪一项的渐进时间复杂度最小？（）

第4题

假设有n 根柱子，需要按照以下规则依次放置编号为 1,2,3..的圆柱：每根柱子的底部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4个根子时，最多可以放置（）个圆环。

第5题

以下对数据结构表述不恰当的一项是？（）

第6题

以下连通无向图中，（）一定可以用不超过两种颜色进行染色。

第7题

最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下：给定两个序列X={x₁,x₂,x₃,…,x_m}和Y={y₁,y₂,y₃,…,y_n},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z={z₁,z₂,z₃,…,z_k},使得序列Z既是序列X的子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最大的。(注：序列A是序列B的子序列，当且仅当在保持序列B元素顺序的情况下，从序列B中删除若干个元素，可以使得剩余的元素构成序列A。)则序列“ABCAAAABA”和“ABABCBABA”的最长公共子序列长度为（）

第8题

一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出x点，得到2x元；第二次掷出y点，当y=x时玩家会失去之前得到的2x元，而当y≠x时玩家能保住第一次获得的2x元。上述x,y∈{1,2,3,4,5,6}。例如：玩家第一次掷出3点得到6元后，但第二次再次掷出3点，会失去之前得到的6元，玩家最终收益为0元；如果玩家第一次掷出3点、第二次掷出4点，则最终收益是6元。假设骰子掷出任意一点的概率均为1/6,玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少?（）

第9题

假设我们有以下的C++代码：

int  a=5,b=3,c=4;
bool res = a & b ||c ^ b && a | c;

请问，res的值是什么?（）

提示：在C++中，逻辑运算的优先级从高到低依次为：逻辑非(!)、逻辑与(&&)、逻辑或(I)。位运算的优先级从高到低依次为：位非(~)、位与(&)、位异或(^)、位或(I)。同时，双目位运算的优先级高于双目逻辑运算；逻辑非和位非优先级相同，且高于所有双目运算符。

第10题

假设快速排序算法的输入是一个长度为 n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?（）

第11题

以下哪个命令，能将一个名为”main.cpp“的 C++源文件，编译并生成一个名为”main“的可执行文件?（）

第12题

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数量最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心?（）

第13题

如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

第14题

若，定义；其中对于给定自然数n₀，存在序列n₀,n₁,n₂,...,n_m,其中对于都有n_i=f(n_i-1)且n_m=n_m-1，称n_m为n₀关于f的不动点，问在100₁₆至1A0₁₆中，关于f的不动点为9的自然数个数为（  ）。

第15题

现在用如下代码来计算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);
}

第16题

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的自然数，完成下面的判断题和单选题：

当输入非零时，输出一定不为零。（）

第17题

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，程序的输出不变。（）

第18题

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”。（）

第19题

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”。（）

第20题

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”时，输出为()。

第21题

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的值为(）。

第22题

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行删去，输出不变。（）

第23题

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”时，输出的第一行大于第二行。（）

第24题

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”时，输出的第一行与第二行相等。（）

第25题

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)的时间复杂度为(）。

第26题

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)的时间复杂度为（）。

第27题

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”时，输出的第二行为（）。

第28题

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。（）

第29题

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”，输出不变。（）

第30题

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”。（）

第31题

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函数的时间复杂度为（）。

第32题

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行中的“>”替换为“>=”，那么原输出与现输出的大小关系为（）。

第33题

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”时，输出为（）。

第34题

(第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;
}

①处应填(    )

第35题

(第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;
}

②处应填(   )

第36题

(第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;
}

③处应填(  )

第37题

(第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;
}

④处应填(    )

第38题

(第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;
}

⑤处应填(   )

第39题

(最大值之和)给定整数序列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;
}

①处应填（）

第40题

(最大值之和)给定整数序列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;
}

②处应填（）

第41题

(最大值之和)给定整数序列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;
}

③处应填()

第42题

(最大值之和)给定整数序列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;
}

④处应填()

第43题

(最大值之和)给定整数序列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;
}

⑤处应填()