信息学奥赛-提高级 题库
(最大值之和)给定整数序列a0,… an-1,求该序列所有非空连续子序列的最大值之和。上述参数满足1≤n≤105和1≤a;≤108。
一个序列的非空连续子序列可以用两个下标l和r(其中0≤l≤r<n)表示,对应的序列为alal+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]和[22]虽然是原序列的子序列,但不是连续子序列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,所以会被分别计算。解决该问题有许多算法,以下程序使用分治算法,时间复杂度0(nlogn)。
试补全程序。

(序列重排)全局数组变量 a 定义如下:
Const int SIZE = 100;
int a[SIZE],n;
它记录着一个长度为 n 的序列a[1],a[2],…,a[n]。
现在需要一个函数,以整数 p(1≤p≤n)为参数,实现如下功能:将序列 a 的前 p 个数与后 n–p 个数对调,且不改变这 p 个数(或 n–p 个数)之间的相对位置。例如,长度为 5 的序列 1,2,3,4,5,当 p=2 时重排结果为 3,4,5,1,2。
有一种朴素的算法可以实现这一需求,其时间复杂度为 O(n)、空间复杂度为 O(n):
void swap1(int p)
{
int i, j, b[SIZE];
for (i = 1; i <= p; i++)
b[ ( 1) ] = a[i]; //(2 分)
for (i = p + 1; i <= n; i++)
b[i - p] = a[i];
for (i = 1; i <= n; i++)
a[i] = b[i];
}
我们也可以用时间换空间,使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法:
void swap2(int p)
{
int i, j, temp;
for (i = p + 1; i <= n; i++) {
temp = a[i];
for (j = i; j >= (2) ; j--) //(2 分)
a[j] = a[j - 1];
(3) = temp; //(2 分)
}
}
事实上,还有一种更好的算法,时间复杂度为O(n)、空间复杂度为O(1):
void swap3(int p)
{
int start1, end1, start2, end2, i, j, temp;
start1 = 1;
end1 = p;
start2 = p + 1;
end2 = n;
while (true) {
i = start1;
j = start2;
while ((i <= end1) && (j <= end2)) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}
if (i <= end1)
start1 = i;
else if ( (4) ) { //(3 分)
start1 = (5) //(3 分)
endl = (6) //(3 分)
start2 = j;
}
else
break;
}
}
(1)n – p + i
(2)i – p + 1
(3)a[i – p]
(4)j <= end2
(5)i(或 start2,或 end1 + 1)
(6)j – 1
(RMQ 区间最值问题)给定序列 a0, … , an-1,和 m 次询问,每次询问给定 l, r,求max {al, … , ar} 。
为了解决该问题,有一个算法叫 the Method of Four Russians,其时间复杂度为0(n + m),步骤如下:
• 建立 Cartesian(笛卡尔)树,将问题转化为树上的 LCA(最近公共祖先)问题。
• 对于 LCA 问题,可以考虑其 Euler 序(即按照 DFS 过程,经过所有点,环游回根的序列),即求 Euler 序列上两点间一个新的 RMQ 问题。
• 注意新的问题为 ±1 RMQ,即相邻两点的深度差一定为 1。
下面解决这个 ±1 RMQ 问题,“序列”指 Euler 序列:
• 设 t 为 Euler 序列长度。取 b =
将序列每 b 个分为一大块, 使用 ST 表(倍增表)处理大块间的 RMQ 问题,复杂度

