江三

2020-05-22 22:12 广东金融学院 Java

关注

牛客小白月赛25 题解

一.总结

兰子姐姐的题还是比较能够让人看到希望的，但是由于 cout double 的 bug ，在F和G浪费了太多时间，还有各种细节都没注意到，都没时间做完。

本次怀疑人生：F/G/J

二.题解

A.AOE还是单体？

样例的解释明显告诉我们如何去计算，就是判断使用一次群体攻击的花费是否大于单独攻击 k 次的花费，然后我们就可以根据 x 来决定使用多少次群体攻击。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;

ll a[manx],s[manx];
// ll a[N][N];

int main(){
    io;
    ll n,x; cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
    sort(a+1,a+1+n);
    ll ans=0;
    if(x<=n){
        for(int i=n-x;i<=n;i++)
            ans+=a[i]-a[n-x];
        ans+=a[n-x]*x;
    }
    else ans=s[n];
    cout<<ans;
    return 0;
}

B.k-size字符串

~~F和G浪费太多时间导致没时间写~~ 太菜了赛后补的题

题目就是给 n 个字符 a 和 m 个字符 b，求 k size 字符。
很明显就是隔板问题，但是要注意有两种情况，一种是ab开头的类型，一种是ba开头的类型。
公式：

$ab：C(n-1,k/2-1) * C(m-1,k-k/2-1)$

$ba：C(m-1,k/2-1) * C(n-1,k-k/2-1)$

以 ab 为例子来说：

a 的话就是有 n-1 个间隔（因为有 n 个 a），然后我们可以选取 $k/2-1$ 个隔板放下去，这样就分成了 $k/2$ 份；
b 的话就是有 m-1 个间隔（因为有 m 个 b），然后我们可以选取 $(k-k/2)-1$ 个隔板放下去，这样就分成了 $(k-k/2)$ 份；

代码：

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;
const int mod=1e9+7;

ll a[70];

ll qp(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%p;
        a=a%p*a%p;
        b>>=1;
    }
    return ans%p;
}
ll Inv(ll x,ll p){return qp(x,p-2,p);}
ll Cal(ll n,ll m,ll p){
    if(m>n) return 0;
    ll ans=1;
    for(int i=1;i<=m;++i)ans=ans*Inv(i,p)%p*(n-i+1)%p;
    return ans%p;
}
int main(){
    ll n,m,k; cin>>n>>m>>k;
    if(n+m<k || k==1){
        puts("0");
        return 0;
    }
    ll ans=0;
    ans+= Cal(n-1,k/2-1,mod)*Cal(m-1,k-k/2-1,mod)%mod;
    ans%=mod;
    ans+= Cal(m-1,k/2-1,mod)*Cal(n-1,k-k/2-1,mod)%mod;
    cout<<ans%mod;
    return 0;
}

C.白魔法师

树形DP模板题，类似于没有上司的舞会。
以 $dp[u][0]$ 表示以u为根的子树没有使用魔法得到的最大白色联通块的大小， $dp[u][1]$ 表示以u为根的子树使用魔法得到的最大白色联通块的大小。
那么很明显，我们在 dfs 的时候，只要用一个变量 cnt 来记录没有使用魔法子树的白色联通块大小和，一个变量 sb 来记录使用了魔法最大的白色联通块大小，就可以得到公式:

当 $col[u]==White$ 有： $dp[u][0] = cnt+1, dp[u][1]=dp[u][0]+sb$
当 $col[u]==Black$ 有： $dp[u][0] = 0, dp[u][1]=cnt+1$

在 dfs 的过程中 ans 取 max 就好了。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;
const int mod=1e9+7;

vector<ll>g[manx];
ll n,ans;
ll col[manx],dp[manx][4];
string s;

void dfs(ll u,ll pre){
    dp[u][0]=col[u];
    ll sb=-1e18,cnt=0;
    for(auto v:g[u]){
        if(v==pre) continue;
        dfs(v,u);
        cnt+=dp[v][0];
        sb=max(sb,dp[v][1]-dp[v][0]);
    }
    if(col[u]) dp[u][0]=cnt+1,dp[u][1]=dp[u][0]+sb;
    else dp[u][1]=cnt+1;
    ans=max(dp[u][1],ans);
    ans=max(dp[u][0],ans);
}

int main(){
    cin>>n; cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++)
        if(s[i]=='W') col[i]=1;
    for(int i=2;i<=n;i++){
        ll u,v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

D.抽卡

概率数学题，算出不可能的概率，再用 1 减去就可以了。
注意减的时候可能出现负数，所以需要加个 mod 再取模。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;
const int mod=1000000007;

ll a[manx],b[manx];

ll qp(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%p;
        a=a%p*a%p;
        b>>=1;
    }
    return ans%p;
}
int main(){
    io;
    ll n; cin>>n;
    ll ans=1;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        cin>>b[i];
        ll x=(a[i]-b[i])*qp(a[i],mod-2,mod)%mod;
        ans=ans*x%mod;
    }
    cout<<(1-ans+mod)%mod;
    return 0;
}

E.点击消除

用栈模拟字符串匹配的过程，如果遇到相同的就把连续两个弹出去~

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;

