【用脚趾头解决NOIP】(2)NOIP2009~NOIP2015年普及组完善程序

文章索引：

这一篇博客，算是我的作业吧。

根据难度与时间，我从完善程序的第一题开始，从NOIP2009到NOIP2015年，逐题写出思考思想。

NOIP2009（完善程序第一题）：最大连续字段和

题意描述：

给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。

题目源代码：

#include <cstdio>
#include <iostream>
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg;
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    tmp=0;
    ans=0;
    len=0;
    beg=/*空<1>*/;
    for(i=1;i<=n;i++){
        if(tmp+a[i]>ans){
            ans=tmp+a[i];
            len = i-beg;
        }
        else if(/*空<2>*/ && i-beg>len){
            len = i-beg;
        }
        if(tmp+a[i]/*空<3>*/){
            beg=/*空4*/;
            tmp=0;
        }
        else /*空5*/
        cout<<ans<<" "<<len<<endl;
        return 0;
    }
}

解题过程：

空<1>其实很明显，前面都在初始化，这个beg一起初始化就好了，即beg=0.

空<2>之后的表达式依然将长度扩充，得到现统计结果（tmp+a[i]）与原统计结果(ans)相同。即tmp+a[i]==ans

空<3>发现之后的表达式中将目前累计的结果（tmp）清空，题意中提到“所有的元素均为正整数、负整数、0”，所以有出现0的情况，如果最大连续字段和中出现负数的情况下一定不是最优解，所以这个空是特判和小于0的，即

tmp+a[i]<0（实际上填写“<0”）

空<4>显而易见，既然将beg再一次进行赋值，因为从原来到现在的总和出现负数，所以将beg重新设置成i就可以了。即

beg = i（实际上填写"i"）

空<5>就是在tmp+a[i]大于等于0的时候，将计数器累加即可。即tmp+=a[i]（或者tmp=tmp+a[i]）

（这道题目居然不是用状态转移方程来写，丧病啊！）

下一题。

NOIP2010（完善程序第一题）:哥德巴赫猜想

题意描述:

哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。

题目源代码：

#include <iostream>
using namespace std;
int main(){
    const int SIZE = 1000;
    int n,r,p[SIZE],i,j,k,ans;
    bool tmp;
    cin>>n;
    r=1;
    p[1]=2;
    for(i=3;i<=n;i++){
        /*空<1>*/
        for(j=1;j<=r;j++){
            if(i%/*空<2>*/==0){
                tmp=false;
                break;
            }
        }
        if(tmp){
            r++;
            /*空<3>*/
        }
    }
    ans=0;
    for(i=2;i<=n/2;i++){
        tmp = false;
        for(j=1;j<=r;j++){
            for(k=<span style="font-family:FangSong_GB2312;">j</span>;k<=r;k++){
                if(i+i==/*空<4>*/){
                    tmp=true;
                    break;
                }
            }
        }
        if(tmp) ans++;
    }
    cout<<ans<<endl;
}

如果输入2010,输出的是  空<5>  

解题过程
空<1>：当前tmp未初始化，直接初始化tmp。即tmp=true

空<2>得知p数组为素数表，那么每一次搜索时扫描素数表中的每一个元素。如果扫描到了该元素的倍数，则标记。

所以填i%p[j]==0（实际上填"p[j]"）

空<3>如果找到一个素数，就把r扩展，将得到的新元素（i）赋值给目前为空的p[r]中。即p[r] = i

空<4>哥德巴赫猜想：任一大于2的偶数都可写成两个质数之和。如果i的两倍与任意两个素数和相同，就将tmp设成true，得到这里需要枚举素数。所以写成if(i+i==p[j]+p[k])（实际填写“p[j]+p[k]”）。

空<5>这。。。这不是阅读程序写运行结果么？？

不解释。答案1004

好吧=_=经历了不知道为什么完形填空变成阅读理解完善程序变成读程序写运行结果之后，来到了下一题。

NOIP2011（完善程序第一题）:子矩阵

题意描述：

给输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标：若不存在输出“There is no 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 haveAns,good;
    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++)
            /*空<1>*/;
    haveAns = false;
    for(i=1;i<=n1-n2+1;i++){
        for(j=1;j<=/*空<2>*/){
            /*空<3>*/;
            for(k1=1;k1<=n2;k1++){
                for(k2=1;k2<=/*空<4>*/;k2++){
                    if(a[i+k1-1][j+k2-1]!=b[k1][k2]){
                        good = false;
                    }
                }
            }
            if(good){
                cout<<i<<" "<<j<<endl;
                /*空<5>*/;
            }
        }
    }
    if(!haveAns) printf("There is no answer");
    return 0;
} 
</span>

