牛客小白月赛25 （C 换根 D 概率 G 二分 J 异或操作）

题目链接

前言

一天打了四场，（

10:30-12:00 leetcode 

13：00-18：00 厦门大学月赛 

17：20-19：20 codeforces

19：00-22：00 牛客小白月赛）

脑子有点跟不上了，E题单调栈啊却没想到，G题二分写wa了。。

 

C-白魔法师

思路：换根dp，设dp[i]为 i这个节点为白色时的最大白色联通块，然后随便换根一下就好了

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
 
inline ll read()
{
    ll x=0,w=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
    return w==1?x:-x;
}
const int N=1e5+10;
int dp[N],n,ans,a[N];
vector<int>G[N];
char s[N];
void dfs1(int u,int fa)
{
    if(a[u]) dp[u]=1;
    for(int v:G[u]){
        if(v==fa) continue;
        dfs1(v,u);
        if(a[v]) dp[u]+=dp[v];
    }
}
void dfs2(int u,int fa)
{
    //printf("u:%d dp:%d\n",u,dp[u]);
    if(a[u]) ans=max(ans,dp[u]);
    else ans=max(ans,dp[u]+1);
    for(int v:G[u]){
        if(v==fa) continue;
        int t=0;
        if(a[v]) t=dp[u]-dp[v];
        else t=dp[u];
        //printf("u:%d v:%d t:%d\n",u,v,t);
 
        if(a[u]) dp[v]+=t;
        dfs2(v,u);
    }
}
int main()
{
    cin>>n;
    scanf("%s",s+1);
    rep(i,1,n) if(s[i]=='W') a[i]=1;
    for(int i=2;i<=n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1,-1);
    //rep(i,1,n) printf("i:%d dp:%d\n",i,dp[i]);
 
    dfs2(1,-1);
    printf("%d\n",ans);
}

D-抽卡

做法：1-没有卡的概率，水吧

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll powmod(ll a,ll b) {ll res=1;a%=mod;
assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int N=1e5+10;
ll a[N],b[N];
int n;
void solve()
{
    scanf("%d",&n);
    rep(i,1,n) scanf("%lld",&a[i]);
    rep(i,1,n) scanf("%lld",&b[i]);
 
    ll ans=1;
    rep(i,1,n)
    {
        ll fz=a[i]-b[i];
        ll fm=a[i];
        ans=ans*fz%mod*powmod(fm,mod-2)%mod;
    }
    ans=(1-ans+mod)%mod;
    cout<<ans<<endl;
 
 
}
int main()
{
 
    //int _;cin>>_;while(_--)
    solve();
}

G-解方程

贴一个学习long double类型二分的板子吧，跟我的板子完全不一样，可能是我板子姿势不对吧

#include<bits/stdc++.h>
using namespace std;
#define ld long double
const ld esp=1e18;
int a;
ld b,c;
ld bs(ld l,ld r){
    if(r-l<=esp)return l;
    while(l<r-esp){
        ld mid=(r+l)/2;
        ld res=1;
        for(int i=0;i<a;i++)res*=mid;
        res+=b*log(mid);
        if(res<c)l=mid;
        else r=mid;
    }
    return l;

}
int main(){
    cin>>a>>b>>c;
    printf("%.7Lf",bs(1,c));
}

J-异或和之和

经典题了，牛客+cf出的次数不低于三次了。题解写了好多类似的了。就不详细写了。

牛客类似题：博客B题

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const int N=2e5+10;
const ll mod=1e9+7;
ll a[N],n;
ll vis[70],f[N],fac[70],inv[N];
void cal(ll x)
{
    for(int i=0;i<=63;++i){
        if(x&1) vis[i]++;
        x>>=1;
    }
}
void add(ll &x,ll y)
{
    x=(x+y)%mod;
}
ll getC(ll n,ll m)
{
    if(m>n) return 0;
    return f[n]*inv[n-m]%mod*inv[m]%mod;
}
void init()
{
    f[0]=1;inv[0]=inv[1]=1;
    for(int i=1;i<N;++i) f[i]=f[i-1]*i%mod;
    ///2的次方逆元
    for(int i=2;i<N;i++)///逆元的预处理
        inv[i]=ll(mod-mod/i)*inv[mod%i]%mod;

    for(int i=1;i<N;i++)///阶乘的逆元预处理
        inv[i]=inv[i-1]*inv[i]%mod;
}

int main()
{
//    printf("%d\n",0^0^1);
//    printf("%d\n",0^1^1);
//    printf("%d\n",1^1^1);
//    printf("%d\n",0^0^0);
    init();
    fac[0]=1;
    for(int i=1;i<=63;++i) fac[i]=fac[i-1]*2%mod;


    n=read();
    rep(i,1,n){a[i]=read();cal(a[i]);}


    ll ans=0;
    for(int i=0;i<=63;++i){
        add(ans,getC(vis[i],3)*fac[i]%mod);
        add(ans,getC(n-vis[i],2)*vis[i]%mod*fac[i]%mod);
    }

    printf("%lld\n",ans);

}