第1題

在linux 系統(tǒng)終端中，以下哪個(gè)命令用于創(chuàng)建一個(gè)新的目錄?（）

第2題

0,1,2,3,4 中選取4個(gè)數(shù)字，能組成（）個(gè)不同四位數(shù)。(注: 最小的四位數(shù)是 1000最大的四位數(shù)是9999)

第3題

假設(shè) n 是圖的頂點(diǎn)的個(gè)數(shù)，m 是圖的邊的個(gè)數(shù)，為求解某一問題有下面四種不同時(shí)間復(fù)雜度的算法。對(duì)于 m=O(n)的稀疏圖而言，下面的四個(gè)選項(xiàng)，哪一項(xiàng)的漸進(jìn)時(shí)間復(fù)雜度最?。浚ǎ?/p>

第4題

假設(shè)有n 根柱子，需要按照以下規(guī)則依次放置編號(hào)為 1,2,3..的圓柱：每根柱子的底部固定，頂部可以放入圓環(huán)；每次從柱子頂部放入圓環(huán)時(shí)，需要保證任何兩個(gè)相鄰圓環(huán)的編號(hào)之和是一個(gè)完全平方數(shù)。請(qǐng)計(jì)算當(dāng)有 4個(gè)根子時(shí)，最多可以放置（）個(gè)圓環(huán)。

第5題

以下對(duì)數(shù)據(jù)結(jié)構(gòu)表述不恰當(dāng)?shù)囊豁?xiàng)是？（）

第6題

以下連通無向圖中，（）一定可以用不超過兩種顏色進(jìn)行染色。

第7題

最長公共子序列長度常常用來衡量兩個(gè)序列的相似度。其定義如下：給定兩個(gè)序列X={x₁,x₂,x₃,…,x_m}和Y={y₁,y₂,y₃,…,y_n},最長公共子序列(LCS)問題的目標(biāo)是找到一個(gè)最長的新序列Z={z₁,z₂,z₃,…,z_k},使得序列Z既是序列X的子序列，又是序列Y的子序列，且序列Z的長度k在滿足上述條件的序列里是最大的。(注：序列A是序列B的子序列，當(dāng)且僅當(dāng)在保持序列B元素順序的情況下，從序列B中刪除若干個(gè)元素，可以使得剩余的元素構(gòu)成序列A。)則序列“ABCAAAABA”和“ABABCBABA”的最長公共子序列長度為（）

第8題

一位玩家正在玩一個(gè)特殊的擲骰子的游戲，游戲要求連續(xù)擲兩次骰子，收益規(guī)則如下：玩家第一次擲出x點(diǎn)，得到2x元；第二次擲出y點(diǎn)，當(dāng)y=x時(shí)玩家會(huì)失去之前得到的2x元，而當(dāng)y≠x時(shí)玩家能保住第一次獲得的2x元。上述x,y∈{1,2,3,4,5,6}。例如：玩家第一次擲出3點(diǎn)得到6元后，但第二次再次擲出3點(diǎn)，會(huì)失去之前得到的6元，玩家最終收益為0元；如果玩家第一次擲出3點(diǎn)、第二次擲出4點(diǎn)，則最終收益是6元。假設(shè)骰子擲出任意一點(diǎn)的概率均為1/6,玩家連續(xù)擲兩次骰子后，所有可能情形下收益的平均值是多少?（）

第9題

假設(shè)我們有以下的C++代碼：

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

請(qǐng)問，res的值是什么?（）

提示：在C++中，邏輯運(yùn)算的優(yōu)先級(jí)從高到低依次為：邏輯非(!)、邏輯與(&&)、邏輯或(I)。位運(yùn)算的優(yōu)先級(jí)從高到低依次為：位非(~)、位與(&)、位異或(^)、位或(I)。同時(shí)，雙目位運(yùn)算的優(yōu)先級(jí)高于雙目邏輯運(yùn)算；邏輯非和位非優(yōu)先級(jí)相同，且高于所有雙目運(yùn)算符。

