2024河南省萌新联赛第（六）场 郑州大学

A.装备二选一（一）

原题链接

题意：

自己的武器可以增加a%暴击率，发生暴击时本次攻击率增加b倍，击败boss的武器可以增加c%暴击率，发生暴击时本次攻击率增加d倍，求boss的输出率是否比自己的武器高

思路：

一个数学问题，一开始一直没看到没有发生暴击时本次也是输出的，用数学思路解决就可以，暴击率乘以增加倍数加上原来的攻击等于该武器的输出率，如果boss的大于自己的输出YES，否则输出NO。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;signed main()
{IOSint a,b,c,d;cin>>a>>b>>c>>d;double x=a*1.0/100*b;double y=c*1.0/100*d;double x1=(100-a)*1.0/100;double y1=(100-c)*1.0/100;//cout<<x<<" "<<y<<'\n';if(x+x1<y+y1)cout<<"YES"<<'\n';elsecout<<"NO"<<'\n';
}

B.百变吗喽

原题链接

题意：

给出两个字符串s,t，找出如何将s添加一个字符变成t，求出方案数，并输出应该添加那个字符和添加到第几位的后面，如果添加到最前面，则是添加到第0位的后面。

思路：

先统计字符串中每个字符的个数，如果t字符串减去s字符串不为1，则输出0；循环字符串，如果该地方两个字符串不同，那么t[i]就是需要添加的字符，在往前循环s字符串，如果与t[i]相等，就说明也可以添加到该字符后面，直到不相等结束。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;int a[30],b[30];signed main()
{IOSstring s,t;int ss=0,tt=0,ans=1;cin>>s>>t;for(int i=0;i<s.size();i++){a[s[i]-'a']++;}for(int i=0;i<t.size();i++){b[t[i]-'a']++;}for(int i=0;i<30;i++){ss+=abs(b[i]-a[i]);}if(ss!=1)cout<<"0"<<'\n';else{char ch;for(int i=0;i<t.size();i++){if(s[i]!=t[i]){ch=t[i];tt=i;break;}}for(int i=tt-1;i>=0;i--){if(s[i]==ch)ans++;elsebreak;}cout<<ans<<'\n';for(int i=ans-1;i>=0;i--){cout<<tt-i<<" "<<ch<<'\n';}}
}

C.16进制世界

原题链接

题意：

给出两个数n,m分别表示n个月饼，饱食度的和不大于m，接下来n行分别表示每个月饼的饱食度和幸福度，求在饱食度不大于m，并且幸福度为16的倍数时最多吃的月饼的数量

思路：

背包问题请看这

如果出去幸福度不看的话就是一个01背包问题，其实加上幸福度后也不算难，因为需要满足幸福度是16的倍数，所以只需要两个数x,y加起来是16的倍数，所以我们就设饱食度为j时，幸福度与16取模为k时能吃的最多月饼个数，递推方程为:
$$f[j][k]=max(f[j][k],f[j-v[i]][(k-w[i]+16)$$

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=2e5+20;
int v[N],w[N],f[N][20];signed main()
{IOSint n,m;cin>>n>>m;for(int i=0;i<n;i++){int x,y;cin>>x>>y;v[i]=x;w[i]=(y%16);}f[0][0]=1;for(int i=0;i<n;i++){for(int j=m;j>=v[i];j--){for(int k=0;k<16;k++){if(f[j-v[i]][(k-w[i]+16)%16]!=0)f[j][k]=max(f[j][k],f[j-v[i]][(k-w[i]+16)%16]+1);}}}int ans=0;for(int i=1;i<=m;i++){ans=max(ans,f[i][0]-1);}cout<<ans<<'\n';
}

D.四散而逃

原题链接

题意：

一个数n表示n个格子，接下来n个数表示每个格子里的人数，每次可以选择一个格子使得格子里的人一个往右跑，一个往左跑，选择的格子满足该格子必须有两个人及以上并且不能是两边的格子，问至少多少次才能让全部人都在两边格子，如果不能输出-1

思路：

首先考虑是三个格子的特殊情况，如果中间那个格子是奇数就输出-1，否则输出a[2]/2；多个格子时，如果中间的格子每个都是一个人就输出-1，否则每个格子次数都是(a[i]+1)/2，依次累加，就是答案。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=2e5+20;
int a[N];signed main()
{IOSint n,s=0,ss=0;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];if(n==3){if(a[2]%2!=0)cout<<"-1"<<'\n';elsecout<<a[2]/2<<'\n';}else{for(int i=2;i<=n-1;i++){if(a[i]%2!=0)s++;s+=a[i]/2;if(a[i]==1)ss++;}if(ss==n-2)cout<<"-1"<<'\n';elsecout<<s<<'\n';}
}

F.追寻光的方向

原题链接

题意：

给出一个整数n，表示路灯个数，接下来n个整数表示每个路灯的亮度值，每次回跑到实现范围内最大的亮度值处休息，问到达第n个路灯总共需要休息几次。

思路：

把第2个路灯到第n-1个路灯按亮度值从小到大排序b[n]，然后在原来没排序的路等职从第2个到第n个循环，令t=n，如果等于b[t]，就让休息次数加1，t–，m=i，继续循环下一个，如果循环到最后一个值不等于b[t]，就继续从第m开始循环，直到等于为止，最后输出s.

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=2e5+20;
int a[N],b[N];signed main()
{IOSint n,s=0,m;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];}sort(b+2,b+n+1);int t=n;for(int i=2;i<=n;i++){if(a[i]==b[t]){s++;t--;m=i;}if(i==n&&a[i]!=b[t]){t--;i=m;}}cout<<s-1<<'\n';
}