• (重点)对于一个块内的 RMQ 问题,也需要O(1) 的算法。由于差分数组 2b-1
种,可以预处理出所有情况下的最值位置,预处理复杂度 O(b2b),不超过 O(n)。
• 最终,对于一个查询,可以转化为中间整的大块的 RMQ 问题,以及两端块内的 RMQ 问题。
试补全程序。
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 100000, MAXT = MAXN << 1;
const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;
struct node {
int val;
int dep, dfn, end;
node *son[2]; // son[0], son[1] 分别表示左右儿子
} T[MAXN];
int n, t, b, c, Log2[MAXC + 1];
int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];
node *root, *A[MAXT], *Min[MAXL][MAXC];
void build() { // 建立 Cartesian 树
static node *S[MAXN + 1];
int top = 0;
for (int i = 0; i < n; i++) {
node *p = &T[i];
while (top && S[top]->val < p->val)
①;
if (top)
②;
S[++top] = p;
}
root = S[1];
}
void DFS(node *p) { // 构建 Euler 序列
A[p->dfn = t++] = p;
for (int i = 0; i < 2; i++)
if (p->son[i]) {
p->son[i]->dep = p->dep + 1;
DFS(p->son[i]);
A[t++] = p;
}
p->end = t - 1;
}
node *min(node *x, node *y) {
return ③ ? x : y;
}
void ST_init() {
b = (int)(ceil(log2(t) / 2));
c = t / b;
Log2[1] = 0;
for (int i = 2; i <= c; i++)
Log2[i] = Log2[i >> 1] + 1;
for (int i = 0; i < c; i++) {
Min[0][i] = A[i * b];
for (int j = 1; j < b; j++)
Min[0][i] = min(Min[0][i], A[i * b + j]);
}
for (int i = 1, l = 2; l <= c; i++, l <<= 1)
for (int j = 0; j + l <= c; j++)
Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);
}
void small_init() { // 块内预处理
for (int i = 0; i <= c; i++)
for (int j = 1; j < b && i * b + j < t; j++)
if (④)
Dif[i] |= 1 << (j - 1);
for (int S = 0; S < (1 << (b - 1)); S++) {
int mx = 0, v = 0;
for (int i = 1; i < b; i++) {
⑤;
if (v < mx) {
mx = v;
Pos[S] = i;
}
}
}
}
node *ST_query(int l, int r) {
int g = Log2[r - l + 1];
return min(Min[g][l], Min[g][r - (1 << g) + 1]);
}
node *small_query(int l, int r) { // 块内查询
int p = l / b;
int S = ⑥;
return A[l + Pos[S]];
}
node *query(int l, int r) {
if (l > r)
return query(r, l);
int pl = l / b, pr = r / b;
if (pl == pr) {
return small_query(l, r);
} else {
node *s = min(small_query(l, pl * b + b - 1),
small_query(pr * b, r));
if (pl + 1 <= pr - 1)
s = min(s, ST_query(pl + 1, pr - 1));
return s;
}
}
int main() {
int m;
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> T[i].val;
build();
DFS(root);
ST_init();
small_init();
while (m--) {
int l, r;
cin >> l >> r;
cout << query(T[l].dfn, T[r].dfn)->val << endl;
}
return 0;
}
时间复杂度
【问题描述】
小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序,于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。
A++语言的循环结构如下:

其中“F i x y”表示新建变量 (i 变量 i 不可与未被销毁的变量重名)并初始化为 x,然后判断 i 和 y 的大小关系,若 i 小于等于 y 则进入循环,否则不进入。每次循环结束后 i 都会被修改成 i +1,一旦 i 大于 y 终止循环。
x 和 y 可以是正整数(x 和 y 的大小关系不定)或变量 n。n 是一个表示数据规模的变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数远大于 100。
“E”表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。
注:本题中为了书写方便,在描述复杂度时,使用大写英文字母“O”表示通常意义下“Θ”的概念。
【输入格式】
输入文件名为 complexity.in。
输入文件第一行一个正整数 t,表示有 t(t ≤ 10)个程序需要计算时间复杂度。
每个程序我们只需抽取其中 “F i x y”和“E”即可计算时间复杂度。注意:循环结构允许嵌套。
接下来每个程序的第一行包含一个正整数 L 和一个字符串,L 代表程序行数,字符串表示这个程序的复杂度,“O(1)”表示常数复杂度,“O(n^w)”表示复杂度为n^w,其中w是一个小于100的正整数(输入中不包含引号),输入保证复杂度只有O(1)和O(n^w)两种类型。
接下来 L 行代表程序中循环结构中的“F i x y”或者 “E”。
程序行若以“F”开头,表示进入一个循环,之后有空格分离的三个字符(串)i x y,其中 i 是一个小写字母(保证不为“n”),表示新建的变量名,x 和 y 可能是正整数或n ,已知若为正整数则一定小于 100。
程序行若以“E”开头,则表示循环体结束。
【输出格式】
输出文件名为 complexity.out。
输出文件共 t 行,对应输入的 t 个程序,每行输出“Yes”或“No”或者“ERR”(输出中不包含引号),若程序实际复杂度与输入给出的复杂度一致则输出“Yes”,不一致则输出“No”,若程序有语法错误(其中语法错误只有: ① F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况),则输出“ERR”。
注意:即使在程序不会执行的循环体中出现了语法错误也会编译错误,要输出“ERR”。
【输入输出样例 1】

