CSP考试题库 - 第22页

第421题

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

①处应填( )

A. k >= f[u] B. k <= f[u] C. k >f[u] D. k< f[u]

第422题

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

②处应填( )

A. deg[v]== 1 B. deg[v]== o C. deg[v]>1 D. deg[v]>o

第423题

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

③处应填( )

A. std::min(f[u]+ f[v],LIM) B. std::min(f[u]+ f[v]+ 1,LIM) C. std::min(f[u]* f[v],LIM) D. std::min(f[u]*(f[v]+ 1),LIM)

第424题

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

④处应填( )

A. u!=-1 B. !E[u].empty() C. k >o D. k >1

第425题

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

⑤处应填( )

A. k += f[u] B. k -= f[u] C. --k D. ++k

第426题

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

①处应填（）

A. pre[i]=std::max(pre[i-1],a[i-1]) B. pre[i + 1]= std::max(pre[i],pre[i +1]) C. pre[i]= std::max(pre[i - 1],a[i]) D. pre[i]= std::max(pre[i],pre[i - 1])

第427题

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

②处应填（）

A. a[j]< max B. a[j]< a[i] C. pre[j - mid]< max D. pre[j - mid]< max

第428题

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

③处应填()

A. (long long)(j - mid)* max B. (long long)(j - mid)*(i - 1)* max C. sum[j - mid] D. sum[j - mid]*(i - 1)

第429题

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

④处应填()

A. (long long)(r - j)* max B. (long long)(r - j)*(mid - i)* max C. sum[r - mid]- sum[j - mid] D. (sum[r - mid]- sum[j - mid])*(mid - i)

第430题

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

⑤处应填()

A. solve(o, n) B. solve(o, n - 1) C. solve(1,n) D. solve(1, n - 1)

训练

CSP考试

知识点标签