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

news/2024/7/5 2:16:08

加油加油加油！

文章目录

    • 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;
}

萌新一枚，欢迎各位巨佬指出不足。


http://lihuaxi.xjx100.cn/news/285922.html

相关文章

Python | 一万多条拼车数据，看春运的迁徙图

Python | 一万多条拼车数据，看春运的迁徙图

作者 | 白苏&#xff0c;医疗健康领域产品经理一枚&#xff0c;Python&R爱好者来源 | InThirty编辑 | Jane今天是腊月二十八&#xff0c;你们都到家了吗&#xff1f;这篇文章&#xff0c;作者对北京、上海、广州、深圳、杭州等地 1万多条出行数据进行分析&#xff0c;得出了…
阅读更多...
Unity3d多线程

Unity3d多线程

为什么80%的码农都做不了架构师&#xff1f;>>> &#xff08;一&#xff09;多线程的创建 Thread t new Thread(new ThreadStart(Go)); Thread t1 new Thread(Go); 两种创建方式没有区别&#xff1b; &#xff08;二&#xff09;多线程的状态控制和优先级 多线程…
阅读更多...
第1关：利用栈实现整数的十进制转八进制

第1关：利用栈实现整数的十进制转八进制

#ifndef stack__h #define stack__h#include <stdio.h> #include <stdlib.h>typedef int T; // 数据元素的数据类型struct Stack{T* data; // 数据元素存储空间的开始地址int top; // 栈顶的位置int max; // 栈的最大长度 };Stack* Stack_Create(int maxlen)…
阅读更多...
数据可视化[python-pyecharts]制作中国各省份近三个月新型冠状病毒肺炎变化图

数据可视化[python-pyecharts]制作中国各省份近三个月新型冠状病毒肺炎变化图

大体思路&#xff1a; 通过pyecharts等库一个for循环批量绘制近几个月每天的图&#xff0c;最后通过pr将图片合成 先看一下某一天的样图&#xff0c;用pr组合起来之后就是个动态的了 文章目录安装pyecharts库数据来源代码部分1.导入库2.将路径中所有文件找出保存至列表3.处理导…
阅读更多...
树上启发式合并问题 ---- 2019icpc南昌 K. Tree （树上启发式合并 + 动态开点线段树)

树上启发式合并问题 ---- 2019icpc南昌 K. Tree （树上启发式合并 + 动态开点线段树)

题目链接 题目大意&#xff1a; 就是给你一颗树&#xff0c;每个点有个权值viv_ivi​&#xff0c;问你有多少对(x,y)(x,y)(x,y)满足&#xff1a; xxx不是yyy的祖先yyy也不是xxx的祖先xxx和yyy的距离不超过kkkxxx和yyy最近公共祖先&#xff1a;zzz,满足vxvy2vzv_xv_y2v_zvx​vy…
阅读更多...
程序员最常说的9句话，精准！

程序员最常说的9句话，精准！

1、别更新了学不动了。2、我不会修电脑&#xff0c;谢谢。3、听说今晚不用加班。4、是你的网络有问题。5、清一下缓存再试试6、扫码提需求&#xff0c;谢谢。7、换一台设备试试看。8、保证今晚十点上线。9、键盘给你&#xff0c;你来写。IT程序猿 微博网友评论&#xff1a;猫儿…
阅读更多...
为何Google将几十亿行源代码放在一个仓库？

为何Google将几十亿行源代码放在一个仓库？

作者 | Rachel Potvin&#xff0c;Josh Levenberg 译者 | 张建军 编辑 | apddd 【AI科技大本营导读】与大多数开发者的想象不同&#xff0c;Google只有一个代码仓库——全公司使用不同语言编写的超过10亿文件&#xff0c;近百TB源代码都存放在自行开发的版本管理系统Piper中&…
阅读更多...
7个Debug linux程序的Strace 列子

7个Debug linux程序的Strace 列子

Strace是一个能帮助你解决问题的debugging工具 Strace监控指定程序系统调用和信号&#xff0c;在你没有源代码又想dubug程序的执行时是会用到的。Strace会以程序的开始到结束来顺序执行的 你可以从这个7个Strace 例子开始起步了解Strace 1.跟踪可执行程序的执行 你可以使用stra…
阅读更多...
最新文章

Copyright @ 2022~2023