完善程序，每年两题，每题每空2-4分，共28分。
【解题步骤】
1、读题：解决什么问题？题目给出了什么算法？输入如何转化输出？
2、明确变量的含义，通过变量单词的意思猜测；
3、大致想想：如果让你实现程序，你会怎么做。
4、通读程序，理顺程序结构，千万不要因为程序很长而觉得气馁，有时程序越长，填空越简单
5、按照程序执行的顺序做，遇到难的先放一边。有些空格很简单，一下就能看出来的。
6、根据对程序的理解（结合自己已知的算法）大胆猜测，小心验证地填上很难的几个空
7、填完了以后，再执行一遍程序，有样例就结合样例，没样例就自己造数据模拟。
【解题技巧】
1、变量初始化：这个得结合后面的运算确定，不过有些也很简单，如sum=0之类的。
2、for循环初、终值：如果是嵌套的循环，可结合父循环或子循环确定。
3、更新最优解：比较或赋值。
4、要填的空格与某句对应，这样的例子在下面能找到很多。
(大整数开方)
输入一个正整数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(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++)
[ ① ] +=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(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]+= [ ③ ] ;
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]+=([ ④ ])*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)
[ ⑤ ];
return ans;
}
bool over(hugeint a,hugeint b)
// 若大整数a>b则返回true，否则返回false
{
int i;
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;
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]-[ ⑦ ];
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]xxxxxxxxxxxxxxxx
corect:ans.num[i+j-1]
2.
ans.num[i]%=10
3.
a.num[i]+b.num[i]
4.
ans.num[i]%2
5.
ans.len++
6.
a.len<b.len
7.
'0'
8.
times(middle,middle),target
得分：16/18
[noip 2013 PJ 第 28 题](#noip 2013 PJ 第 28 题)
#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) && ( ① ) && (is_bst( a[root].left_child, lower_bound, cur ) == 1) && (is_bst( ②, ③, ④ ) == 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( ⑤, -INFINITE, INFINITE ) << endl;
return(0);
}
cur<upper_bound
2.
a[root].right
3.
cur
4.
upper_bound
5.
1
[noip 2014 PJ 第 27 题](#noip 2014 PJ 第 27 题)
' '为 TAB 制表符
完善程序：
（打印日历） 输入月份 m(1≤m≤12)，按一定格式打印 2015 年第 m 月的月历。(第三、四空 2.5 分， 其余 3 分)
例如，2015 年 1 月的月历打印效果如下(第一列为周日)：
S M T W T F S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
#include <iostream>
#include <string>
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 M T W T F S" << endl; /* ' '为 TAB 制表符 */
①;
for (i = 1; i < m; i++)
offset = ②;
for (i = 0; i < offset; i++)
cout << ' ';
for (i = 1; i <= ③; i++)
{
cout << ④;
if (i == dayNum[m] || ⑤ == 0)
cout << endl;
else
cout << ' ';
}
return (0);
}
offset=4
2.
(offset+dayNum[i])%7
3.
dayNum[m]
4.
i
5.
(offset+i)%7
得分：14/14
[整数二分算法模板 —— 模板题 AcWing 789. 数的范围](#整数二分算法模板 —— 模板题 AcWing 789. 数的范围)
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
[浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根](#浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根)
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
[noip 2014 PJ 第 28 题](#noip 2014 PJ 第 28 题)
注意避免二分死循环，就算你写的二分不会死循环，但是初赛的二分写法妖艳的很
完善程序：
(中位数 median) 给定 n(n 为奇数且小于 1000)个整数，整数的范围在 0~m(0<m<2^31)之间，请使用二分法求这 n 个整数的中位数。所谓中位数，是指将这 n 个数排序之后，排在正中间的数。(第五空 2分，其余 3 分)
#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 (①)
{
mid = (lbound + rbound) / 2;
②;
for (i = 0; i < n; i++)
if (③)
④;
if (count > n / 2)
lbound = mid + 1;
else
⑤;
cout << mid << " " << lbound << " " << rbound << " " << count << endl;
}
cout << rbound << endl;
return (0);
}
lbound<rbound
2.
count=0
3.
x[i]>mid
4.
count++
5.
rbound=mid
第 28 题
完善程序： （郊游活动）有 n 名同学参加学校组织的郊游活动，已知学校给这 n 名同学 的郊游总经费为 A 元，与此同时第 i 位同学自己携带了 Mi 元。为了方便郊 游，活动地点提供 B(≥n)辆自行车供人租用，租用第 j 辆自行车的价格为 Cj 元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管 理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多 有多少位同学能够租用到自行车。（第四、五空 2.5 分，其余 3 分）
本题采用二分法。对于区间[l, r]，我们取中间点 mid 并判断租用到自行 车的人数能否达到 mid。判断的过程是利用贪心算法实现的。
#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;
bool check(int nn) {
int count = 0, i, j;
i = ①;
j = 1;
while (i <= n) {
if(②)
count += C[j] - M[i];
i++;
j++;
}
return ③;
}
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(④){
ans = mid;
l = mid + 1;
}else
r = ⑤;
}
cout << ans << endl;
return 0;
}
得分：11/13
分析：第一个空填错了，这里的贪心是指M[i]最大的mid(nn)个人，即用编号为n-mid(nn)+1~n 的个人的钱去怼C[1~B] (从小到大)，因为他们是对总花费贡献最小的。
所以第一空应该填'n-nn+1'
btw:这里判断的的是mid个人是否可行，所以1~ mid-1的人的花费并不用算（因为压根儿没选他们好不啦）