信息学奥赛-入门级 题库
插入排序

#include <bits/stdc++.h>
using namespace std;
int n, q, a[8005], b[8005], num, x, v, ans;
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
// 计算每个数在数组中的排位
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (i == j || a[j] < a[i] || a[j] == a[i]) {
b[i]++;
} else {
b[j]++;
}
}
}
for (int i = 0; i < q; i++) {
scanf("%d", &num);
if (num == 1) {
scanf("%d%d", &x, &v);
for (int i = 1; i <= n; i++) {
if (i == x) {
continue;
}
// 根据条件更新排位
if ((a[i] < a[x] || (a[i] == a[x] && i < x)) &&
(a[i] > v || (a[i] == v && i > x))) {
b[i]++;
b[x]--;
} else if ((a[i] > a[x] || (a[i] == a[x] && i > x)) &&
(a[i] < v || (a[i] == v && i < x))) {
b[i]--;
b[x]++;
}
}
a[x] = v;
}
if (num == 2) {
scanf("%d", &x);
printf("%d\n", b[x]);
}
}
return 0;
}(寻找被移除的元素)问题:原有长度为n+1公差为1等升数列,将数列输到程序的数组时移除了一个元素,导致长度为n的开序数组可能不再连续,除非被移除的是第一个或最后一个元素。需要在数组不连续时,找出被移除的元素。试补全程序。
奖学金
【问题描述】
某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排在前面,这样,每个学生的排序是唯一确定的。
任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前5名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分)是:
7 279
5 279
这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和),但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279
7 279
则按输出错误处理,不能得分。
【输入】
输入文件scholar.in包含n+1行:
第1行为一个正整数n,表示该校参加评选的学生人数。
第2到n+1行,每行有3个用空格隔开的数字,每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n(恰好是输入数据的行号减1)。
所给的数据都是正确的,不必检验。
【输出】
输出文件scholar.out共有5行,每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。
【输入输出样例1】

【输入输出样例2】

【限制】
50%的数据满足:各学生的总成绩各不相同
100%的数据满足:6<=n<=300
#include <bits/stdc++.h>
using namespace std;
long long a[100100];
struct student{
int a,b,c;//语文,数学,英语;
int id;
int sum;
};
bool cmp(student da,student db){
if(da.sum!=db.sum){
return da.sum>db.sum;//总分比较。
}else if(da.a!=db.a){
return da.a>db.a;//语文成绩比较。
}
return da.id<db.id;//编号比较。
}
int main() {
int n;
cin>>n;
student stu[n];
for(int i=0;i<n;i++){
cin>>stu[i].a>>stu[i].b>>stu[i].c;
stu[i].id=i+1;
stu[i].sum=stu[i].a+stu[i].b+stu[i].c;//总和。
}
stable_sort(stu,stu+n,cmp);
for(int i=0;i<5;i++){
cout<<stu[i].id<<" "<<stu[i].sum<<endl;
}
return 0;
}
明明的随机数
【问题描述】
明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
【输入文件】
输入文件random.in 有2行,第1行为1个正整数,表示所生成的随机数的个数:
N
第2行有N个用空格隔开的正整数,为所产生的随机数。
【输出文件】
输出文件random.out 也是2行,第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。
【输入样例】
10
20 40 32 67 40 20 89 300 400 15
【输出样例】
8
15 20 32 40 67 89 300 400
#include<stdio.h>
int main(){
int N,a[1001]={0},t,i;
int count=0;
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d",&t);
if(a[t]==0){
a[t]=t;
count++;
}
}
printf("%d\n",count);
for(i=0;i<1001;i++){
if(a[i]!=0)
printf("%d ",a[i]);
}
return 0;
}
在 A,B 两个城市之间设有 N 个路站(如下图中的 S1,且 N<100),城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20,且每条路段上的距离均为一个整数)。
A,B 的一条通路是指:从 A 出发,可经过任一路段到达 S1,再从 S1 出发经过任一路段,…最后到达 B。通路上路段距离之和称为通路距离(最大距离≤ 1000)。当所有的路段距离给出之后,求出所有不同距离的通路个数(相同距离仅记一次)。
例如:下图所示是当 N=1 时的情况:

从 A 到 B 的通路条数为 6,但因其中通路 5+5=4+6,所以满足条件的不同距离的通路条数为 5。
算法说明:本题采用穷举算法。
数据结构:N:记录 A,B 间路站的个数
数组 D[I,0]记录第 I-1 到第 I 路站间路段的个数D[I,1],D[I,2],…记录每个路段距离
数组 G 记录可取到的距离
程 序 清 单 :

问题描述:将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:

