牛客小白月赛25 补题+题解[A-J]

加油加油加油！

文章目录

- A.AOE还是单体？
- B.k-size字符串
- C.白魔法师
- D.抽卡
- E.点击消除
- F.疯狂的自我检索者
- G.解方程
- H.神奇的字母（二）
- I.十字爆破
- J.异或和之和

A.AOE还是单体？

思路：这题数据范围2e5，如果想暴力的话，会果断超时这毋庸置疑，正解应该是贪心，对于怎样选择使用技能，选择方法：当剩余怪物的个数大于或等于x时，我们选择AOC伤害，如果小于，也就是说还不如我一滴血一滴血的去打怪物划算，就选择单体伤害了。
我们可以通过排序解决这个问题，找出使用多少次AOE伤害后剩下x个怪物，之后把这x个怪物的血量加起来即可。
要有特判一次也不使用AOE伤害的情况

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 300010;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;ll a[maxn];int main()
{ll n,x;ll ans=0;ll cnt=0;cin>>n>>x;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);cnt+=a[i];}sort(a+1,a+n+1);if(n-x+1<=0){cout<<cnt<<endl;return 0;}ans=a[n-x+1]*x;for(int i=n-x+1;i<=n;i++){ans+=a[i]-a[n-x+1];}cout<<ans<<endl;return 0;
}

B.k-size字符串

（这里采用出题人的官方解释，写的十分详细）

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;ll pre[maxn];
ll power(ll a,ll b,ll c) {ll ans=1;a = a%c;while(b) {if(b&1)ans=ans*a%c;a=a*a%c;b=b>>1;}return ans;
}
ll c(ll a, ll b) {if (b>a) return 0;ll ans=pre[a]*power(pre[b]*pre[a-b]%mod,mod-2,mod)%mod;return ans;
}
void init() {pre[0]=1;for (int i=1;i<maxn;i++)pre[i]=pre[i-1]*i%mod;
}
int main() {init();ll n,m,k;cin >>n>>m>>k;if (n<m) swap(n,m);if (k==1||k>n+m)cout<<0<<endl;else{ll ans=0;for (int i=1;i<=n;i++) {int j=k-i;if (j<=0) continue;ll x=c(n-1,i-1),y=c(m-1,j-1);if (j==i-1||j==i+1) {ans=(ans+x%mod*y%mod)%mod;}else if (j==i){ans=(ans+2*x%mod*y%mod)%mod;}}cout<<ans<<endl;}return 0;
}

C.白魔法师

题解：这个题我们可以先通过并查集把联通的白块给合并起来，并且实时更新一个区域白块数量的最大值（只记录在根节点位置），然后我们在找出黑块的位置，并且查找他周围白块的数量（数量不要忘记加上当前黑块的数量，也就是1），因为一个区域的白块最大值只记录在父节点的位置上，所以我们需要找到父节点的位置再加数量

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;
char s[maxn];
vector <vector<int> >maps;
int a[maxn],f[maxn];int ifind(int x){if(f[x]==x) return x;return f[x]=ifind(f[x]);
}
void mer(int x,int y){int dx=ifind(x);int dy=ifind(y);if(dx!=dy){f[dx]=dy;a[dy]+=a[dx];}
}
int main()
{int n;cin>>n;scanf("%s",s+1);maps.resize(maxn);for(int i=0;i<maxn;i++) f[i]=i,a[i]=1;for(int i=0;i<n-1;i++){int x,y;scanf("%d%d",&x,&y);maps[x].push_back(y);maps[y].push_back(x);if(s[x]=='W'&&s[y]=='W'){mer(x,y);} //}int imax=0;for(int i=1;i<=n;i++){if(s[i]=='W') imax=max(imax,a[ifind(i)]);}for(int i=1;i<=n;i++){int ans=1;if(s[i]=='B'){for(int j=0;j<maps[i].size();j++)if(s[maps[i][j]]=='W') ans+=a[ifind(maps[i][j])];imax=max(imax,ans);}}cout<<imax<<endl;return 0;
}

D.抽卡

QAQ这个题主要考察的知识点是逆元的知识点（虽然之前做过逆元的题目，但是这次完全没想到用这个方法，甚至自己傻乎乎的在想最大公约数）
题解：这个题主要考的逆元的知识，它可以把分数当成整数来进行运算，这个题我们可以先求出怎么抽也抽不中的概率，然后用一减去这个概率即可。

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;ll a[maxn],b[maxn];
ll qp(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}int main()
{int n;cin>>n;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<n;i++) cin>>b[i];ll ans=1;for(int i=0;i<n;i++){ans=ans*(a[i]-b[i])%mod*qp(a[i],mod-2)%mod;}ans=(mod+(1-ans))%mod;cout<<ans<<endl;return 0;
}

