全部知识点
（壳栈）小 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＝_____ 。
如图所示，图中每条边上的数字表示该边的长度，则从 A 到 E 的最短距离是______。
#include <iostream>
using namespace std;
int main()
{
int a, b, c, d, ans;
cin >> a >> b >> c;
d = a - b;
a = d + c;
ans = a * b;
cout << "Ans = " << ans << endl;
return 0;
}输入：
2 3 4
输出：____
#include <iostream>
using namespace std;
int fun(int n)
{
if(n == 1)
return 1;
if(n == 2)
return 2;
return fun(n - 2) - fun(n - 1);
}
int main()
{
int n;
cin >> n;
cout << fun(n) << endl;
return 0;
}输入：
7
输出：____
#include <iostream>
#include <string>
using namespace std;
int main()
{
string st;
int i, len;
getline(cin, st);
len = st.size();
for(i = 0; i < len; i++)
if(st[i] >= 'a' && st[i] <= 'z')
st[i] = st[i] - 'a' + 'A';
cout << st << endl;
return 0;
}输入：
Hello, my name is Lostmonkey.
输出：____
#include <iostream>
using namespace std;
const int SIZE = 100;
int main()
{
int p[SIZE];
int n, tot, i, cn;
tot = 0;
cin >> n;
for(i = 1; i <= n; i++)
p[i] = 1;
for(i = 2; i <= n; i++)
{
if(p[i] == 1)
tot++;
cn = i * 2;
while(cn <= n)
{
p[cn] = 0;
cn += i;
}
}
cout << tot << endl;
return 0;
}输入：
30
输出：____
（数字删除）下面程序的功能是将字符串中的数字字符删除后输出。请填空。
#include <iostream>
using namespace std;
int delnum(char *s)
{
int i, j;
j = 0;
for(i = 0; s[i] != '\0'; i++)
if(s[i] < '0' ① s[i] > '9')
{
s[j] = s[i];
②;
}
return ③;
}
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 << ④;
cout << endl;
return 0;
}（最大子矩阵和）给出 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 ①;
for(i = 1; i <= m; i++)
②
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++)
rowsum[i][j] = ③;
for(first = 1; first <= n; first++)
for(last = first; last <= n; last++)
{
④;
for(i = 1; i <= m; i++)
{
area += ⑤;
if(area > ans)
ans = area;
if(area < 0)
area = 0;
}
}
cout << ans << endl;
return 0;由数字 1,1,2,4,8,8 所组成的不同的四位数的个数是 _____.
如图所示，图中每条边上的数字表示该边的长度，则从 A 到 E 的最短距离是 _____.
#include<iostream>
using namespace std;
int main(){
int a, b, i, tot, c1, c2;
cin >> a >> b;
tot = 0;
for (i = a; i <= b; i++){
c1 = i / 10;
c2 = i % 10;
if((c1 + c2) % 3 == 0)
tot++;
}
cout << tot << endl;
}输入：
7 31
输出：（ ）