【算法课OJ】实验四

Author Avatar
source. 10月 21, 2018
  • 在其它设备中阅读本文章

爱完美，所以苦。

链接：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表示输入错误。

样例输入

  1. 2011 21 10

样例输出

  1. 0

题意

输入年、月、日，判定是否符合格式。

思路

Water，打个每个月对应天数的表。

2月要考虑是平年还是闰年，平年28天，闰年29天，我们先设为28天。

首先判断是否为闰年。

然后看月和日是否符合条件。

代码

  1. #include<iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4. int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
  5. bool isLeap(int y)
  6. {
  7.     if(y%400 == 0) return true;
  8.     if(y%4 == 0 && y%100) return true;
  9.     return false;
  10. }
  11. int main()
  12. {
  13.     int y,m,d;
  14.     while(~scanf("%d %d %d",&y,&m,&d))
  15.     {
  16.         bool flag = isLeap(y);
  17.         if(m <= 0 || m > 12 || d <= 0)
  18.         {
  19.             puts("0");
  20.             continue;
  21.         }
  22.         int dd = days[m];
  23.         if(m == 2 && flag) dd++;
  24.         if(d <= dd)
  25.         {
  26.             puts("1");
  27.             continue;
  28.         }
  29.         puts("0");
  30.     }
  31.     return 0;
  32. }

问题 B: 哈夫曼编码

题目描述

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

输入

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

输出

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

样例输入

  1. 3
  2. hrvsh
  3. lcxeasexdphiopd
  4. mntflolfbtbpplahqolqykrqdnwdoq

样例输出

  1. 10
  2. 51
  3. 115

题意

给定一个字符串，输出它的哈夫曼编码长度。

思路

直接STL（<queue>）开一个priority_queue（优先级队列），注意每次出的是最小的。

代码

  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<algorithm>
  5. #include<queue>
  6. #include<vector>
  7. using namespace std;
  8. const int maxn = 2000;
  9. int num[30],ans;
  10. struct cmp1
  11. {
  12.     bool operator()(int& a,int& b)
  13.     {
  14.         return a > b;
  15.     }
  16. };
  17. int main()
  18. {
  19.     int t;
  20.     char str[maxn];
  21.     scanf("%d",&t);
  22.     while(t--)
  23.     {
  24.         scanf("%s",str);
  25.         memset(num,0,sizeof(num));
  26.         int len = strlen(str);
  27.         for(int i = 0; i < len; i++)
  28.             num[int(str[i]-'a')]++;
  30.         priority_queue<int,vector<int>,cmp1> pq;
  31.         for(int i = 0; i < 26; i++)
  32.             if(num[i]) pq.push(num[i]);
  33. //        if(pq.size() == 1)
  34. //        {
  35. //            printf("%d\n",pq.top());
  36. //        }
  37.         ans = 0;
  38.         while(pq.size() > 1)
  39.         {
  40.             int a,b;
  41.             a = pq.top();
  42.             pq.pop();
  43.             b = pq.top();
  44.             pq.pop();
  45.             pq.push(a+b);
  46.             ans += a+b;
  47.         }
  48.         printf("%d\n",ans);
  49.     }
  50.     return 0;
  51. }

问题 C: 2n皇后问题

题目描述

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

输入

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

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

输出

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

样例输入

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

样例输出

  1. 2

题意

n皇后问题++，有两种颜色的皇后，同色间互相满足n皇后问题条件（不同行、列、对角），注意任意两个棋子不能放同一个位置。

思路

dfs。

