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

比赛链接

A 装备二选一（一）

简单介绍：

66E61d他拥有一个可以为他增加a%的暴击率，发生暴击时会使他本次普通攻击伤害变为原来的b倍

现在存在另一个武器，可以为他增加a%的暴击率，发生暴击时会使他本次普通攻击伤害变为原来的b倍，询问是否能替换获得更高输出能力

这个题卡了我好久，都不准备写了，后来带个数考虑到了占比问题

思路：

我们将最开始的能力当作100，然后分为两部分，暴击的乘以其倍数，不暴击的不变，结果求和，比较两个武器哪个更好

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
//int a[110],b[110];
void solve()
{int a,b,c,d;cin>>a>>b>>c>>d;if(a*b+(100-a)<c*d+(100-c))cout<<"YES"<<endl;elsecout<<"NO"<<endl;	
}
signed main()
{IOSint t;t=1;//cin>>t;while(t--)solve();return 0;
}

B 百变吗喽

简单介绍：

给出两个字符串s，t，确保给出的字符串len(s)=len(t)-1,我们可以进行一次操作：在任意位置插入任意小写字母，求出有多少种操作方案

思路：

1. 用两个数组存储s,t中各个字母出现的次数，比较s，t ，将其字符不同的位置用r记录
2. 比较两个数组记录的字母数量，如果不同则用c累加差值，用q记录该字符
3. 如果想要根据插入即可让字符串相等，那么两个数组应只有一个字母数量不同，即c值为1，因此如果c不等于1，输出0即可
4. 如果首次出现不同的位置在1，则**只有1种解法，**输出位置0与字符q即可
5. 如果不在1，则判断该位置紧挨着是否出现重复该字符及次数w，因为如果重复则可以插在不同位置，有不同的方案，靠前第一个与该字符不同的位置开始插入，有w种方案

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int a[1000010],b[1000010];void solve()
{int ty=0;string s,t;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']++;}int r=-1;for(int i=0;i<t.size();i++){if(s[i]!=t[i]){r=i;break;}}if(r==0)ty=1;if(r==-1)r=t.size()-1;
//	cout<<r<<endl;char q;int c=0;for(int i=0;i<26;i++){if(a[i]!=b[i]){q=i+'a';c+=abs(a[i]-b[i]);}}//cout<<q<<endl;if(c!=1)cout<<"0"<<endl;else if(ty==1){cout<<"1"<<endl;cout<<"0 "<<q<<endl;}else{int w=1,u=r;for(int i=r-1;i>=0;i--){if(t[i]==t[r]){w++;u=i;}elsebreak;}int i=u;cout<<w<<endl;while(w--){cout<<i<<" "<<q<<endl;i++;}}
}signed main()
{IOSint t;t=1;// cin>>t; while(t--)solve();return 0;
}

C 16进制世界

简单介绍：

这是一个类似于01背包的问题，不过多了一个限制条件幸福度，幸福度必须为16的倍数

思路：

直接按照类似于01背包处理，需要16的倍数这一限制条件，我们可以对16取模，增加一维幸福度的判断，关于背包问题可以参考博客

代码：

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
using namespace std;
const int N = 1e5 + 10;
int dp[N][20];
void solve() 
{int n,m;cin>>n>>m;memset(dp,-0x3f,sizeof(dp));dp[0][0]=0;for(int i=1;i<=n;i++){int v,w;cin>>v>>w;w%=16;for(int i=m;i>=v;i--){for(int j=0;j<16;j++){dp[i][j]=max(dp[i-v][(j+w)%16]+1,dp[i][j]);}}}int ans=INT_MIN;for(int i=0;i<=m;i++){ans=max(ans,dp[i][0]);}cout<<ans<<endl;return;
}signed main()
{IOS;int t = 1;while (t--) solve();return 0;
}

D 四散而逃

简单介绍：

n个格子排成一排，每个格子有a[i]个人，每次奔逃选择三个下标，i，j, k使得1<=i<j<k<=n，并且a[j]>=2,从j号格子中选择两人分别逃到i号和k号格子

求出最少需要多少次奔逃才能够让所有人都到达1号格子或者n号格子。若无论多少次操作都做不到，就输出-1

思路：

1. 如果n为3时，我们可以发现中间的数为奇数时，最后会剩下一个1无法处理，因此输出-1，如果为偶数，则除以2即为结果
2. 如果2至（n-1），这些方格都为1人，我们无从下手，因此也输出-1
3. 当其他情况时，我们可以在选择大于等于2人奔逃时，让人跑向奇数方格中，这样就可以使其变为偶数
4. 由于每个奇数都要尽力变为偶数，因此如果该方格人数x为偶数时，需要奔逃次数为x/2，为奇数时，需要奔逃次数为（x+1）/2，最终将n个格子需要奔逃次数相加输出即可

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
int a[1000010];
map<int,int>p;
void solve()
{int n;cin>>n;int q=0;int sum=0;for(int i=1;i<=n;i++){cin>>a[i];if(i>1&&i<n){if(a[i]>1)q=1;}}//cout<<q<<endl;if(n==3){if(a[2]%2==0)cout<<a[2]/2<<endl;elsecout<<"-1"<<endl;}else if(q==0)cout<<"-1"<<endl;else{for(int i=2;i<n;i++){sum+=(a[i]+1)/2;}cout<<sum<<endl;}
}
signed main()
{IOSint t;t=1;//cin>>t;while(t--)solve();return 0;
}

