15.嗜睡猫问题
题目描述：
众所周知，TT家里有一只魔法喵。这只喵十分嗜睡。
一睡就没有白天黑夜。喵喵一天可以睡多次！！每次想睡多久就睡多久

喵睡觉的时段是连续的，即一旦喵喵开始睡觉了，
就不能被打扰，不然喵会咬人哒

可以假设喵喵必须要睡眠连续不少于 A 个小时，即一旦喵喵开始睡觉了，
至少连续 A 个小时内（即A*60分钟内）不能被打扰！

现在你知道喵喵很嗜睡了，它一天的时长都在吃、喝、拉、撒、睡，
换句话说要么睡要么醒着滴！

众所周知，这只魔法喵很懒，和TT一样懒，
它不能连续活动超过 B 个小时。

猫主子是不用工作不用写代码滴，十分舒适，所以，它是想睡就睡滴。
但是，现在猫主子有一件感兴趣的事，就是上BiliBili网站看的新番。
新番的播放时间它已经贴在床头啦（每天都用同一张时间表哦），这段时间它必须醒着！！
作为一只喵喵，它认为安排时间是很麻烦的事情，现在请你帮它安排睡觉的时间段。

输入说明：
多组数据，多组数据，多组数据哦，每组数据的格式如下：

第1行输入三个整数，A 和 B 和 N (1 <= A <= 24, 1 <= B <= 24, 1 <= n <= 20)

第2到N+1行为每日的新番时间表，
每行一个时间段，格式形如 hh:mm-hh:mm (闭区间)，
这是一种时间格式，hh:mm 的范围为 00:00 到 23:59。
注意一下，时间段是保证不重叠的，但是可能出现跨夜的新番，
即新番的开始时间点大于结束时间点。
保证每个时间段的开始时间点和结束时间点不一样，
即不可能出现类似 08:00-08:00 这种的时间段。
时长的计算由于是闭区间所以也是有点坑的，比如 12:00-13:59 的时长就是 120 分钟。
不保证输入的新番时间表有序。

输出说明：
我们知道，时间管理是一项很难的活，所以你可能没有办法安排的那么好，
使得这个时间段满足喵喵的要求，
即每次睡必须时间连续且不少于 A 小时，每次醒必须时间连续且不大于 B 小时，
还要能看完所有的番，所以输出的第一行是 Yes 或者 No，
代表是否存在满足猫猫要求的时间管理办法。

然后，对于时间管理，你只要告诉喵喵，它什么时候睡觉即可。
即第2行输出一个整数 k，代表当天有多少个时间段要睡觉
接下来 k 行是喵喵的睡觉时间段，
每行一个时间段，格式形如 hh:mm-hh:mm (闭区间)，这个在前面也有定义。
注意一下，如果喵喵的睡眠时段跨越当天到达了明天，
比如从23点50分睡到0点40分，那就输出23:50-00:40，
如果从今晚23:50睡到明天早上7:30，那就输出23:50-07:30。

输出要排序吗？
（输出打乱是能过的，也就是说，题目对输出的那些时间段间的顺序是没有要求的）

哦对了，喵喵告诉你说，本题是 Special Judge，
如果你的输出答案和 Sample 不太一样，也可能是对的，
它有一个判题程序来判定你的答案（当然，你对你自己的答案肯定也能肉眼判断）

数据样例：
输入
12 12 1
23:00-01:00
3 4 3
07:00-08:00
11:00-11:09
19:00-19:59输出：
Yes
1
01:07-22:13
No 

问题分析：
本问题是对时间段如何进行处理，我们首先看番的时间进行输入存储。
按照看番时间转化为分钟计时，并按照升序进行排序。时间段右端大于左端时，转化为明天。
因为时间段是连续的，因而将第二天的首个时间段也要进行时间段的录入。

在时间段录入完成后，我们需要判断处理两个看番时间之间是否能够睡觉问题。
方法是计算两个相邻时间段之间的使时间差，
不能睡觉时，我们可以将前后的看番时间与该时间段都视为看番时间，放入看番时间段的前面。
如果该段时间可以睡，我们不用处理该段时间。
只需将该段时间前一个看番时间视为不能睡，并放入动态数组中进行储存。

经过上述处理后，我们得出了所有不能睡的时间段。
我们这时只需要判断不能睡的时间段是否满足要求。
进行动态数组的遍历判断所有时间段是否符合要求。
对遍历结果相应输出 YES 或 NO 。

不能睡的时间段的之间的时间是可以睡的时间段。
因而时间段数为 size-1。
具体时间段为不断取不能睡的时间段的左右端点。

注意：对时间输出时将分钟转化为24小时制，过程需判断时与分的数据位数。

