完善程序，每年两题，每题每空
2-4
分，共
28
分。
【解题步骤】
1
、仔细读题，尤其是题目给你的解题思路：解决什么问题？用的什么算法？输入输出是什么？
……
2
、要知道变量的含义，也可通过变量单词的意思知道，比如
sum
表示和，
que
表示队列等等。
3
、在充分了解前两点的基础上，先根据自己的想法大致想想：如果让你实现程序，你会怎么做。
4
、通读程序，理顺程序结构，千万不要因为程序很长而觉得气馁，有时程序越长，填空越简单。
5
、按照程序执行的顺序做，遇到难的先放一边，继续往下做。有些空格很简单，一下就能看出来的。
6
、到这步为止，程序大概意图就知道了，然后就是填比较难的几格了。这一点就靠你对程序的理解了。
7
、填完了以后，再执行一遍程序，有样例就结合样例，没样例就自己造数据模拟。
【解题技巧】
1
、变量初始化：这个得结合后面的运算确定，不过有些也很简单，如
sum=0
之类的。
2
、
for
循环初、终值：如果是嵌套的循环，可结合父循环或子循环确定。
3
、更新最优解：比较或赋值。
4
、要填的空格与某句对应，这样的例子在下面能找到很多。
NOIP2011-1.
子矩阵
给输入一个
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++)
cin>>b[i][j]
;
haveAns=false;
for(i=1;i<=n1-n2+1;i++)
for(j=1;j<=
m1-m2+1
;j++){
good=true
;
for(k1=1;k1<=n2;k1++)
for(k2=1;k2<=
m2
;k2++){
if(a[i+k1-1][j+k2-1]!=b[k1][k2])
good=false;
}
if(good){
cout<<i<<”<<j<<endl;
haveAns=true
;
}
}
if(!haveAns)
cout<<“Thereis no answer”<<endl;
return 0;
}
NOIP2011-2.
大整数开方
输入一个正整数
n ( 1 ≤n≤10^100
)
，试用二分法计算它的平方根的整数部分。
#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
int len,num[SIZE];
};
//
其中
len
表示大整数的位数
; num[1]
表示个位，
num[2]
表示十位，以此类推
hugeint times(hugeint a,hugeint b)
//
计算大整数
a
和
b
的乘积
{
int i,j;
hugeint ans;
memset(ans.num,0,sizeof(ans.num));
for(i=1;i<=a.len;i++)
for(j=1;j<=b.len;j++)
ans.num[i+j-1]
+=a.num[i]*b.num[j];
for(i=1;i<=a.len+b.len;i++){
ans.num[i+1]+=ans.num[i]/10;
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(hugeint a,hugeint b)
//
计算大整数
a
和
b
的和
{
int i;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]+=
a.num[i]+b.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(hugeint a,hugeint b)
//
计算大整数
a
和
b
的平均数的整数部分
{
int i;
hugeint ans;
ans=add(a,b);
for(i=ans.len;i>=2;i–){
ans.num[i-1]+=(
ans.num[i] % 2
)*10;
ans.num[i]/=2;
}
ans.num[1]/=2;
if(ans.num[ans.len]==0)
ans.len–;
return ans;
}
hugeint plustwo(hugeint a)
//
计算大整数
a
加
2
之后的结果
{
int i;
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)
ans.len++
;
return ans;
}
bool over(hugeint a,hugeint b)
//
若大整数
a>b
则返回
true
，否则返回
false
{
int i;
if(
a.len<b.len
)
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;
int i;
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]-
‘0’
;
memset(left.num,0,sizeof(left.num));
left.len=1;
left.num[1]=1;
right=target;
do{
middle=average(left,right);
if(over(
times(middle,middle),target
))
right=middle;
else
left=middle;
}while(!over(plustwo(left),right) );
for(i=left.len;i>=1;i–)
cout<<left.num[i];
return 0;
}
NOIP2012-1.
坐标统计
输入
n
个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点
(
即
x
、
y
坐标都比它小
)
，它可以控制的点的数目称为
“
战斗力
”
。依次输出每个点的战斗力，最后输出战斗力最高的点的编号
(
如果两个点战斗力一样，输出较大的编号
)
。
#include<iostream>
using namespace std;
const int SIZE = 100;
int x[SIZE], y[SIZE], f[SIZE];
int n, i, j, max_f, ans;
int main()
{
cin>>n;
for (i = 1; i <= n; i++)
cin>>x[i]>>y[i];
max_f = 0;
for (i = 1; i <= n; i++)
{
f[i] =
0
;
for (j = 1; j <= n; j++)
{
if (x[j] <x[i] &&
y[j] < y[i]
;
f[i]++
;
}
if(
f[i] >= max_f
)
{
max_f = f[i];
ans = i
;
}
}
for (i = 1; i <= n; i++)
cout<<f[i]<<endl;
cout<<ans<<endl;
return o;
}
NOIP2012-2.
排列数
输入两个正整数
n, m (1 ≤n ≤20, 1 ≤m ≤n)
，在
1~n
中任取
m
个数，按字典序从小到大输出所有这样的排列。例如
输入
:
3 2
输出
:
1 2
1 3
2 1
2 3
3 1
3 2
#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 =
false
;
for (i = m; i>= 1; i–)
{
used[data[i]] = false
;
for (j =data[i]+1; j <= n; j++) if (!used[j])
{
used[j] =true;
data[i] =
j
;
flag = true;
break;
}
if (flag)
{
for (k = i+1;k <= m; k++)
for (j = 1; j<=
n
; j++) if (!used[j])
{
data[k] = j;
used[j] =true;
break;
}
break
;
}
}
}
}
NOIP2013-1.
序列重排
全局数组变量
a
定义如下
:
const int SIZE = 100;
int a[SIZE], n;
它记录着一个长度为
n
的序列
a[1], a[2], …, a[n]
。
现在需要一个函数，以整数
p (1 ≤ p≤ n)
为参数，实现如下功能
:
将序列
a
的前
p
个数与后
n – p
个数对调，且不改变这
p
个数
(
或
n – p
个数
)
之间的相对位置。例如，长度为
5
的序列
1, 2, 3, 4, 5
，当
p = 2
时重排结果为
3, 4, 5, 1, 2
。
有一种朴素的算法可以实现这一需求，其时间复杂度为
O(n)
、空间复杂度为
O(n):
void swap1(int p)
{
int i, j, b[SIZE];
for (i = 1; i <= p; i++)
b[
n–p+i
] = a[i];
for (i = p + 1; i <= n; i++)
b[i-p]=
a[i]
;
for(i=1;i<=
n
;i++)
a[i] = b[i];
}
我们也可以用时间换空间，使用时间复杂度为
O(n
2
)
、空间复杂度为
O(1)
的算法
:
void swap2(int p)
{
int i, j, temp;
for (i = p + 1; i <= n; i++) {
temp = a[i];
for(j=i;j>=
i–p+1
;j–)
a[j] = a[j – 1];
a[i – p]
= temp;
}
}
NOIP2013-2.
二叉查找树
二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数
n
，表示这棵树有
n
个顶点，编号分别为
1, 2, …, n
，其中编号为
1
的为根结点。之后的第
i
行有三个数
value, left_child, right_child
，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用
0
代替。输出
1
表示这棵树是二叉查找树，输出
0
则表示不是。
#include <iostream>
using namespace std;
const int SIZE = 100;
const int INFINITE = 1000000;
struct node {
int left_child, right_child, value;
};
node a[SIZE];
int is_bst(int root, int lower_bound, int upper_bound)
{
int cur;
if (root == 0)
return 1;
cur = a[root].value;
if ((cur > lower_bound) && (
cur < upper_bound
) &&
(is_bst(a[root].left_child, lower_bound, cur)== 1) &&
(is_bst(
a[root].right_child
,
cur
,
upper_bound
)== 1))
return 1;
return 0;
}
int main()
{
int i, n;
cin>>n;
for (i = 1; i <= n; i++)
cin>>a[i].value>>a[i].left_child>>a[i].right_child;
cout<<is_bst(
1
,-INFINITE, INFINITE)<<endl;
return 0;
}
NOIP2014-1.
数字删除
下面程序的功能是将字符串中的数字字符删除后输出。请填空。
#include <iostream>
using namespace std;
int delnum(char *s) {
int i, j;
j = 0;
for (i = 0; s[i] != ‘\0’; i++)
if (s[i] < ‘0’
||
s[i] > ‘9’) {
s[j] = s[i];
j++
;
}
return
j
;
}
const int SIZE = 30;
int main() {
char s[SIZE];
int len, i;
cin.getline(s, sizeof(s));
len = delnum(s);
for (i = 0; i < len; i++)
cout<<
s[i]
;
cout << endl;
return 0;
}
NOIP2014-2.
最大子矩阵和
给出
m
行
n
列的整数矩阵，求最大的子矩阵和
(
子矩阵不能为空
)
。
输入第一行包含两个整数
m
和
n
，即矩阵的行数和列数。之后
m
行，每行
n
个整数，描述整个矩阵。程序最终输出最大的子矩阵和。
#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][1]
;
for (i = 1; i <= m; i++)
rowsum[i][0]=0
;
for (i = 1; i <= m; i++)
for (j = 1; j<= n; j++)
rowsum[i][j] =
rowsum[i][j-1]+matrix[i][j]
;
for (first = 1; first <= n; first++)
for (last = first;last <= n; last++) {
area=0
;
for (i = 1; i<= m; i++) {
area+=
rowsum[i][last]-rowsum[i][first-1]
;
if (area > ans)
ans = area;
if (area < 0)
area = 0;
}
}
cout << ans << endl;
return 0;
}
NOIP2015-1.
打印月历
输入月份
m(1≤m≤12)
，按一定格式打印
2015
年第
m
月的月历。例如，
2015
年
1
月的月历打印效果如下
(
第一列为周日
)
：
#include<iostream>
#include<string>
usingnamespace std;
const intdayNum[ ] = {-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
制表符
offset=4
;
for(i= 1; i < m; i++)
offset =
(offset+dayNum[i])%7
;
for(i= 0; i < offset; i++)
cout << ‘\t’;
for(i=1;i<=
dayNum[m]
;i++)
{
cout<<
i
;
if(i == dayNum[m] ||
(offset+i)%7
==0)
cout << endl;
else
cout << ‘\t’;
}
return 0;
}
NOIP2015-2.
中位数
median
给定
n(n
为奇数且小于
1000)
个整数，整数的范围在
0~m(0<m<2^31)
之间，请使用二分法求这
n
个整数的中位数。所谓中位数，是指将这
n
个数排序之后，排在正中间的数。
#include<iostream>
usingnamespace std;
const intMAXN = 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(
lbound<rbound
)
{
mid = (lbound + rbound) / 2;
count=0
;
for(i = 0; i < n; i++)
if(
x[i]>mid
)
count++
;
if(count > n / 2)
lbound = mid + 1;
else
rbound=mid
;
cout << mid << ” “<< lbound << ” ” << rbound << ” “<< count << endl;
}
cout<< rbound << endl;
return 0;
}
NOIP2016-1.
读入整数
请完善下面的程序，使得程序能够读入两个
int
范围内的整数，并将这两个整数分别输出，每行一个。输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。
例如
:
输入
:
123 -789
输出
:
123
-789
#include<iostream>
using namespacestd;
int readint() {
int num = 0;
//
存储读取到的整数
int negative = 0;
//
负数标识
charc;
//
存储当前读取到的字符
c =cin.get();
while((c < ‘0’ || c > ‘9’) && c != ‘-‘)
c =
cin.get()
;
if (c== ‘-‘)
negative = 1;
else
num=c-‘0’
;
c =cin.get();
while(
c>=’0’&&c<=’9′
) {
num=num*10+c-‘0’
;
c = cin.get();
}
if(negative == 1)
return -num
;
return num;
}
int main() {
int a,b;
a =readint();
b =readint();
cout<< a << endl << b << endl;
return 0;
}
NOIP2016-2.
郊游活动
有
n
名同学参加学校组织的郊游活动，已知学校给这
n
名同学的郊游总经费为
A
元，与此同时第
i
位同学自己携带了
Mi
元。为了方便郊游，活动地点提供
B(≥n)
辆自行车供人租用，租用第
j
辆自行车的价格为
Cj
元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。
本题采用二分法。对于区间
[l, r]
，我们取中间点
mid
并判断租用到自行车的人数能否达到
mid
。判断的过程是利用贪心算法实现的。
#include<iostream>
using namespacestd;
#define MAXN1000000
int n, B, A,M[MAXN], C[MAXN], l, r, ans, mid;
bool check(int nn){
intcount = 0, i, j;
i =
n-nn+1
;
j = 1;
while(i <= n) {
if (
M[i]<=C[j]
)
count += C[j] – M[i];
i++;
j++;
}
return
count<=A
;
}
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 (
check(mid)
) {
ans = mid;
l = mid + 1;
} else
r =
mid-1
;
}
cout<< ans << endl;
return 0;
}