2024牛客寒假算法基础集训营1（补题）

2024-02-28 20:28
文章标签 算法 基础 牛客 2024 补题 寒假 集训营

本文主要是介绍2024牛客寒假算法基础集训营1（补题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • A
  • B
  • C
  • D
  • E
  • F
  • G
  • H
  • I
  • J
  • K
  • L

A

n的范围很小暴力直接 O ( n 3 ) O(n^3) O(n3)直接做就行。
我还傻的统计了一下前后缀，不过怎么写都行这道题。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y secondusing namespace std;const int N=30,mod=1e9+7;
int n,m,a[N],b[N],k;
int f[60][60];
char s[60];
int l[60],r[60]; 
bool st=false;void solve()
{int n;cin>>n;rep(i,1,59)	l[i]=r[i]=0;cin>>(s+1);//DFSmap<char,int>cnt;rep(i,1,n){if(cnt.find('D')!=cnt.end())	l[i]=1;cnt[s[i]]=1;}cnt.clear();fep(i,n,1){if(cnt.find('S')!=cnt.end())	r[i]=1;cnt[s[i]]=1;}//bool st=1;rep(i,1,n){if(s[i]=='F'&&l[i]==1&&r[i]==1){cout<<1<<' ';st=0;break;}}if(st)	cout<<0<<' ';//dfsst=1;rep(i,1,59)	l[i]=r[i]=0;cnt.clear();rep(i,1,n){if(cnt.find('d')!=cnt.end())	l[i]=1;cnt[s[i]]=1;}cnt.clear();fep(i,n,1){if(cnt.find('s')!=cnt.end())	r[i]=1;cnt[s[i]]=1;}rep(i,1,n){if(s[i]=='f'&&l[i]==1&&r[i]==1){cout<<1<<' ';st=0;break;}}if(st)	cout<<0<<' ';cout<<endl;
}signed main()
{IOS	
//  	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

B

赛时的思路是：周围三个点特判，然后左边求最小和右边求最小，最后和特判取最小。
代码写的比较一坨很乱，最后也没调出来。
遇见这种感觉还是重写吧。
主要就是分类讨论

  1. 看鸡左边被堵没有
  2. 看鸡右边被堵没有
  3. 看鸡左边有没有火
  4. 看鸡右边有没有火
  5. 特判（2，0）
    自己写的太丑了，放一份加了注释的jls的代码吧。
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;//left1表示左边是否有火，right1表示右边是否有火//left2表示左边是否能堵住鸡，right2表示右边是否能堵住鸡int left1 = 0, left2 = 0;int right1 = 0, right2 = 0;std::set<std::pair<int, int>> s;for (int i = 0; i < n; i++) {int r, c;std::cin >> r >> c;if (c <= 0) {left1 = 1;}if (c >= 0) {right1 = 1;}s.emplace(r, c);}for (auto [r, c] : s) {if (!c) {continue;}//这里和3异或真的简化了很多代码if (s.count({r ^ 3, c}) || s.count({r ^ 3, c + (c > 0 ? -1 : 1)})) {if (c > 0) {right2 = 1;} else {left2 = 1;}}}int ans = 4 - left1 - left2 - right1 - right2;ans = std::min(ans, int(3 - s.count({2, 0}) - s.count({1, -1}) - s.count({1, 1})));std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}

C

S m i n = 所有人办事的时间 + 等待时间 S_{min}=所有人办事的时间+等待时间 Smin​=所有人办事的时间+等待时间
等待时间 = T 1 ∗ n + T 2 ∗ ( n − 1 ) + . . . + T n ∗ 1 等待时间=T_1 * n + T_2 * (n-1)+...+ T_n * 1 等待时间=T1​∗n+T2​∗(n−1)+...+Tn​∗1
这就转化成了一个经典的问题排序不等式
当 T 1 、 T 2 、 . . . 、 T n T_1、T_2、...、T_n T1​、T2​、...、Tn​按从小到大的对应和n~1相乘
然后看鸡能查到谁的前面

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y secondusing namespace std;const int N=1e5+10,mod=1e9+7;
int n,q,tc;
int t[N],d[N];//x为鸡插队的时间
bool check(int x,int m)
{//找到受鸡插队影响的第一个位置 int l=1,r=n;int k=upper_bound(d+1,d+1+n,x)-d;int sum=(n-k+1)*tc;return sum<=m;
}void solve()
{cin>>n>>q>>tc;rep(i,1,n)	cin>>t[i];sort(t+1,t+1+n);int sm=0;//计算每个人不满意度,sm就是没插队的最小不满意度 //di也是每个人完成工作的时间 rep(i,1,n)	d[i]=d[i-1]+t[i],sm+=d[i];rep(i,1,q){int m;cin>>m;int l=0,r=d[n];while(l<r){int mid=(l+r)>>1;if(check(mid,m))	r=mid;else	l=mid+1;}cout<<l+tc<<endl;}
}signed main()
{IOS	
//   	freopen("1.in", "r", stdin);int _;
//	cin>>_;
//	while(_--)solve();return 0;
}

D

代码是参考jls的，写的真的很优雅
思路：
这里有一个小 t r i c k trick trick,数相乘的话会很大，而 M M M只有 1 e 9 1e9 1e9, 2 3 0 2^30 230就会到达 1 e 9 1e9 1e9。
也就是说，不为0的数相乘很快会超范围有很多不合法的。
对于相同的数，平移的话是都是一样的。
我们考虑不同的数有多少个。
不同的数最多有20个，20个的话就会相乘就会超范围。
然后里面就暴力去瞎搞就行

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define _for(i,a,b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define vi vector<int>using namespace std;
const int maxn=1e5+10,mod=1e9+7,K=4e4,inf=1e9;void solve() {int n,Q;cin>>n>>Q;map<int,int>cnt;rep(i,1,n) {int a;cin>>a;cnt[a]+=1;}set<int>s{0};//只有当不同的数为20个以内时乘起来才不会超出范围if(cnt.size()<=20) {//将map中的内容复制到vector中vector<pii>a(cnt.begin(),cnt.end());int n=a.size();int d=a[0].x-K;//枚举每一个数_for(i,0,n) {//枚举每一个数进行两种操作的总的变化量for(d=max(d,a[i].x-K); d<=a[i].first+K;d++) {//从前往后算一遍答案				int res=1;_for(j,0,n) {//看一下这个数会变成的数，vint v=a[j].x-d;//1的话对res没有影响if(v==1) {continue;}//-1的话看值为这个数的有多少个if(v==-1) {if(a[j].y%2==1) {res*=-1;}continue;}//两个都不是的话就把，所有值为这个数的都乘上去_for(c,0,a[j].y) {res*=v;//中间溢出范围直接退出if(abs(res)>inf) {break;}}//溢出的话直接退出if(abs(res)>inf) {break;}}//满足的话用set存一下，供查询if(abs(res)<=inf) {s.insert(res);}}}}while(Q--) {int M;cin>>M;if(s.count(M)) {cout<<"Yes"<<endl;} else {cout<<"No"<<endl;}}
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("1.in", "r", stdin);int _;
//	cin>>_;
//	while(_--)solve();return 0;
}

E

e题看到数据范围n和m都很小，dfs，对于每场比赛，ab两位选手，考虑每场比赛。
ab两位选手

  1. a胜b败
  2. a败b胜
  3. ab平局
#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y secondusing namespace std;const int N=20,mod=1e9+7;
int n,m,ans;
struct node
{int val,idx;bool operator <(const node t){return val>t.val;}
}a[N],b[N];PII op[N];void dfs(int u)
{if(u==m+1){memcpy(b,a,sizeof a);sort(b+1,b+1+n);
//		cout<<"AAAAAA"<<endl;
//		rep(i,1,n)	cout<<a[i].idx<<' '<<a[i].val<<endl;int k=0;rep(i,1,n)	if(b[i].idx==1)	k=i;ans=min(ans,k);return;}int x=find(op[u].x),y=find(op[u].y);//x胜a[x].val+=3;dfs(u+1); a[x].val-=3;//y胜a[y].val+=3;dfs(u+1); a[y].val-=3;//平局a[x].val+=1;a[y].val+=1;dfs(u+1); a[x].val-=1;a[y].val-=1;
}void solve()
{cin>>n>>m;ans=n;rep(i,1,n){int x;cin>>x;a[i]={x,i};}int k=0;rep(i,1,m){int x,y;cin>>x>>y;if(x>y)	swap(x,y);op[++k]={x,y};}dfs(1);cout<<ans<<endl;return;
}signed main()
{IOS	
//  	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

F

考的是知识点 第二类斯特林数
从题目还是比较容易看出来这是一道第二类斯特林数的题目的，直接从前往后求一遍通项公式。
需要补一下组合数学的知识
d7039fd6bc9ff6fe6361180a79f2f5b.jpg
image

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define vi vector<int>using namespace std;
const int maxn=1e6+10,mod=1e9+7;int ksm(int a,int b, int p){int res=1;while(b){if(b&1)	res=res*a%p;a=a*a%p;b>>=1;	}return res;
}
int fac[maxn],invfac[maxn];
void solve() {int n,m;cin>>n>>m;
// 	vi fac(n+1),invfac(n+1);fac[0]=invfac[0]=1;rep(i,1,maxn){fac[i]=fac[i-1]*i%mod;invfac[i]=ksm(fac[i],mod-2,mod);}      int ans=0;rep(i,0,m){ans+=((m-i)&1?-1:1)*ksm(i,n,mod)%mod*invfac[i]%mod*invfac[m-i]%mod;ans%=mod;}cout<<(ans+mod)%mod<<endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("1.in", "r", stdin);int _;
//	cin>>_;
//	while(_--)solve();return 0;
}

G

前缀和,先对优惠卷按价格排序，然后根据优惠卷可叠加，我们可以知道只要优惠的钱+m>=商品原价就可以更新答案。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y secondusing namespace std;const int N=1e5+10,mod=1e9+7;
int n,m;
struct node
{int x,y;bool operator <(const node t){return x<t.x;	} 
}a[N];void solve()
{cin>>n>>m;rep(i,1,n)	cin>>a[i].x>>a[i].y;sort(a+1,a+1+n);int ans=0,sum=0;rep(i,1,n){sum+=a[i].y;if(sum+m>=a[i].x){ans=max(ans,sum+m);}}if(!ans)	cout<<m<<endl;else	cout<<ans<<endl;
}signed main()
{IOS	
//  	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

H

位运算贪心
涉及到位运算的题一定要把数字当成二进制串看
并且不存在进位意味着–位和位之间是独立的。
一般都是贪心的考虑每一位。

对于m我们设第x位为1，设选中的物品与起来为sum，如果sum的第x位为0，那么第x位之后所有的位都是任意的

  • 枚举第x位
  • 选择物品的第x位是0
  • 选择物品的高位应该是m高位的子集
  • 低位任意
#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_backusing namespace std;void solve()
{int n,m;cin>>n>>m;vector<int>v(n+1),w(n+1);rep(i,1,n)	cin>>v[i]>>w[i];int ans=0;auto check=[&](int s){int res=0;rep(i,1,n){//==的优先级高于&if((s&w[i])==w[i]){res+=v[i];}}ans=max(ans,res);};check(m);fep(i,29,0){if((m>>i)&1){check(m^(1<<i)|((1<<i)-1));	}}cout<<ans<<endl;return;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

I

两种方式的区别在于半径。
我们可以模拟题目中的过程然后在本地多跑几组数据看看r的均值有什么规律
技巧就是打表找规律

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_backusing namespace std;
const int N=2010;int mod=1e9+7;void solve()
{int n;cin>>n;int s=0;rep(i,1,n){int x,y,r;cin>>x>>y>>r;s+=r;}if(s/n<20.0)	cout<<"bit-noob"<<endl;else	cout<<"buaa-noob"<<endl;return;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

J

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define _for(i,a,b) for(int i=(a); i<(b); ++i)
#define pii pair<int, int>
#define pdd pair<double,double>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define vi vector<int>using namespace std;
const int maxn=1e5+10,mod=1e9+7,K=4e4,inf=1e9;
int a[maxn];
int n,x,y;bool check(int tar) {set<int>S;if(abs(x-y)<=tar)	S.insert(y);int lst=x;rep(i,1,n){if(S.size()&&abs(a[i]-lst)<=tar){S.insert(lst);}while(S.size()&&abs(*S.begin()-a[i])>tar)	S.erase(*S.begin());while(S.size()&&abs(*S.rbegin()-a[i])>tar)	S.erase(*S.rbegin());lst=a[i];}return S.size();
}void solve() {cin>>n>>x>>y;rep(i,1,n) {cin>>a[i];}int l=0,r=1e9;while(l<r) {int mid=(l+r)>>1;if(check(mid)) {r=mid;} else {l=mid+1;}}cout<<l<<endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("1.in", "r", stdin);int _;
//	cin>>_;
//	while(_--)solve();return 0;
}

K

基环树

L

这道题应该是个签到题。主要是题面有点吓人。
直接考虑光源在最下面，这种情况地上的未被照射到的面积应该是最大的。
面积很好求，就是一个等腰梯形的面积。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y secondusing namespace std;const int N=1e5+10,mod=1e9+7;
int n,q,tc;void solve()
{int c,d,h,w;cin>>c>>d>>h>>w;db ans=1.0*(6*w)*c/2;printf("%.5lf\n",ans);
}
signed main()
{
// 	IOS	
//  	freopen("1.in", "r", stdin);int _;cin>>_;while(_--)solve();return 0;
}

这篇关于2024牛客寒假算法基础集训营1（补题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/756533。

相关文章

SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
C#基础之委托详解(Delegate)

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》：本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托（Multicast Delegates）4. 委托的用途事件处理回调函数LINQ
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型，3步搞定一个应
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
MySQL中my.ini文件的基础配置和优化配置方式

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面：幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件
阅读更多...
Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

《Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)》：本文主要介绍Python基于火山引擎豆包大模型搭建QQ机器人详细的相关资料,包括开通模型、配置APIKEY鉴权和SD... 目录豆包大模型概述开通模型付费安装 SDK 环境配置 API KEY 鉴权Ark 模型接口Prompt
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2