2024牛客寒假算法基础集训营1

A.DFS搜索

判断子序列构成的字符中是否包含”DFS“和”dfs"

数据范围特别小甚至可以解决问题，我们可以使用如果前面的出现判断后面的然后看指针的方式即可(参考别人的高级写法)

void solve(){cin>>n;string s; cin>>s;for(auto t : {"DFS","dfs"}){int k=0;for(int i=0;i<n;i++)if(k<3 && s[i]==t[k]) k++;cout<<(k==3)<<' ';}cout<<endl;return ;
}

B.关鸡

比赛中我们发现很多人不是一发过的就可以慢点写多考虑一些细节，特别是什么情况会挡住，

1.   这样是挡住的

2.是挡住

然后考虑左右是否都有挡住，这种题目不怕写的麻烦主要是注意细节

void solve(){cin>>n;map<int,int> mp[3];while(n--){int r,c; cin>>r>>c;mp[r][c]++;}int need=3;int cnt=0;if(mp[1].count(1)) cnt++;if(mp[1].count(-1)) cnt++;if(mp[2].count(0)) cnt++;need=3-cnt;bool left=false,right=false;bool okl=false,okr=false;for(auto&[v,w]:mp[1]){if(v<0){left=true;if(mp[2].count(v) ||mp[2].count(v-1)||mp[2].count(v+1)) okl=true;}if(v>0){right=true;if(mp[2].count(v) ||mp[2].count(v-1)||mp[2].count(v+1)) okr=true;}}for(auto&[v,w]:mp[2]){if(v<0){left=true;if(mp[1].count(v) ||mp[1].count(v-1)||mp[1].count(v+1)) okl=true;}if(v>0){right=true;if(mp[1].count(v) ||mp[1].count(v-1)||mp[1].count(v+1)) okr=true;}}int now=3;if(okl && okr){now=0;}else{if(okl){if(right) now=1;else now=2 - (mp[2].count(0) ? 1 : 0);}else if(okr){if(left) now=1;else now=2 - (mp[2].count(0) ? 1 : 0);}else{if(left && right) now=2;}}need=min(need,now);cout<<need<<endl;

C.按闹分配

我们考虑这样来思考，首先在没人插队的时候肯定是最小的在前面最好这样的贡献是最小的,因为每个人的贡献是前面的人之和加上自己的，接着我们来看什么地方插队，我们可以发现一定是在一个完整的人后面进行插队的操作，如果是在一个人做任务的中间，那么加的贡献就是从这个人加上后面的人数*t,不如直接在这个人前面，然后我们进入的贡献就是我后面人数*t,所以我插入之后的位置就是表示我后面的人数

void solve(){cin>>n>>q>>m;LL sum=0;for(int i=1;i<=n;i++){cin>>a[i];b[i]=b[i-1]+a[i];sum+=b[i];}sort(a+1,a+1+n);for(int i=1;i<=n;i++){b[i]=b[i-1]+a[i];sum+=b[i];}while(q--){LL x; cin>>x;int t=min(x/m,n);cout<<b[n-t]+m<<endl;}return ;
}

D.数组成鸡

我们可以发现的就是我们一次性是对整个数组进行操作，然后总共又1e5个数，除了1，0，-1，我们可以发现最多可以使用的数就是只有32个2之内，所以数据其实是很小的，我们不妨暴力的来思考这个问题对于每一个数求解一下他增加减少的范围使得大于数据范围就退出，这个波动次数一定不会很多所以不会超时(这种题型一般都有这样一个trick的手法就是2e5的乘法太大了然后利用这个性质)

void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);set<LL> S;S.insert(0);auto check = [&](LL x){LL res=1;for(int i=1;i<=n;i++){res*=(a[i]+x);if(abs(res)>1e9) return false;}S.insert(res);return true;};for(int i=1;i<=n;i++){if(a[i]==a[i-1]) continue;LL add=-a[i]+1;while(check(add)) add++;LL sub=-a[i]-1;while(check(sub)) sub--;}while(m--){LL x; cin>>x;cout<<(S.count(x) ? "Yes" : "No")<<endl;}return ;
}

E.本题又主要考察了贪心

这个题目我们发现数据范围是很小的，虽然第一想法是能不能贪心但是我们会发现明显是错误的因为贪心的话我们无法保证除了1之外的对局是怎样的情况，我们发现对局只有10次如果我们直接暴力枚举所有的情况的话就是，然后利用如果以及确保1是第一位了直接剪枝，这样的话时间复杂度是ok的所以我们直接使用dfs去暴力枚举即可

PII e[M];
int a[N],b[N];
int ans;void dfs(int u){if(ans==1) return ;if(u>m){int res=a[1];for(int i=1;i<=n;i++){b[i]=a[i];}sort(b+1,b+1+n,greater<int>());int pos=n;for(int i=1;i<=n;i++){if(b[i]==res){pos=i; break;}}ans=min(ans,pos);return ;}auto [x,y]=e[u];vector<PII> v={{3,0},{0,3},{1,1}};for(auto[i,j]:v){a[x]+=i,a[y]+=j;dfs(u+1);a[x]-=i,a[y]-=j;}}
void solve(){cin>>n>>m;ans=n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){int x,y; cin>>x>>y;e[i]={x,y};}dfs(1);cout<<ans<<endl;return ;
}

F.鸡数题！