问题求解:求出一种分法,使P为最小(若有多种方案仅记一种〉
程序说明:
数组:a[1],a[2],...A[N]存放原数
s[1],s[2],...,s[K]存放每个部分的和
b[1],b[2],...,b[N]穷举用临时空间
d[1],d[2],...,d[N]存放最佳方案
程序:


将
个0和
个1,排成一圈。从任一个位置开始,每次按逆时针的方向以长度为n+1的单位进行数二进制数。
要求给出一种排法,用上面的方法产生出来的
个二进制数都不相同。
例如,当n=2时, 即
个0 和
个1 排成如下一圈:

比如,从A位置开始,逆时针方向取三个数000,然后再从B位置上开始取三个数001,接着从C开始取三个数010,...可以得到000,001,010,101,011,111,110,100共8个二进制数且都不相同。
程序说明
以n=4为例,即有16个0,16个1,
数组a用以记录32个0,1的排法,
数组b统计二进制数是否已出现过。
程序清单

[问题描述]
下面程序的功能是从键盘读取A,B数组的元素,A,B数组均已从小到大排好序(无相同元素),现将A,B合并为数组C,同样要求数组C也是从小到大排好序(有相同元素时只保留一个)。
程序中N表示数组A,B的长度,i,j,k分别表示数组A,B,C的取数或存数的指针。
[程序清单]

输入一长度不超过80个字符的字符串(称为源串),该字符串由小写英文字母、空格组成,并以'.'结束。单词是由连续字母组成,两个单词之间至少有一个空格。本程序的功能为:首先找出字符串中所有单词并保留一个空格作为单词分隔,存入数组ch中。然后用键盘输入一个待查找的单词,以字符'$'结束。采用顺序查找的方法在ch中进行查找,若找到,则输出该单词在ch中出现的序号(若有多个位置出现该单词,则只输出第一个序号位置)。若不存在,则输出'NOT FOUND'。
程序如下:


设数组A[10..100,20..100] 以行优先的方式顺序存储,每个元素占4个字节,且已知A[10,20]的地址为1000,则A[50,90]的地址是()
[问题描述] 读入n个不相同且不为0的数(1<=n<=100),不用排序,求出其中第r个大的数(1≤r≤n),即有r-1个数比它大,其余的数都比它小。
例如:输入3,14,22,15,17,6,其中第3个大的数为15。
[算法说明] 以数组a[1..100]记录读入的n个数,并以0结束(0本身不是n个数中的数)。然后从第一个数开始,将它与其余的数进行比较并记录出比它大的数的个数(存于变量y中),若y=r-1时,得到所求结果:否则对下一个数进行同样的处理。
[程序清单]

[问题描述] 一个正整数(非素数)可表示成它的因子(1与其本身除外)的乘积。
例如:12有因子2,3,4,6,所以可表示为:
12=223=43=26
给出任一个正整数N,求出它所有的因子乘积的表达式(交换律得出的不同式子算同一种)。
[算法说明] 读入一个整数N,首先求出它的所有的因子以及每个因子可能的次数。
例如:整数48:
因子:2 3 4 6 8 12 16 24
次数:4 1 2 1 1 1 1 1
将上面的结果存入数组A:ARRAY[0..20,1..2]中。其中:A[¡,1]表示因子;A[¡,2]表示次数。
然后用简单回溯的方法求出所有可能的表示。
数组B[0..20]记录取数情况;c:array[0..20]工作单元。
[程序清单]


有N×N个数据组成如下方阵:

现将
…存储在一维数组A[1],A[2],…A[(N*(N+1))/2] 中。
试问:任给i,j怎样求出K来,使得A[K]的值正好是
请写出由i,j计算K值的表达式。
设有N个不同整数的数列:例如N=4时,有4个不同整数的数列为17,4,16,5。数列中的第1个数17,比它后面的三个数都大,则称数17的逆数为3。数列中的第2个数4比它后面的数都小,则称数4的逆数为0。同时记数列中全部逆数的和称为数列的逆数。上例中,数列17,4,16,5的逆数:为3+0+1+0=4。
[程序要求] 当给出N个不同整数的数列后,求出此数列的逆数。
[算法描述] 为求得上面问题的解,设置数组A:array[1..N] of Integer 和逆数计数器5,然后用一个二重循环求出数列的逆数。
[程 序]

装球:设有n个盒子(n足够大,可装入任何数量的球),分别编号1,2,……。同时有k个小球(k>0),今将k 个小球装入到盒子中去。
装入规则如下:
(1)第一个盒子不能为空。
(2)装入必须严格按递增顺序进行。
例如,当k=8,n=6时,装入方法有1,2,5或1,3,4
(3)在满足上面的两个条件下,要求有球的盒子尽可能多。
(4)装完后,相邻盒子中球个数差的绝对值之和最小(未装的盒子不计)。
如上例中:
装入法1,2,5,则差的绝对值之和为2-1+5-2=4
装入法1,3,4,则差的绝对值之和为3-1+4-3=3
[程序要求] 给出k(k表示小球的个数)之后,求出满足上述四个条件的装入方法。
[算法描述] 设计一个数组A用数组元素代表盒子,然后依次装入小球。
[程序清单]



