全部知识点
include<iostream>
using namespace std;
int n, i, ans;
int main(){
cin>>n;
ans = 0;
for (i = 1; i <= n; i++)
if (n % i == 0)ans++;
cout<<ans<<endl;
}输入： 18
输出： ___________
#include <iostream>
using namespace std;
int n, i, j, a[100][100];
int solve(int x, int y){
int u, v;
if (x == n)return a[x][y];
u = solve(x + 1, y);
v = solve(x + 1, y + 1);
if (u > v)
return a[x][y] + u;
else
return a[x][y] + v;
}
int main(){
cin>>n;
for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
cin>>a[i][j];
cout<<solve(1, 1)<<endl;
return 0;
}输入：
5 2
-1 4
2 -1 -2
-1 6 4 0
3 2 -1 5 8
输出： ______________
#include <iostream>
#include <string>
using namespace std;
int n, ans, i, j;
string s;
char get(int i){
if (i < n)
return s[i];
else
return s[i-n];
}
int main(){
cin >> s;
n = s.size();
ans = 0;
for (i = 1; i <= n-1; i++){
for (j = 0; j <= n-1; j++)
if (get(i+j) < get(ans+j)){
ans = i; break;
}else if (get(i+j) > get(ans+j))
break;
}
for (j = 0; j <= n-1; j++)
cout<<get(ans+j);
cout<<endl;
}输入： CBBADADA
输出： ______
（坐标统计）输入 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] =①;
for (j = 1; j <= n; j++){
if (x[j] < x[i] && ②)
③;
}
if (④){
max_f = f[i];
⑤;
}
}
for (i = 1; i <= n; i++)
cout<<f[i]<<endl;
cout<<ans<<endl;
}（排列数）输入两个正整数 n，m（1 输入： 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;
}
⑤;
}
}
}
}
7 个同学围坐一圈，要选 2 个不相邻的作为代表，有____种不同的选法。
某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1, s2, , , sn ，均为 0 或 1 。 该系统每次随机生成 n 个数 a1, a2, …… , an ， 均为 0 或 1 ， 请用户回答 (s1a1+ s2a2+ …… + snan) 除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系 统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。 然而，事与愿违。例如，当 n = 4 时，有人窃听了以下 5 次问答：就破解出了密码 s1 = _________ ， s2 = _________ ，s3 = _________ ， s4 = _________ 。(答案用逗号隔开）
#include <iostream>
using namespace std;
int main(){
int a, b;
cin>>a>>b;
cout<<a<<"+"<<b<<"="<<a+b<<endl;
}输入： 3 5
输出：
#include <iostream>
using namespace std;
int main(){
int a, b, u, i, num;
cin>>a>>b>>u;
num = 0;
for (i = a; i <= b; i++)
if ((i % u) == 0) num++;
cout<<num<<endl;
return 0;
}输入： 1 100 15
输出：
#include <iostream>
using namespace std;
int main(){
const int SIZE = 100;
int n, f, i, left, right, middle, a[SIZE];
cin>>n>>f;
for (i = 1; i <= n; i++)
cin>>a[i];
left = 1;
right = n;
do {
middle = (left + right) / 2;
if (f <= a[middle])
right = middle;
else
left = middle + 1;
} while (left < right);
cout<<left<<endl;
return 0;
}输入：
12 17
2 4 6 9 11 15 17 18 19 20 21 25
输出：
#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;
}
⑤;
}
}
}
}