这个题目考察的是斯特林数，属于数论中的知识，我们首先分析这个题本身,也就是把一堆位置的1放在m个盒子中排序，我们可以发现就是第二类斯特林数，n个不同的球放在m个本质相同的盒子里面，我们使用公式求解即可

// 快速幂+组合数
int fn[N],fnm[N];
LL qmi(LL a,LL b,LL p){// 快速幂LL res=1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res;
}void intn(){fn[0]=fnm[0]=1;for(int i=1;i<N;i++){fn[i]=(LL)fn[i-1]*i%mod;fnm[i]=(LL)fnm[i-1]*qmi(i,mod-2,mod)%mod;}
}LL inv(LL x){return qmi(x,mod-2,mod);
}
void solve(){cin>>n>>m;LL ans=0;if(n>=m){for(int i=0;i<=m;i++){LL now=qmi(i,n,mod);now=now*fnm[i]%mod*fnm[m-i]%mod;if((m-i)&1) ans=(ans-now+mod)%mod;else ans=(ans+now+mod)%mod;}}cout<<ans<<endl;return ;
}

G.why买外卖

这个题目首先我们发现是没办法用数组存储的，但是同时他具有前缀和的性质，所以我们可以使用map来做一个前缀和的处理然后如果说对于这个价位在优惠之后我可以购买他的话(v-w)<=m，那么贡献就是v+m-(v-w) (v是价格,m是手上的钱，w是对应的这个价格的优惠)，我们可以认为是优惠券抵消了之后我还需要花多少钱剩余的钱加上我这个价位就是答案，注意：（优惠券的价格可以大于购买值） 也就是我买 5 元钱 以上 他优惠10元，那么我自然而然买10元更好所以不需要和0比较

struct code{LL a,b;bool operator<(const code&t)const{return a<t.a;}
}e[N];void solve(){cin>>n>>m;for(int i=1;i<=n;i++){LL a,b; cin>>a>>b;e[i]={a,b};}sort(e+1,e+1+n);map<LL,LL> mp;for(int i=1;i<=n;i++){auto [a,b]=e[i];if(i==1) mp[a]=b;else mp[a]=mp[e[i-1].a]+b;}LL res=m;for(auto&[v,w]:mp){LL now=0;if(v-w<=m){now=v+m-(v-w);}res=max(res,now);}cout<<res<<endl;return ;
}

H.01背包，但是bit

首先题目告诉我们的是按位与，也就是只要有1就是1,我们对于位运算的题目第一想法是拆位，我们思考这样一个问题，如果(32位中的一位)对于我这一位我不要了,那么只要在不超过我前面的基础上我后面的是可以任意选的这是一个明显的策略，（当然对于容量而言这一位必须是1），同时我对于所有的和我位置完全一样或者少于等于我的也是ok的，这样我们发现我们考虑了所有的情况，但是怎么去处理又是一个问题-->还得是落脚点在位运算中，我们考虑这一位^1，然后|(（1<<i）-1)

如果说与我&之后还是他本身也就是说对于这个点是符合上面这种手法的前面的不超过后面的小于等于即可,所以这样就可以解决问题

int v[N],w[N];void solve(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}LL ans=0;auto get = [&](int m){LL res=0;for(int i=1;i<=n;i++){if((m&w[i])==w[i]){res+=v[i];}}ans=max(ans,res);};for(int i=32;i>=0;i--){if(m>>i&1){get(m^(1<<i)|((1<<i)-1));}}get(m);cout<<ans<<endl;return ;
}

I.It's bertrand paradox. Again!

这个题做法很多重点还是落在概率和期望中，题目告诉我们很多等可能的概率，我们来找他们的区别，一个是[x,y] [r]不合理修改r ,另外的是[x,y] [r] 全部都修改，我们可以发现的是如果对于r:[1,100]

他们对应出现[x,y]的概率是不一样的，我们可以简单算以下就是面积的比例，然后[1,100]是对应出现的但是有些是不合理就会继续操作我们不妨先每一个都出现对于的次数，然后对于不合理的接着这个过程就可以计算出每一个位置大概的出现次数，接着和给的次数比较，如果差距很大那就是错误的，我们可以用一个简单范围来计算即可

void solve(){cin>>n;m=1e5;vector<int> cnt(105),c(105);while(n--){int x,y,r; cin>>x>>y>>r;cnt[r]++;}while(m>100){int now=m/100;for(int i=1;i<=100;i++){double x=1.0*(200-2*i)*(200-2*i)/(200*200);// 假设我抽到的是1的话那么1是ok的概率是这么多c[i]+=x*now;m-=x*now;}}int ok=0;for(int i=1;i<=100;i++){if(abs(c[i]-cnt[i])>=100) ok++;}cout<<(ok > 10 ?  "bit-noob" : "buaa-noob" )<<endl;return ;
}

L.要有光

属于诈骗题目我们只需要发现其实就是一个梯形的面积即可

void solve(){LL c,d,h,w; cin>>c>>d>>h>>w;LL ans=w*c*3;cout<<ans<<endl;return ;
}

M.牛客老粉才知道的秘密

我们发现如果到头了不是恰好的话后面的每一个位置都会回来同时与上一层位置差几个位置

所以如果有余数翻倍否则就是本身

void solve(){cin>>n;int ans=n/6;if(n%6) ans*=2;cout<<ans<<endl;return ;
}