ZZULI 郑州轻工业学院第 21 届新生正式比赛
A: 另一个爱与希望的故事
题目描述
madoka的面前有n级台阶,目前她处于第0级台阶,她每一次可以选择选择爬一级台阶或是连爬两级台阶,madoka想知道她有几种到达第n级台阶的走法。出乎意料的是,n级台阶中有k级台阶被损坏了,madoka无法抵达这些被损坏的台阶。
输入
第一行输入一个正整数T,表示测试样例数。
对于每个测试样例,共两行,第一行给出两个正整数n,k,表示台阶的级数以及损坏的台阶数。
第二行给出k个正整数ai,表示第ai级台阶被损坏。
1 <= T <= 10
1 <= n <= 105
1 <= k,ai <= n输出
对于每个测试样例,输出一个正整数,表示madoka到达第n级台阶的方法数。
答案对1000000007取模。样例输入 Copy
2 3 1 1 3 3 1 2 3样例输出 Copy
1 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1000000007;
ll dp[100005];
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof dp);
int n,k;
cin>>n>>k;
for(int i=1;i<=k;i++)
{
int a;
scanf("%d",&a);
dp[a]=-1;
}
if(dp[1]!=-1)dp[1]=1;
else dp[1]=0;
if(dp[2]!=-1&&dp[1])dp[2]=2;
else if(dp[2]!=-1&&!dp[1])dp[2]=1;
else dp[2]=0;
for(int i=3;i<=n;i++)
{
if(dp[i]==-1)
{
dp[i]=0;continue;
}
dp[i]=(dp[i-1]+dp[i-2])%mod;
}
cout<<dp[n]<<endl;
}
return 0;
}
B: BanGosu!
题目描述
Yui最近在玩音游,但Yui并不满足于玩游戏,她决定制作一款属于自己的音游,名为BanGosu!。
在bangosu中,会给出n个半径为r的圆圈,玩家需要在恰当的时刻点击屏幕上出现的圆圈。针对每次点击,点击的位置离圆圈的圆心越近,玩家本次点击可以获得更高的评级,得到的分数也越高。当点击位置距离圆心距离小于0.2*r时为perfect,大于等于0.2*r且小于0.5*r为great,大于等于0.5*r且小于r为good,否则是miss。
除了点击的评级会影响获得的分数外,连击数(combo)也会对获得的分数有加成,每次成功的点击(评级为miss之外)都会使连击数加1。
针对每个出现的圆圈,Yui可以保证在恰当的时刻点击,但点击的位置却不一定准确。给出n个圆圈的位置以及Yui每次点击的位置,你需要算出Yui的最终得分。
- miss会使combo数清零。
- combo数的上涨先于得分判定,假设你现在combo为99,当你再次点击得到great评级时,你的combo数会先上升至100再计算得分,因此你该次点击的得分为
great的评级得分*(1+得分加成),即200*(1+0.01)=202.
- 得分加成只针对当前这次点击
评级 得分 perfect 300 great 200 good 100 miss 0
combo 得分加成 0 <= combo <100 0% 100 \le combo <200 1% 200 \le combo <300 2% 300 \le combo <400 3% 400 \le combo 4%
输入
第一行输入两个整数n和r,分别表示圆的数量和圆的半径。
接下来n行,每行两个正数xi$和yi,表示圆心坐标。
再有n行,每行两个正数xi和yi,表示点击坐标,第i个点击对应第i个圆。
n <= 106
r <= 1000
1 <= xi,yi <= 109输出
输出一个整数score,表示总得分
样例输入 Copy
3 10 114 514 19 19 8 10 114 514.5 19 100 8 17样例输出 Copy
400
#include<bits/stdc++.h>
using namespace std;
#define ll long long
double xi[1000006][2];
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
double r;
cin>>n>>r;
for(int i=1;i<=n;i++)scanf("%lf%lf",&xi[i][0],&xi[i][1]);
double x,y;
ll cnt=0;
ll ans=0;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&x,&y);
double d=sqrt((x-xi[i][0])*(x-xi[i][0])+(y-xi[i][1])*(y-xi[i][1]));
if(d>=r)cnt=0;
else cnt++;
if(d<0.2*r)
{
if(cnt>=400)ans+=300*1.04;
else if(cnt>=300)ans+=300*1.03;
else if(cnt>=200)ans+=300*1.02;
else if(cnt>=100)ans+=300*1.01;
else ans+=300;
}
else if(d<0.5*r)
{
if(cnt>=400)ans+=200*1.04;
else if(cnt>=300)ans+=200*1.03;
else if(cnt>=200)ans+=200*1.02;
else if(cnt>=100)ans+=200*1.01;
else ans+=200;
}
else if(d<r)
{
if(cnt>=400)ans+=100*1.04;
else if(cnt>=300)ans+=100*1.03;
else if(cnt>=200)ans+=100*1.02;
else if(cnt>=100)ans+=100*1.01;
else ans+=100;
}
}
cout<<ans<<endl;
return 0;
}
C: 奇怪的引擎
题目描述
输入
第一行输入一个正整数T(1<=T<=1000),表示测试的组数。
下面有T组测试,每组测试1行,每行有一个实数P(0<=P<=1012),表示当前引擎的功率。输出
对于每组测试,输出当前时间t,单独占一行,当输出t与正确答案的误差不超过10-6时视为答案正确。
样例输入 Copy
2 0 613.7022552757样例输出 Copy
0 114.514
思路:设置上限以及下限然后使用二分查找答案。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int T;
cin>>T;
while(T--)
{
double p;
cin>>p;
double l=0.0,r=10000000000.0;
while(l+0.0000001<r)
{
double mid=(l+r)/2;
double ans=sqrt(mid*mid*mid)/2+sin(mid);
if(ans<=p)l=mid;
else r=mid;
}
printf("%lf\n",l);
}
return 0;
}
D: Diana压缩算法
题目描述
王嘉然在摸鱼时想出了一个01串的压缩算法,该算法如下:
首先将01串切分,相邻三个一组(比如一个长度为6的01串,切分后前三个一组,后三个一组),之后,使每个组对应一个小写字母,要求内容相同的组所对应的字母相同,把每个组都替换为相对应的字母,并且替换后得到的字符串字典序最小。
但是大聪明杜向晚显然没有理解这个算法,她需要一个人帮她完成01串的压缩。输入
第一行一个整数n(n <= 105)
第二行输入一个字符串s,|s| = 3 * n输出
输出一个字典序最小的字符串
样例输入 Copy
3 010000010样例输出 Copy
aba提示
为使字典序最小,把010对应a,000对应b。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int vis[1005];
char s[1005];
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
char c='a';
int n;
cin>>n;
n*=3;
int cnt=0;
int x;
for(int i=1;i<=n;i++)
{
scanf("%1d",&x);
cnt=cnt*10+x;
if(i%3==0)
{
if(!vis[cnt])
{
vis[cnt]=1;
s[cnt]=c;
c++;
}
cout<<s[cnt];
cnt=0;
}
}
return 0;
}
F: 天天爱跑步
题目描述
小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。天天爱跑步是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。
游戏一共有n个玩家,每个玩家每天需要跑60圈才能打卡,玩家打卡后游戏会记录每个玩家完成打卡所花费的时间,你能帮小c设计一个程序,将所有玩家按完成打卡时间的长短排序吗?(假设所有玩家每天都能完成打卡)输入
第一行一个整数n(n <= 5000)
接下来n行,每行的格式为:
name h:m:s
其中name代表人名,由小写字母构成,长度不超过10,h,m,s,分别代表时,分,秒,0 < h < 100 , 0 < m < 60 , 0 < s < 60输出
输出n行,每行一个字符串,表示排名为i的玩家的人名
按用时升序排序,若用时相同,则按照输入顺序排序样例输入 Copy
2 homura 1:1:2 madoka 1:1:1样例输出 Copy
madoka homura
在比赛时,并不知道用cmp排序并不稳定,于是当时的排序就没过,经过这次比赛,引以为戒,注意cmp一定要严格排序。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
string name;
int h,m,s;
int time;
}q[5010];
bool cmp(node a, node b)
{
if(a.h!=b.h)return a.h<b.h;
if(a.m!=b.m)return a.m<b.m;
if(a.s!=b.s)return a.s<b.s;
return a.time<b.time;
}
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>q[i].name;
scanf("%d:%d:%d",&q[i].h,&q[i].m,&q[i].s);
q[i].time=i;
}
sort(q+1,q+n+1,cmp);
for(int i=1;i<=n;i++)cout<<q[i].name<<endl;
return 0;
}
H: 奇怪的加法问题
题目描述
近期,彬彬迷上了艾尔登法环,但他没有足够的资金,于是他找到了杰哥去借钱,但杰哥却被一道很简单的数论题目所难倒,如果彬彬能够解出该题,那么杰哥将借给彬彬一些资金。可彬彬是个只会小学数学的学渣,你能帮助他吗?
给出一个数组a,求所有的ai + aj(满足i < j)异或后再对2取模的值
例如:给出一个长度为4的数组a = {a1, a2, a3, a}
求((a1+a2) xor (a1+a3) xor (a1+a4) xor (a2+a3) xor (a2+a4) xor (a3+a4)) MOD 2
xor:异或运算
对于二进制下的每一位,异或运算结果如下:
运算 结果 0 xor 0 0 0 xor 1 1 1 xor 0 1 1 xor 1 0
输入
第一行输入一个n,代表数组长度为n, 1 <= n <= 5*105
第二行给出n个整数ai,0 <= ai <= 109输出
输出一个整数,表示答案
样例输入 Copy
3 1 3 4样例输出 Copy
0
通俗来讲,异或运算就是把数转化为二进制之后,相加不进位的一种加法,如二进制下相对应的数字为1和1,那么这个位上运算过后就是(1+1)%2。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
cin>>n;
ll j=0,o=0;
ll a;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a);
if(a&1)j++;
else o++;
}
j*=o;
if(j&1)puts("1");
else puts("0");
return 0;
}
J: 扫描线
题目描述
给你一个大小为n×n的数字矩形,请你选择删除一部分数据,使得数字矩形分成两部分,删除的数据必须在同一条直线上,直线必须与矩形对角线平行,求两部分的最小差值
注意!至少要删除一个数字
例如下面的数字矩阵:
1 2 3 4
4 3 2 1
5 6 2 1
3 4 5 6
我们用下划线代表删除的字符
你可以删去一部分数字使其变为:
1 _ 3 4
_ 3 2 1
5 6 2 1
3 4 5 6
下面的删除方法也是合法的:
_ 2 3 4
4 _ 2 1
5 6 _ 1
3 4 5 _
下面的情况也是合法的:
_ 2 3 4
4 3 2 1
5 6 2 1
3 4 5 6
这种情况也可以当成两部分,一部分为空,将其和视为0,另一部分和为51
演示一下非法的情况:
_ 2 3 4
4 _ 2 1
5 6 _ 1
3 4 5 6
这种删除方式是非法的,因为没有把矩阵分成两部分,并且在删除的数字连成的直线上还有数字
_ 2 _ 4
4 _ 2 1
5 6 2 1
3 4 5 6
这种删除方式也是非法的,因为删除的数据在两条直线上,并且在删除的数字连成的直线上还有数字
输入
第一行输入一个整数n(3 <= n <= 1000)
接下来n行,每行n个整数,每个数字aij表示第i行第j个格子里的数是aij(-1000 <= aij <= 1000)
输出
输出一个整数表示答案
样例输入 Copy
4 1 2 3 4 4 3 2 1 5 6 2 1 3 4 5 6样例输出 Copy
1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mp[1005][1005];
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n;
cin>>n;
ll ccnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&mp[i][j]);
ccnt+=mp[i][j];
}
ll ans=1e10;
ll cnt=ccnt;
ll r=0;
for(int i=1;i<=2*n-1;i++)
{
ll res=0;
if(i<=n)
{
for(int j=n-i+1,l=1;j<=n;j++,l++)res+=mp[j][l];
}
else
{
for(int j=1,l=i-n+1;l<=n;j++,l++)res+=mp[j][l];
}
cnt-=res;
ans=min(ans,abs(cnt-r));
r+=res;
}
cnt=ccnt;
r=0;
for(int i=1;i<=2*n-1;i++)
{
ll res=0;
if(i<=n)
{
for(int j=1,l=i;j<=i;j++,l--)res+=mp[j][l];
}
else
{
for(int j=i-n+1,l=n;j<=n;j++,l--)res+=mp[j][l];
}
cnt-=res;
ans=min(ans,abs(cnt-r));
r+=res;
}
cout<<ans<<endl;
return 0;
}
K: 黄金戟
题目描述
某褪色者把血量点到40后,终于击败了大树守卫,拿到了梦寐以求的装备——黄金戟。但是使用黄金戟却需要满足一些要求:力气不少于30点,灵巧不少于14点,信仰不少于12点。
对于力气这个属性,褪色者可以选择双持武器来降低武器对于力气的要求,双持武器后,可以视为自身的力气提升50%(加成后的力气向下取整),比如自身只有10点力气,但双持武器却可以使用要求15点力气的武器。当然,双持只针对力气这一个属性,其他的属性不受双持武器的影响。
给出该褪色者当前的属性,你需要判断是否可以使用黄金戟。输入
第一行输入一个正整数T,表示测试样例数。
之后T行,每行给出三个正整数a,b,c,分别表示褪色者的力气,灵巧,信仰三个属性。
1≤T≤1000
0≤a,b,c≤100
输出
对于每个测试样例
若不需要双持武器就可以使用黄金戟,输出"Yes"(不含引号)
如果需要双持才能使用黄金戟,输出"ulii"(不含引号)
如果双持也无法使用黄金戟,输出"No"(不含引号)
样例输入 Copy
3 30 14 12 20 14 12 30 13 12样例输出 Copy
Yes ulii No提示
第一个样例满足要求
第二个样例需要双持后,力气20*1.5=30,才能使用黄金戟
第三个样例灵巧不足,无法使用黄金戟
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int T;
cin>>T;
while(T--)
{
int a,b,c;
cin>>a>>b>>c;
if(b>=14&&c>=12)
{
if(a>=30)puts("Yes");
else if(a>=20)puts("ulii");
else puts("No");
}
else puts("No");
}return 0;
}