F 追寻光的方向

简单介绍：

小G所在道路有n个路灯，每个路灯发出的光亮为l[i],小G每次全力以赴跑到最亮的路灯下休息，然后继续跑到下一个最亮的路灯下，求出小G如果想到达第n个路灯下，需要休息几次？

思路：

1. 用map容器将路灯的亮度与位置对应存入
2. 将路灯亮度排序，倒着遍历其位置，如果该路灯的位置在比他亮的路灯之前则无需处理，如果在之后则需要将休息次数加一
3. 由于最后一段到n的路程无需休息，所以输出时应该将休息次数减一输出

这个题我多想了，我刚开始想如果有两个相等的数，下标是不是需要一个二维数组或者容器来储存呢？

后来我发现，同一个数字的话，我们只记录最后的那个下标就可以啦，多想咯

代码

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
int a[1000010];
map<int,int>p;
void solve()
{int n;cin>>n;//int ma=INT_MIN;for(int i=1;i<=n;i++){cin>>a[i];p[a[i]]=i;}sort(a+1,a+n+1);int r=-1;int w=0;for(int i=n;i>0;i--){if(p[a[i]]>r){w++;r=p[a[i]];}}cout<<w-1<<endl;
}
int main()
{IOSint t;t=1;//cin>>t;while(t--)solve();return 0;
}

G 等公交车

简单介绍：

给出各个站点到发车点的距离和公交车的发车时刻，接下来求出在时刻t时来到了x号站点的乘客的最少等待时间，如果无法乘上车，则输出”TNT“

思路：

1. 如果该乘客到达的时间点比最晚发车到达其站台的车还要迟，则无法乘车
2. 我们在乘客所在站点的距离，依次加发车时刻,为不同车到达该站点的时间（因为公交车1米/分钟），直到出现第一个大于乘客下车的时刻，用这个时刻减去乘客下车时刻即为所需等待的最短时间

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
int a[100010],b[100010];
void solve()
{memset(b,0,sizeof(b));int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}int q;cin>>q;int x,y;for(int i=1;i<=q;i++){cin>>x>>y;if(x>a[y]+b[m])cout<<"TNT"<<endl;else{int ty;for(int i=1;i<=m;i++){if(a[y]+b[i]>=x){ty=a[y]+b[i];break;}}cout<<ty-x<<endl;}} 
}
signed main()
{IOSint t;t=1;//cin>>t;while(t--)solve();return 0;
}

I 正义从不打背身:

简单介绍：

小x面前有n个敌人，他只能击败正对自己的敌人，每次操作为将1.2.3…n位置变换为n.n-1…3.2.1,然后将敌人旋转180度，请求出m次操作后，敌人是否全被击败

思路：

1. 我们通过具体操作发现其位置出现是有规律的，m次操作即为m，m-2，…依次减2，然后正着将未输出的全部输出即为所求顺序
2. 翻转奇数次则变换，偶数次则不变，次数为m-i+1，然后根据是否正面朝向判断是否被击败

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
int a[2000010],b[2000010];
void solve()
{int n,m;cin>>n>>m;string s;cin>>s;s=" "+s; for(int i=1;i<=m;i++){if((m-i+1)%2!=0){if(s[i]=='P')b[i]=0;elseb[i]=1;}else{if(s[i]=='P')b[i]=1;elseb[i]=0;}}int k=0;int t;if(m%2==0)t=1;elset=2;for(int i=m;i>=1;i-=2){a[++k]=b[i];}for(int i=t;i<=m;i+=2){a[++k]=b[i];}if(n>m){for(int i=m+1;i<=n;i++){a[++k]=(s[i]=='P');}}for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<endl;return;
}
signed main()
{IOSint p;p=1;//cin>>t;while(p--)solve();return 0;
}

L koala的程序

简单介绍：

这是一个约瑟夫环问题，n个人，从第一个人开始，从1报数，报到m的人出局，下个人接着从1报数，n个人报完再从第一个人轮换，直到最后剩一个人为止，给出n-1个人的出局顺序

思路：

1. 我们可以用树状数组+二分来解决这个问题，我们将人数用树状数组的存储方式存入数组，我们想查找前面有多少人时可以引用函数sum来求解
2. 我们用二分可以找到出局的人
3. 当出局一个人时，我们用add（l,-1)，即可达到更新维护前缀和的目的
4. 每次出局后，记得更新剩余人数

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
int tr[2000010]; 
int n,m;
int lowbit(int x)
{return x&(-x);
}void add(int a,int b)
{for(int i=a;i<=n;i+=lowbit(i)){tr[i]+=b;}	
}int sum(int c)
{int res=0;for(int i=c;i>0;i-=lowbit(i)){res+=tr[i];}return res;
}void solve()
{//int n,m;cin>>n>>m;	for(int i=1;i<=n;i++){add(i,1);}int now=1;int nn=n; while(nn){now=(now+m-1-1)%nn+1;int l=1;int r=n;while(l<r){int mid=l+r>>1;if(sum(mid)>=now)r=mid;elsel=mid+1;}if(nn==1)break;cout<<l<<" ";add(l,-1);nn--;}
}
signed main()
{IOSint p;p=1;//cin>>p;while(p--)solve();return 0;
}

H题有时间再补吧。。。