一、字母排列
将LANQIAO中的字母重新排列，可以得到不同的单词，如LANQIAO、AAILNOQ等，注意这7个字母都要被用上，单词不一定有具体的英文意义。
请问，总共能排列如多少个不同的单词。
- 分析思路：
高中的排列组合，而且是全排列，因为有两个相同的字母A，会造成重复，所以除以2的全排列
- 答案提交：2520
二、字节
在计算机存储中，12.5MB是多少字节？
- 分析思路：
1MB=2^10 =1024KB;
1KB=2^10=1024Byte
所以这道题目:12.5 *1024 *1024=13107200
- 答案：13107200
三、括号序列
由1对括号，可以组成一种合法括号序列：()。
由2对括号，可以组成两种合法括号序列：()()、(())。
由4对括号组成的合法括号序列一共有多少种？
- 分析思路
法一：可以采用枚举法
（）、（）、（）、（）
（（））、（（））、（（））、（（））、（（））、（（））
（（（）））、（（（）））、（（（）））
（（（（））））
4+6+3+1=14
法二：卡特兰数
0对括号：[空序列] 1种可能
1对括号：() 1种可能
2对括号：()() (()) 2种可能
3对括号：((())) ()(()) ()()() (())() (()()) 5种可能
n对括号有多少种正确配对的可能
考虑n对括号时的任意一种配对方案，最后一个右括号有唯一的与之匹配的左括号，于是有唯一的表示A(B)，其中A和B也是合法的括号匹配序列
假设S(n)为n对括号的正确配对数目，
那么有递推关系S(n)=S(0)S(n-1)+S(1)S(n-2) +…+S(n-1)S(0)，显然S(n)是卡特兰数。
S(2)=S(0) ×S(1)+S(1) ×S(0)=1 ×1+1 ×1=2
S(3)=S(0) ×S(2)+S(1) ×S(1)+S(2) ×S(0)=1 ×2+1 ×1+2 ×1=5
S(4)=14 - 答案：14
四、无向连通图
一个包含有2019个结点的无向连通图，最少包含多少条边？
- 分析思路
概念：在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。
如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。
如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。
有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。
n个定点的无向连通图最少有n-1条边,
n个定点的有向连通图最少有n条边,
所以2019个节点的无向连通图有
2019-1=2018条
- 答案：2018
五、反倍数
给定三个整数 a, b, c，如果一个整数既不是 a 的整数倍也不是 b 的整数倍还不是 c 的整数倍，则这个数称为反倍数。
请问在 1 至 n 中有多少个反倍数。
输入格式
输入的第一行包含一个整数 n。
第二行包含三个整数 a, b, c，相邻两个数之间用一个空格分隔。
输出格式
输出一行包含一个整数，表示答案。
样例输入
30
2 3 6
样例输出
10
样例说明
以下这些数满足要求：1, 5, 7, 11, 13, 17, 19, 23, 25, 29。
评测用例规模与约定
对于 40% 的评测用例，1 <= n <= 10000。
对于 80% 的评测用例，1 <= n <= 100000。
对于所有评测用例，1 <= n <= 1000000，1 <= a <= n，1 <= b <= n，1 <= c <= n
- 分析思路：
对倍数求余，若求余后等于0，表示是它的倍数；若求余后，不等于0，表示不是它的倍数
- 代码
#include<stdio.h>
int main(){
int ans=0;
int n;
int a,b,c;
scanf("%d",&n);
scanf("%d %d %d",&a,&b,&c);
for(int i=1;i<n;i++){
if(i%a!=0&&i%b!=0&&i%c!=0)
ans++;
}
printf("%d\n",ans);
return 0;
}
六、凯撒密码
定一个单词，请使用凯撒密码将这个单词加密。
凯撒密码是一种替换加密的技术，单词中的所有字母都在字母表上向后偏移3位后被替换成密文。即a变为d，
b变为e，…，w变为z，x变为a，y变为b，z变为c。
例如，lanqiao会变成odqtldr。
输入格式
输入一行，包含一个单词，单词中只包含小写英文字母。
输出格式
输出一行，表示加密后的密文。
样例输入
lanqiao
样例输出
odqtldr
评测用例规模与约定
对于所有评测用例，单词中的字母个数不超过100。
- 分析思路
将字符串转为ASII码的思路，对应的ASII
a:97
z:122
A:65
Z:90
题目没有要求大写字母，我在代码里写了 - 代码：
#include <iostream>
using namespace std;
char s(char ch){
if(int(ch) >= 97&&int(ch) <= 122){
// 小写字母时,97 - 122
return char(97 + ((int(ch) - 97 + 3) % 26));
//} else if(int(ch) >= 65 && int(ch) <= 90){
// 大写字母时,65 - 90
// return char(65 + ((int(ch) - 97 + 3) % 26));
}else{
// 非字母直接返回
return ch;
}
}
int main() {
string str = "";
getline(cin,str);
int length = str.length();
for(int i = 0; i < length; i++){
str[i] = s(str[i]);
}
cout<<str;
return 0;
}
七、螺旋矩阵
对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数，我们称填好的表格为一个螺旋矩阵。
例如，一个 4 行 5 列的螺旋矩阵如下：
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8
输入格式
输入的第一行包含两个整数 n, m，分别表示螺旋矩阵的行数和列数。
第二行包含两个整数 r, c，表示要求的行号和列号。
输出格式
输出一个整数，表示螺旋矩阵中第 r 行第 c 列的元素的值。
样例输入
4 5
2 2
样例输出
15
评测用例规模与约定
对于 30% 的评测用例，2 <= n, m <= 20。
对于 70% 的评测用例，2 <= n, m <= 100。
对于所有评测用例，2 <= n, m <= 1000，1 <= r <= n，1 <= c <= m。
- 分析思路：
题目是要从第一行第一列开始旋转整个矩阵，返回最后一个数字
- 代码:
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int n, m;
int r, c;
cin>>n>>m;// n为行数，m列数
cin>>r>>c;// r为输出的行，c为输出的列
int arr[1010][1010]; //空间稍微留大一点
memset(arr,0, sizeof(arr));// 所有置为0
int sum = n * m; // 总数
int row = 0, col = 0, ans = 1;
arr[row][col] = 1;
while(ans < sum)
{
// 向右走，直到走到头或者下一个已经走过
while(col + 1 < m && !arr[row][col+1])
arr[row][++col] = ++ans;
// 向下走，直到走到头或者下一个已经走过
while(row + 1 < n && !arr[row+1][col])
arr[++row][col] = ++ans;
// 向左走，直到走到头或者下一个已经走过
while(col - 1 >= 0 && !arr[row][col-1])
arr[row][--col] = ++ans;
// 向上走，直到走到头或者下一个已经走过
while(row - 1 >= 0 && !arr[row-1][col])
arr[--row][col] = ++ans;
}
cout<<arr[r-1][c-1];
return 0;
}
八、摆动序列
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。
小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。
输入格式
输入一行包含两个整数 m，n。
输出格式
输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
样例输入
3 4
样例输出
14
样例说明
以下是符合要求的摆动序列：
2 1 2
2 1 3
2 1 4
3 1 2
3 1 3
3 1 4
3 2 3
3 2 4
4 1 2
4 1 3
4 1 4
4 2 3
4 2 4
4 3 4
评测用例规模与约定
对于 20% 的评测用例，1 <= n, m <= 5；
对于 50% 的评测用例，1 <= n, m <= 10；
对于 80% 的评测用例，1 <= n, m <= 100；
对于所有评测用例，1 <= n, m <= 1000。
- 分析思路：
- 深度优先搜索：纸牌放盒子中
- 类似数的全排列;
- 1与k开头一定只能排两位;
- 代码：
#include <iostream>
using namespace std;
int dp[1010][1010];
int main() {
// m为长度，n为数的最大取值范围
int m,n;
cin>>m>>n;
for(int i = 1; i <= n; i++)
dp[1][i] = n - i + 1;
for(int i = 2; i <= m; i++)
if(i & 1)
for(int j = n; j >= 1; j--)
dp[i][j] = (dp[i-1][j-1] + dp[i][j+1]) % 10000;
else
for(int j = 1; j <= n; j++)
dp[i][j] = (dp[i-1][j+1] + dp[i][j-1]) % 10000;
int ans = m & 1 ? dp[m][1] : dp[m][n];
cout<<ans;
return 0;
}