#include<iostream>
#include<string>
#include<deque>
#include<algorithm>
#include<vector>
using namespace std;int A,B,N;
string s;
struct time
{int l;int r;bool operator < (const time &t){return l < t.l;} 
};deque<time> dq;
vector<time> p;void init()
{while(dq.size()) dq.pop_back();while(p.size()) p.pop_back();
}void out2(int x)
{if(x>=10) cout<<x;else cout<<"0"<<x;
}void out(int l,int r)
{if(l>=1440) l=l-1440;if(r>=1440) r=r-1440;int h1,m1,h2,m2;h1=l/60; m1=l-h1*60+1;if(m1>=60){h1=h1+1;m1=m1-60; if(h1>=24) h1=h1-24;}h2=r/60; m2=r-h2*60-1;if(m2<0) {h2=h2-1;m2=m2+60;if(h2<0) h2=h2+24;	}out2(h1);cout<<":";out2(m1);cout<<"-";out2(h2);cout<<":";out2(m2);cout<<endl; 
}void solve()
{	for(int i=0;i<N;i++){cin>>s;time t;t.l=((s[0]-48)*10+(s[1]-48))*60+((s[3]-48)*10+(s[4]-48));t.r=((s[6]-48)*10+(s[7]-48))*60+((s[9]-48)*10+(s[10]-48));if(t.r<t.l) t.r+=24*60;  //归到明天 dq.push_back(t); } sort(dq.begin(),dq.end()); //排序处理time t=dq.front(); t.l+=24*60;t.r+=24*60; dq.push_back(t);//最早的时间段添加至最后 time t1,t2;while(true){t1=dq.front();dq.pop_front();if(dq.empty())  //只剩一个元素，跳出循环 {p.push_back(t1);break;}t2=dq.front();dq.pop_front();if(t2.l-t1.r<(A*60+1)) //这段时间不能睡 {t.l=t1.l;t.r=t2.r; dq.push_front(t);}else{dq.push_front(t2);p.push_back(t1);}} //遍历vector，动态数组中存放不能睡的时间段 for(int i=0;i<p.size();i++){t=p.at(i);if((t.r-t.l+1)>B*60){cout<<"No"<<endl;return; }} cout<<"Yes"<<endl;int begin=0,end=0;cout<<p.size()-1<<endl;begin=p.at(0).r;for(int i=1;i<p.size();i++){end=p.at(i).l;out(begin,end);begin=p.at(i).r;}     
}int main()
{while(scanf("%d %d %d",&A,&B,&N)!=EOF){init();solve();}return 0;
}

16.1.数鸭子问题

问题描述：
这一天，TT因为疫情在家憋得难受，在云吸猫一小时后，TT决定去附近自家的山头游玩。
TT来到一个小湖边，看到了许多在湖边嬉戏的鸭子，TT顿生羡慕。
此时他发现每一只鸭子都不一样，或羽毛不同，或性格不同。
TT在脑子里开了一个map<鸭子，整数> tong，把鸭子变成了一些数字。
现在他好奇，有多少只鸭子映射成的数的数位中不同的数字个数小于k。

输入输出描述：
输入第一行包含两个数n,k，表示鸭子的个数和题目要求的k。
接下来一行有n个数a_i，每个数表示鸭子被TT映射之后的值。输出一行，一个数，表示满足题目描述的鸭子的个数。
无行末空格 数据样例：
输入： 
6 5
123456789 9876543210 233 666 1 114514 
输出：
4

问题分析：
我们的总体思路是统计一个数中不同数字个数sum，sum与k比较，通过是否+1来得出答案。
对每个数进行处理，因而进行n次循环。
对每个数处理的过程中，我们将其视为字符串进行处理。
对10个数字进行0/1判断，进行处理计数。
通过计数值sum与k进行比较，判断最终的答案是否+1。
最终对答案ans,进行输出。

#include<iostream>
#include<cstring>
using namespace std;int main() 
{int n,k,ans,sum;char s[20];int a[11];ans=0;cin>>n>>k;while (n--){scanf("%s",s);for (int i=0;i<=9;i++)a[i]=0;sum=0;for (int i=0;i<strlen(s);i++){if(a[s[i]-'0'] == 0){sum++;a[s[i]-'0'] = 1;}  }if(sum<k)ans++; }cout<<ans<<endl;return 0;
}

16.2.抵御射线

问题描述：
据传，2020年是宇宙射线集中爆发的一年，这和神秘的宇宙狗脱不了干系！
但是瑞神和东东忙于正面对决宇宙狗，宇宙射线的抵御工作就落到了ZJM的身上。
宇宙射线的发射点位于一个平面，ZJM已经获取了所有宇宙射线的发射点，他们的坐标都是整数。
而ZJM要构造一个保护罩，这个保护罩是一个圆形，中心位于一个宇宙射线的发射点上。
同时，因为大部分经费都拨给了瑞神，所以ZJM要节省经费，做一个最小面积的保护罩。
当ZJM决定好之后，东东来找ZJM一起对抗宇宙狗去了，所以ZJM把问题扔给了你。

输入描述
输入第一行一个正整数N，表示宇宙射线发射点的个数
接下来N行，每行两个整数X,Y，表示宇宙射线发射点的位置
输出描述
输出包括两行
第一行输出保护罩的中心坐标x,y 用空格隔开
第二行输出保护罩半径的平方
(所有输出保留两位小数，如有多解，输出x较小的点，如扔有多解，输入y较小的点)
无行末空格 样例输入
5
0 0
0 1
1 0
0 -1
-1 0
样例输出
0.00 0.00
1.00 

问题分析：
问题中的数据规模不大，但数据坐标范围大，故数据坐标采用long long类型。
寻找过程为：统计每个点所形成面罩的半径平方。并记录该点坐标。
从所有点中得出答案的过程为：
按半径平方、x，y的比较顺序，选取小的点。
注意：输出时保留两位小数，printf("%lld.00",ans)。 

#include<iostream>
using namespace std;struct point
{long long x;long long y;
}p[1005];int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;long long r,x,y,ans=1e16;for(int i=1;i<=n;i++){r=0;for(int j=1;j<=n;j++){if(i==j){continue;}r=max(r,(p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));	}if(r<ans||(r==ans&&p[i].x<x)||(r==ans&&p[i].x==x&&p[i].y<y)){x=p[i].x;y=p[i].y;ans=r;}}printf("%lld.00 %lld.00\n",x,y);printf("%lld.00",ans);
}

