NOIP真题
第661题
#include<iostream>
using namespace std;
int fun(char *a, char *b)
{
a = b;
(*a)++;
}
int main()
{
char c1,c2,*p1,*p2;
c1='A';
c2='a';
p1 = &c1;
p2 = &c2;
fun(p1,p2);
cout << c1 << c2 << endl;
return 0;
}输出：（ ）
第662题
（打印月历）输入月份 m(1≤m≤12)，按一定格式打印 2015 第 m 月的月历。
例如，2015 年一月的月历打印效果如下（第一列为周日）：
#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 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;
}
第663题
(中位数）给定 n（n 为奇数且小于1000）个整数，整数的范围在0~m（0
#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 << rbound << endl;
return 0;
}
第664题
在 1 和 2015 之间（包括 1 和 2015 在内）不能被 4、5、6 三个数任意一个数整除的数有_____个。
第665题
结点数为 5 的不同形态的二叉树一共有_____种。（结点数为 2 的二叉树一共有 2 种：一种是根结点和左儿子，另一种是根结点和右儿子。）
第666题
#include <iostream>
using namespace std;
struct point{
int x;
int y;
};
int main()
{
struct EX{
int a;
int b;
point c;
}e;
e.a=1;
e.b=2;
e.c.x=e.a+e.b;
e.c.y=e.a*e.b;
cout<<e.c.x<<','<<e.c.y<<endl;
return 0;
}输出：（ ）
第667题
#include <iostream>
using namespace std;
void fun(char *a,char *b)
{
a=b;
(*a)++;
}
int main()
{
char c1,c2,*p1,*p2;
c1='A';
c2='a';
p1=&c1;
p2=&c2;
fun(p1,p2);
cout<<c1<<c2<<endl;
return 0;
}输出：（ ）
第668题
#include <iostream>
using namespace std;
int main()
{
int len,maxlen;
string s,ss;
maxlen=0;
do
{
cin>>ss;
len=ss.length();
if(ss[0]=='#')break;
if(len>maxlen)
{
s=ss;
maxlen=len;
}
}while(true);
cout<<s<<endl;
return 0;
}输入：
I
am
a
citizen
of
China
#
输出：（ ）
第669题
#include <iostream>
using namespace std;
int fun(int n,int fromPos,int toPos)
{
int t,tot;
if(n==0)return 0;
for(t=1;t<=3;t++)
if(t!=fromPos && t != toPos)break;
tot=0;
tot+=fun(n-1,fromPos,t);
tot++;
tot+=fun(n-1,t,toPos);
return tot;
}
int main()
{
int n;
cin>>n;
cout<<fun(n,1,3)<<endl;
return 0;
}输入：5
输出：（ ）
第670题
(双子序列最大和)给定一个长度为n(3≤n≤1000) 的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序列长度至少为 1，且两个连续子序列之间至少间隔 1 个数。
#include <iostrea m>
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];
①;
for (i = n - 2; i >= 0; i --)
if (rmax[i + 1] <= 0)
②;
else
③;
for (i = n - 2; i >= 0; i --)
if (rmax[i] < rmax[i + 1])
④;
ans = x[ 0] + x [2];
for (i = 1; i < n - 1; i++) {
sum = ⑤;
if (sum > ans)
ans = sum;
}
cout << ans << endl;
return 0;
}
第671题
(最短路径问题)无向连通图 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) {
① ;
for (i = 0; i < n; i++)
if (used[i] != 1 && dist[i] != -1 && (v == -1 || ② ))
③ ;
if(v == -1)
break;
④ ;
for (i = 0; i < n; i++)
if (w[v][i] != -1 && (dist[i] == -1 || ⑤ ))
dist[i] = dist[v] + w[v][i];
}
for (i = 0; i < n; i++)
cout << dist[i] << endl;
return 0;
}
第672题
从一个 4×4 的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。
第673题
约定二叉树的根节点高度为 1。一棵结点数为 2016 的二叉树最少有（①）个叶子结点；一棵结点数为2016 的二叉树最小的高度值是（②）。
第674题
#include <iostream>
using namespace std;
int main()
{
int max, min, sum, count = 0;
int tmp;
cin >> tmp;
if (tmp==0) return 0;
max = min = sum = tmp;
count++;
while (tmp != 0) {
cin >> tmp;
if (tmp != 0)
{
sum += tmp;
count++;
if (tmp > max) max = tmp;
if (tmp < min) min = tmp;
}
}
cout << max << "," << min << "," << sum / count << endl;
return 0;
}输入：
1 2 3 4 5 6 0 7
输出：（ ）
第675题
#include <iostream>
using namespace std;
int main()
{
int i=100,x=0,y=0;
while (i>0)
{
i--;
x=i%8;
if (x==1) y++;
}
cout<<y<<endl;
return 0;
}输出：（ ）
第676题
#include <iostream>
using namespace std;
int main()
{
int a[6] = {1, 2, 3, 4, 5, 6};
int pi = 0;
int pj = 5;
int t, i;
while (pi < pj)
{
t = a[pi];
a[pi] = a[pj];
a[pj] = t;
pi++;
pj--;
}
for (i = 0; i < 6; i++)
cout << a[i] << ",";
cout << endl;
return 0;
}输出：（ ）
第677题
#include <iostream>
using namespace std;
int main()
{
int i,length1, length2;
string s1, s2;
s1 = "I have a dream.";
s2 = "I Have A Dream.";
length1 = s1.size();
length2 = s2.size();
for (i = 0; i < length1; i++)
if (s1[i] >= 'a' && s1[i] <= 'z')
s1[i] -= 'a'-'A';
for (i = 0; i < length2; i++)
if (s2[i] >= 'a' && s2[i] <= 'z')
s2[i] -= 'a'-'A';
if (s1 == s2) cout << "=" << endl;
else if (s1 > s2) cout << ">" << endl;
else cout << "<" << endl;
return 0;
}输出：（ ）
第678题
（读入整数）请完善下面的程序，使得程序能够读入两个 int 范围内的整数，并将这两个整数分别输出，每行一个。
输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。
例如:
输入:
123 -789
输出:
123
-789
#include <iostream>
using namespace std;
int readint() {
int num = 0; // 存储读取到的整数
int negative = 0; // 负数标识
char c;
c = cin.get(); // 存储当前读取到的字符
while ((c < '0' || c > '9') && c != '-')
c = ① ;
if (c == '-')
negative = 1;
else
② ;
c = cin.get();
while ( ③ ) {
④ ;
c=cin.get();
}
if (negative == 1)
⑤ ;
return num;
}
int main() {
int a, b;
a = readint();
b = readint();
cout << a << endl << b << endl;
return 0;
}
第679题
（郊游活动）有 n 名同学参加学校组织的郊游活动，已知学校给这 n 名同学的郊游总经费为 A 元，与此 同时第 i 位同学自己携带了 Mi 元。为了方便郊游，活动地点提供 B(≥n) 辆自行车供人租用，租用第j 辆自行车的价格为 Cj 元，每位同学可以使用自己携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。
本题采用二分法。对于区间 [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;
}
第680题
一个 1×8 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_____种填涂方案。