算法分析与设计(四)

http://192.168.173.163/JudgeOnline/contest.php?cid=1254

密码:123654

算法实验4

判断日期是否符合格式

题目描述

我们知道一年有12个月,每个月最多有31天,年有平年和闰年之分,本题目要求如果输入一个日期,程序需要判断用户输入的日期是否正确。

提示:测试输入的三个数字中,年份是正数,月份和日期有可能是负数,程序需要对这两个数为负数的情况进行判断。

输入

多组测试用例,对每组测试用例:

用户输入是三个数字,分别表示年,月和日。 例如 2007 10 21 ,表示2007年10月21日,这个输入经过判断是正确的。又例如输入 1993 11 38 ,这个输入经过判断是错误的,因为日期不能超过31天。

输出

程序的输出分为两种,1或者0。1表示输入正确,0表示输入错误。

样例输入

1
2011 21 10

样例输出

1
0

AC代码

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
#include <iostream>
using namespace std;
int a[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int b[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };
bool isyear(int year) {
if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
return 1;
else return 0;
}
int main() {
int y, m, d;
while (cin >> y >> m >> d) {
if (d > 31 || m > 12 || d <= 0 || m <= 0) {
cout << 0 << endl;
continue;
}
if(isyear(y)){
if (b[m] < d) {
cout << 0 << endl;
continue;
}
}
else {
if (a[m] < d) {
cout << 0 << endl;
continue;
}
}
cout << 1 << endl;
}
return 0;
}

哈夫曼编码

题目描述

给定一只含有小写字母的字符串;输出其哈夫曼编码的长度

输入

第一行一个整数T,代表样例的个数,接下来T行,每行一个字符串,0<T<=2000,字符串长度0<L<=1500.

输出

对于每个字符串,输出其哈夫曼编码长度

样例输入

1
2
3
4
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq

样例输出

1
2
3
10
51
115

AC代码

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
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
int f[26];
memset(f, 0, sizeof(f));
cin >> s;
for (int i = 0; i < s.length(); i++) {
f[s[i] - 'a']++;
}
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 0; i < 26; i++) {
if (f[i] > 0) {
q.push(f[i]);
}
}
int tmp = 0;
while (q.size()>=2) {
int m = q.top();
q.pop();
int n = q.top();
q.pop();
tmp += m + n;
q.push(m+n);
}
cout << tmp << endl;
}
return 0;
}

2n皇后问题

题目描述

给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入 n 个黑皇后和 n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n 小于等于 8。

输入

输入的第一行为一个整数 n,表示棋盘的大小。

接下来 n 行,每行 n 个 0 或 1 的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为 0,表示对应的位置不可以放皇后。

输出

输出一个整数,表示总共有多少种放法

样例输入

1
2
3
4
5
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

1
2

AC代码

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
#include<bits/stdc++.h>
using namespace std;

int bqueen[8];
int wqueen[8];
int chessboard[8][8];
int sum = 0;
int n;

int BlackQueen(int k){
for (int i = 0; i < k - 1; i++){
int judge = bqueen[i] - bqueen[k - 1];
if (judge == 0 || fabs(k - 1 - i) == fabs(judge))
return 0;
}
if (k == n){
sum++;
return 0;
}
for (int j = 0; j < n; j++){
if (j != wqueen[k] && chessboard[k][j]){
bqueen[k] = j;
BlackQueen(k + 1);
}
}
}

int WhiteQueen(int k){
for (int i = 0; i < k - 1; i++) {
int judge = wqueen[i] - wqueen[k - 1];
if (judge == 0 || fabs(k - 1 - i) == fabs(judge))
return 0;
}
if (k == n){
BlackQueen(0);
return 0;
}
for (int j = 0; j < n; j++){
if (chessboard[k][j]){
wqueen[k] = j;
WhiteQueen(k + 1);
}
}
}

int main(){
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> chessboard[i][j];
WhiteQueen(0);
cout << sum << endl;
return 0;
}

图的m着色问题

题目描述

给定无向连通图G和m种不同的颜色,用这些颜色给图的各个顶点着一种颜色,若某种方案使得图中每条边的2个顶点的颜色都不相同,则是一个满足的方案,找出所有的方案。

输入

第一行有3个正整数n,k和m,分别表示n个顶点,k条边,m种颜色
接下来k行,每行2个正整数,表示一条边的两个顶点

输出

所有不同的着色方案数

样例输入

1
2
3
4
5
6
7
8
9
5 8 4 
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

样例输出

1
48

AC代码

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
#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn = 2e3 + 5;
int n,k,m,ans;
int map[maxn][maxn];
int color[maxn];
void dfs(int d)
{
if(d == n+1)
{
ans++;
return;
}
for(int i = 1; i <= m; i++)
{
bool flag = true;
for(int j = 1; j <= n; j++)
{
if(map[d][j] && color[j] == i)
{
flag = false;
break;
}
}
if(flag)
{
color[d] = i;
dfs(d+1);
color[d] = 0;
}
}
}
int main()
{
scanf("%d %d %d",&n,&k,&m);
for(int i = 0; i < k; i++)
{
int tmp1,tmp2;
scanf("%d %d",&tmp1,&tmp2);
map[tmp1][tmp2] = 1;
map[tmp2][tmp1] = 1;
}
dfs(1);
printf("%d\n",ans);
return 0;
}

部分和问题

题目描述

给定n个整数,判断是否可以从中选择若干数字,使得他们的和恰好为k。

输入

多组测试用例。

对于每组测试用例,第一行一个正整数n,第二行n个整数,第三行一个整数k。

1N20,输入整数及k均小于1e8

输出

若可以使得和为k,输出”Yes”,否则”No”。

样例输入

1
2
3
4
1 2 4 7
13

样例输出

1
Yes

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
int n;
long long k;
long long a[21];
bool dfs(int i, long long sum) {
if (i == n) return sum == k;
if (dfs(i + 1, sum)) return true;
if (dfs(i + 1, sum + a[i]))return true;
return false;
}
int main() {
while (cin >> n) {
for (int i = 0; i < n; i++)
cin >> a[i];
cin >> k;
if (dfs(0, 0)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
-------------end ♥-------------