这一道题......

当我打出这道题目的代码之后，我无风自凌乱=_=，我只想说：

这已经不能叫水题了，简直是送分！送分啊！

空<1>输入...... 答案:cin>>b[i][j]

空<2>直接照搬上面的for循环。 答案:m1-m2+1;

空<3>因为good没有初始化，下面又将它设置为false，得到这里将good设置为true。即good = true

空<4>照搬...... 答案:m2

空<5>......我说什么好呢......因为得到答案，将haveAns设为true。答案:haveAns = true
所以......允许我笑一下。

下一题.....

NOIP2012（完善程序第一题）:坐标统计

题意描述:

输入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]=/*空<1>*/;
		for(j=1;j<=n;j++)
		{
			if(x[j]<x[i] &&/*空<2>*/)
			     /*空<3>*/;
		}
		if(/*空<4>*/)
		{
			max_f=f[i];
			/*空5*/ ;	
		}
	}
	for(i=1;i<=n;i++) cout<<f[i]<<endl;
	cout<<ans<<endl;
	return 0;	
}

思路描述:

空<1>：为了防止上一次的统计结果影响到这一次，所以要清0.即f[i] = 0(实际上填写“0”)

空<2>：因为需要X2,Y2坐标都需要小于X1,Y1时，点1才能拥有点2的战斗力+1，所以填写y[j]<y[i]

空<3>：因为控制了当前点，战斗力增加。填写f[i]++或f[i] = f[i]+1

空<4>：......

空<5>：因为如果有多个点战斗力相同，就要输出编号最大的点的编号，所以需要记住当前点的编号，继续向后（有可能有更大的编号）。又因为输出的是ans，得到答案:ans = max_f。

(令人欣慰的是：CCF在2012世界末日的时候没有放弃治疗)

NOIP2013（完善程序第一题）:序列重排

题意描述:

全局数组变量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个数）之间的相对位置。

题目源代码:

/*朴素算法,时间复杂度 O(n) , 空间复杂度 O(n)*/
void swap1(int p){
    int i,j,b[SIZE];
    for(i=1;i<=p;i++)
        b[/*空<1>*/] = a[i];
    for(i=p+1;i<=n;i++)
        b[i-p] = /*空<2>*/;
    for(i=1;i<=/*空<3>*/;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>=/*空<4>*/;j--){
            a[j] = a[j-1];
            /*空<5>*/ = temp;
        }
    }
}

开始解题√

这里我们需要画图了。

设: a[ ] = {1,2,3,4,5} , p=2

初始序列:

空<1>：很明显这里是出来p之前（包括p）的元素，将这里的元素进行替换。我们的目标数组是:

得到元素位置转移:1→4，2→5

经过简单演算后得知:b[n-p+1] = a[i]，即正确答案为b[n-p+1]。

空<2>:同样依照上面的图片。

元素位置转移:

3→1 , 4→2 , 5→3

经过演算后得知：b[i] = a[i+p]，即b[i-p] = a[i]，答案是a[i]。

空<3>:虽然不知道他为什么要覆盖a数组（可能是b数组还要用），总之就是讲b数组复制到a。所以填写n

NOIP2014(完善程序第一题):数字删除

题意描述：

给定一个字符串，将字符串中的数字字符删除后输出。

题目源代码:

#include <iostream>
int delnum(char *s){
    int i,j;
    j = 0;
    for(i=0; s[i] != '\0' ; i++){
        if(s[i] < '0' /*空<1>*/ s[i] > '9'){
            s[j] = s[i];
            /*空<2>*/;
        }
    }
    return /*空<3>*/;
}
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<</*空<4>*/;
    }
    cout<<endl;
    return 0;
}

解题开始：

空<1>:很明显，这里是要判断这个字符是否是数字，即 s[i]<‘0’||s[i]>‘9’;(实际上填写"||")

空<2>:因为要统计更新后数组的长度，将j记为数组长度，这里更新了数组，所以长度加1，即j++

空<3>:计算完毕，返回的是数组长度，即j