16.3.宇宙狗危机

问题描述：
但是宇宙狗有一个很可爱的女朋友。
最近，他的女朋友得到了一些数，同时，她还很喜欢树，所以她打算把得到的数拼成一颗树。
这一天，她快拼完了，同时她和好友相约假期出去玩。
贪吃的宇宙狗不小心把树的树枝都吃掉了。
所以恐惧包围了宇宙狗，他现在要恢复整棵树。
但是它只知道这棵树是一颗二叉搜索树，同时任意树边相连的两个节点的gcd都超过1。
但是宇宙狗只会发射宇宙射线，他来请求你的帮助，问你能否帮他解决这个问题。

输入描述
输入第一行一个t，表示数据组数。
对于每组数据，第一行输入一个n，表示数的个数
接下来一行有n个数a_i，输入保证是升序的。
输出描述
每组数据输出一行，如果能够造出来满足题目描述的树，输出Yes，否则输出No。
无行末空格。样例输入
1
6
3 6 9 18 36 108
样例输出
Yes问题分析： 
是一个区间dp的动态规划问题。
现有一个数组f1[i][j]记录i到j能不能构造成这样得一个二叉搜索树。
然后有f2的数组记录每两个数之间的状态是否符合题意，即是不是gcd是不是大于1，
其中f1[i][j]的转移方程为f1[i][j]=f1[i][k]&&f1[k][j]，
即当【i，k】和【k,j】都是一个合法的二叉搜索树的时候，
其合并起来的也是一个合法的二叉搜索树。
然后开始枚举区间，即从小区间开始，区间的长度分别为1个点到n个点。
然后可以根据区间长度枚举这个区间的起点和终点。
并且在其中枚举根节点，在此处的时候即用到转移方程来进行更新。
同时可以用f2数组来判断更新f1[i-1][j]和f1[i][k+1]。
最终输出来f1[1][n]。
但只使用一个f1数组没法记录下所有状态，
即虽然你知道f1[i][j]可以是一个合法的二叉搜索树，
但是在这里你不知道它作为一个合法的二叉搜索树的时候，
他的根节点和左右子树分别是什么，故有信息缺失。
所以在这里的时候又增加了l和r数组，即l[i][j]表示以j为跟，i为左子树的合法的树。
r[i][j]则是表示以i为根，j为右子树的合法的树。

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;int t,n,a[800];
bool f1[800][800],f2[800][800];
bool l[800][800],r[800][800];int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }int main()
{cin >> t;while (t--){memset(f1, 0, sizeof(f1));memset(f2, 0, sizeof(f2));memset(l, 0, sizeof(l));memset(r, 0, sizeof(r));cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];l[i][i] = r[i][i] = 1;}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (i!=j && gcd(a[i], a[j]) > 1){f2[i][j] = true;	}}}for (int len = 0; len < n; len++){for (int q = 1; q + len <= n; q++){int z = q + len;for (int root = q; root <= z; root++)if (l[q][root] && r[root][z]){f1[q][z] = 1;if (f2[q - 1][root]) r[q - 1][z] = 1;if (f2[root][z + 1]) l[q][z + 1] = 1;}}}if (f1[1][n]) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}