信息学奥赛-入门级 题库
完善程序:(排列数)输入两个正整数n, m (1 ≤n ≤20, 1 ≤m ≤n),在 1~n 中任取 m 个数,按字典序从小到大输出所有这样的排列。例如
输入
输出:
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i,j, k;
bool flag;
int main()
{
cin>>n>>m;
memset(used, false, sizeof(used));
for (i = 1; i <= m; i++)
{
data[i] = i;
used[i] = true;
}
flag = true;
while (flag)
{
for (i = 1; i <= m-1; i++) cout<<data[i]<<" ";
cout<<data[m]<<endl;
flag = ① ;
for (i = m; i >= 1; i--)
{
② ;
for (j = data[i]+1; j <= n; j++) if (!used[j])
{
used[j] = true;
data[i] = ③ ;
flag = true;
break;
}
if (flag)
{
for (k = i+1; k <= m; k++)
for (j = 1; j <= ④ ; j++) if (!used[j])
{
data[k] = j;
used[j] = true;
break;
}
⑤ ;
}
}
}
}
①false 0
②used[data[i]] = false
③j
④n
⑤break
每份考卷都有一个8位二进制序列号。当且仅当一个序列号含有偶数个1 时,它才是有效的。例如,0000000 、01010011 都是有效的序列号,而 11111110不是。那么,有效的序列号共有 个。
128
定义字符串的基本操作为:删除一个字符\插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串A变成字符串B的最少操作步数,称为字符串A到字符串B的编辑距离。字符串“ ABCDEFG ”到字符串“ BADECG ”的编辑距离为 。
3
(子矩阵)给输入一个n1*m1的矩阵a,和n2*m2的矩阵b,问a中是否存在子矩阵和b相等。
若存在,输出所有子矩阵左上角的坐标:若不存在输出“There isno answer”。
#include<iostream>
using namespace std;
const int SIZE = 50;
int n1,m1,n2,m2,a[SIZE][SIZE],b[SIZE][SIZE];
int main()
{
int i,j,k1,k2;
bool good ,haveAns;
cin>>n1>>m1;
for(i=1;i<=n1;i++)
for(j=1;j<=m1;j++)
cin>>a[i][j];
cin>>n2>>m2;
for(i=1;i<=n2;i++)
for(j=1;j<=m2;j++)
①
haveAns=false;
for(i=1;i<=n1-n2+1;i++)
for(j=1;j<= ② ;j++){
③ ;
for(k1=1;k1<=n2;k1++)
for(k2=1;k2<= ④ ;k2++){
if(a[i+k1-1][j+k2-1]!=b[k1][k2])
good=false;
}
if(good){
cout<<i<<''<<j<<endl;
⑤ ;
}
}
if(!haveAns)
cout<<"There is no answer"<<endl;
return 0;
}
① cin>>b[i][j]
② m1-m2+1
③ good=true
④ m2
⑤ haveAns=true
(大整数开方) 输入一个正整数n(1≤n≤10100),试用二分法计算它的平方根的整数部分。
#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
// 其中len表示大整数的位数;num[1]表示个位,num[2]表示十位,以此类推
hugeint times(hugeinta,hugeintb)
// 计算大整数a和b的乘积
{
inti,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)
for(j=1;j<=b.len;j++)
① +=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
② ;
}
if(ans.num[a.len+b.len]>0)
ans.len=a.len+b.len;
else
ans.len=a.len+b.len-1;
return ans;
}
hugeint add(hugeinta,hugeintb)
// 计算大整数a和b的和
{
inti;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
if(a.len>b.len)
ans.len=a.len;
else
ans.len=b.len;
for(i=1;i<=ans.len;i++){
ans.num[i]+= ③ ;
ans.num[i+1]+= ans.num[i]/10;
ans.num[i]%=10;
}
if(ans.num[ans.len+1]>0)
ans.len++;
return ans;
}
hugeint average(hugeinta,hugeintb)
// 计算大整数a和b的平均数的整数部分
{
inti;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i--){
ans.num[i-1]+=( ④ )*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len--;
return ans;
}
hugeint plustwo(hugeinta)
// 计算大整数加2之后的结果
{
inti;
hugeint ans;
ans=a;
ans.num[1]+=2;
i=1;
while( (i<=ans.len)&&(ans.num[i]>=10) ){
ans.num[i+1]+=ans.num[i]/10;
ans.num[i]%=10;
i++;
}
if(ans.num[ans.len+1]>0)
⑤ ;
return ans;
}
boolover(hugeinta,hugeintb)
// 若大整数a>b则返回true,否则返回false
{
inti;
if( ⑥ )
return false;
if( a.len>b.len )
return true;
for(i=a.len;i>=1;i--){
if(a.num[i]<b.num[i])
return false;
if(a.num[i]>b.num[i])
return true;
}
return false;
}
int main()
{
string s;
inti;
hugeint target,left,middle,right;
cin>>s;
memset(target.num,0,sizeof(target.num));
target.len=s.length();
for(i=1;i<=target.len;i++)
target.num[i]=s[target.len-i]- ⑦
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over( ⑧ ))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i--)
cout<<left.num[i];
return 0;
}
① ans.num[i+j-1]
② ans.num[i]%=10
③ a.num[i]+b.num[i]
④ ans.num[i] % 2
⑤ ans.len++
⑥ a.len<b.len
⑦ '0'或 48
⑧ times(middle,middle),target
01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07 unsigned short x, y;
08 cin >> x >> y;
09 x = (x | x << 2) & 0x33;
10 x = (x | x << 1) & 0x55;
11 y = (y | y << 2) & 0x33;
12 y = (y | y << 1) & 0x55;
13 unsigned short z = x | y << 1;
14 cout << z << endl;
15 return 0;
16 }
假设输入的 x、y 均是不超过 15 的自然数,完成下面的判断题和单选题:
01 #include <algorithm>
02 #include <iostream>
03 #include <limits>
04
05 using namespace std;
06
07 const int MAXN = 105;
08 const int MAXK = 105;
09
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14 if (m == 1) return n;
15 if (n == 0) return 0;
16
17 int ret = numeric_limits<int>::max();
18 for (int i = 1; i <= n; i++)
19 ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
20 return ret;
21 }
22
23 int g(int n, int m)
24 {
25 for (int i = 1; i <= n; i++)
26 h[i][1] = i;
27 for (int j = 1; j <= m; j++)
28 h[0][j] = 0;
29
30 for (int i = 1; i <= n; i++) {
31 for (int j = 2; j <= m; j++) {
32 h[i][j] = numeric_limits<int>::max();
33 for (int k = 1; k <= i; k++)
34 h[i][j] = min(
35 h[i][j],
36 max(h[i - k][j], h[k - 1][j - 1]) + 1);
37 }
38 }
39
40 return h[n][m];
41 }
42
43 int main()
44 {
45 int n, m;
46 cin >> n >> m;
47 cout << f(n, m) << endl << g(n, m) << endl;
48 return 0;
49 }
假设输入的 n、m 均是不超过 100 的正整数,完成下面的判断题和单选题:
01 #include <iostream>
02
03 using namespace std;
04
05 int n, k;
06
07 int solve1()
08 {
09 int l = 0, r = n;
10 while (l <= r) {
11 int mid = (l + r) / 2;
12 if (mid * mid <= n) l = mid + 1;
13 else r = mid - 1;
14 }
15 return l - 1;
16 }
17
18 double solve2(double x)
19 {
20 if (x == 0) return x;
21 for (int i = 0; i < k; i++)
22 x = (x + n / x) / 2;
23 return x;
24 }
25
26 int main()
27 {
28 cin >> n >> k;
29 double ans = solve2(solve1());
30 cout << ans << ' ' << (ans * ans == n) << endl;
31 return 0;
32 }
假设 int 为 32 位有符号整数类型,输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数,完成下面的判断题和单选题:
(枚举因数)从小到大打印正整数 n 的所有正因数。
试补全枚举程序。
01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int main() {
05 int n;
06 cin >> n;
07
08 vector<int> fac;
09 fac.reserve((int)ceil(sqrt(n)));
10
11 int i;
12 for (i = 1; i * i < n; ++i) {
13 if (①) {
14 fac.push_back(i);
15 }
16 }
17
18 for (int k = 0; k < fac.size(); ++k) {
19 cout << ② << " ";
20 }
21 if (③) {
22 cout << ④ << " ";
23 }
24 for (int k = fac.size() - 1; k >= 0; --k) {
25 cout << ⑤ << " ";
26 }
27 }
(洪水填充)现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下:给定起始像素的位置和待填充的颜色,将起始像素和所有可达的像素(可达的定义:经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同),替换为给定的颜色。
试补全程序。
01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int ROWS = 8;
05 const int COLS = 8;
06
07 struct Point {
08 int r, c;
09 Point(int r, int c) : r(r), c(c) {}
10 };
11
12 bool is_valid(char image[ROWS][COLS], Point pt,
13 int prev_color, int new_color) {
14 int r = pt.r;
15 int c = pt.c;
16 return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
17 ① && image[r][c] != new_color);
18 }
19
20 void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
21 queue<Point> queue;
22 queue.push(cur);
23
24 int prev_color = image[cur.r][cur.c];
25 ② ;
26
27 while (!queue.empty()) {
28 Point pt = queue.front();
29 queue.pop();
30
31 Point points[4] = { ③ , Point(pt.r - 1, pt.c),
32 Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
33 for (auto p : points) {
34 if (is_valid(image, p, prev_color, new_color)) {
35 ④ ;
36 ⑤ ;
37 }
38 }
39 }
40 }
41
42 int main() {
43 char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
44 {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
45 {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
46 {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
47 {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
48 {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
49 {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
50 {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
51
52 Point cur(4, 4);
53 char new_color = 'y';
54
55 flood_fill(image, cur, new_color);
56
57 for (int r = 0; r < ROWS; r++) {
58 for (int c = 0; c < COLS; c++) {
59 cout << image[r][c] << " ";
60 }
61 cout << endl;
62 }
63 // 输出:
64 // g g g g g g g g
65 // g g g g g g r r
66 // g r r g g r g g
67 // g y y y y r g r
68 // g g g y y r g r
69 // g g g y y y y r
70 // g g g g g y g g
71 // g g g g g y y g
72
73 return 0;
74 }
#include <cstdlib>
#include <iostream>
using namespace std;
char encoder[26] = {'C','S','P',0};
char decoder[26];
string st;
int main() {
int k = 0;
for (int i = 0; i < 26; ++i)
if (encoder[i] != 0) ++k;
for (char x ='A'; x <= 'Z'; ++x) {
bool flag = true;
for (int i = 0; i < 26; ++i)
if (encoder[i] ==x) {
flag = false;
break;
}
if (flag) {
encoder[k]= x;
++k;
}
}
for (int i = 0; i < 26; ++i)
decoder[encoder[i]- 'A'] = i + 'A';
cin >> st;
for (int i = 0; i < st.length( ); ++i)
st[i] = decoder[st[i] -'A'];
cout << st;
return 0;
}
#include <iostream>
using namespace std;
long long n, ans;
int k, len;
long long d[1000000];
int main() {
cin >> n >> k;
d[0] = 0;
len= 1;
ans = 0;
for (long long i = 0; i <n; ++i) {
++d[0];
for (int j = 0; j + 1<len; ++j) {
if (d[j] == k) {
d[j] = 0;
d[j + 1] += 1;
++ans;
}
}
if (d[len- 1] == k) {
d[len - 1] = 0;
d[len] =1;
++len;
++ans;
}
}
cout << ans << endl;
return 0;
}
假设输入的n是不超过2^62的正整数,k都是不超过10000的正整数,完成下面的判断题和单选题:
#include <algorithm>
#include <iostream>
using namespace std;
int n;
int d[50][2];
int ans;
void dfs(int n, int sum) {
if (n == 1) {
ans = max(sum, ans);
return;
}
for (int i = 1; i < n; ++i) {
int a = d[i - 1][0], b = d[i - 1][1];
int x = d[i][0], y = d[i][1];
d[i - 1][0] = a + x;
d[i - 1][1] = b + y;
for (int j = i; j < n - 1; ++j)
d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
int s = a + x + abs(b - y);
dfs(n - 1, sum + s);
for (int j = n - 1; j > i; --j)
d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
d[i - 1][0] = a, d[i - 1][1] = b;
d[i][0] = x, d[i][1] = y;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i][0];
for (int i = 0; i < n;++i)
cin >> d[i][1];
ans = 0;
dfs(n, 0);
cout << ans << endl;
return 0;
}
假设输入的n是不超过5。的正整数,d[i][0], d[i][l]都是不超过 10000的正整数,完成下面的判断题和单选题:
(质因数分解)给出正整数n,请输出将n质因数分解的結果,结果从小 到大输出。
例如:输入n=120,程序应该输出2 2 2 3 5,表示120=2 X2X2X 3X5。输入保证2≤n≤10^9。提示:先从小到大枚举变量i,然后用i不停试 除n来寻找所有的质因子。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for(i = ①; ② <=n; i ++){
③{
printf("%d ", i);
n = n / i;
}
}
if(④)
printf("%d ", ⑤);
return 0;
}
(最小区间覆盖)给出n个区间,第i个区间的左右端点是[ai, bi]。现在 要在这些区间中选出若干个,使得区间[0,m]被所选区间的并覆盖(即每 一个0≤i≤m都在某个所选的区间中)。保证答案存在,求所选区间个数 的最小值。
输入第一行包含两个整数n和m(1≤n≤5000, 1≤m≤10^9 )
接下来n行,每行两个整数ai,bi(0≤ai, bi ≤ m)。
提示:使用贪心法解决这个问题。先用0(n^2)的时间复杂度排序,然后贪心 选择这些区间。
试补全程序。
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans = 0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}
甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲________(去了/没去)(1 分),乙________(去了/没去)(1 分),丁________(去了/没去)(1 分),周末________(下雨/没下雨)(2 分)。
答:去了 没去 没去 没下雨 (第4 空 2 分,其余 1 分)