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

本文主要是介绍河南萌新联赛2024第（六）场：郑州大学（ABCDFGHIL），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

写在前面

昨天打的这场萌新联赛打的也是非常烂，感觉最近不在状态，打比赛总感觉发挥不出自己的水平，可能是集训一个多月都没咋休息了，身心也是有点疲惫，在坚持几天就开学了，在这最后几天在加把劲，多学一点东西总归是好的(菜是原罪QWQ)

A 装备二选一（一）

思路

签到题，假设普通攻击为1并且攻击木桩100次，那么它产生暴击的次数就为 $a|c$ 次，比较两次的伤害即可

code

void solve(){int a,b,c,d;cin >> a >> b >> c >> d;int ans1=a*b+(100-a);int ans2=c*d+(100-c);if(ans2>ans1) cout << "YES";else cout << "NO";return ;
}

B 百变吗喽

思路

考点：模拟

对于字符串s来说，它只可能比字符串t少一个字符
首先先找出字符串s缺少的字符(若缺少的字符超过1，那么字符串s就不可能等于字符串t，直接输出0)

找到该字符以及该字符在t的位置，这时需要判断它的左右两边是否为相同的字符，若满足则继续判断
每次都将满足的字符的下标存入ans数组里面，最后将ans进行升序排序，输出ans即可

code

void solve(){vector<int> ans;int k=-1;string s,t;cin >> s >> t;char c;for(int i=0;i<s.size();++i){if(s[i]!=t[i]){k=i;c=t[i];for(int j=i+1;j<t.size();++j){if(t[j]!=s[j-1]){cout << 0 << endl;return ;}}break;}}if(k==-1){c=t[t.size()-1];k=t.size()-1;	} ans.push_back(k);int k1=k;while(k>0){k--;if(t[k]==c) ans.push_back(k);else break;}while(k1<t.size()-1){k1++;if(t[k1]==c) ans.push_back(k1);else break;}sort(ans.begin(),ans.end());cout << ans.size() << endl;for(auto i : ans) cout << i << " " << c << endl;return ;
}

C 16进制世界

思路

考点：背包DP

题目要求月饼的幸福度之和为16的倍数，那么它的价值就为当前幸福度求余16
定义 $f[j][k]$ 表示当前背包容量为j并且幸福度为k时，它所容纳的月饼数
显然$f[1-m][0]$ 是我们答案的区间

考虑状态转移，当前幸福度为k时，它可以由(k+w)%16而来
说明上一步的余数k加上当前幸福度w对16的求余刚好等于k

那么它的状态转移方程就为 $f[j][k]=max(f[j][k],f[j-v][(k+w)\%16]+1)$
这是填表法的做法，还有另一种刷表法的做法：$f[j][(k+w)\%16]=max(f[j][(k+w)\%16],f[j-v][k]+1)$

code

void solve(){int n,m;cin >> n >> m;vector<vector<int>> f(m+1,vector<int>(16,-inf));f[0][0]=0;//初始值for(int i=1;i<=n;++i){int v,w;cin >> v >> w;w%=16;for(int j=m;j>=v;--j)for(int k=0;k<=15;++k){f[j][k]=max(f[j][k],f[j-v][(k+w)%16]+1);// 填表法//	f[j][(k+w)%16]=max(f[j][(k+w)%16],f[j-v][k]+1); 刷表法}}int ans=0;for(int j=0;j<=m;++j) ans=max(ans,f[j][0]);cout << ans << endl; return ;
}

D 四散而逃

思路

考点：模拟

把玩一下可以发现，只要序列中的数不全为1，那么所有人都可以逃出去(n=3需要特判，若中间的数为奇数则不满足)
我们只需要遍历一遍数组，若当前数为偶数，那么它需要的操作数就为$a[i]/2$
若当前数为奇数，那么它需要的操作数就为$a[i]/2+1$
两者结合，则为 $(a[i]+1)/2$

code

int a[N];
void solve(){int n;cin >> n;for(int i=1;i<=n;++i) cin >> a[i];if(n==3 && a[2]%2){cout << -1 << endl;return ;}int flag=1;for(int i=2;i<n;++i){if(a[i]!=1) flag=0;}if(flag){cout << -1 << endl;return ;}int ans=0;for(int i=2;i<n;++i) ans+=(a[i]+1)/2;cout << ans << endl;return ;
}

F 追寻光的方向

思路

考点：模拟

签到题，遍历一遍数组，每次遍历到当前序列的最大值时，ans++，将前面的序列的数都减去，继续循环，直到循环结束，输出ans

code

int a[N],b[N];
map<int,int> m;
void solve(){int n;cin >> n;for(int i=1;i<=n;++i){cin >> a[i];b[i]=a[i];m[a[i]]++;} int ans=0;sort(b+1,b+1+n,greater<int>());int l=1; if(b[1]==a[1]) l++;m[a[1]]--;for(int i=2;i<n;++i){if(a[i]==b[l]){ans++;}m[a[i]]--;while(m[b[l]]==0 && l<=n) l++;}cout << ans;return ;
}