E.点击消除

题解：这个题主要是考察了栈的运用，可以用数组模拟一下栈。

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 300010;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;char str[maxn],ans[maxn];
int main()
{int i,len,j;scanf("%s",str);len=strlen(str);ans[0]=str[0];j=1;for(i=1;i<len;i++){ans[j]=str[i];                        //进栈if(j>=1&&ans[j]==ans[j-1])            //出栈j-=2;j++;}ans[j]='\0';if(j==0) printf("0");else{cout<<ans<<endl;}return 0;
}

F.疯狂的自我检索者

题解：把已知的数全都加起来，再把未知的分别假设为1和5即可

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 300010;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;int main()
{int n,m;cin>>n>>m;double x=0,t;for(int i=0;i<n-m;i++){scanf("%lf",&t);x+=t;}double imax=(x+5*m)/n;double imin=(x+m)/n;printf("%.5f %.5f",imin,imax);return 0;}

G.解方程

题解：这个题方程其实是一个具有单调性的方程（我也不知道怎么证明，用了Mathematic画了一下这个图像，有了神奇的发现），所以二分就行，这里说误差小于1e-7所以二分的精确值我直接设到了1e-8

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;
double a,b,c;
bool che(double x){if(pow(x,a)+b*log(x)>=c){return true;}else return false;
}
int main()
{cin>>a>>b>>c;double l=0, r=1e9;double mid;double ans=0;while(r-l>1e-8){mid=(l+r)/2.0;if(che(mid)){ans=mid;r=mid-1e-7;}else l=mid+1e-7;}printf("%.14f",ans);return 0;
}

H.神奇的字母（二）

题解：用while不断输入，设置一个数组记录每个字母出现的次数

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 300010;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;string s;
int a[100];
int main()
{while(cin>>s){for(int i=0;i<s.size();i++){a[s[i]-'a']++;}}char x;int imin=0;for(int i=0;i<26;i++){if(imin<a[i]){imin=a[i];x=i+'a';}}cout<<x<<endl;return 0;}

I.十字爆破

题解：因为没有明确的给出m和n的范围，所以我们开一个一维数组当二维数组用就行，（即切分开）a[i*m+j]代表a[i][j]
然后预处理行和列最后相加即可

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 1e6+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;ll x[maxn];
ll hang[maxn];
ll lie[maxn];
ll a[maxn];
int main()
{int n,m;int cnt=1;ll ans=0;cin>>n>>m;for(int i=1;i<=n*m;i++){scanf("%lld",&x[i]);ans+=x[i];lie[i-(cnt-1)*m]+=x[i];if(i%m==0){hang[cnt++]=ans;ans=0;}}for(int i=1;i<=n;i++){for(int f=1;f<=m;f++){printf("%lld ",hang[i]+lie[f]-x[(i-1)*m+f]);
//            cout<<"hang"<<hang[i]<<endl;
//            cout<<"lie"<<lie[f]<<endl;}printf("\n");}return 0;}

J.异或和之和

比赛的时候只想到可能会与二进制每个位0和1的个数有关，其他的确实没想到
题解：如果某位异或和为1 那只有两种情况
一种 1 1 1 另一种1 0 0
我们用高中所学过的组合公式即可

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;
ll a[100];int main()
{ll n,m;cin>>n;for(int i=0;i<n;i++){scanf("%lld",&m);for(int j=0;j<64;j++){a[j]+=((m>>j)&1);}}ll sum=0;for(int i=0;i<64;i++){sum+=(1ll<<i)%mod*(a[i]*(a[i]-1)*(a[i]-2)/6%mod)%mod;sum+=(1ll<<i)%mod*(a[i]*(n-a[i])*(n-a[i]-1)/2%mod)%mod;sum%=mod;}cout<<sum<<endl;return 0;
}