day22 adv120、127、132、141、145、149、150、154、167、194、202、222、233

设计复数库，实现基本的复数加减乘除运算。
输⼊入时只需分别键⼊入实部和虚部，以空格分割，两个复数之间⽤用运算符分隔；输出时按a+bi的格式在
屏幕上打印结果。参加样例例输⼊入和样例例输出。
注意考虑特殊情况，⽆无法计算时输出字符串串”error”。
样例例输⼊入
2 4 * -3 2
样例例输出
-14-8i
样例例输⼊入
3 -2 + -1 3
样例例输出
2+1i
思考：
就是要注意一下乘法和除法时复数的情况
以及输出时除法要有一位有效数字

#include<iomanip>

setprecision

#include<iostream>
#include<iomanip>
using namespace std;
int main(){int a1,a2,b1,b2;char ch;cin>>a1>>a2>>ch>>b1>>b2;if(ch=='+'){	int l=a1+b1;int r=a2+b2;if (l != 0) {
if (r != 0) {
if (r > 0)
cout << l << "+" << r << "i";
else
cout << l << r << "i";
}
else {
cout << l;
}
}
else {
if (r != 0) {
cout << r << "i";
}
else {
cout << 0;
}
}}else if(ch=='-'){int l=a1-b1;int r=a2-b2;if (l != 0) {
if (r != 0) {
if (r > 0)
cout << l << "+" << r << "i";
else
cout << l << r << "i";
}
else {
cout << l;
}
}
else {
if (r != 0) {
cout << r << "i";
}
else {
cout << 0;
}
}}else if(ch=='*'){int l=a1*b1-a2*b2;int r=a1*b2+a2*b1;if (l != 0) {
if (r != 0) {
if (r > 0)
cout << l << "+" << r << "i";
else
cout << l << r << "i";
}
else {
cout << l;
}
}
else {
if (r != 0) {
cout << r << "i";
}
else {
cout << 0;
}
}}else{if(b1==0||b2==0){cout<<"error";return 0;}double l=(a1*b1+a2*b2)/(b1*b1+b2*b2);double r=(a2*b1-a1*b2)/(b1*b1+b2*b2);if (l != 0) {
if (r != 0) {
if (r > 0)
cout <<setprecision(1)<< l << "+" << r << "i";
else
cout <<setprecision(1)<< l << r << "i";
}
else {
cout <<setprecision(1)<< l;
}
}
else {
if (r != 0) {
cout <<setprecision(1)<< r << "i";
}
else {
cout << 0;
}
}}return 0;
} 

问题描述
　　已知2011年年11⽉月11⽇日是星期五，问YYYY年年MM⽉月DD⽇日是星期⼏几？注意考虑闰年年的情况。尤其是
逢百年年不不闰，逢400年年闰的情况。
输⼊入格式
　　输⼊入只有⼀一⾏行行
　　YYYY MM DD
输出格式
　　输出只有⼀一⾏行行
　　W
数据规模和约定
　　1599 <= YYYY <= 2999
　　1 <= MM <= 12
　　1 <= DD <= 31，且确保测试样例例中YYYY年年MM⽉月DD⽇日是⼀一个合理理⽇日期
　　1 <= W <= 7，分别代表周⼀一到周⽇日
样例例输⼊入
2011 11 11
样例例输出
5)

思考：
一定要注意若比2011年大的和比2011年小的是不同的情况！！！！

