信息学奥赛-入门级 题库
(切割绳子)有n条绳子,每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割,但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段,求绳段的最大长度是多少。(第一、二空2.5分,其余3分)
输入:第一行是一个不超过100的正整数n,第二行是n个不超过106的正整数,表示每条绳子的长度,第三行是一个不超过108的正整数m。
输出:绳段的最大长度,若无法切割,输出Failed。
#include <iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main() {
cin >> n;
count = 0;
for (i = 0; i < n; i++) {
cin >> len[i];
(1) ;
}
cin >> m;
if ( (2) ) {
cout << "Failed" << endl;
return 0;
}
lbound = 1;
ubound = 1000000;
while ( (3) ) {
mid = (4) ;
count = 0;
for (i = 0; i < n; i++)
(5) ;
if (count < m)
ubound = mid - 1;
else
lbound = mid;
}
cout << lbound << endl;
return 0;
}
(1)count=count+len[i] 或 count+=len[i]
(2)count<m 或 m>count
(3)lbound<ubound 或 ubound>lbound
(4)(lbound+ubound+1)/2 或 (lbound+ubound+1)>>1 或 (lbound+ubound)/2+1
(5)count=count+len[i]/mid 或 count+=len[i]/mid
约定二叉树的根节点高度为1。一棵结点数为2016的二叉树最少有 个叶子结点;一棵结点数为2016的二叉树最小的高度值是 。
1(2 分)
11(3 分)
(读入整数)请完善下面的程序,使得程序能够读入两个int范围内的整数,并将这两个整数分别输出,每行一个。(第一、五空2.5分,其余 3 分)
输入的整数之间和前后只会出现空格或者回车。 输入数据保证合法。 例如:
输入:
输出:
#include <iostream>
using namespace std;
int readint() {
int num = 0; // 存储读取到的整数
int negative = 0; // 负数标识
char c;// 存储当前读取到的字符
c = cin.get();
while ((c < '0' || c > '9') && c != '-')
c = (1) ;
if (c == '-')
negative = 1;
else
(2) ;
c = cin.get();
while ( (3) ) {
(4) ;
c = cin.get();
}
if (negative == 1)
(5) ;
return num;
}
int main() {
int a, b;
a = readint();
b = readint();
cout << a << endl << b << endl;
return 0;
}
(1)cin.get()
(2)num=c-'0' 或 num=c-48
(3)c>='0'&&c<='9' 或 c>=48&&c<=57
(4)num=num*10+c-'0' 或 num=num*10+c-48
(5)num=-num 或 return -num
(郊游活动)有n名同学参加学校组织的郊游活动,已知学校给这n名同学 的郊游总经费为A元,与此同时第 i 位同学自己携带了Mi元。为了方便郊游, 活动地点提供B(≥n)辆自行车供人租用,租用第j 辆自行车的价格为Cj元, 每位同学可以使用自己携带的钱或者学校的郊游经费,为了方便账务管 理,每位同学只能为自己租用自行车, 且不会借钱给他人, 他们想知道最多 有多少位同学能够租用到自行车。(第四、五空2.5分,其余3分)
本题采用二分法。对于区间[l, r] ,我们取中间点mid并判断租用到自行车的人数能否达到mid。判断的过程是利用贪心算法实现的。
#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;
bool check(int nn) {
int count = 0, i, j;
i = (1) ;
j = 1;
while (i <= n) {
if ( (2) )
count += C[j] - M[i];
i++;
j++;
}
return (3) ;
}
void sort(int a[], int l, int r) {
int i = l, j = r, x = a[(l + r) / 2], y;
while (i <= j) {
while (a[i] < x) i++;
while (a[j] > x) j--;
if (i <= j) {
y = a[i]; a[i] = a[j]; a[j] = y;
i++; j--;
}
}
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}
int main() {
int i;
cin >> n >> B >> A;
for (i = 1; i <= n; i++)
cin >> M[i];
for (i = 1; i <= B; i++)
cin >> C[i];
sort(M, 1, n);
sort(C, 1, B);
l = 0;
r = n;
while (l <= r) {
mid = (l + r) / 2;
if ( (4) ) {
ans = mid;
l = mid + 1;
} else
r = (5) ;
}
cout << ans << endl;
return 0;
}
(1)n-nn+1
(2)M[i]<C[j] 或 M[i]<=C[j]
(3)count<=A
(4)check(mid)
(5)mid-1
完善程序: (打印月历)输入月份 m(1≤m≤12),按一定格式打印 2015 年第 m 月的月历。 (第三、四空 2.5 分,其余 3 分)
例如,2015 年 1 月的月历打印效果如下(第一列为周日):

#include <iostream>
#include <string>
using namespace std;
const int dayNum[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int m, offset, i;
int main()
{
cin >> m;
cout << "S\tM\tT\tW\tT\tF\tS" << endl; //'\t'为 TAB 制表符
⑴ ;
for(i = 1; i < m; i++)
offset = ⑵ ;
for(i = 0; i < offset; i++)
cout << '\t';
for(i = 1; i <= ⑶ ; i++)
{
cout << ⑷ ;
if(i == dayNum[m] || ⑸ == 0)
cout << endl;
else
cout << '\t';
}
return 0;
}
⑴offset = 4
⑵(offset + dayNum[i]) % 7
⑶dayNum[m]
⑷i
⑸(offset + i) % 7
完善程序:(中位数 median)给定 n(n 为奇数且小于 1000)个整数, 整数的范围在 0~m(0<m<2^31)之间, 请使 用二分法求这 n 个整数的中位数。所谓中位数,是指将这 n 个数排序之后,排在正中间的数。 (第五空 2分,其余 3 分)
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, lbound, rbound, mid, m, count;
int x[MAXN];
int main()
{
cin >> n >> m;
for(i = 0; i < n; i++)
cin >> x[i];
lbound = 0;
rbound = m;
while( ⑴ )
{
mid = (lbound + rbound) / 2;
⑵ ;
for(i = 0; i < n; i++)
if( ⑶ )
⑷ ;
if(count > n / 2)
lbound = mid + 1;
else
⑸ ;
cout << mid << " " << lbound << " " << rbound << " " << count << endl;
}
cout << rbound << endl;
return 0;
}
⑴lbound <= rbound
⑵count = 0
⑶x[i] >= mid
⑷count++
⑸rbound = mid - 1
把M个同样的球放到N个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?(用K表示)。
例如:M=7,N=3时,K=8;在这里认为(5,1,1)和(1,5,1)是同一种放置方法。
问:M=8,N=5时,K= 。
18