G.等公交车

原题链接

题意：

给两个数n,m，表示n个站点，m辆车，一分钟一米，n个整数依次递增表示每个站点到出发点的距离，m个整数表示每辆车出发的时间，接下来q次查询，每次查询给出一个时间和站点，求最少需要等多长时间，如果坐不上车，输出TNT

思路：

首先是如果当前到达的时间大于最后一辆车加上中间的路径，那么不可能坐上车，直接输出TNT；令到达的时间减去到该站点的距离，表示一分钟不用等时车应该几点出发，循环车出发的时间，当车出发的时间大于等于改时间时，输出，并结束循环，因为出发时间是依次递增的，后面出发的车一定等待时间更长。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=2e5+20;
int d[N],t[N];signed main()
{IOSint n,m,q;cin>>n>>m;for(int i=1;i<=n;i++)cin>>d[i];for(int i=1;i<=m;i++)cin>>t[i];int s=t[m]+d[n];cin>>q;while(q--){int x,y,ss=INT_MAX;;cin>>x>>y;if(x>s)cout<<"TNT"<<'\n';else if(x>t[m]+d[y])cout<<"TNT"<<'\n';else{int tt=x-d[y];for(int i=1;i<=m;i++){if(t[i]-tt>=0){cout<<t[i]-tt<<'\n';break;}}}}
}

I.正义从不打背身

原题链接

题意：

给两个数n,m，n表示有n个敌人，m表示m次操作，操作内容：

第i次操作是先把序号为[1,i]的点位置上的敌人位置改变，改变规则为：从1,2,3……，i变为i,i-1,……,3,2,1（原来i号位置的敌人更换到1号位置……）；

然后把[1,i]的点的敌人原地旋转180

可以击败正对自己的敌人，不可以击中背对自己的敌人，P代表正面，B代表背面

思路：

就是打表找规律，规律还是比较容易的，但我当时因为时间不够给想简单了。正确的规律就是后m+1~n是没有变化的，前m个数的前半部分是以m开头，2为公差递减到1或2的等差数列，后半部分是以1,2中剩余的那个开头，以2为公差递增到m-1。根据这个规律写就可以了。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=2e6+20;
int a[N];signed main()
{IOSint n,m;cin>>n>>m;for(int i=1;i<=n;i++){char ch;cin>>ch;if(ch=='P')a[i]=1;elsea[i]=0;}int tt=m;for(int i=1;i<=n;i++){a[i]+=tt;a[i]=a[i]%2;tt--;if(tt==0) break;}tt=m;int f=0;for(int i=1;i<=m;i++){cout<<a[tt]<<" ";if(f==0) tt-=2;else{if(tt==1){if(m%2==1)tt+=1;elsett+=2;}elsett+=2;}if(tt==0||tt==1){tt=1;f=1;}}for(int i=m+1;i<=n;i++)cout<<a[i]<<" ";
//	if(m%2==0)
//	tt=m/2;
//	else
//	tt=m/2+1;
//	for(int i=0;i<tt;i++)
//	{
//		if(s[i]=='P')
//		s[i]='B';
//		else
//		s[i]='P';
//	}
//	for(int i=0;i<n;i++)
//	{
//		if(s[i]=='P')
//		cout<<"1"<<" ";
//		else
//		cout<<"0"<<" ";
//	}
}