【题解】牛客小白月赛25
感想：有一说一这次的小白月赛还真的挺舒服的了，代码量小，而且大部分题如果做过类似的题其实很容易就想出来怎么做了，除了B感觉是一个组合数学不是那么好想（数学太差啦），感觉这套题对小白而言是一套挺有意思的题，喜欢这套题。
A AOE还是单体？
三分的模板题，用三分枚举使用多少次第二个技能，然后输出最后的最优值即可。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=2e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
ll a[maxn];
int n,x;
ll val(ll mid){
ll sum=mid*x;
for(int i=1;i<=n;i++){
if(a[i]>mid) sum+=a[i]-mid;
}
return sum;
}
int main(){
scanf("%d%d",&n,&x);
ll sum1=0,sum2=0;
ll mx=1e18;
for(int i=1;i<=n;i++){
scanf("%lld",a+i);
sum1+=a[i];
mx=min(mx,a[i]);
}
ll l=0,r=1e9;
while(l<r){
ll lmid=(2*l+r)/3,rmid=(2*r+l+2)/3;
if(val(lmid)<val(rmid)){
r=rmid-1;
}
else l=lmid+1;
}
printf("%lld",min(sum1,val(l)));
return 0;
}B k-size字符串
有空去想了，就是一个组合数学题，是小球放到盒子那种类型的。
对于k，我们可以先放好这个k，也就是说：可以先abab……,baba……，相当于把盒子放好，让你往里面填小球。
那么对于k是奇偶分为两种情况：（因为奇数除2向下取整）
k是奇数:
k是偶数: 是，b个剩余的球放到a个盒子里面。
那怎么算呢？
我们知道如果盒子不为空可以用隔板法来算，那么同理，现在盒子为空，我们就默认盒子都有一个球，那就是一共有n+m个球，有n+m-1个空隙，插入n-1个板隔开，所以答案就是 。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
ll qPow(ll a,ll b){
ll ans=1;
while(b>0){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
ll C(ll a,ll b){
ll ans=1;
for(int i=1;i<=b;i++){
ans=(ans*(a-i+1)%mod*qPow(i,mod-2))%mod;
}
return ans;
}
ll CC(ll a,ll b){
if(a<=0||b<0) return 0;
return C(a+b-1,a-1);
}
int main(){
ll n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
if(k&1){
printf("%lld",(CC(k/2+1,n-k/2-1)*CC(k/2,m-k/2)+CC(k/2,n-k/2)*CC(k/2+1,m-k/2-1))%mod);
}
else{
printf("%lld",2*CC(k/2,n-k/2)*CC(k/2,m-k/2)%mod);
}
return 0;
}C 白魔法师
树上DP，dp[i][0]表示整个以i为根子树一次都没有用过技能能得到的连通值,dp[i][1]表示整个以i为根子树使用了一次技能能得到的连通值。
然后根据当前点是W还是B来分类讨论一下：
如果当前点是W，那么:
更新完dp[i][0]后
其中mx为dp[to][1]-dp[to][0]里面的最大值，因为只能用一次技能，所以要找到自己孩子子树里面用一次技能获得收益最多的点。
如果当前点是B，那么:
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
VI edge[maxn];
char s[maxn];
int dp[maxn][2];
void dfs(int u,int fa){
int mx=0;
for(int i=0;i<edge[u].size();i++){
int to=edge[u][i];
if(to==fa) continue;
dfs(to,u);
if(s[u]=='B'){
dp[u][1]+=dp[to][0];
}
else{
mx=max(dp[to][1]-dp[to][0],mx);
dp[u][0]+=dp[to][0];
}
}
if(s[u]=='B'){
dp[u][0]=0;
dp[u][1]++;
}
else{
dp[u][0]++;
dp[u][1]=dp[u][0]+mx;
}
}
int main(){
int n;
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
edge[x].pb(y);
edge[y].pb(x);
}
dfs(1,0);
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dp[i][0]);
ans=max(ans,dp[i][1]);
}
printf("%d",ans);
return 0;
}D 抽卡
逆元应用题，因为只需要抽到一张或以上就行，那么概率就是100%减去一张都抽不到的概率。
因为要取模，所以只需要把下面的除数用费马小定理，用快速幂qPow(x,mod-2)就好了。
代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
ll qPow(ll a,ll b){
ll ans=1;
while(b>0){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
ll a[maxn],b[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",a+i);
}
for(int i=1;i<=n;i++){
scanf("%lld",b+i);
}
ll tmp1=1,tmp2=1;
for(int i=1;i<=n;i++){
tmp1=(tmp1*(a[i]-b[i]))%mod;
tmp2=(tmp2*a[i])%mod;
}
printf("%lld\n",(1-tmp1*qPow(tmp2,mod-2)%mod+mod)%mod);
return 0;
}E 点击消除
栈的模板题，就用栈模拟一下，从左往右扫一遍字符串，如果栈顶和当前枚举到的字符相同就把pop栈顶，否则就把字符存入栈中，最后把栈内元素倒出来逆序输出就好了。
代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=3e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
string s;
int main(){
cppio;
cin>>s;
int n=s.length();
stack<char> sta;
for(int i=0;i<n;i++){
if(!sta.empty()){
if(sta.top()==s[i]) sta.pop();
else sta.push(s[i]);
}
else{
sta.push(s[i]);
}
}
if(sta.empty()) cout<<0;
string ss;
while(!sta.empty()){
ss+=sta.top();
sta.pop();
}
reverse(ss.begin(),ss.end());
cout<<ss;
return 0;
}F 疯狂的自我检索者
最小平均分就是未知的都是1分，最大平均分就是未知的都是5分。
答案就是：
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e3+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
int main(){
int n,m;
scanf("%d%d",&n,&m);
double sum=0;
for(int i=1;i<=n-m;i++){
double x;
scanf("%lf",&x);
sum+=x;
}
printf("%.5lf ",(sum+m*1)/n);
printf("%.5lf ",(sum+m*5)/n);
return 0;
}G 解方程
因为方程
可以写成
因为 是单调的，
也是单调的，所以f(x)就是一个单调函数，所以可以用二分来找到解。
但是要用long double，因为1e-7这个精度太高了，double没有这么高的精度。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
int main(){
// printf("%lf\n",exp(1));
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
long double l=0,r=1e9;
while(r-l>eps){
long double mid=(r+l)/2;
long double tmp=pow(mid,a)+b*log(mid);
if(tmp<c) l=mid;
else r=mid;
}
printf("%.7Lf\n",l);
return 0;
}H 神奇的字母（二）
模拟一下算一下出现次数最多的字母就好了。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e3+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
char s[maxn];
int num[maxn];
int main(){
int mx=0;
while(gets(s)){
int n=strlen(s);
if(n==0) break;
for(int i=0;i<n;i++){
num[s[i]-'a']++;
if(num[mx]<num[s[i]-'a']) mx=s[i]-'a';
}
}
printf("%c",'a'+mx);
return 0;
}I 十字爆破
先算一下二维前缀和，然后对于每个点的答案就是
也就是取一行和取一列然后去掉重复取的那个点。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
vector<ll> mp[maxn];
vector<ll> sum[maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
sum[0].resize(m+2,0);
for(int i=1;i<=n;i++){
mp[i].resize(m+20,0);
sum[i].resize(m+20,0);
for(int j=1;j<=m;j++){
scanf("%lld",&mp[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+mp[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ll summ=sum[n][j]-sum[n][j-1]+sum[i][m]-sum[i-1][m];
printf("%lld%c",summ-mp[i][j]," \n"[j==m]);
}
}
return 0;
}J 异或和之和
一般这种二进制求和的题很多都是求每一位的贡献的，这题当然也不例外了。
先算在所有数里面，每一位为1出现多少次，为0出现多少次。
然后每一位的贡献就是：
也就是：如果这一位是1，那么如果要有贡献，其他两个数要么都是1要么都是0，对于其他两个数都是0，只需要用组合数C(0的数量,2)就好，对于其他两个数都是1，我们就算3个都是1有多少种情况，也就是C(1的数量,3)。
最后把贡献加起来就好了。
代码:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;
const int maxn=1e6+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;
ll num[100][2];
ll qPow(ll a,ll b){
ll ans=1;
while(b>0){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
ll x;scanf("%lld",&x);
for(int j=0;j<62;j++){
if((1ll<<j)&x){
num[j][1]++;
}
else num[j][0]++;
}
}
ll sum=0;
for(int i=0;i<62;i++){
ll tmp=0;ll one=num[i][1],zero=num[i][0];ll k=(1ll<<i)%mod;
tmp=(tmp+k*one%mod*zero%mod*(zero-1)%mod*qPow(2,mod-2))%mod;
tmp=(tmp+k*one%mod*(one-1)%mod*(one-2)%mod*qPow(6,mod-2)%mod)%mod;
sum=(sum+tmp)%mod;
}
printf("%lld\n",sum);
return 0;
}
投递小红书等公司10个岗位
查看3道真题和解析
