NOIP真题
#include <iostream>
using namespace std;
int main(){
const int SIZE = 100;
int height[SIZE], num[SIZE], n, ans;
cin>>n;
for (int i = 0; i < n; i++) {
cin>>height[i];
num[i] = 1;
for (int j = 0; j < i; j++) {
if ((height[j] < height[i]) && (num[j] >= num[i]))
num[i] = num[j]+1;
}
}
ans = 0;
for (int i = 0; i < n; i++) {
if (num[i] > ans) ans = num[i];
}
cout<<ans<<endl;
}输入：
6
2 5 3 11 12 4
输出：
（序列重排）全局数组变量 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[ ① ] = a[i];
for (i = p + 1; i <= n; i++)
b[i - p] = ② ;
for (i = 1; i <= ③ ; 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 >= ④ ; j--)
a[j] = a[j - 1];
⑤ = temp;
}
}（二叉查找树）二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于 其右子树上所有节点的值。试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数 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) && ( ① ) &&
(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;
}本题中，我们约定布尔表达式只能包含 p, q, r三个布尔变量，以及“与”(∧)、“或”(∨)、“非”(¬)三种布尔运算。如果无论 p,q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。
例如，(p∨q)∨r 和 p∨(q∨r) 等价，p∨¬p 和 q∨¬q 也等价；而 p∨q 和 p∧q 不等价。那么，两两不等价的布尔表达式最多有____个。
对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的独立集。那么，图 3 有____个不同的独立集。
#include <iostream>
using namespace std;
int n, i, temp, sum, a[100];
int main(){
cin>>n;
for (i = 1;i <= n;i++)
cin>>a[i];
for (i = 1;i <= n - 1;i++)
if (a[i] > a[i + 1]) {
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
for (i = n;i >= 2;i--)
if (a[i] < a[i - 1]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
}
sum = 0;
for (i = 2;i <= n - 1;i++)
sum += a[i];
cout<<sum / (n - 2)<<endl;
return 0;
}输入：
8
40 70 50 70 20 40 10 30
输出：____
#include <iostream>
using namespace std;
int n, i, ans;
int gcd(int a, int b){
if (a % b == 0)
return b;
else
return gcd(b, a%b);
}
int main(){
cin>>n;
ans = 0;
for (i = 1;i <= n;i++)
if (gcd(n,i) == i)ans++;
cout<<ans<<endl;
}输入：120
输出：____
#include <iostream>
using namespace std;
const int SIZE = 20;
int data[SIZE];
int n, i, h, ans;
void merge(){
data[h-1] = data[h-1] + data[h];
h--;
ans++;
}
int main(){
cin>>n;
h = 1;
data[h] = 1;
ans = 0;
for (i = 2;i <= n;i++){
h++;
data[h] = 1;
while (h > 1 && data[h] == data[h-1])
merge();
}
cout << ans << endl;
}1、输入：8
输出：____
2、输入：2012
输出：____
#include <iostream>
#include <string>
using namespace std;
int lefts[20], rights[20], father[20];
string s1, s2, s3;
int n, ans;
void calc(int x, int dep){
ans = ans + dep*(s1[x] - 'A' + 1);
if (lefts[x] >= 0) calc(lefts[x], dep+1);
if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x){
if (lefts[x] >= 0) check(lefts[x]);
s3 = s3 + s1[x];
if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th){
if (th == n){
s3 = "";
check(0);
if (s3 == s2){
ans = 0;
calc(0, 1);
cout<<ans<<endl;
}
return;
}
if (lefts[x] == -1 && rights[x] == -1){
lefts[x] = th;
father[th] = x;
dfs(th, th+1);
father[th] = -1;
lefts[x] = -1;
}
if (rights[x] == -1){
rights[x] = th;
father[th] = x;
dfs(th, th+1);
father[th] = -1;
rights[x] = -1;
}
if (father[x] >= 0)dfs(father[x], th);
}
int main(){
cin>>s1;
cin>>s2;
n = s1.size();
memset(lefts, -1, sizeof(lefts));
memset(rights, -1, sizeof(rights));
memset(father, -1, sizeof(father));
dfs(0, 1);
}输入：
ABCDEF
BCAEDF
输出：____
（排列数）输入两个正整数 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 =①;
for (i = m; i >= 1; i--){
②;
for (j = data[i]+1; j <= n; j++)
if (!used[j]){
used[j] = true;
data[i] =③;
flag = true;
break;
}
if (flag){
for (k = i+1; k <= m; k++)
for (j = 1; j <=④; j++)
if (!used[j]){
data[k] = j;
used[j] = true;
break;
}
⑤;
}
}
}
}（壳栈）小 Z 设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前 c 个元素是它的壳，支持翻转操作。其中，c > 2 是一个固定的正整数，表示壳的厚度。小 Z 还希望，每次操作，无论是压入、弹出还是翻转，都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？
程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数 c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足 c 个，应当输出相应的错误信息。
#include <iostream>
using namespace std;
const int NSIZE = 100000,CSIZE = 1000;
int n, c, r, tail, head, s[NSIZE], q[CSIZE];
//数组 s 模拟一个栈，n 为栈的元素个数
//数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标
bool direction, empty;
int previous(int k){
if (direction)
return ((k + c - 2) % c) + 1;
else
return (k % c) + 1;
}
int next(int k){
if (direction)
①;
else
return ((k + c - 2) % c) + 1;
}
void push(){
int element;
cin>>element;
if (next(head) == tail) {
n++;
②;
tail = next(tail);
}
if (empty)
empty = false;
else
head = next(head);
③= element;
}
void pop(){
if (empty) {
cout<<"Error: the stack is empty!"<<endl;
return;
}
cout<<④<<endl;
if (tail == head)
empty = true;
else {
head = previous(head);
if (n > 0) {
tail = previous(tail);
⑤= s[n];
n--;
}
}
}
void reverse(){
int temp;
if (⑥== tail) {
direction = !direction;
temp = head;
head = tail;
tail = temp;
}else
cout<<"Error: less than "<<c<<" elements in the stack!"<<endl;
}
int main(){
cin>>c;
n = 0;
tail = 1;
head = 1;
empty = true;
direction = true;
do{
cin>>r;
switch (r) {
case 1: push();break;
case 2: pop();break;
case 3: reverse();break;
}
} while (r != 0);
return 0;
}某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1，s2，, ， sn，均为 0 或 1。该系统每次随机生成 n 个数 a1，a2，, ， an，均为 0 或 1，请用户回答 （s 1a1+s 2 a2+… +s n an）除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问 答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。然而，事与愿违。 例如，当 n=4 时，有人窃听了以下 5 次问答：
就破解出了密码 s1= _ ， s2= _ ，s3= _， s4= _。(结果之间用空格隔开即可）
现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概率 地随机跳到 1，2，, ， k 号荷尔蒙叶之一上，直至跳到 1 号荷叶为止。当 n=2 时，平均一 共跳 2 次；当 n=3 时，平均一共跳 2.5 次。则当 n=5 时，平均一共跳 _____次。
#include <iostream>
#include <string>
using namespace std;
int main() {
string str;
cin>>str;
int n = str.size();
bool isPlalindrome = true;
for (int i = 0;i < n/2;i++) {
if (str[i] != str[n-i-1]) isPlalindrome = false;
}
if (isPlalindrome)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}输入：
abceecba
输出：________
#include <iostream>
using namespace std;
int main(){
int a, b, u, v, i, num;
cin>>a>>b>>u>>v;
num = 0;
for (i = a;i <= b;i++)
if (((i % u) == 0) || ((i % v) == 0))
num++;
cout<<num<<endl;
return 0;
}输入：
1 1000 10 15
输出：________
#include <iostream>
using namespace std;
int main(){
const int SIZE = 100;
int height[SIZE], num[SIZE], n, ans;
cin>>n;
for (int i = 0;i < n;i++) {
cin>>height[i];
num[i] = 1;
for (int j = 0;j < i;j++) {
if ((height[j] < height[i]) && (num[j] >= num[i]))
num[i] = num[j]+1;
}
}
ans = 0;
for (int i = 0;i < n;i++) {
if (num[i] > ans) ans = num[i];
}
cout<<ans<<endl;
}输入：
8
3 2 5 11 12 7 4 10
输出：________
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 100;
int n, m, p, a[SIZE][SIZE], count;
void colour(int x, int y){
count++;
a[x][y] = 1;
if ((x > 1) && (a[x - 1][y] == 0)) colour(x - 1, y);
if ((y > 1) && (a[x][y - 1] == 0)) colour(x, y - 1);
if ((x < n) && (a[x + 1][y] == 0)) colour(x + 1, y);
if ((y < m) && (a[x][y + 1] == 0)) colour(x, y + 1);
}
int main(){
int i, j, x, y, ans;
memset(a, 0, sizeof(a));
cin>>n>>m>>p;
for (i = 1;i <= p;i++) {
cin>>x>>y;
a[x][y] = 1;
}
ans = 0;
for (i = 1;i <= n;i++)
for (j = 1;j <= m;j++)
if (a[i][j] == 0) {
count = 0;
colour(i, j);
if (ans < count)
ans = count;
}
cout<<ans<<endl;
return 0;
}输入：
6 5 9
1 4
2 3
2 4
3 2
4 1
4 3
4 5
5 4
6 4
输出：________
（序列重排）全局数组变量 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[①] = 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(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 >=②;j--)
a[j] = a[j - 1];
③ = 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 (④) {
start1 =⑤;
end1 =⑥;
start2 = j;
}else
break;
}
}（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子 序列并列最长，输出任意一个即可。例如，序列“ 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 =①;
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] ==② ) {
while (count2 > 0) {
if (a[i] == cur1)
count1--;
else
count2--;
i++;
}
cur2 = a[j];
count2 = 1;
}else {
while (count1 > 0) {
if (a[i] == cur1)
③ ;
else
④ ;
i++;
}
⑤ ;
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;
}把 M 个同样的球放到 N 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同 的放置方法？ (用 K 表示 )。 例如， M＝7 ，N＝3 时， K＝8 ；在这里认为和是同一种放置方法。 问： M＝8 ，N＝5 时， K＝_____ 。