信息学奥赛-提高级 题库
(大整数除法)给定两个正整数p和q,其中p不超过10100,q不超过100000,
求p除以q的商和余数。(第一空2分,其余3分)
输入:第一行是p的位数n,第二行是正整数p,第三行是正整数q。
输出:两行,分别是p除以q的商和余数。
#include <iostream>
using namespace std;
int p[100];
int n, i, q, rest;
char c;
int main() {
cin >> n;
for (i = 0; i < n; i++) {
cin >> c;
p[i] = c - '0';
}
cin >> q;
rest = (1) ;
i = 1;
while ( (2) && i < n) {
rest = rest * 10 + p[i];
i++;
}
if (rest < q)
cout << 0 << endl;
else {
cout << (3) ;
while (i < n) {
rest = (4) ;
i++;
cout << rest / q;
}
cout << endl;
}
cout << (5) << endl;
return 0;
}
(1)p[0]
(2)rest<q 或 q>rest
(3)rest / q
(4)rest % q * 10 + p[i]
(5)rest % q
某中学在安排期末考试时发现,有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]
(最大子矩阵和)给出 m 行 n 列的整数矩阵,求最大的子矩阵和(子矩阵不能为空)。
输入第一行包含两个整数 m 和 n,即矩阵的行数和列数。之后 m 行,每行 n 个整数,描述整个矩阵。程序最终输出最大的子矩阵和。(第一空 2 分,其余 3 分,共 14分)
#include <iostream>
using namespace std;
const int SIZE = 100;
int matrix[SIZE + 1][SIZE + 1];
int rowsum[SIZE + 1][SIZE + 1]; //rowsum[i][j]记录第 i 行前 j 个数的和
int m, n, i, j, first, last, area, ans;
int main() {
cin >> m >> n;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
cin >> matrix[i][j];
ans = matrix (1) ;
for (i = 1; i <= m; i++)
(2) ;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
rowsum[i][j] = (3) ;
for (first = 1; first <= n; first++)
for (last = first; last <= n; last++) {
(4) ;
for (i = 1; i <= m; i++) {
area += (5) ;
if (area > ans)
ans = area;
if (area < 0)
area = 0;
}
}
cout << ans << endl;
return 0;
}
(1)[1][1]
(2)rowsum[i][0]=0
(3)rowsum[i][j-1]+matrix[i][j]
(4)area=0
(5)rowsum[i][last]-rowsum[i,first-1]