完善程序,每年两题,每题每空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(n2)、空间复杂度为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 月的月历打印效果如下(第一列为周日):
NOIP普及组初赛历年试题及答案(完善题篇)-少儿编程网
#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;
}

*