信息学奥赛-提高级 题库
(大整数除法)给定两个正整数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
(最长路径)给定一个有向无环图,每条边长度为1,求图中的最长路径长度。(第五空2分,其余3分)
输入:第一行是结点数n(不超过100)和边数m,接下来m行,每行两个整数a,b,表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。
输出:最长路径长度。
提示:先进行拓扑排序,然后按照拓扑序计算最长路径。
#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100]; // 记录每个结点的入度
int len[100]; // 记录以各结点为终点的最长路径长度
int queue[100]; // 存放拓扑排序结果
int main() {
cin >> n >> m;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
graph[i][j] = 0;
for (i = 0; i < n; i++)
degree[i] = 0;
for (i = 0; i < m; i++) {
cin >> a >> b;
graph[a][b] = 1;
(1) ;
}
tail = 0;
for (i = 0; i < n; i++)
if ( (2) ) {
queue[tail] = i;
tail++;
}
head = 0;
while (tail < n - 1) {
for (i = 0; i < n; i++)
if (graph[queue[head] ][i] == 1) {
(3) ;
if (degree[i] == 0) {
queue[tail] = i;
tail++;
}
}
(4) ;
}
ans = 0;
for (i = 0; i < n; i++) {
a = queue[i];
len[a] = 1;
for (j = 0; j < n; j++)
if (graph[j][a] == 1 && len[j] + 1 > len[a])
len[a] = len[j] + 1;
if ( (5) )
ans = len[a];
}
cout << ans << endl;
return 0;
}
(1)degree[b]=degree[b]+1 或 degree[b]++ 或 ++degree[b]
(2)degree[i]==0 或 !degree[i]
(3)degree[i]=degree[i]-1 或 degree[i]-- 或 --degree[i]
(4)head=head+1 或 head++ 或 ++head
(5)ans<len[a] 或 len[a]>ans
下图表示一个果园灌溉系统,有A、B、C、D四个阀门,每个阀门可以打开或关上,所有管道粗细相同,以下设置阀门的方法中,可以让果树浇上水的有( )。

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

3
输入:
3
AB:ACDEbFBkBD
AR:ACDBrT
SARS:Severe Atypical Respiratory Syndrome
输出:
(注:输入各行前后均无空格)
YES,NO,YES,
(交朋友)根据社会学研究表明,人们都喜欢找和自己身高相近的人做朋友。
现在有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座城市和m条双向的道路,每条道路连接着两座不同的城市。其中1号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道,如果只有第i(i>1)个城市因地震而
导致交通中断时,首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第i个城市而导致从首都出发无法到达某个城市,也认为到达该城市的最短路径长度改变。
对于每一个城市i,假定只有第i个城市与外界交通中断,输出有多少个城市会因此导致到首都的最短路径长度改变。
我们采用邻接表的方式存储图的信息,其中head[x]表示顶点x的第一条边的编号,next[i]表示第i条边的下一条边的编号,point[i]表示第i条边的终点,weight[i]表示第i条边的长度。(第一空2分,其余3分)
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define infinity 2147483647
int head[MAXN], next[MAXM], point[MAXM], weight[MAXM];
int queue[MAXN], dist[MAXN], visit[MAXN];
int n, m, x, y, z, total = 0, answer;
void link(int x,int y,int z) {
total++;
next[total] = head[x];
head[x] = total;
point[total] = y;
weight[total] = z;
total++;
next[total] = head[y];
head[y] = total;
point[total] = x;
weight[total] = z;
}
int main() {
int i, j, s, t;
cin >> n >> m;
for (i = 1; i <= m; i++) {
cin >> x >> y >> z; link(x, y, z);
}
for (i = 1; i <= n; i++) dist[i] = infinity;
(1) ;
queue[1] = 1;
visit[1] = 1;
s = 1;
t = 1;
// 使用 SPFA 求出第一个点到其余各点的最短路长度
while (s <= t) {
x = queue[s % MAXN];
j = head[x];
while (j != 0) {
if ( (2) ) {
dist[point[j]] = dist[x] + weight[j];
if (visit[point[j]] == 0) {
t++;
queue[t % MAXN] = point[j];
visit[point[j]] = 1;
}
}
j = next[j];
}
(3) ;
s++;
}
for (i = 2; i <= n; i++) {
queue[1] = 1;
memset(visit, 0, sizeof(visit));
visit[1] = 1;
s = 1;
t = 1;
while (s <= t) { // 判断最短路长度是否不变
x = queue[s];
j = head[x];
while (j != 0) {
if (point[j] != i && (4)
&&visit[point[j]] == 0) {
(5) ;
t++;
queue[t] = point[j];
}
j = next[j];
}
s++;
}
answer = 0;
for (j = 1; j <= n; j++)
answer += 1 - visit[j];
cout << i << ":" << answer - 1 << endl;
}return 0;
}
(1)dist[1]=0
(2) dist[x]+weight[j]<dist[point[j]]
(3)visit[x]=0
(4)dist[x]+weight[j]==dist[point[j]]
(5)visit[point[j]]=1