#include<iostream>
using namespace std;
int month[2][13]={{0,31,29,31,30,31,30,31,31,30,31,30,31},{0,31,28,31,30,31,30,31,31,30,31,30,31}};
int year[2]={366,365};
int f(int y){if(y%4==0&&y%100!=0||y%400==0) return 0;else return 1;}
int main(){int y,m,d,flag;cin>>y>>m>>d;int y1=2011,m1=11;int sum=0;if(y==y1&&m>=m1){flag=f(y1);if(m==m1){sum=d+sum;}elsesum=month[flag][11]+sum+d;cout<<(sum-6)%7;return 0;}else if(y==y1&&m<m1){flag=f(y1);for(int i=m+1;i<m1;i++){sum=month[flag][i]+sum;}sum+=(month[flag][m]-d);cout<<8-sum%7;return 0;}if(y>y1){	sum+=61;for(int j=y1+1;j<y;j++){flag=f(j);sum+=year[flag];}flag=f(y);for(int i=0;i<m;i++){sum=month[flag][i]+sum;}cout<<(sum+d-6)%7;	}else{flag=f(y1);for(int i=0;i<11;i++)sum=month[flag][i]+sum;//2011年 for(int j=y+1;j<y1;j++){//年 flag=f(j);sum+=year[flag];}flag=f(y);sum+=(month[flag][m]-d);//y年 for(int i=m+1;i<=12;i++){sum=month[flag][i]+sum;}cout<<8-sum%7;	}return 0;}

问题描述
n个⾊色盲聚在⼀一起，讨论⼀一块布的颜⾊色。尽管都是⾊色盲，却盲得各不不相同。每个⼈人都有⾃自⼰己的主张，
争论不不休。最终，他们决定采取⺠民主投票的⽅方式决定布的颜⾊色，不不管布同不不同意。某种颜⾊色⽤用字符串串
表示(字符串串为颜⾊色单词或词组，也就是可能有被空格隔开的两个单词组成的颜⾊色词组)，只要字符串串
不不同，程序即判断颜⾊色不不同。现在给出这n个⼈人所选择的颜⾊色，输出最有可能的颜⾊色（也就是获得投
票最多的颜⾊色），如果有多个颜⾊色获得了了最多的投票，则将它们按字典序分⾏行行全部输出。
输⼊入格式
第⼀一⾏行行⼀一个正整数n，表示⾊色盲的⼈人数
接下来n⾏行行，每⾏行行⼀一句句话
输出格式
若⼲干⾏行行，获得投票最多的颜⾊色，按字典序输出
样例例输⼊入
5
red
blue
black
black
blue
样例例输出
black
blue
思考：
注意颜色不一定是red 还有light red这种，所以要用getline进行获取
还有用map进行匹配

#include<iostream>
#include<map>
#include<cmath>
using namespace std;
int main(){int n,maxn=0;cin>>n;string s;map<string,int>m;for(int i=0;i<=n;i++){getline(cin,s);m[s]++;maxn=max(maxn,m[s]);}for(map<string,int>::iterator i=m.begin();i!=m.end();i++){if(i->second==maxn){cout<<i->first<<endl;}}return 0;
}

问题描述
　　笨⼩小猴的词汇量量很⼩小，所以每次做英语选择题的时候都很头疼。但是他找到了了⼀一种⽅方法，经试验
证明，⽤用这种⽅方法去选择选项的时候选对的⼏几率⾮非常⼤大！
　　这种⽅方法的具体描述如下：假设maxn是单词中出现次数最多的字⺟母的出现次数，minn是单词中
出现次数最少的字⺟母的出现次数，如果maxn-minn是⼀一个质数，那么笨⼩小猴就认为这是个Lucky
Word，这样的单词很可能就是正确的答案。
输⼊入格式
　　输⼊入⽂文件只有⼀一⾏行行，是⼀一个单词，其中只可能出现⼩小写字⺟母，并且⻓长度⼩小于100。
输出格式
输出⽂文件共两⾏行行，第⼀一⾏行行是⼀一个字符串串，假设输⼊入的的单词是Lucky Word，那么输出“Lucky
Word”，否则输出“No Answer”；第⼆二⾏行行是⼀一个整数，如果输⼊入单词是Lucky Word，输出maxn-minn
的值，否则输出0。
样例例输⼊入
error
样例例输出
Lucky Word
2

思考：
注意字符串里面出现字母最少的（要加判断原来有无出现在字符串当中）

#include<iostream>
using namespace std;
bool iszhi(int n){if(n==1||n==0)return false;else if(n==2)return true;else{for(int i=2;i<n;i++){if(n%i==0){return false;break;}}return true;}}
int main(){int maxn=-1,minn=999999;int a[26]={0};string s;cin>>s;for(int i=0;i<s.length();i++){a[s[i]-'a']++;}for(int i=0;i<26;i++){maxn=max(maxn,a[i]);if(a[i]!=0)minn=min(minn,a[i]);}if(iszhi(maxn-minn)){cout<<"Lucky Word"<<endl<<maxn-minn;}elsecout<<"No Answer"<<endl<<0;return 0;
}

问题描述
某场⽐比赛过后，你想要知道A~E五个⼈人的排名是什什么，于是要求他们每个⼈人说了了⼀一句句话。（经典的开
头……-_-!）得了了第1名的⼈人23，说了了假话；得了了第5名的⼈人不不好意思，也说了了假话；为了了使求解问题简
单，第3名同样说了了假话。（奇数名次说假话）
输⼊入格式
共5⾏行行，各⾏行行依次表示A~E说的话。
每⾏行行包含⼀一个形如“A>=3”的名次判断，即⼀一个⼤大写字⺟母+关系运算符+⼀一个数字，不不包含空格。
⼤大写字⺟母A_{E，关系运算<、<=、=、>=、>、!=，数字1}5。注意：等于是“=”不不是“==”！
输出格式
可能有多解，请按照字典序输出排名序列列，每个解⼀一⾏行行
最后⼀一⾏行行输出解的数量量
样例例输⼊入
A=2
D=5
E>3
A>2
B!=1
样例例输出
ACDEB
AECBD
BADCE
BCADE
BDACE
CEADB
CEBDA
7

问题描述
为了了准备⼀一个学⽣生节，组织者在会场的⼀一⽚片矩形区域（可看做是平⾯面直⻆角坐标
系的第⼀一象限）铺上⼀一些矩形地毯。⼀一共有n 张地毯，编号从1 到n。现在将这些地毯按照
编号从⼩小到⼤大的顺序平⾏行行于坐标轴先后铺设，后铺的地毯覆盖在前⾯面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地⾯面某个点的最上⾯面的那张地毯的编号。注意：在矩形
地毯边界和四个顶点上的点也算被地毯覆盖。
输⼊入格式
输⼊入共 n+2 ⾏行行。
第⼀一⾏行行，⼀一个整数 n，表示总共有n 张地毯。
接下来的 n ⾏行行中，第i+1 ⾏行行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每
两个整数之间⽤用⼀一个空格隔开，分别表示铺设地毯的左下⻆角的坐标（a，b）以及地毯在x
轴和y 轴⽅方向的⻓长度。
第 n+2 ⾏行行包含两个正整数x 和y，表示所求的地⾯面的点的坐标（x，y）。
输出格式
输出共 1 ⾏行行，⼀一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
样例例输⼊入
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
样例例输出
3
样例例输⼊入
3
样例例输出
-1
数据规模和约定
对于 30%的数据，有n≤2；
对于 50%的数据，0≤a, b, g, k≤100；
对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。
思考：
struct一个新的类型然后进行操作很新颖

#include<iostream>
#include<vector>
using namespace std;
struct bian{int a,b,g,k;
};
int main(){int n;cin>>n;vector<bian>v(n);for(int i=0;i<n;i++)cin>>v[i].a>>v[i].b>>v[i].g>>v[i].k;int x,y;cin>>x>>y;for(int i=v.size()-1;i>=0;i--){if(x>=v[i].a&&x<=(v[i].a+v[i].g)&&y>=v[i].b&&y<=(v[i].b+v[i].k)){cout<<i+1;return 0;}	}cout<<-1;return 0;
}

问题描述
农⺠民约翰⺟母⽜牛总是产⽣生最好的肋肋⻣骨。你能通过农⺠民约翰和美国农业部标记在每根肋肋⻣骨上的数字认出它
们。农⺠民约翰确定他卖给买⽅方的是真正的质数肋肋⻣骨，是因为从右边开始切下肋肋⻣骨，每次还剩下的肋肋⻣骨
上的数字都组成⼀一个质数。
例例如有四根肋肋⻣骨的数字分别是：7 3 3 1，那么全部肋肋⻣骨上的数字 7331是质数；三根肋肋⻣骨 733是质数；⼆二根肋肋⻣骨 73 是质数；当然,最后⼀一根肋肋⻣骨 7 也是质数。7331 被叫做⻓长度 4 的特殊质数。
写⼀一个程序对给定的肋肋⻣骨的数⽬目 N (1<=N<=8),求出所有的特殊质数。数字1不不被看作⼀一个质数。
输⼊入格式
单独的⼀一⾏行行包含N。
输出格式
按顺序输出⻓长度为 N 的特殊质数,每⾏行行⼀一个。
样例例输⼊入
4
样例例输出
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

思考：
从第一位数字进行判断是否是素数

#include<iostream>
using namespace std;
bool iszhi(int n){if(n==1||n==0)return false;for(int i=2;i<n;i++){if(n%i==0)return false;}return true;
}
int n;
void dfs(int num,int level){if(level==n){cout<<num<<endl;}else{for(int i=0;i<=9;i++){if(iszhi(num*10+i)){dfs(num*10+i,level+1);}}}
}
int main(){cin>>n;dfs(0,0);return 0;
}

问题描述
　　右右喜欢听故事，但是右右的妈妈总是讲⼀一些“从前有座⼭山，⼭山⾥里里有座庙，庙⾥里里有个⽼老老和尚给⼩小和
尚讲故事，讲的什什么呢？从前有座⼭山……”这样循环的故事来搪塞右右。
　　我们定义，如果⼀一个字符串串是以⼀一个或者⼀一个以上的⻓长度为k的重复字符串串所连接成的，那么这个
字符串串就叫做周期为k的串串。
　　例例如:
　　字符串串’abcabcabcabc’周期为3，因为它是由4个循环’abc’组成的。它同样是以6为周期（两个重
复的’abcabc’）和以12为周期（⼀一个循环’abcabcabcabc’）。
　　右右现在想给他的朋友⼤大灰狼转述妈妈讲的故事，请帮他写⼀一个程序，可以测定⼀一个字符串串的最
⼩小周期。
输⼊入格式
　　⼀一个最⼤大⻓长度为100的⽆无空格的字符串串。
输出格式
　　⼀一个整数，表示输⼊入的字符串串的最⼩小周期。
样例例输⼊入
HaHaHa
样例例输出
2
样例例输⼊入
Return0
样例例输出
7

思考：
判断从1-len/2之间有无最小周期数，若无则最小周期数是len
判断通过裁剪进行判断substar(start,len)

#include<iostream>
#include<cstring>
using namespace std;
int main(){string s;cin>>s;int len=s.length();for(int i=1;i<=len/2;i++){int flag=0;if(len%i!=0)continue;string s1=s.substr(0,i);string s2;for(int j=i;j<len;j=j+i){s2=s.substr(j,i);if(s1!=s2){flag=1;break;}}if(flag==0){cout<<i;return 0;}}cout<<len;return 0;
}

问题描述
在上⼀一季⾥里里，曾提到过质数的孤独，其实从另⼀一个⻆角度看，⽆无情隔膜它们的合数全是质数的后代，因
为合数可以由质数相乘结合⽽而得。
如果⼀一个合数由两个质数相乘⽽而得，那么我们就叫它是质数们的直接后代。现在，给你⼀一系列列⾃自然
数，判断它们是否是质数的直接后代。
输⼊入格式
第⼀一⾏行行⼀一个正整数T，表示需要判断的⾃自然数数量量
接下来T⾏行行，每⾏行行⼀一个要判断的⾃自然数
输出格式
共T⾏行行，依次对于输⼊入中给出的⾃自然数，判断是否为质数的直接后代，是则输出Yes，否则输出No
样例例输⼊入
4
3
4
6
12
样例例输出
No
Yes
Yes
No
数据规模和约定
1<=T<=20
2<=要判断的⾃自然数<=105
思考：
把质数集合弄出来先，然后在做对比

#include<iostream>
#include<vector>
using namespace std;
int a[100005]={0};
vector<int >v;
bool iszhi(int n){if(n==1||n==0)return false;else{for(int i=2;i<n;i++){if(n%i==0)return false;}return true;}
} 
void getprime(){a[0]=a[1]=1;for(int i=2;i*i<=100005;i++){if(a[i]==0)for(int j=i*i;j<=100000;j=j+i){a[j]=1;}}for(int i=0;i<=100000;i++)if(a[i]==0)v.push_back(i);}
int main(){int n;cin>>n;getprime();for(int i=0;i<n;i++){int t,flag=1;cin>>t;for(int i=0;i<v.size();i++){if(t%v[i]==0)if(iszhi(t/v[i]))flag=0;	}	if(flag==0) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

问题描述
　　”嘟嘟嘟嘟嘟嘟
　　喇喇叭响
　　我是汽⻋车⼩小司机
　　我是⼩小司机
　　我为祖国运输忙
　　运输忙”
　　这是⼉儿歌“快乐的⼩小司机”。话说现在当司机光有红⼼心不不⾏行行，还要多拉快跑。多拉不不是超载，是要
让所载货物价值最⼤大，特别是在当前油价⽇日新⽉月异的时候。司机所拉货物为散货，如⼤大⽶米、⾯面粉、沙
⽯石、泥泥⼟土……
　　现在知道了了汽⻋车核载重量量为w，可供选择的物品的数量量n。每个物品的重量量为gi,价值为pi。求汽⻋车
可装载的最⼤大价值。（n<10000,w<10000,0<gi<=100,0<=pi<=100)
输⼊入格式
　　输⼊入第⼀一⾏行行为由空格分开的两个整数n w
　　第⼆二⾏行行到第n+1⾏行行，每⾏行行有两个整数，由空格分开，分别表示gi和pi
输出格式
　　最⼤大价值（保留留⼀一位⼩小数）
样例例输⼊入
5 36
99 87
68 36
79 43
75 94
7 35
样例例输出
71.3
解释：
先装第5号物品，得价值35，占⽤用重量量7
再装第4号物品，得价值36.346,占⽤用重量量29
最后保留留⼀一位⼩小数，得71.3

思考
要看准确题目，因为并不是每样物品只有一件，所以不是动态规划
这时候就要注意看单价
进行排列之后再进行贪心算法（尽可能多的让单价高的装车）

#include<iostream>
#include<algorithm>
using namespace std;
int dp[10000][10000];
struct node{double a,b;double f;
};
bool cmp(node t1,node t2){return t1.f>t2.f;
}
int main(){int n,w;cin>>n>>w;double ans=0.0;node *arr=new node [n];for(int i=0;i<n;i++){cin>>arr[i].a>>arr[i].b;arr[i].f=arr[i].b/arr[i].a;}sort(arr,arr+n,cmp);for(int i=0;i<n;i++){if(w>=arr[i].a){ans+=arr[i].b;w-=arr[i].a;}else{ans+=w*1.0/arr[i].a*arr[i].b;break;}}printf("%.1f",ans);delete [] arr;return 0;
}

最近的m天盾神都去幼⼉儿园陪⼩小朋友们玩去了了~
　　每个⼩小朋友都拿到了了⼀一些积⽊木，他们各⾃自需要不不同数量量的积⽊木来拼⼀一些他们想要的东⻄西。但是有
的⼩小朋友拿得多，有的⼩小朋友拿得少，有些⼩小朋友需要拿到其他⼩小朋友的积⽊木才能完成他的⼤大作。如
果某个⼩小朋友完成了了他的作品，那么他就会把⾃自⼰己的作品推倒，⽽而⽆无私地把他的所有积⽊木都奉献出
来；但是，如果他还没有完成⾃自⼰己的作品，他是不不会把积⽊木让出去的哟~
　　盾神看到这么和谐的⼩小朋友们感到⾮非常开⼼心，于是想帮助他们所有⼈人都完成他们各⾃自的作品。盾
神现在在想，这个理理想有没有可能实现呢？于是把这个问题交给了了他最信赖的你。
输⼊入格式
　　第⼀一⾏行行为⼀一个数m。
　　接下来有m组数据。每⼀一组的第⼀一⾏行行为n，表示这天有n个⼩小朋友。接下来的n⾏行行每⾏行行两个数，分
别表示他现在拥有的积⽊木数和他⼀一共需要的积⽊木数。
输出格式
　　输出m⾏行行，如果第i天能顺利利完成所有作品，输出YES，否则输出NO。
样例例输⼊入
2
2
2 2
1 3
3
1 5
3 3
0 4
样例例输出
YES
NO
数据规模和约定
　　1<=n<=10000，1<=m<=10。
　　
思考：
授信把能够拼成积木的积木个数释放，其次从小排列需要积木个数小的先拼

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node{int t1,t2,res;
};
bool cmp(node t1,node t2){return t1.res>t2.res;
}
int main(){int m;cin>>m;while(m--){int n,sum=0;cin>>n;node *a=new node[n];for(int i=0;i<n;i++){cin>>a[i].t1>>a[i].t2;a[i].res=a[i].t1-a[i].t2;if(a[i].res>=0){sum+=a[i].t1;a[i].res=-99999999;}}sort(a,a+n,cmp);int k=0;int flag=0;while(a[k].res!=-99999999){if(sum+a[k].res>=0){a[k].res=-99999999;sum+=a[k].t1;}else{cout<<"N0"<<endl;flag=1;break;}k++;}if(flag==0)cout<<"YES"<<endl;}return 0;
}

问题描述
　　给定两个字符串串，寻找这两个字串串之间的最⻓长公共⼦子序列列。
输⼊入格式
　　输⼊入两⾏行行，分别包含⼀一个字符串串，仅含有⼩小写字⺟母。
输出格式
　　最⻓长公共⼦子序列列的⻓长度。
样例例输⼊入
abcdgh
aedfhb
样例例输出
3
样例例说明
　　最⻓长公共⼦子序列列为a，d，h。
数据规模和约定
　　字串串⻓长度1~1000。

思考：
用动态规划_{只需建⽴立⼀一个长宽为两个字符串长度+1的二维数组}dp[i][j]表示String a的前i个字符构成的字符串和String b的前j个字符构成的字符串这两者得到的最长公共子序列的长度为dp[i][j]

#include<iostream>
using namespace std;
int dp[1001][1001];
int main(){string s1,s2;cin>>s1>>s2;for(int i=1;i<=s1.length();i++){for(int j=1;j<=s2.length();j++){if(s1[i-1]==s2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]); }}}cout<<dp[s1.length()][s2.length()];return 0;
} 

问题描述
利利⽤用标准库中的cos(x)和fabs(x)函数实现arccos(x)函数，x取值范围是[-1, 1]，返回值为[0, PI]。要求
结果准确到⼩小数点后5位。(PI = 3.1415926)
提示：要达到这种程度的精度需要使⽤用double类型。
样例例输⼊入
0.5
样例例输出

#include<iostream>
#include<cmath>
#define PI 3.1415926
#define min 0.000001
using namespace std;
double n;
double arccos(double x,double y){if(y-x<min) return x;double mid=(x+y)/2;if(cos(mid)==n) return mid;else if(cos(mid)>x) return arccos(mid,y);else return arccos(x,mid);
}
int main(){cin>>n;printf("%.5f",arccos(0,PI));return 0;
}

问题描述
　　队列列操作题。根据输⼊入的操作命令，操作队列列（1）⼊入队、（2）出队并输出、（3）计算队中元
素个数并输出。
输⼊入格式
　　第⼀一⾏行行⼀一个数字N。
　　下⾯面N⾏行行，每⾏行行第⼀一个数字为操作命令（1）⼊入队、（2）出队并输出、（3）计算队中元素个数并
输出。
输出格式
　　若⼲干⾏行行每⾏行行显示⼀一个2或3命令的输出结果。注意：2.出队命令可能会出现空队出队（下溢），请
输出“no”，并退出。
样例例输⼊入
7
1 19
1 56
2
3
2
3
2
样例例输出
19
1
56
0
no
数据规模和约定
　　1<=N<=50

#include<iostream>
#include<queue>
using namespace std;
int main(){int n;cin>>n;queue<int> q;for(int i=0;i<n;i++){int query,temp;cin>>query;if(query==1){cin>>temp;q.push(temp);}else if(query==2){if(!q.empty()){temp=q.front();q.pop();cout<<temp<<endl;}else{cout<<"no"<<endl;return 0;}}if(query==3){cout<<q.size()<<endl;}
}
return 0;
}