问题 A: 判断日期是否符合格式
题目描述
我们知道一年有12个月，每个月最多有31天，年有平年和闰年之分，本题目要求如果输入一个日期，程序需要判断用户输入的日期是否正确。
提示：测试输入的三个数字中，年份是正数，月份和日期有可能是负数，程序需要对这两个数为负数的情况进行判断。
输入
多组测试用例，对每组测试用例：
用户输入是三个数字，分别表示年，月和日。 例如 2007 10 21 ，表示2007年10月21日，这个输入经过判断是正确的。又例如输入 1993 11 38 ，这个输入经过判断是错误的，因为日期不能超过31天。
输出
程序的输出分为两种，1或者0。1表示输入正确，0表示输入错误。
样例输入
2011 21 10
样例输出
0
思路
建立每个月对应天数的数组。
2月要考虑是平年还是闰年，平年28天，闰年29天，我们先设为28天。
首先判断是否为闰年。
然后看月和日是否符合条件。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<iostream>
using namespace std;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main()
{
bool isLeap(int year);
int y, m, d;
while(~scanf("%d %d %d", &y, &m, &d))
{
bool flag = isLeap(y);
if(m <= 0 || m > 12 || d <= 0)
{
cout << 0 << endl;
continue;
}
int dd = days[m];
if(m == 2 && flag)
dd++;
if(d <= dd)
{
cout << 1 << endl;
continue;
}
cout << 0 << endl;
}
return 0;
}
bool isLeap(int year)
{
if(year % 400 == 0)
return true;
if(year % 4 == 0 && year % 100)
return true;
return false;
}
|
问题 B: 哈夫曼编码
题目描述
给定一只含有小写字母的字符串；输出其哈夫曼编码的长度
输入
第一行一个整数T，代表样例的个数，接下来T行，每行一个字符串，0<T<=2000,字符串长度0<L<=1500.
输出
对于每个字符串，输出其哈夫曼编码长度
样例输入
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq
样例输出
10
51
115
思路
要构造哈夫曼编码首先就必须要计算出每个字母出现的频率，扫描一遍即可;接下来就需要用这些频率来构造哈夫曼树，在这里需要使用优先队列这个数据结构，将频率全部push进入优先队列按从小到大排列后，使用贪心算法，每次都是将最小的两个频率拿出来构造哈夫曼树，两数的和再次push进队列，重复进行即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int main()
{
int T, i;
cin >> T;
while(T--)
{
char s[2000];
cin >> s;
int fre[26] = { 0 };
int len = strlen(s);
for(i = 0; i < len; i++)
{
fre[s[i] - 'a']++;
}
priority_queue<int, vector<int>, greater<int> >q;
for(i = 0; i < 26; i++)
{
if(fre[i] > 0)
{
q.push(fre[i]);
}
}
int sum = 0;
while(q.size() >= 2)
{
int a = q.top();
q.pop();
int b = q.top();
q.pop();
sum += a + b;
q.push(a + b);
}
cout << sum << endl;
}
return 0;
}
|
问题 C: 2n皇后问题
题目描述
给定一个 n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入 n 个黑皇后和 n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n 小于等于 8。
输入
输入的第一行为一个整数 n，表示棋盘的大小。
接下来 n 行，每行 n 个 0 或 1 的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为 0，表示对应的位置不可以放皇后。
输出
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
思路
n皇后问题++，有两种颜色的皇后，同色间互相满足n皇后问题条件（不同行、列、对角），注意任意两个棋子不能放同一个位置。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <iostream>
using namespace std;
const int maxn = 10;
int map[maxn][maxn];
int x1[maxn], x2[maxn], ans, n;
bool check1(int xx, int yy)
{
int i;
if(!map[xx][yy])
return false;
for(i = 0; i < xx; i++)
{
if(yy == x1[i])
return false;
if(abs(xx - i) == abs(yy - x1[i]))
return false; //斜对角
}
return true;
}
bool check2(int xx, int yy)
{
int i;
if(!map[xx][yy])
return false;
for(i = 0; i < xx; i++)
{
if(yy == x2[i])
return false;
if(abs(xx - i) == abs(yy - x2[i]))
return false; //斜对角
}
return true;
}
void queen(int l)
{
int i, j;
if(l == n)
{
ans++;
return;
}
for(i = 0; i < n; i++)
{
if(check1(l, i))
{
x1[l] = i;
map[l][i] = 0;
for(j = 0; j < n; j++)
{
if(check2(l, j))
{
x2[l] = j;
queen(l + 1);
x2[l] = -1;
}
}
map[l][i] = 1;
x1[l] = -1;
}
}
}
int main()
{
int i, j;
cin >> n;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
cin >> map[i][j];
}
}
ans = 0;
queen(0);
cout << ans << endl;
return 0;
}
|
问题 D: 图的m着色问题
题目描述
给定无向连通图G和m种不同的颜色，用这些颜色给图的各个顶点着一种颜色，若某种方案使得图中每条边的2个顶点的颜色都不相同，则是一个满足的方案，找出所有的方案。
输入
第一行有3个正整数n，k和m，分别表示n个顶点，k条边，m种颜色
接下来k行，每行2个正整数，表示一条边的两个顶点
输出
所有不同的着色方案数
样例输入
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
48
思路
用邻接矩阵存图：1表示点i和点j间有边。
dfs，每次看目前设的颜色是否符合条件，若符合则进入下一层。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
using namespace std;
const int maxn = 2000 + 5;
int n, k, m, ans;
int map[maxn][maxn];
int color[maxn];
int main()
{
void dfs(int d);
int i;
cin >> n; // 5
cin >> k; // 8
cin >> m; // 4
for(i = 0; i < k; i++)
{
int tmp1, tmp2;
cin >> tmp1;
cin >> tmp2;
map[tmp1][tmp2] = 1;
map[tmp2][tmp1] = 1;
}
dfs(1);
cout << ans << endl;
return 0;
}
void dfs(int d)
{
int i, j;
if(d == n+1)
{
ans++;
return;
}
for(i = 1; i <= m; i++) //颜色m = 4种
{
bool flag = true;
for(j = 1; j <= n; j++) //n个点
{
if(map[d][j] && color[j] == i) //连通且颜色为i则失败
{
flag = false;
break;
}
}
if(flag)
{
color[d] = i; //染色
dfs(d+1); //下一结点
color[d] = 0; //回到未染色状态
}
}
}
|
问题 E: 部分和问题
题目描述
给定n个整数，判断是否可以从中选择若干数字，使得他们的和恰好为k。
输入
多组测试用例。
对于每组测试用例，第一行一个正整数n，第二行n个整数，第三行一个整数k。
1≤N≤20，输入整数及k均小于1e8。
输出
若可以使得和为k，输出”Yes”,否则”No”。
样例输入
4
1 2 4 7
13
样例输出
Yes
247
思路
很明显，这是一道简单的dfs搜索，直接理由dfs的定义解决，不过最让人头痛的是如何实现 剪枝，减少不必要的时间浪费，剪枝还不熟练，这道题需要减掉的是
1.从当前状态如何转移都不会存在解
2.当sum超过k时，也没必要继续搜索
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
using namespace std;
int n, k, a[22], b[22];
int main()
{
bool dfs(int x, int sum);
int i;
while(~scanf("%d", &n))
{
for(i = 0; i < n; i++)
cin >> a[i];
cin >> k;
if(dfs(0, 0))
{
cout << "Yes" << endl;
for(i = 0; i < n; i++)
if(b[i])
cout << a[i];
cout << endl;
}
else
cout << "No" << endl;
}
}
bool dfs(int x, int sum) //从左到右遍历一遍可得解
{
if(sum > k)
return false; //此处属于后期补充，当代码加上这一个剪枝后，时间就会变为8MS，所以平时还要多注重剪枝，考虑优化代码啊！！！
if(x == n)
return sum == k; //如果前n项计算过了，返回sum=k是否相等
if(dfs(x + 1, sum))
{
b[x] = 0;
return true;
} //如果不加上a[x]的情况，标记为0；
if(dfs(x + 1, sum + a[x]))
{
b[x] = 1;
return true;
} //如果加上a[x]的情况，标记为1；
return false;
}
|
声明
本文参考了下面大佬的文章
- https://blog.csdn.net/gar_denia/article/details/86760575
- https://comydream.github.io/2018/10/19/algorithm-experiment-3/
- https://blog.csdn.net/fanke666/article/details/68063260
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。
