首页 > 代码库 > qscoj 喵哈哈村的魔法考试 Round #5 (Div.2) 题解(前1,2,3题)ps:前三题在本人水平可掌控范围之内
qscoj 喵哈哈村的魔法考试 Round #5 (Div.2) 题解(前1,2,3题)ps:前三题在本人水平可掌控范围之内
题目链接:http://qscoj.cn/problem/30/
第一题
喵哈哈村的狼人杀大战(1)
时间限制: 1000ms 内存限制: 128M
喵哈哈村最近热衷于玩一个叫做狼人杀的游戏!
张小田今天她抽到的是民的身份,按照她的一贯玩法,她不会考虑发言者的发言,她只考虑站队情况。
现在是警上竞选的投票环节,现在只剩下还能当警长的两个真假预言家。
张小田认为,如果在某一天,有连续坐在一起的k个人投票给同一个人的话,那么她就认为这一局可能比较危险。
投给第一个预言家的,就记为0,投给第二个预言家的记为1,于是就可以得到一个01串。
现在张小田就交给你来判断,如果按照张小田 的逻辑来看这一局是否危险!
----
题目翻译:给你一个01串,你需要判断这个01串里面是否存在连续的相同字符的长度大于等于k个。
假设当前k为3,那么010101001就不危险,11101010就危险。
注意,该01串是串,而不是环。
该题包含多组测试数据。
第一行一个整数k。
第二行一个01串,s。
满足:1<=len(s)<=100,1<=k<=100
如果危险的话,输出Lose,否则输出Win
分析
模拟题一道嘛……for一遍整个字符串,设一个max记录最长的连续字符,我自己用了一个煞笔方法,其实只需要统计变好了。
代码
#include<bits/stdc++.h> using namespace std; int main(){ int k; while(cin>>k){ string s; cin>>s; int cnt = 1; int mx = 1; for(int i=1;i<s.size();i++){ if(s[i]==s[i-1]){ cnt++; mx=max(cnt,mx);//模拟一遍找出最长的连续字符 }else cnt=1; } if(mx>=k){ cout<<"Lose"<<endl; }else{ cout<<"Win"<<endl; } } }
那个煞笔方法
#include<bits/stdc++.h> using namespace std; string s; int k; int main() { while(cin>>k) { cin>>s; int pre=1;//无论如何都会有1个连续的 int n=s.size(); int i=0; do { if(s[i]==s[i-1]) { pre++; } else if(s[i]!=s[i-1]) { pre=1; } if(pre>=k) { cout<<"Lose"<<endl; break; } else if(i==n-1) { cout<<"Win"<<endl; } i++; //从一开始向后面比较,直到最后都不大于等于k,就说明存活了 } while(i<n); } return 0; }
题目链接:http://qscoj.cn/problem/31/
喵哈哈村的狼人杀大战(2)
最后更新: 2017年3月7日 20:12 时间限制: 1000ms 内存限制: 128M
喵哈哈村最近热衷于玩一个叫做狼人杀的游戏!
星星同学今天她抽到的是狼的身份,按照她的一贯玩法,她喜欢无情的屠杀掉所有的神。
她现在已经很清楚了场上的预言家,女巫,猎人是谁。但是她唯一不知道的就是白痴这张神牌在谁的身上。于是她诈一诈她的下家——天行廖。
星星同学的逻辑是这样的:她可以考一道题给天行廖,如果天行廖能够答上来的话,那么天行廖肯定不是白痴,因为白痴是答不上题的。
这道题是这样的:
如果一个数只包含4和7的话,那么这个串就是幸运数,比如4777,774就是幸运数,而467就不是幸运数。
如果一个幸运数中包含的4和7的数量相同的话,那么这个数就是超级幸运数,比如4747就是超级幸运串,447就不是。
现在给你一个n,你需要找到一个最小的超级幸运数,并且这个超级幸运数大于等于n。
本题包含若干组测试数据。
第一行一个整数n。
满足 1<=n<=10^9
输出最小的超级幸运数,。
分析
这个题乍一看是暴力枚(我当年的水平),实际是一道dfs,如果仔细分析一下如果用暴力枚会浪费很多时间,因为本题是想求的值只包含47,所以用dfs只讨论+4或+7,所以说会节省很多时间。
上代码
#include<bits/stdc++.h> #define MAXN 1e15 using namespace std; long long n; long long ans=MAXN; void dfs(int four,int seven,long long now) { if(now>=n&&four==seven)//更新最小值(因为dfs讨论的是所有的情况) { ans=min(ans,now); } if(now>=n*100)//一条深度终止 { return; } dfs(four+1,seven,now*10+4); dfs(four,seven+1,now*10+7);//要么选+4,要么选+7 } long long sovle() { ans=MAXN;//ans先设一个超大的值 dfs(0,0,0); cout<<ans<<endl; } int main() { while(cin>>n) { sovle(); } return 0; }
题目链接:http://qscoj.cn/problem/31/
喵哈哈村的狼人杀大战(3)
时间限制: 1000ms 内存限制: 128M
喵哈哈村最近热衷于玩一个叫做狼人杀的游戏!
昊昊同学今天他抽到的是平民的身份,按照他的一贯玩法,他喜欢挂机,就什么事儿都不干。
于是他早早的就被推出去了。
现在他很无聊,于是他想了一道题来给自己打发时间。
定义f(x)=abs(ax^3+bx^2+cx+d),abs为绝对值符号。
给你a,b,c,d,l,r。
他想知道[l,r]这个范围内,f(x)的最大值。
题目包含多组测试数据。
第一行六个整数,a,b,c,d,l,r。
满足-10<=a,b,c,d<=10,-100<=l<=r<=100
对于每组测试诗句,输出最大值,需要保留两位小数。
分析
此题纯属暴力枚举,就枚举从r到l间的最大值,包括r和l,因为题目给的是保留两位小数输出,说以枚举的精度到0.001吧。
ps:写此题的时候以为while(读入)只能读入一个值(好尴尬),结果写出了一个死循环超时了……
代码
#include<bits/stdc++.h> using namespace std; double l,r; double a,b,c,d; double f(double a,double b,double c,double d,double x) { return fabs(a*x*x*x+b*x*x+c*x+d); }//依照题意写的函数 void solve() { double ans=-1; if(f(a,b,c,d,l)>ans) { ans=f(a,b,c,d,l); } if(f(a,b,c,d,r)>ans) { ans=f(a,b,c,d,r); }//判断两个范围结点 while(l<=r) { ans=max(ans,f(a,b,c,d,l)); l=l+0.001; } printf("%.2lf\n",ans); } int main() { while(cin>>a>>b>>c>>d>>l>>r)//最搞的读入 { solve(); } return 0; }
这个是死循环……
#include<bits/stdc++.h> using namespace std; double l,r; double f(double a,double b,double c,double d,double x) { return fabs(a*x*x*x+b*x*x+c*x+d); } void solve() { double a,b,c,d; double ans=-1; cin>>a>>b>>c>>d>>l>>r; if(f(a,b,c,d,l)>ans) { ans=f(a,b,c,d,l); } if(f(a,b,c,d,r)>ans) { ans=f(a,b,c,d,r); } while(l<=r) { ans=max(ans,f(a,b,c,d,l)); l=l+0.001; } printf("%.2lf\n",ans); } int main() { while(1)//输入数据时可以按ctrl+z结束,所以不能写死循环 { solve(); } return 0; }
本人蒟蒻一枚
第一次接触(写)blog
希望自己能在卿学姐的培养下茁壮成长~
qscoj 喵哈哈村的魔法考试 Round #5 (Div.2) 题解(前1,2,3题)ps:前三题在本人水平可掌控范围之内