代码

  1. #include<iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4. const int maxn = 10;
  5. int map[maxn][maxn];
  6. int x1[maxn],x2[maxn],ans,n;
  7. bool check1(int xx,int yy)
  8. {
  9.     if(!map[xx][yy]) return false;
  10.     for(int i = 0; i < xx; i++)
  11.     {
  12.         if(yy == x1[i]) return false;
  13.         if(abs(xx - i) == abs(yy - x1[i])) return false; //斜对角
  14.     }
  15.     return true;
  16. }
  17. bool check2(int xx,int yy)
  18. {
  19.     if(!map[xx][yy]) return false;
  20.     for(int i = 0; i < xx; i++)
  21.     {
  22.         if(yy == x2[i]) return false;
  23.         if(abs(xx - i) == abs(yy - x2[i])) return false; //斜对角
  24.     }
  25.     return true;
  26. }
  27. void queen(int l)
  28. {
  29.     if(l == n)
  30.     {
  31.         ans++;
  32.         return;
  33.     }
  34.     for(int i = 0; i < n; i++)
  35.     {
  36.         if(check1(l,i))
  37.         {
  38.             x1[l] = i;
  39.             map[l][i] = 0;
  40.             for(int j = 0; j < n; j++)
  41.             {
  42.                 if(check2(l,j))
  43.                 {
  44.                     x2[l] = j;
  45.                     queen(l+1);
  46.                     x2[l] = -1;
  47.                 }
  48.             }
  49.             map[l][i] = 1;
  50.             x1[l] = -1;
  51.         }
  52.     }
  53. }
  54. int main()
  55. {
  56.     scanf("%d",&n);
  57.     for(int i = 0; i < n; i++)
  58.     {
  59.         for(int j = 0; j < n; j++)
  60.         {
  61.             scanf("%d",&map[i][j]);
  62.         }
  63.     }
  64.     ans = 0;
  65.     queen(0);
  66.     printf("%d",ans);
  67.     return 0;
  68. }

问题 D: 图的m着色问题

题目描述

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

输入

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

输出

所有不同的着色方案数

样例输入

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

样例输出

  1. 48

题意

给定一个图、颜色数，求方案数。

思路

用邻接矩阵存图：1表示点i和点j间有边。

dfs，每次看目前设的颜色是否符合条件，若符合则进入下一层。

代码

  1. #include<iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4. const int maxn = 2e3 + 5;
  5. int n,k,m,ans;
  6. int map[maxn][maxn];
  7. int color[maxn];
  8. void dfs(int d)
  9. {
  10.     if(d == n+1)
  11.     {
  12.         ans++;
  13.         return;
  14.     }
  15.     for(int i = 1; i <= m; i++)     //颜色m种
  16.     {
  17.         bool flag = true;
  18.         for(int j = 1; j <= n; j++)     //n个点
  19.         {
  20.             if(map[d][j] && color[j] == i)  //连通且颜色为i则失败
  21.             {
  22.                 flag = false;
  23.                 break;
  24.             }
  25.         }
  26.         if(flag)
  27.         {
  28.             color[d] = i;   //染色
  29.             dfs(d+1);       //下一结点
  30.             color[d] = 0;   //回到未染色状态
  31.         }
  32.     }
  33. }
  34. int main()
  35. {
  36.     scanf("%d %d %d",&n,&k,&m);
  37.     for(int i = 0; i < k; i++)
  38.     {
  39.         int tmp1,tmp2;
  40.         scanf("%d %d",&tmp1,&tmp2);
  41.         map[tmp1][tmp2] = 1;
  42.         map[tmp2][tmp1] = 1;
  43.     }
  44.     dfs(1);
  45.     printf("%d\n",ans);
  46.     return 0;
  47. }

问题 E: 部分和问题

题目描述

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

输入

多组测试用例。

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

1≤N≤20，输入整数及k均小于1e8。

输出

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

样例输入

  1. 4
  2. 1 2 4 7
  3. 13

样例输出

  1. Yes

题意

如题目描述所示。

思路

dfs。

代码

  1. #include<iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4. const int maxn = 25;
  5. int n,a[maxn],k;
  6. bool dfs(int l,int sum)
  7. {
  8.     if(sum == k) return true;
  9.     if(l == n) return false;
  10.     return dfs(l+1,sum)||dfs(l+1,sum+a[l]);
  11. }
  12. int main()
  13. {
  14.     while(~scanf("%d",&n))
  15.     {
  16.         for(int i = 0; i < n; i++)
  17.             scanf("%d",&a[i]);
  18.         scanf("%d",&k);
  19.         if(dfs(0,0)) puts("Yes");
  20.         else puts("No");
  21.     }
  22.     return 0;
  23. }

本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/10/21/algorithm-experiment-4/

Powered by Hexo
Theme - Material