信息学奥赛-提高级 题库
下图表示一个果园灌溉系统,有A、B、C、D四个阀门,每个阀门可以打开或关上,所有管道粗细相同,以下设置阀门的方法中,可以让果树浇上水的有( )。

一个 1×8 的方格图形(不可旋转)用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色,且不允许两个黑格相邻,共有_________种填 涂方案。
55
某中学在安排期末考试时发现,有7个学生要参加7门课程的考试,下表列出了哪些学生参加哪些考试(用√表示要参加相应的考试)。 最少要安排_________个不同的考试时间段才能避免冲突?

3
(交朋友)根据社会学研究表明,人们都喜欢找和自己身高相近的人做朋友。
现在有n名身高两两不相同的同学依次走入教室,调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时,这名同学会更想和高的那个人做朋友。比如一名身高为1.80米的同学进入教室时,有一名身高为1.79米的同学和一名身高为1.81米的同学在教室里,那么这名身高为1.80米的同学会更想和身高为1.81米的同学做朋友。对于第一个走入教室的同学我们不做预测。
由于我们知道所有人的身高和走进教室的次序,所以我们可以采用离线的做法来解决这样的问题,我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。(第一空2分,其余3分)
#include <iostream>
using namespace std;
#define MAXN 200000
#define infinity 2147483647
int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN];
int rank[MAXN];
int n;
void sort(int l, int r) {
int x = height[rank[(l + r) / 2]], i = l, j = r, temp;
while (i <= j)
{
while (height[rank[i]] < x) i++;
while (height[rank[j]] > x) j--;
if ( (1) ) {
temp = rank[i]; rank[i] = rank[j]; rank[j] = temp;
i++; j--;
}
}
if (i < r) sort(i, r);
if (l < j) sort(l, j);
}
int main()
{
cin >> n;
int i, higher, shorter;
for (i = 1; i <= n; i++) {
cin >> height[i];
rank[i] = i;
sort(1, n);
for (i = 1; i <= n; i++) {
previous[rank[i]] = rank[i - 1];
(2) ;
}
for (i = n; i >= 2; i--){
higher = shorter = infinity;
if (previous[i] !=0)
shorter = height[i] - height[previous[i]]; if
(next[i] != 0)
(3) ;
if ( (4) )
answer[i] = previous[i];
else
answer[i] = next[i];
next[previous[i]] = next[i];
(5) ;
}
for (i = 2; i <= n; i++)
cout << i << ":" << answer[i];
return 0;
}
(1)i<=j
(2)next[rank[i]]=rank[i+1]
(3)higher=height[next[i]]-height[i]
(4)shorter<higher
(5)previous[next[i]]=previous[i]
双子序列最大和)给定一个长度为n(3≤n≤1000)的整数序列,要求从中选出两个连续子序列,使得这两个连续子序列的序列和之和最大,最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求:每个连续子序列长度至少为1,且两个连续子序列之间至少间隔1个数。(第五空4分,其余 2.5分)
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, ans, sum;
int x[MAXN];
int lmax[MAXN];
// lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中,最大的序列和
int rmax[MAXN];
// rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中,最大的序列和
int main() {
cin >> n;
for (i = 0; i < n; i++)
cin >> x[i];
lmax[0] = x[0];
for (i = 1; i < n; i++)
if (lmax[i - 1] <= 0)
lmax[i] = x[i];
else
lmax[i] = lmax[i - 1] + x[i];
for (i = 1; i < n; i++)
if (lmax[i] < lmax[i - 1])
lmax[i] = lmax[i - 1];
(1) ;
for (i = n - 2; i >= 0; i--)
if (rmax[i + 1] <= 0)
(2) ;
else
(3) ;
for (i = n - 2; i >= 0; i--)
if (rmax[i] < rmax[i + 1])
(4) ;
ans = x[0] + x[2];
for (i = 1; i < n - 1; i++) {
sum = (5) ;
if (sum > ans)
ans = sum;
}
cout << ans << endl;
return 0;
}
(1)rmax[n-1]=x[n-1]
(2)rmax[i]=x[i]
(3)rmax[i]=rmax[i+1]+x[i]
(4)rmax[i]=rmax[i+1]
(5) lmax[i-1]+rmax[i+1]