第10題

假設(shè)快速排序算法的輸入是一個(gè)長度為 n 的已排序數(shù)組，且該快速排序算法在分治過程總是選擇第一個(gè)元素作為基準(zhǔn)元素。以下哪個(gè)選項(xiàng)描述的是在這種情況下的快速排序行為?（）

第11題

以下哪個(gè)命令，能將一個(gè)名為”main.cpp“的 C++源文件，編譯并生成一個(gè)名為”main“的可執(zhí)行文件?（）

第12題

在圖論中，樹的重心是樹上的一個(gè)結(jié)點(diǎn)，以該結(jié)點(diǎn)為根時(shí)，使得其所有的子樹中結(jié)點(diǎn)數(shù)最多的子樹的結(jié)點(diǎn)數(shù)量最少。一棵樹可能有多個(gè)重心。請(qǐng)問下面哪種樹一定只有一個(gè)重心?（）

第13題

如圖是一張包含6個(gè)頂點(diǎn)的有向圖，但頂點(diǎn)間不存在拓?fù)湫?。如果要?jiǎng)h除其中一條邊，使這6個(gè)頂點(diǎn)能進(jìn)行拓?fù)渑判颍?qǐng)問總共有多少條邊可以作為候選的被刪除邊？（）

第14題

若，定義；其中對(duì)于給定自然數(shù)n₀，存在序列n₀,n₁,n₂,...,n_m,其中對(duì)于都有n_i=f(n_i-1)且n_m=n_m-1，稱n_m為n₀關(guān)于f的不動(dòng)點(diǎn)，問在100₁₆至1A0₁₆中，關(guān)于f的不動(dòng)點(diǎn)為9的自然數(shù)個(gè)數(shù)為（  ）。

第15題

現(xiàn)在用如下代碼來計(jì)算xn,其時(shí)間復(fù)雜度為（）。

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

假設(shè)輸入的x是不超過65535的自然數(shù)，完成下面的判斷題和單選題：

當(dāng)輸入非零時(shí)，輸出一定不為零。（）

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

假設(shè)輸入的x是不超過65535的自然數(shù)，完成下面的判斷題和單選題：

將f函數(shù)的輸入?yún)?shù)的類型改為 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;
}

假設(shè)輸入的x是不超過65535的自然數(shù)，完成下面的判斷題和單選題：

當(dāng)輸入為“65535”時(shí)，輸出為“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;
}

假設(shè)輸入的x是不超過65535的自然數(shù)，完成下面的判斷題和單選題：

當(dāng)輸入為“1”時(shí)，輸出為“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;
}

假設(shè)輸入的x是不超過65535的自然數(shù)，完成下面的判斷題和單選題：

當(dāng)輸入為“512”時(shí)，輸出為()。

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

假設(shè)輸入的x是不超過65535的自然數(shù)，完成下面的判斷題和單選題：

當(dāng)輸入為“64”時(shí)，執(zhí)行完第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;
}

假設(shè)輸入的n是不超過1000000的自然數(shù)，完成下面的判斷題和單選題：

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

假設(shè)輸入的n是不超過1000000的自然數(shù)，完成下面的判斷題和單選題：

當(dāng)輸入為“10”時(shí)，輸出的第一行大于第二行。（）

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

假設(shè)輸入的n是不超過1000000的自然數(shù)，完成下面的判斷題和單選題：

當(dāng)輸入為“1000”時(shí)，輸出的第一行與第二行相等。（）

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

假設(shè)輸入的n是不超過1000000的自然數(shù)，完成下面的判斷題和單選題：

solve1(n)的時(shí)間復(fù)雜度為(）。

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

假設(shè)輸入的n是不超過1000000的自然數(shù)，完成下面的判斷題和單選題：

solve(2)的時(shí)間復(fù)雜度為（）。

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

假設(shè)輸入的n是不超過1000000的自然數(shù)，完成下面的判斷題和單選題：

輸入為“5”時(shí)，輸出的第二行為（）。

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

假設(shè)輸入總是合法的且|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
}

