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

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

8.21 2024第（六）场：郑州大学

C 16进制世界

若干月饼，有饱腹度和幸福值。要求饱腹度小于M,幸福值之和为16的倍数。

求，最多吃多少月饼。

背包都学完了，这题都没做出来，丢人

思路

这是01背包和二维费用背包问题的结合。

用$i$表示dp的阶段

$j$ 更新不同体积下最大数量

$k$ 更新不同余数下最大数量

因为要求幸福值和为16的倍数，即余数为0.所以我们需要初始化为**-INF,$f[0][0]=0$**。

这样保证$f[i][0]$ 表示的结果一定是余数为0，饱腹值为i。

不懂的话可以看这篇博客

背包九讲（灵魂版）-CSDN博客

代码

#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++)
const int N=1e5+10;
int v,w,f[N][20];
signed main()
{IOSmemset(f,128,sizeof(f));//初始化无穷小f[0][0]=0;int n,m;cin>>n>>m;fir(i,1,n){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-v][(k+16-w)%16]+1,f[j][k]);}}  int ans=0;fir(i,0,m)//这种初始化，需要比较一下ans=max(ans,f[i][0]);cout<<ans<<'\n';
}

G 等公交车

给出递增发车时间，站点距离。判断需要等多长时间。

题目很简单，赛后发现暴力也能过。可惜没早点看，说到底还是二分不够熟悉，脑子不清晰，大于小于都没搞清，17：02，A也没用了

思路

由于递增，二分查找合适车辆。m+1初始化INF,这样赶不上，l=m+1

代码

const int N=1e5+10;
int a[N],b[N],t,x;
bool check(int mid)
{if(b[mid]+a[x]<t) return 1;return 0;
}
signed main()
{IOSint n,m;cin>>n>>m;fir(i,1,n)cin>>a[i];fir(i,1,m){ cin>>b[i];}  b[m+1]=2000000020;int q;cin>>q;while(q--){cin>>t>>x;int l=1,r=m+1;while(l<r){int mid=(l+r)>>1;if(check(mid)) l=mid+1;else r=mid;}if(l==m+1) cout<<"TNT\n";else cout<<b[l]+a[x]-t<<'\n';}
}

H 24点

给你1-13的四个数字，询问能否组成24.

你可是玩过24点的，怎么这个都没做出来呀，不就是±*/么，全排列函数没记住！考虑那么多括号干嘛，仔细想一想，已经全排列了，再把+ - * /交换一下，已经解决很多括号问题了，再考虑除法精度，ok。不过还是相信你的，给你时间，可以A

思路

运用全排列函数列举不同组合

对于加减乘除，利用函数运算

$i,j,k$ 循环三个运算符号

if（A||B）

A 从前往后依次运算

B （a,b）(c，d) 前后加两个括号

减，除，交换项，分别考虑两次。

即**（a,b）考虑 a/b b/a**

目的是减少括号的列举

a/(b+c-d)

对于后三个加括号，可以这样排列

b c d a

运用A ,从前往后依次算

代码

#include <bits/stdc++.h>
using namespace std;double c(double x, double y, int op) {if (op == 0) return x + y;else if (op == 1) return x - y;else if (op == 2) return y - x;else if (op == 3) return x * y;else if (op == 4) return x / y;else if (op == 5) return y / x;return 0;
}void solve() {int a[4];for (int i = 0; i < 4; i++) {string s;cin >> s;if (s == "A") a[i] = 1;else if (s == "J") a[i] = 11;else if (s == "Q") a[i] = 12;else if (s == "K") a[i] = 13;else if (s == "10") a[i] = 10;else a[i] = s[0] - '0';}sort(a, a + 4);do {for (int i = 0; i < 6; i++)for (int j = 0; j < 6; j++)for (int k = 0; k < 6; k++) if (abs(c(c(c(a[0], a[1], i), a[2], j), a[3], k) - 24.0) < 1e-8 ||abs(c(c(a[0], a[1], i), c(a[2], a[3], j), k) - 24.0) < 1e-8)return cout << "YES\n", void();} while (next_permutation(a, a + 4));cout << "NO\n";
}int main() {ios::sync_with_stdio(false), cin.tie(nullptr);int T;cin >> T;while (T--) solve();
}

B 百变吗喽

给两个字符串，s,t.长度差一。

s中能不能插入一个字符变成t.

几种插法，分别插哪，插谁

思路

赛事代码太麻烦，整理大佬的.

双指针，分别从首尾查找，遇到不同字符停止。

如果能插一个字符相等，i1>=i2

虽然我的复杂，但是至少A的不算很慢，也没有烦人的bug

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,i1,i2;
string s1,s2;
int main(){
cin>>s1>>s2;
n=s2.length();
for(i1=0;i1<n-1 && s1[i1]==s2[i1];i1++);
for(i2=n-1;i2>=0 && s1[i2-1]==s2[i2];i2--);
if(i2<=i1){
cout<<i1-i2+1<<endl;
for(int i=i2;i<=i1;i++)
cout<<i<<" "<<s2[i]<<endl;
}
else cout<<0<<endl;
return 0;
}

L koala的程序

约瑟夫问题

请看博客约瑟夫环问题（模板题，递推，树状数组，双端队列）-CSDN博客

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

---