char s[manx];
// ll a[N][N];

int main(){
    io;
    char c; ll top=0;
    while(cin>>c){
        s[++top]=c;
        if(top>=2&&s[top-1]==s[top]){
          //  cout<<top<<" "<<s[top]<<" "<<c<<endl;
            top-=2;
            continue;
        }
    }
    if(!top) cout<<0;
    else
        for(int i=1;i<=top;i++)
            cout<<s[i];
    return 0;
}

F.疯狂的自我检索者

怀疑人生第一题。

最小情况就是剩余m个人都给1分，最大情况就是剩余m个人都给5分。

但是注意坑点！！！取消了同步就不能用 puts和print 不然就会 wa ！！老是忘记这个坑点，浪费了许久。

代码：

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;

double a[manx];
// ll a[N][N];

int main(){
   // io;
    ll n; cin>>n;
    ll m; cin>>m;
    double ans=0;
    for(int i=1;i<=n-m;i++) cin>>a[i],ans+=a[i];
    double mi=ans+m*1.0,ma=ans+m*5.0;
    printf("%.5lf %.5lf",mi/n,ma/n);
    return 0;
}

G.解方程

怀疑人生第二题。

模板小数二分，就是判断二分的 mid 代入方程后是否比 c 大，本来代码是可以通过的，但是我用cout输出就一直wa，直到后来换成了print，好像在这题直接白给一个小时(20.13~21.21)?

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;
const int mod=1000000007;

ll a,b,c;
ll pd(double x){
    double ans=1.0;
    for(int i=1;i<=a;i++) ans*=x;
    ans+=b*1.0*log(x);
    return (ans-c)>(1e-7);
}

int main(){
   // io;
    cin>>a>>b>>c;
    double l=1.0,r=1e9;
    for(int i=1;i<=100;i++){
        double mid=(r+l)/2;
        if(pd(mid)) r=mid;
        else l=mid;
    }
    printf("%.8lf",l);
    return 0;
}

H.神奇的字母（二）

可以桶排，也可以 map 记录。

代码：

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;

ll a[manx];
// ll a[N][N];
map<char,ll>v;

int main(){
    io;
    char c,sb; ll ans=0;
    while(cin>>c){
        if(c>='a'&&c<='z') v[c]++;
        if(v[c]>ans) ans=v[c],sb=c;
    }
    cout<<sb;
    return 0;
}

I.十字爆破

好像做过很多次这种题目了。

每个点为列贡献+行贡献-本点贡献
由于n*m<1e6，所以可以开出2维数组，但是不能直接开 $a[1e6][1e6]$ ,要开成 $a[n+1][m+1]$ 。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;

// ll a[N][N];

int main(){
    io;
    ll n,m; cin>>n>>m;
    ll a[n+1][m+1],b[n+1],c[m+1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=b[i]=c[j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j],b[i]+=a[i][j],c[j]+=a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<b[i]+c[j]-a[i][j]<<" ";
        }
        cout<<endl;
    }

    return 0;
}

J.异或和之和

..怀疑人生第三题，wa 了10次，赛后才发现 $(1<<i)$ 在超出 int 的范围会变成0，应该写成 $(1ll<<i)$ 。

二进制的题目一般都是按位算贡献，在这道题我们可以通过计算 64 个二进制位出现的次数，然后用组合数学来计算对答案的贡献：

因为只有出现奇数次才会对答案有贡献，出现偶数次的话会抵消异或成 0 ，所以我们只考虑选取的 3 个数中在这个位为 1 的个数为 1 或者 3 的情况。
当该位出现次数大于等于1，设为 x，则有 $(n-x)$ 个数在这个二进制上为 0 ，所以对答案的贡献为： $x*C(n-x,2)$ ;
当该位出现次数大于等于3，设为 x，所以对答案的贡献为： $C(x,3)$ ;

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;
const int mod=1e9+7;

ll a[70];

ll qp(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%p;
        a=a%p*a%p;
        b>>=1;
    }
    return ans%p;
}
ll Inv(ll x,ll p){return qp(x,p-2,p);}
ll Cal(ll n,ll m,ll p){
    if(m>n) return 0;
    ll ans=1;
    for(int i=1;i<=m;++i)ans=ans*Inv(i,p)%p*(n-i+1)%p;
    return ans%p;
}
int main(){
    io;
    ll n; cin>>n; ll ma=0;
    for(int i=1;i<=n;i++){
        ll x; cin>>x; ma=max(ma,x);
        for(int j=0;j<=64;j++){
            ll sb=(1ll<<j);
            if(sb>x) break;
            if(sb&x) a[j]++;
        }
    }
    ll ans=0;
    for(int i=0;i<=64;i++){
        if(!a[i]) continue;
        ll x=(1ll<<i);
        if(x>ma) break;
        x%=mod;
        if(n-a[i]>=2&&a[i]>=1) ans=(ans+a[i]%mod*Cal(n-a[i],2,mod)%mod*x%mod)%mod;
        if(a[i]>=3)ans=(ans+Cal(a[i],3,mod)%mod*x%mod)%mod;
        //cout<<i<<" "<<ans<<endl;
    }
    cout<<ans%mod;
    return 0;
}