假設(shè)輸入總是合法的且|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
}

假設(shè)輸入總是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判斷題和單選題：

當(dāng)輸入為“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
}

假設(shè)輸入總是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判斷題和單選題：

設(shè)a數(shù)組中最大值減最小值加1為A，則f函數(shù)的時(shí)間復(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
}

假設(shè)輸入總是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判斷題和單選題：

將第10行中的“>”替換為“>=”，那么原輸出與現(xiàn)輸出的大小關(guān)系為（）。

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

假設(shè)輸入總是合法的且|a[i]l≤108、n≤10000和1≤k≤n(n-1)/2,完成下面的判斷題和單選題：

當(dāng)輸入為“582-538-12”時(shí)，輸出為（）。

第34題

(第k小路徑)給定一張.個(gè)點(diǎn).條邊的有向無環(huán)圖，頂點(diǎn)編號(hào)從0到n-1。對(duì)于一條路徑，我們定義"路徑序列"為該路徑從起點(diǎn)出發(fā)依次經(jīng)過的頂點(diǎn)編號(hào)構(gòu)成的序列。求所有至少包含一個(gè)點(diǎn)的簡單路徑中，“路徑序列"字典序第k小的路徑。保證存在至少k條路徑。上述參數(shù)滿足1≤n.m≤105和1≤k≤1018。

在程序中，我們求出從每個(gè)點(diǎn)出發(fā)的路徑數(shù)量。超過1018的數(shù)都用1018表示。然后我們根據(jù)k的值和每個(gè)頂點(diǎn)的路徑數(shù)量，確定路徑的起點(diǎn)，然后可以類似地依次求出路徑中的每個(gè)點(diǎn)。

試補(bǔ)全程序。

#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;
}

①處應(yīng)填(    )

第35題

(第k小路徑)給定一張.個(gè)點(diǎn).條邊的有向無環(huán)圖，頂點(diǎn)編號(hào)從0到n-1。對(duì)于一條路徑，我們定義"路徑序列"為該路徑從起點(diǎn)出發(fā)依次經(jīng)過的頂點(diǎn)編號(hào)構(gòu)成的序列。求所有至少包含一個(gè)點(diǎn)的簡單路徑中，“路徑序列"字典序第k小的路徑。保證存在至少k條路徑。上述參數(shù)滿足1≤n.m≤105和1≤k≤1018。

在程序中，我們求出從每個(gè)點(diǎn)出發(fā)的路徑數(shù)量。超過1018的數(shù)都用1018表示。然后我們根據(jù)k的值和每個(gè)頂點(diǎn)的路徑數(shù)量，確定路徑的起點(diǎn)，然后可以類似地依次求出路徑中的每個(gè)點(diǎn)。

試補(bǔ)全程序。

#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;
}

②處應(yīng)填(   )

第36題

(第k小路徑)給定一張.個(gè)點(diǎn).條邊的有向無環(huán)圖，頂點(diǎn)編號(hào)從0到n-1。對(duì)于一條路徑，我們定義"路徑序列"為該路徑從起點(diǎn)出發(fā)依次經(jīng)過的頂點(diǎn)編號(hào)構(gòu)成的序列。求所有至少包含一個(gè)點(diǎn)的簡單路徑中，“路徑序列"字典序第k小的路徑。保證存在至少k條路徑。上述參數(shù)滿足1≤n.m≤105和1≤k≤1018。

在程序中，我們求出從每個(gè)點(diǎn)出發(fā)的路徑數(shù)量。超過1018的數(shù)都用1018表示。然后我們根據(jù)k的值和每個(gè)頂點(diǎn)的路徑數(shù)量，確定路徑的起點(diǎn)，然后可以類似地依次求出路徑中的每個(gè)點(diǎn)。

試補(bǔ)全程序。

#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;
}

③處應(yīng)填(  )

