【算法课OJ】实验四
爱完美，所以苦。
链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1116
密码：123654
问题 A: 判断日期是否符合格式
题目描述
我们知道一年有12个月，每个月最多有31天，年有平年和闰年之分，本题目要求如果输入一个日期，程序需要判断用户输入的日期是否正确。
提示：测试输入的三个数字中，年份是正数，月份和日期有可能是负数，程序需要对这两个数为负数的情况进行判断。
输入
多组测试用例，对每组测试用例：
用户输入是三个数字，分别表示年，月和日。 例如 2007 10 21 ，表示2007年10月21日，这个输入经过判断是正确的。又例如输入 1993 11 38 ，这个输入经过判断是错误的，因为日期不能超过31天。
输出
程序的输出分为两种，1或者0。1表示输入正确，0表示输入错误。
样例输入
2011 21 10
样例输出
0
题意
输入年、月、日，判定是否符合格式。
思路
Water，打个每个月对应天数的表。
2月要考虑是平年还是闰年，平年28天，闰年29天，我们先设为28天。
首先判断是否为闰年。
然后看月和日是否符合条件。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isLeap(int y)
{
if(y%400 == 0) return true;
if(y%4 == 0 && y%100) return true;
return false;
}
int main()
{
int y,m,d;
while(~scanf("%d %d %d",&y,&m,&d))
{
bool flag = isLeap(y);
if(m <= 0 || m > 12 || d <= 0)
{
puts("0");
continue;
}
int dd = days[m];
if(m == 2 && flag) dd++;
if(d <= dd)
{
puts("1");
continue;
}
puts("0");
}
return 0;
}
问题 B: 哈夫曼编码
题目描述
给定一只含有小写字母的字符串；输出其哈夫曼编码的长度
输入
第一行一个整数T，代表样例的个数，接下来T行，每行一个字符串，0<T<=2000,字符串长度0<L<=1500.
输出
对于每个字符串，输出其哈夫曼编码长度
样例输入
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq
样例输出
10
51
115
题意
给定一个字符串，输出它的哈夫曼编码长度。
思路
直接STL（<queue>）开一个priority_queue（优先级队列），注意每次出的是最小的。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 2000;
int num[30],ans;
struct cmp1
{
bool operator()(int& a,int& b)
{
return a > b;
}
};
int main()
{
int t;
char str[maxn];
scanf("%d",&t);
while(t--)
{
scanf("%s",str);
memset(num,0,sizeof(num));
int len = strlen(str);
for(int i = 0; i < len; i++)
num[int(str[i]-'a')]++;
priority_queue<int,vector<int>,cmp1> pq;
for(int i = 0; i < 26; i++)
if(num[i]) pq.push(num[i]);
// if(pq.size() == 1)
// {
// printf("%d\n",pq.top());
// }
ans = 0;
while(pq.size() > 1)
{
int a,b;
a = pq.top();
pq.pop();
b = pq.top();
pq.pop();
pq.push(a+b);
ans += a+b;
}
printf("%d\n",ans);
}
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皇后问题条件（不同行、列、对角），注意任意两个棋子不能放同一个位置。
思路
dfs。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn = 10;
int map[maxn][maxn];
int x1[maxn],x2[maxn],ans,n;
bool check1(int xx,int yy)
{
if(!map[xx][yy]) return false;
for(int 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)
{
if(!map[xx][yy]) return false;
for(int 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)
{
if(l == n)
{
ans++;
return;
}
for(int i = 0; i < n; i++)
{
if(check1(l,i))
{
x1[l] = i;
map[l][i] = 0;
for(int 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()
{
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
scanf("%d",&map[i][j]);
}
}
ans = 0;
queen(0);
printf("%d",ans);
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，每次看目前设的颜色是否符合条件，若符合则进入下一层。
代码
#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++) //颜色m种
{
bool flag = true;
for(int 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; //回到未染色状态
}
}
}
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;
}
问题 E: 部分和问题
题目描述
给定n个整数，判断是否可以从中选择若干数字，使得他们的和恰好为k。
输入
多组测试用例。
对于每组测试用例，第一行一个正整数n，第二行n个整数，第三行一个整数k。
1≤N≤20，输入整数及k均小于1e8。
输出
若可以使得和为k，输出”Yes”,否则”No”。
样例输入
4
1 2 4 7
13
样例输出
Yes
题意
如题目描述所示。
思路
dfs。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn = 25;
int n,a[maxn],k;
bool dfs(int l,int sum)
{
if(sum == k) return true;
if(l == n) return false;
return dfs(l+1,sum)||dfs(l+1,sum+a[l]);
}
int main()
{
while(~scanf("%d",&n))
{
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);
scanf("%d",&k);
if(dfs(0,0)) puts("Yes");
else puts("No");
}
return 0;
}
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/10/21/algorithm-experiment-4/