【输入输出样例 1 说明】
第一个程序 i 从 1 到 1 是常数复杂度。
第二个程序 x 从 1 到 n 是 n 的一次方的复杂度。
第三个程序有一个 F 开启循环却没有 E 结束,语法错误。
第四个程序二重循环,n 的平方的复杂度。
第五个程序两个一重循环,n 的一次方的复杂度。
第六个程序第一重循环正常,但第二重循环开始即终止(因为n远大于100,100大于4)。
第七个程序第一重循环无法进入,故为常数复杂度。
第八个程序第二重循环中的变量 x 与第一重循环中的变量重复,出现语法错误②,输出ERR。
【数据规模与约定】
对于 30%的数据:不存在语法错误,数据保证小明给出的每个程序的前 L/2 行一定为以 F 开头的语句,第 L/2+1 行至第 L 行一定为以 E 开头的语句,L<=10,若 x、y 均为整数,x 一定小于 y,且只有 y 有可能为 n。
对于 50%的数据:不存在语法错误,L<=100,且若 x、y 均为整数,x 一定小于 y,且只有 y 有可能为 n。
对于 70%的数据:不存在语法错误,L<=100。
对于 100%的数据:L<=100。
#include<bits/stdc++.h>
#define gc getchar()
using namespace std;
int T,n,k,o,bz[6000],aa[6000],maxn,p,l,t[6000],tt,pp[6000],ttt,tttt;
//o表示层数,t表示是否进入此循环,p表示是n的几次方
char a;
int main()
{
scanf("%d",&T);
while(T--)
{
p=tt=ttt=tttt=l=k=o=maxn=a=0;
memset(bz,0,sizeof(bz)),memset(t,0,sizeof(t));
memset(aa,0,sizeof(aa)),memset(pp,0,sizeof(pp));
scanf("%d",&n);
while(a!='(') a=gc;
a=gc;
if(a=='1') k=0;
else
{
a=gc;
scanf("%d",&k);
}
for(int i=1;i<=n;i++)
{
if(tt==0&&o<100) maxn=max(p,maxn);
while(a!='F'&&a!='E') a=gc;
if(a=='F')
{
o++;
while(a>'z'||a<'a') a=gc;
if(bz[a-'a']) o=999;
if(o<100)
bz[a-'a']=1,aa[o]=a;
gc,a=gc;
if(a=='n')
{
a=gc,a=gc;
if(a!='n')
{
l=0;
while(a<='9'&&a>='0') l=l*10+a-'0',a=gc;
if(l<=100) maxn=max(p,maxn),tt++,t[o]=1;
}
}
else
{
ttt=tttt=0;
while(a!=' ') ttt=ttt*10+a-'0',a=gc;
a=gc;
if(a=='n')
{
p++,pp[o]=1;
if(tt==0) maxn=max(p,maxn);
}
else
{
while(a<='9'&&a>='0') tttt=tttt*10+a-'0',a=gc;
if(ttt>tttt) tt++,t[o]=1;
}
}
a=gc;
}
else
{
if(o<=0)
{
o=999;
}
if(o<100)
{
bz[aa[o]-'a']=0,tt-=t[o],t[o]=0;
p-=pp[o],pp[o]=0,o--;
}
a=gc;
}
}
if(o==0)
{
if(maxn==k) printf("Yes\n");
else printf("No\n");
}
else printf("ERR\n");
}
return 0;
}