第37題

(第k小路徑)給定一張.個(gè)點(diǎn).條邊的有向無環(huán)圖，頂點(diǎn)編號(hào)從0到n-1。對(duì)于一條路徑，我們定義"路徑序列"為該路徑從起點(diǎn)出發(fā)依次經(jīng)過的頂點(diǎn)編號(hào)構(gòu)成的序列。求所有至少包含一個(gè)點(diǎn)的簡單路徑中，“路徑序列"字典序第k小的路徑。保證存在至少k條路徑。上述參數(shù)滿足1≤n.m≤105和1≤k≤1018。

在程序中，我們求出從每個(gè)點(diǎn)出發(fā)的路徑數(shù)量。超過1018的數(shù)都用1018表示。然后我們根據(jù)k的值和每個(gè)頂點(diǎn)的路徑數(shù)量，確定路徑的起點(diǎn)，然后可以類似地依次求出路徑中的每個(gè)點(diǎn)。

試補(bǔ)全程序。

#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;
}

④處應(yīng)填(    )

第38題

(第k小路徑)給定一張.個(gè)點(diǎn).條邊的有向無環(huán)圖，頂點(diǎn)編號(hào)從0到n-1。對(duì)于一條路徑，我們定義"路徑序列"為該路徑從起點(diǎn)出發(fā)依次經(jīng)過的頂點(diǎn)編號(hào)構(gòu)成的序列。求所有至少包含一個(gè)點(diǎn)的簡單路徑中，“路徑序列"字典序第k小的路徑。保證存在至少k條路徑。上述參數(shù)滿足1≤n.m≤105和1≤k≤1018。

在程序中，我們求出從每個(gè)點(diǎn)出發(fā)的路徑數(shù)量。超過1018的數(shù)都用1018表示。然后我們根據(jù)k的值和每個(gè)頂點(diǎn)的路徑數(shù)量，確定路徑的起點(diǎn)，然后可以類似地依次求出路徑中的每個(gè)點(diǎn)。

試補(bǔ)全程序。

#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;
}

⑤處應(yīng)填(   )

第39題

(最大值之和)給定整數(shù)序列ao,a?,a?……an,求該序列所有非空連續(xù)子序列的最大值之和。上述參數(shù)滿足1≤n≤10?和1≤ai≤108。

一個(gè)序列的非空連續(xù)子序列可以用兩個(gè)下標(biāo)I和r(其中0≤l≤r≤n)表示，對(duì)應(yīng)的序列為ai,ai+1,……ar。兩個(gè)非空連續(xù)子序列不同，當(dāng)且僅當(dāng)下標(biāo)不同。

例如，當(dāng)原序列為[1,2,1,2]  時(shí)，   要計(jì)算子序 列[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]雖然是原序列的子序列，但不是連續(xù)子序列，所以不應(yīng)該被計(jì)算。另外，注意其中有一些值相同的子序列，但由于他們?cè)谠蛄兄械南聵?biāo)不同，屬于不同的非空連續(xù)子序列，所以會(huì)被分別計(jì)算。解決該問題有許多算法，以下程序使用分治算法，時(shí)間復(fù)雜度O(n log n).

嘗試補(bǔ)全程序

#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;
}

①處應(yīng)填（）

第40題

(最大值之和)給定整數(shù)序列ao,a?,a?……an,求該序列所有非空連續(xù)子序列的最大值之和。上述參數(shù)滿足1≤n≤10?和1≤ai≤108。

一個(gè)序列的非空連續(xù)子序列可以用兩個(gè)下標(biāo)I和r(其中0≤l≤r≤n)表示，對(duì)應(yīng)的序列為ai,ai+1,……ar。兩個(gè)非空連續(xù)子序列不同，當(dāng)且僅當(dāng)下標(biāo)不同。

