完善程序，每年两题，每题每空2-4分，共28分。
【数学题目】
1、变量赋初值，如果以后用到的是加减运算，则赋初值0；如果以后用到的是乘除运算，则赋初值为1。
2、循环条件的填空，分析表达式的规律，看表达式中的最后一项的值是否到了第m项或者是第n项，如果到了，则在循环中的第二个表达式中用到的是i<=或者i>=。
3、循环条件中如果用的是while 语句，则循环变量的初值应该在while 的外面定义和赋初值，在循环语句中必须给变量自加或者是自减，即i++或i–。
【字符串题目】
1、把一个数字字符转变成对应的数值的格式是：ch=’1’-‘0’;把大写字母转变为小写字母的格式：c h=c h+32 ;把小写字母转变为大写字母的格式为：ch=ch-32 。
2、区分好字符数组中的指针和指针所指的值的关系。在循环语句中，当指针往后走一个位置的时候，用的是指针的自加，而不是指针所指的值的自加。
【结构体题目】
1、注意定义结构体变量时的格式。
2、结构体中成员的调用格式。结构体中的成员分为多种类型，调用结构体中的成员，使用的是“.”或者是“—>”运算符。
3、如果返回的是结构体的话，函数的返回类型必须是结构体类型。调用函数的格式中，调用的若是结构体数组，则只用写结构体数组名。
【函数题目】
1、看函数的返回类型，函数的返回类型必须和return语句返回的表达式的类型一致。
2、函数的调用的情况，函数调用时只用写函数的名称，以及函数的参数。如：f1(x)和f2(x,y)。
【数组题目】
1、求一个数值数组中的所有值的平均值和把大于或者小于平均值的数放到另外一个数组中。首先定义一个变量来存放平均值，如果变量avg 已经定义但是没有赋初值，那么这个空填写的内容的为：avg =0;
2、求平均值时有两种方法，如果在for 语句的后面有avg=avg /N;则第二个空一般的填写时avg+=s[i];如果说没有avg=avg /N;则填写的是：avg +=s[i]/N。
3、二维数组遍历时，使用的是两个循环，使用的是循环的嵌套使用，第二个循环填写的内容为：j=0。
NOIP2011-1. 大整数开方（同普及组2011-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;
}
NOIP2011-2. 笛卡尔树
对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点，每个节点的权值都大雨父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。现输入序列的规模n（1≤n<100）和序列的n个元素，试求其对应的笛卡尔树的深度d（根节点深度为1），以及有多少个叶子节点的深度为d。
#include<iostream>
using namespace std;
const int SIZE=100+5;
const int INFINITY=1000000;
int n,a[SIZE],maxDeep,num;
void solve(int left,int right,int deep)
{
int i,j,min;
if(deep>maxDeep){
maxDeep=deep;
num=1;
}
else if(deep==maxDeep)
num++;
min= INFINITY;
for(i=left;i<=right;i++)
if(min>a[i]){
min=a[i];
j = i;
}
if(left<j)
solve(left, j –1, deep + 1);
if(j<right)
solve(j+ 1, right, deep + 1);
}
int main()
{
inti;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
maxDeep=0;
solve(1,n,1);
cout<<maxDeep<<‘ ‘<<num<<endl;
return 0;
}
NOIP2012-1. 排列数（同普及组2012-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;
}
}
}
}
NOIP2012-2.新壳栈
小Z设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前c个元素是它的壳，支持翻转操作。其中，c> 2 是一个固定的正整数，表示壳的厚度。小Z还希望，每次操作，无论是压入、弹出还是翻转，都仅用与c无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？
程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足c个，应当输出相应的错误信息。
#include<iostream>
usingnamespacestd;
const int NSIZE=100000, CSIZE=1000;
int n,c,r,tail,head, s[NSIZE],q[CSIZE];
//数组s模拟一个栈，n为栈的元素个数
//数组q模拟一个循环队列，tail为队尾的下标，head为队头的下标
booldirection,empty;
int previous(intk)
{
if(direction)
return ((k+c -2)%c)+1;
else
return (k%c)+1;
}
int next(intk)
{
if(direction)
return (k % c) + 1;
else
return ((k+c -2)%c)+1;
}
void push()
{
int element;
cin>>element;
if(next(head)==tail){
n++;
s[n] = q[tail];
tail=next(tail);
}
if(empty)
empty=false;
else
head=next(head);
q[head]=element;
}
void pop()
{
if(empty){
cout<<“Error:thestackisempty!”<<endl;
return;
}
cout<<q[head]<<endl;
if(tail==head)
empty=true;
else{
head=previous(head);
if(n>0){
tail=previous(tail);
q[tail]=s[n];
n–;
}
}
}
voidreverse()
{
int temp;
if(next(head)==tail){
direction = !direction;
temp=head;
head=tail;
tail=temp;
}
else
cout<<“Error:lessthan”<<c<<“elementsinthestack!”<<endl;
}
int main()
{
cin>>c;
n= 0;
tail=1;
head=1;
empty=true;
direction=true;
do{
cin>>r;
switch(r){
case1:push();break;
case2:pop();break;
case3:reverse();break;
}
}while(r!=0);
return 0;
}
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;
}
}
事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(1)：
void swap3(int p)
{
int start1, end1, start2, end2, i, j, temp;
start1 = 1;
end1 = p;
start2 = p + 1;
end2 = n;
while (true) {
i = start1;
j = start2;
while ((i <= end1) && (j <= end2)) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}
if (i <= end1)
start1 = i;
else if ( j<= end2 ) {
start1 = i
endl = j–1
start2 = j;
}
else
break;
}
}
NOIP2013-2. 两元序列
试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长，输出任意一个即可。例如，序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中，有两段满足条件的最长子序列，长度均为7，分别用下划线和上划线标出。
#include <iostream>
using namespace std;
int main()
{
const int SIZE = 100;
int n, i, j, a[SIZE], cur1, cur2, count1, count2,
ans_length, ans_start, ans_end;
//cur1, cur2分别表示当前子序列中的两个不同整数
//count1, count2分别表示cur1, cur2在当前子序列中出现的次数
cin>>n;
for (i = 1; i <= n; i++)
cin>>a[i];
i = 1;
j = 1;
//i, j分别表示当前子序列的首尾，并保证其中至多有两个不同整数
while ((j <= n) && (a[j] == a[i]))
j++;
cur1 = a[i];
cur2 = a[j];
count1 = j-1
count2 = 1;
ans_length = j – i + 1;
while (j < n) {
j++;
if (a[j] == cur1)
count1++;
else if (a[j] == cur2)
count2++;
else {
if (a[j – 1] == cur1 ) {
while (count2 > 0) {
if (a[i] == cur1)
count1–;
else
count2–;
i++;
}
cur2 = a[j];
count2 = 1;
}
else {
while (count1 > 0) {
if (a[i] == cur1)
count1–
else
count2–
i++;
}
cur1= a[j]
count1 = 1;
}
}
if (ans_length < j – i + 1) {
ans_length = j – i + 1;
ans_start = i;
ans_end = j;
}
}
for (i = ans_start; i <= ans_end; i++)
cout<<a[i]<<‘ ‘;
return 0;
}
NOIP2014-1. 双栈模拟数组
只使用两个栈结构 stack1 和 stack2，模拟对数组的随机读取。作为栈结构，stack1 和 stack2 只能访问栈顶(最后一个有效元素)。栈顶指针 top1 和 top2 均指向栈顶元素的下一个位置。
输入第一行包含两个整数，分别是数组长度 n 和访问次数 m，中间用单个空格隔开。第二行包含 n 个整数，依次给出数组各项(数组下标从 0 到 n-1)。第三行包含 m 个整数，需要访问的数组下标。对于每次访问，输出对应的数组元素。
#include<iostream>
usingnamespace std;
constint SIZE = 100;
intstack1[SIZE], stack2[SIZE];
inttop1, top2;int n, m, i, j;
voidclearStack() {
int i;
for (i = top1; i < SIZE; i++)
stack1[i] = 0;
for (i = top2; i < SIZE; i++)
stack2[i] = 0;
}
intmain() {
cin >> n >> m;
for (i = 0; i < n; i++) cin >> stack1[i];
top1= n ;
top2= 0;
for (j = 0; j < m; j++) {
cin >> i;
while (i < top1 – 1) {
top1–;
stack2[top2]=stack1[top1] ;
top2++;
}
while (i > top1 – 1) {
top2–;
stack1[top1]=stack2[top2];
top1++;
}
clearStack();
cout << stack1[top1-1]<< endl;
}
return 0;
}
NOIP2014-2.最大子矩阵和（同普及组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. 双子序列最大和
给定一个长度为 n(3 ≤ n ≤ 1000)的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求:每个连续子序列长度至少为 1，且两个连续子序列之间至少间隔 1 个数。
#include <iostream>
using namespace std;
const int MAXN = 1000;
int n, i, ans, sum;
int x[MAXN];
int lmax[MAXN];
// lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中，最大的序列和
int rmax[MAXN];
// rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中，最大的序列和
int main() {
cin >>n;
for (i = 0; i< n; i++)
cin >>x[i];
lmax[0] =x[0];
for (i = 1; i< n; i++)
if (lmax[i -1] <= 0)
lmax[i] =x[i];
else
lmax[i] =lmax[i – 1] + x[i];
for (i = 1; i< n; i++)
if (lmax[i]< lmax[i – 1])
lmax[i] =lmax[i – 1];
rmax[n-1]=x[n-1];
for (i = n -2; i >= 0; i–)
if (rmax[i +1] <= 0)
rmax[i]=x[i];
else
rmax[i]=rmax[i+1]+x[i] ;
for (i = n -2; i >= 0; i–)
if (rmax[i]< rmax[i + 1])
rmax[i]=rmax[i+1];
ans = x[0] +x[2];
for (i = 1; i< n – 1; i++) {
sum= lmax[i-1]+rmax[i+1] ;
if (sum >ans)
ans = sum;
}
cout <<ans << endl;
return 0;
}
NOIP2015-2. 最短路径问题
无向连通图 G 有 n 个结点，依次编号为 0,1,2,…,(n-1)。用邻接矩阵的形式给出每条边的边长，要求输出以结点 0 为起点出发，到各结点的最短路径长度。
使用 Dijkstra 算法解决该问题:利用 dist 数组记录当前各结点与起点的已找到的最短路径长度;每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值;不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。
#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i, j, v;
int w[MAXV][MAXV]; // 邻接矩阵，记录边长
// 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度，若无边则为-1
int dist[MAXV];int used[MAXV]; // 记录结点是否已扩展(0:未扩展;1:已扩展)
int main() {
cin >>n;
for (i = 0; i< n; i++)
for (j = 0; j< n; j++)
cin >>w[i][j];
dist[0] = 0;
for (i = 1; i< n; i++)
dist[i] = -1;
for (i = 0; i< n; i++)
used[i] = 0;
while (true) {
v=-1 ;
for (i = 0; i< n; i++)
if(used[i]!=1&&dist[i]!=-1&&(v==-1||dist[i]<dist[v] ))
v=i ;
if (v == -1)
break;
used[v]=1 ;
for (i = 0; i< n; i++)
if (w[v][i] !=-1 && (dist[i] == -1 || dist[v]+w[v][i]<dist[i] ))
dist[i] =dist[v] + w[v][i];
}
for (i = 0; i< n; i++)
cout <<dist[i] << endl;
return 0;
}
NOIP2016-1. 交朋友
根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。现在有 n 名身高两两不相同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为 1.80 米的同学进入教室时，有一名身高为 1.79 米的同学和一名身高为1.81米的同学在教室里，那么这名身高为 1.80 米的同学会更想和身高为 1.81 米的同学做朋友。对于第一个走入教室的同学我们不做预测。
由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。
#include <iostream>
using namespace std;
#define MAXN 200000
#define infinity 2147483647
int answer[MAXN], height[MAXN],previous[MAXN], next[MAXN];
int rank[MAXN];
int n;
void sort(int l, int r) {
int x =height[rank[(l + r) / 2]], i = l, j = r, temp;
while (i <=j)
{
while(height[rank[i]] < x) i++;
while(height[rank[j]] > x) j–;
if(i<=j) {
temp =rank[i]; rank[i] = rank[j]; rank[j] = temp;
i++; j–;
}
}
if (i < r)sort(i, r);
if (l < j)sort(l, j);
}
int main()
{
cin >>n;
int i, higher,shorter;
for (i = 1; i<= n; i++) {
cin >>height[i];
rank[i] = i;
sort(1, n);
for (i = 1; i<= n; i++) {
previous[rank[i]]= rank[i – 1];
next[rank[i]]=rank[i+1];
}
for (i = n; i>= 2; i–){
higher =shorter = infinity;
if(previous[i] !=0)
shorter =height[i] – height[previous[i]];
if (next[i] !=0)
higher=height[next[i]]-height[i];
if (shorter<higher)
answer[i] =previous[i];
else
answer[i] =next[i];
next[previous[i]]= next[i];
previous[next[i]]=previous[i];
}
for (i = 2; i<= n; i++)
cout <<i << “:” << answer[i];
return 0;
}
NOIP2016-2. 交通中断
有一个小国家，国家内有 n 座城市和 m 条双向的道路，每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1)个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。
对于每一个城市 i，假定只有第 i 个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度改变。
我们采用邻接表的方式存储图的信息，其中 head[x]表示顶点 x 的第一条边的编号，next[i]表示第 i 条边的下一条边的编号，point[i]表示第 i 条边的终点，weight[i]表示第 i 条边的长度。
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define infinity 2147483647
int head[MAXN], next[MAXM], point[MAXM],weight[MAXM];
int queue[MAXN], dist[MAXN], visit[MAXN];
int n, m, x, y, z, total = 0, answer;
void link(int x,int y,int z) {
total++;
next[total] =head[x];
head[x] =total;
point[total] =y;
weight[total]= z;
total++;
next[total] =head[y];
head[y] =total;
point[total] =x;
weight[total]= z;
}
int main() {
int i, j, s,t;
cin >> n>> m;
for (i = 1; i<= m; i++) {
cin >> x>> y >> z; link(x, y, z);
}
for (i = 1; i<= n; i++) dist[i] = infinity;
dist[1]=0;
queue[1] = 1;
visit[1] = 1;
s = 1;
t = 1;
// 使用 SPFA 求出第一个点到其余各点的最短路长度
while (s <= t) {
x = queue[s % MAXN];
j = head[x];
while (j != 0) {
if (dist[x]+weight[j]<dist[point[j]]) {
dist[point[j]] = dist[x] + weight[j];
if (visit[point[j]] == 0) {
t++;
queue[t % MAXN] = point[j];
visit[point[j]] = 1;
}
}
j = next[j];
}
visit[x]=0;
s++;
}
for (i = 2; i<= n; i++) {
queue[1] = 1;
memset(visit,0, sizeof(visit));
visit[1] = 1;
s = 1;
t = 1;
while (s <=t) { // 判断最短路长度是否不变
x = queue[s];
j = head[x];
while (j != 0){
if (point[j]!= i && dist[x]+weight[j]==dist[point[j]]
&&visit[point[j]]== 0) {
visit[point[j]]=1;
t++;
queue[t] =point[j];
}
j = next[j];
}
s++;
}
answer = 0;
for (j = 1; j<= n; j++)
answer += 1 -visit[j];
cout <<i << “:” << answer – 1 << endl;
}
return 0;
}
支付宝扫一扫