空<4>:输出更新后的s数组，即cout<<s[i](实际填写"s[i]")

NOIP2015（完善程序第一题）:打印月历

题意描述:

输入月份m（1 ≤ m ≤ 12），按一定格式打印2015年第m月的月历。

题目源代码:

#include <iostream> 
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;     
    /*空<1>*/
    for (i = 1; i < m; i++) 
        offset =/*空<2>*/;        
    for (i = 0; i < offset; i++)
        cout << '\t'; 
    for (i = 1; i <=/*空<3>*/;i++) {
        cout <</*空<4>*/;  
        if (i == dayNum[m] ||/*空<5>*/== 0)
            cout << endl;
        else 
            cout << '\t';     
    } 
    return 0; 
}

解题思路:

2015年1月月历奉上

空<1>:offset这个参数控制着每个月前输出空格的数量。首次设成4.(上面的日历，如果再将周日放到周一前面，就有4个空),即offset=4.

空<2>:这里是为了得到每一个月输出日历前面输出的空格数量。这里有一个神奇的规律。将offset的初始值设置为4后，打印过当月的月历之后，留下的空就是(offset+当月天数)%7,即(offset+Daynum[i])%7。

空<3>:因为开始打印月历，所以要循环第m月的天数。即for(i=1;i<Daynum[m];i++)。（实际上填写"Daynum[m]"）

空<4>:打印出i。即cout<<i（实际上填写"i"）

空<5>:这里是控制每一星期后的换行。那么每一次打印的日期加上offset若取余7等于0，就可以换行。即(offset+i)%7==0。（实际填写"offset+i"）

第一题全部解题完毕。

============================

接下来对第二题进行解答。

NOIP2009（完善程序第二题）:国王放置

题意描述:

在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:

(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)

（注：棋盘行标号为0→n-1，列标号为0→m-1）

题目源代码:

#include <iostream>
using namespace std;
int n,k,ans;
int hash[5][5];
void work(int x,int y,int tot){
    int i,j;
    if(tot==k){
        ans++;
        return;
    }
    do{
        while(hash[x][y]){
            y++;
            if(y==m){
                x++;
                y=/*空<1>*/;
            }
            if(x==n){
                return;
            } 
        }
        for(i=x-1;i<=x+1;i++)
            if(i>=0 && i<n)
                for(j=y-1;j<=y+1;j++)
                    if(j>=0 && j<m)
                        /*空<2>*/;
        /*空<3>*/;
        for(i=x-1;i<=x+1;i++)
            if(i>=0 && i<n)
                for(j=y-1;j<=y+1;j++)
                    if(j>=0 && j<m)
                        /*空<4>*/;
        y++;
        if(y==m){
            x++;
            y=0;
        }
    }while(1);
}
int main(){
    cin >> n >> m >> k;
    ans=0;
    memset(hash,0,sizeof(hash));
    /*空<5>*/;
    cout<<ans<<endl;
}

解题思路:

空<1>:因为y搜索到了最右边，所以将y清零，x继续搜索下去。

空<2>:因为找到了一个可行的解，所以更新hash。即hash[i][j]++;

空<3>:这里进行递归。因为找到可行放置方法，所以递归的时候，返回的是更新的x,y,以及tot++。即work(x,y,tot+1);

空<4>递归完成，不能结束递归。所以将hash重新置为0.这里是hash[i][j]--;

空<5>开始递归。即work(0,0,0)。（因为棋盘的横坐标标号为0~n-1,纵坐标标号为0~m-1，所以要从0,0开始更新）

NOIP2010（完善程序第二题）:过河问题

题意描述:

在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2<=N<1000)和这N个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸.

题目源代码:

#include <iostream>
#include <cstring>
using namespace std;
const int SIZE=100;  
const int INFINITY = 10000; 
const bool LEFT=true; 
const bool RIGHT =false; 
const bool LEFT_TO_RIGHT=true; 
const bool RIGHT_TO_LEFT=false; 
int n,hour[SIZE];
bool pos[SIZE];
int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}
int go(bool stage) { 
    int i,j,num,tmp,ans;     
    if(stage==RIGHT_TO_LEFT)     
    { 
        num=0;
        ans=0; 
        for(i=1;i<=n;i++)   
            if(pos[i]==RIGHT){ 
               num++; 
               if(hour[i]>ans)
                  ans=hour[i];            
            } 
        if(/*空<1>*/) return ans;         
        ans=INFINITY;
        for(i=1;i<=n-1;i++)
            if(pos[i]==RIGHT)                
                for(j=i+1;j<=n;j++)
                    if(pos[j]==RIGHT){ 
                      pos[i]=LEFT;
                      pos[j]=LEFT; 
                      tmp=max(hour[i],hour[j])+/*空<2>*/;
                      if(tmp<ans)
                         ans=tmp;                      
                      pos[i]=RIGHT;                       
                      pos[j]=RIGHT;                                          
                    }        
     return ans;     
    }
    if(stage==LEFT_TO_RIGHT){ 
        ans=INFINITY;         
        for(i=1;i<=n;i++) 
            if(/*空<3>*/){ 
                pos[i]=RIGHT; 
                tmp=/*空<4>*/;
                if(tmp<ans)                     
                ans=tmp;
                /*空<5>*/;
            }         
        return ans;     
    } 
    return 0; 
    }  
int main() { 
    int i;     
    cin>>n; 
    for(i=1;i<=n;i++){ 
        cin>>hour[i];         
        pos[i]=RIGHT;     
    }
    cout<<go(RIGHT_TO_LEFT)<<endl;     
    return 0; 
}

解题思路:

空<1>:这个空是一次特判。如果人数只有两个人或者更少，那么不需要继续运算，返回答案即可。即n<=2

空<2>:这里是人从右向左走的时间判定操作。如果有两个人向左走，那么就把这两个人设成LEFT,表示他们目前在左边。那么他们前进的时间就是两个人中用时多的那个人的用时，但是因为过桥需要灯，所以要有人重新回到右边。这里要用到递归，执行向右走操作。即go(RIGHT_TO_LEFT)

空<3>:这里是判定当前选中的人i是否在左边。如果在，那么就继续执行送灯操作。即if(pos[i] == LEFT)

空<4>:这里是更新tmp，要用当前这个在左边的人去送灯，所以消耗时间是当前这个人的时间，即hour[i],然后需要进行左走右的操作，即go(LEFT_TO_RIGHT)，那么tmp就是hour[i]+go(LEFT_TO_RIGHT)

空<5>这个人最后需要回到左边，所以在递归结束后将pos[i]设置成LEFT,即pos[i] = LEFT

NOIP2011（完善程序第二题）:大整数开方

题意描述:输入一个大整数，用二分法求出这个数的平方根的整数部分

#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++) 
        /*空<1>*/+=a.num[i]*b.num[j];       
    for(i=1;i<=a.len+b.len;i++){         
        ans.num[i+1]+=ans.num[i]/10;
        /*空<2>*/;      
    } 
    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]+=/*空<3>*/;          
        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]+=(/*空<4>*/)*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)
        /*空<5>*/;      
    return ans; 
    }  
bool over(hugeint a,hugeint b) // 若大整数a>b则返回true，否则返回false { 
    int i; 
    if(/*空<6>*/)           
        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]-/*空<7>*/;     
    memset(left.num,0,sizeof(left.num));     
    left.len=1;     
    left.num[1]=1;     
    right=target;     
    do{ 
        middle=average(left,right);         
        if(over(/*空<8>*/))             
            right=middle;         
        else 
            left=middle; 
    }while(!over(plustwo(left),right) );     
    for(i=left.len;i>=1;i--)        
        cout<<left.num[i];     
    return 0; 
    }

空<1>:因为是计算两数的乘积，所以爆保存到第i+j-1位中。即ans.num[i+j-1]

空<2>:这里是进位操作。所以要将这个数对10取余。即ans.num[i]%=10

空<3>:这里是加法操作，将a与b的num[i]相加即可。即a.num[i]+b.num[i]

空<4>:因为要求平局数，那么就要让这个数取余2,，即ans.num[i]%2

空<5>:因为在更高位存在数字，那么将这个数字的长度加1即可。即ans.len++

空<6>:如果b比a长（这样值更大），就返回false，即a.len<b.len

NOIP2012（完善程序第二题）:排列数

题意描述:输入两个正整数n，m（1<n<20,1<m<n），在1~n中任取m个数，按字典序从小到大输出所有这样的排列。

题目源代码:

#include <iostream> 
#include <cstring> 
using namespace std; c
onst 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=/*空<1>*/;
        for(i=m;i>=1;i--)   { 
            /*空<2>*/;
            for(j=data[i]+1;j<=n;j++) 
            if(!used[j])     { 
                used[j]=true; 
                data[i]=/*空<3>*/
                flag=true;      
                break;      
            }    
            if(flag)    { 
                for(k=i+1;k<=m;k++) 
                for(j=1;j<=/*空<4>*/;j++)      
                if(!used[j])      
                { 
                    data[k]=j;      
                    used[j]=true;       
                    break;      
                } 
                /*空<5>*/       
            }   
        }  
    } 
    return 0;  
}

解题咯~

空<1>:因为flag是一个记录变量，所以要一开始初始化为false。答案为false

空<2>:used代表着“使用过”，那么这里的data[i]没有使用过，所以将data[i]设置为没有使用过。即used[data[i]]=false

空<3>:如果j没有使用过，就将j的值记入。即data[i]=j（实际填写“j”）

空<4>:因为要从n个数里选m个，所以这里要枚举这n个数。即j<=n（实际填写"n"）

空<5>:因为做完了，所以退出循环。即break

接下来。

NOIP2013:二叉查找树

题意描述:二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的

值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。 
输入的第一行包含一个整数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) && (/*空<1>*/) && (is_bst(a[root].left_child, lower_bound, cur) == 1) && (is_bst(/*空<2>*/,/*空<3>*/,/*空4>*/) == 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(/*空<5>*/, -INFINITE, INFINITE)<<endl;
	return 0; 
}

空<1>:如果当前节点的值不存在（为0）， 那么不能进行操作。所以要保证cur大于0.所以填写"cur"

空<2>:因为已经遍历完左子树，所以开始遍历右子树（设置为根）。填写a[root].right_child

空<3>:这里将最低的值设置成cur，因为要保证下一个数（在遍历右子树）大于这个数。

空<4>:这里的最大值不需要改变（因为是遍历右子树），所以依旧是upper_bound

空<5>:这里要从根节点开始。即1。

NOIP2014:最大子矩阵和

题意简述:给出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>*/ 
    for(i = 1; i <= m; i ++)        
        /*空<2>*/    
    for(i = 1; i <= m; i++)        
        for(j = 1; j <= n; j++)  
            rowsum[i][j] = /*空<3>*/      
    for(first = 1; first <= n; first++)        
    for(last = first; last <= n; last++){  
        /*空<4>*/ 
        for(i = 1; i <= m; i++)              {  
            area +=/*空<5>*/;          
             if(area > ans) ans = area;                
             if(area < 0)                  
             area = 0;              
             }          
    }  
    cout << ans << endl;      
    return 0;    
}

空<1>:ans的最大答案目前是子矩阵1行1列。所以设置为matrix[1][1]

空<2>:这里是初始化操作，初始化rowsum。因为rowsum是用来统计前i行第j个数的和，所以初始化时就是rowsum[i][0]=0;(前i行第0个数)

空<3>:这里是前i行第j个数的和。所以是前i-1行和加上当前数。当前数即matrix[i][j]。即rownum[i-1][j]+matrix[i][j]

空<4>:因为area没有赋值。所以是初始化area，即area=0

空<5>:这里要加上当前行的last和first-1两个数。即rownum[i][last]+rownum[i][first-1]

NOIP2015:中位数

题意描述:给定n（n为奇数且小于1000）个整数，整数的范围在0~m（0 < m < 231）
之间，请使用二分法求这n个整数的中位数。所谓中位数，是指将这n个数排序之后，排在正中间的数。

题目源代码:

#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 (/*空<1>*/) { 
        mid = (lbound + rbound) / 2;             
        /*空<2>*/;     
        for (i = 0; i < n; i++)             
        if (/*空<3>*/)                    
            /*空<4>*/;     
        if (count > n / 2)             
        lbound = mid + 1;         
        else 
        /*空<5*/       
    } 
    cout << rbound << endl;     
    return 0; }

空<1>:因为是二分法，所以必须要保证左小于右。所以就是lbound<=rbound

空<2>:这里要将计数器count置为0（根据下面的count>n/2得知）.即count=0

空<3>:这里其实要判断有多少数比mid大（根据下面的if(count>n/2)得知），那么这里就是填写mid<x[i]

空<4>:计数。即count++;

空<5>:属于二分的最后操作，将右赋值为mid-1。即rbould=mid-1。

好吧。。。。终于做完了。。。