G 等公交车

思路

考点：贪心+二分

对于每次询问，首先判断最后一班车出发的时间加上到x站的时间是否小于等于t，不满足直接输出TNT
满足则将当时时间t减去到x站的时间，令这个值为d，相当于在出发点查找与之匹配的公交车
查找可以用二分来优化，查找第一个大于等于d的值，然后进行相减即是所需要的时间

code

int a[N],b[N],sum[N];
void solve(){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;while(q--){int t,x;cin >> t >> x;if(b[m]+a[x]<t) cout << "TNT" << endl;else{t-=a[x];int k=lower_bound(b+1,b+1+m,t)-b;cout << b[k]-t << endl;}}return ;
}

H 24点

思路

考点：模拟

对于这四个数，将它们所有的情况进行排列枚举，由于题目有除法，必然会有精度损失，最后需要判断一下当前的值减去24的绝对值是否小于等于1e-6 即可

code

int a[N],flag=0;
unordered_map<string, int> m = {  {"A", 1}, {"2", 2}, {"3", 3}, {"4", 4}, {"5", 5},  {"6", 6}, {"7", 7}, {"8", 8}, {"9", 9}, {"10", 10},  {"J", 11}, {"Q", 12}, {"K", 13}  
};  
void dfs(vector<double> a){if(flag) return ;if(a.size()==1){if(abs(a[0]-24)<=1e-6) flag=1;return ;}for(int i=0;i<a.size();++i)for(int j=0;j<a.size();++j){if(i==j) continue;vector<double> q=a;q[j]=q[i]+q[j];q.erase(q.begin()+i);dfs(q);q=a;q[j]=q[i]-q[j];q.erase(q.begin()+i);dfs(q);q=a;q[j]=q[i]*q[j];q.erase(q.begin()+i);dfs(q);if(q[j]){q=a;q[j]=q[i]/q[j];q.erase(q.begin()+i);dfs(q);}}return ;
}
void solve(){vector<double> a;for(int i=0;i<4;++i){string s;cin >> s;a.push_back(m[s]);}flag=0;dfs(a);if(flag) cout << "YES" << endl;else cout << "NO" << endl;return ;
}

I 正义从不打背身

思路

考点：模拟？

这题需要打表找规律，如图：
假设初始状态为 ‘-’

很明显，如果m为奇数，奇数项的数在前面，并且它的状态发生改变，偶数项的数在后面，且状态不变
m为偶数，偶数项的数在前面，状态发生改变，奇数项在后面，状态不变
对于超出m的项数，那自然也是不变的

我们只需要按规律模拟即可

code

void solve(){int n,m;cin >> n >> m;string s;cin >> s;for(auto &i : s){if(i=='P') i='1';else i='0';}s=' '+s;string s1=s;int l=1,r=m;if(m & 1){for(int i=m;i>=1;--i){if(i & 1) s1[l]=(s[i]=='1'?'0':'1'),l++;else s1[r]=(s[i]=='1'?'1':'0'),r--;}}else{for(int i=m;i>=1;--i){if(!(i & 1)) s1[l]=(s[i]=='1'?'0':'1'),l++;else s1[r]=(s[i]=='1'?'1':'0'),r--;}}for(int i=1;i<=n;++i) cout << s1[i] << " ";return ;
}

L koala的程序

思路

考点：树状数组 or 线段树

对于这题来说，只需要单点查询，用树状数组更为方便

对于题目的代码和样例，我们不难看出这是一道约瑟夫问题
再看一眼n和k的数据范围，3e5，直接用朴素的算法是过不了的，时间复杂度大致为 $O（n^2）$
一看这数据范围自然得用 $O（nlogn）$的算法来做，很显然想到树状数组

对于每次选取的位置，我们能想到 $(now+m-1)\%n$ （now就是当前位置，m为第几个人出队，n为总人数）
但是这样选取，我们无法取到n的位置

假设一个序列 1 2 3 ，m=3
now初始值为1，（1+3-1）% 3 =0

那么我们可以在取模时做一些技巧，即 $(now-1+m-1)\%n+1$ ,进行一次+1 -1 的操作，这样就能取到n了
每次选取到的数，对于树状数组来说，代表的是前缀和的值(具体讲解看下图)

具体实现看代码~~

code

int a[N];
int n,m;
void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)){a[i]+=k;}
}
int sum(int x){int ans=0;for(int i=x;i;i-=lowbit(i)){ans+=a[i];}return ans;
}
int search(int s){int l=1,r=n;while(l<r){int mid=l+r>>1;if(sum(mid)>=s) r=mid;else l=mid+1;} return l;
}
void solve(){cin >> n >> m;for(int i=1;i<=n;++i) add(i,1);int now=1,op=n;while(op>1){now=(now-1+m-1)%op+1;int ans=search(now);cout << ans << " ";add(ans,-1);op--;}return ;
}

这篇关于河南萌新联赛2024第（六）场：郑州大学（ABCDFGHIL）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---