算法实验四。
问题 A: 判断日期是否符合格式
题目描述
我们知道一年有12个月，每个月最多有31天，年有平年和闰年之分，本题目要求如果输入一个日期，程序需要判断用户输入的日期是否正确。
提示：测试输入的三个数字中，年份是正数，月份和日期有可能是负数，程序需要对这两个数为负数的情况进行判断。
输入
多组测试用例，对每组测试用例：
用户输入是三个数字，分别表示年，月和日。 例如 2007 10 21 ，表示2007年10月21日，这个输入经过判断是正确的。又例如输入 1993 11 38 ，这个输入经过判断是错误的，因为日期不能超过31天。
输出
程序的输出分为两种，1或者0。1表示输入正确，0表示输入错误。
样例输入
2011 21 10
样例输出
0
提示
代码
#include<bits/stdc++.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(cin>>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;
}
问题 B: 哈夫曼编码
题目描述
给定一只含有小写字母的字符串；输出其哈夫曼编码的长度
输入
第一行一个整数T，代表样例的个数，接下来T行，每行一个字符串，0<T<=2000,字符串长度0<L<=1500.
输出
对于每个字符串，输出其哈夫曼编码长度
样例输入
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq
样例输出
10
51
115
提示
代码
#include<bits/stdc++.h>
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];
cin>>t;
while(t--)
{
cin>>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]);
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;
}
cout<<ans<<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
提示
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10;
int map_q[maxn][maxn];
int x1[maxn],x2[maxn],ans,n;
bool check1(int xx,int yy)
{
if(!map_q[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_q[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_q[l][i] = 0;
for(int j = 0; j < n; j++)
{
if(check2(l,j))
{
x2[l] = j;
queen(l+1);
x2[l] = -1;
}
}
map_q[l][i] = 1;
x1[l] = -1;
}
}
}
int main()
{
cin>>n;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin>>map_q[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
提示
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
int n,k,m,ans;
int map_c[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_c[d][j] && color[j] == i) //连通且颜色为i则失败
{
flag = false;
break;
}
}
if(flag)
{
color[d] = i; //染色
dfs(d+1); //下一结点
color[d] = 0; //回到未染色状态
}
}
}
int main()
{
cin>>n>>k>>m;
for(int i = 0; i < k; i++)
{
int tmp1,tmp2;
cin>>tmp1>>tmp2;
map_c[tmp1][tmp2] = 1;
map_c[tmp2][tmp1] = 1;
}
dfs(1);
cout<<ans;
return 0;
}
问题 E: 部分和问题
题目描述
给定n个整数，判断是否可以从中选择若干数字，使得他们的和恰好为k。
输入
多组测试用例。
对于每组测试用例，第一行一个正整数n，第二行n个整数，第三行一个整数k。
1≤N≤20，输入整数及k均小于1e8。
输出
若可以使得和为k，输出”Yes”,否则”No”。
样例输入
4
1 2 4 7
13
样例输出
Yes
提示
代码
#include<bits/stdc++.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(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;
}