例如，當(dāng)原序列為[1,2,1,2]  時(shí)，   要計(jì)算子序 列[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]雖然是原序列的子序列，但不是連續(xù)子序列，所以不應(yīng)該被計(jì)算。另外，注意其中有一些值相同的子序列，但由于他們?cè)谠蛄兄械南聵?biāo)不同，屬于不同的非空連續(xù)子序列，所以會(huì)被分別計(jì)算。解決該問題有許多算法，以下程序使用分治算法，時(shí)間復(fù)雜度O(n log n).

嘗試補(bǔ)全程序

#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;
}

②處應(yīng)填（）

第41題

(最大值之和)給定整數(shù)序列ao,a?,a?……an,求該序列所有非空連續(xù)子序列的最大值之和。上述參數(shù)滿足1≤n≤10?和1≤ai≤108。

一個(gè)序列的非空連續(xù)子序列可以用兩個(gè)下標(biāo)I和r(其中0≤l≤r≤n)表示，對(duì)應(yīng)的序列為ai,ai+1,……ar。兩個(gè)非空連續(xù)子序列不同，當(dāng)且僅當(dāng)下標(biāo)不同。

例如，當(dāng)原序列為[1,2,1,2]  時(shí)，   要計(jì)算子序 列[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]雖然是原序列的子序列，但不是連續(xù)子序列，所以不應(yīng)該被計(jì)算。另外，注意其中有一些值相同的子序列，但由于他們?cè)谠蛄兄械南聵?biāo)不同，屬于不同的非空連續(xù)子序列，所以會(huì)被分別計(jì)算。解決該問題有許多算法，以下程序使用分治算法，時(shí)間復(fù)雜度O(n log n).

嘗試補(bǔ)全程序

#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;
}

③處應(yīng)填()

第42題

(最大值之和)給定整數(shù)序列ao,a?,a?……an,求該序列所有非空連續(xù)子序列的最大值之和。上述參數(shù)滿足1≤n≤10?和1≤ai≤108。

一個(gè)序列的非空連續(xù)子序列可以用兩個(gè)下標(biāo)I和r(其中0≤l≤r≤n)表示，對(duì)應(yīng)的序列為ai,ai+1,……ar。兩個(gè)非空連續(xù)子序列不同，當(dāng)且僅當(dāng)下標(biāo)不同。

例如，當(dāng)原序列為[1,2,1,2]  時(shí)，   要計(jì)算子序 列[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]雖然是原序列的子序列，但不是連續(xù)子序列，所以不應(yīng)該被計(jì)算。另外，注意其中有一些值相同的子序列，但由于他們?cè)谠蛄兄械南聵?biāo)不同，屬于不同的非空連續(xù)子序列，所以會(huì)被分別計(jì)算。解決該問題有許多算法，以下程序使用分治算法，時(shí)間復(fù)雜度O(n log n).

嘗試補(bǔ)全程序

#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;
}

④處應(yīng)填()

第43題

(最大值之和)給定整數(shù)序列ao,a?,a?……an,求該序列所有非空連續(xù)子序列的最大值之和。上述參數(shù)滿足1≤n≤10?和1≤ai≤108。

一個(gè)序列的非空連續(xù)子序列可以用兩個(gè)下標(biāo)I和r(其中0≤l≤r≤n)表示，對(duì)應(yīng)的序列為ai,ai+1,……ar。兩個(gè)非空連續(xù)子序列不同，當(dāng)且僅當(dāng)下標(biāo)不同。

例如，當(dāng)原序列為[1,2,1,2]  時(shí)，   要計(jì)算子序 列[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]雖然是原序列的子序列，但不是連續(xù)子序列，所以不應(yīng)該被計(jì)算。另外，注意其中有一些值相同的子序列，但由于他們?cè)谠蛄兄械南聵?biāo)不同，屬于不同的非空連續(xù)子序列，所以會(huì)被分別計(jì)算。解決該問題有許多算法，以下程序使用分治算法，時(shí)間復(fù)雜度O(n log n).

嘗試補(bǔ)全程序

#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;
}

⑤處應(yīng)填()