第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={x1,x2,x3,…,xm}和Y={y1,y2,y3,…,yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z={z1,z2,z3,…,zk},使得序列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题
若,定义;其中对于给定自然数n0,存在序列n0,n1,n2,...,nm,其中对于都有ni=f(ni-1)且nm=nm-1,称nm为n0关于f的不动点,问在10016至1A016中,关于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; }
⑤处应填()