2020-05-19 18:12 贺州学院软件测试

关注

牛客小白月赛25

A题

这是一个贪心的题，需要注意两个点：

1、当x大于等于n时，若是要用蛮牛践踏，mp达不到最小。即使只用一次，mp还是很大的，因此这种情况只能都用蛮牛冲撞。

2、当x小于n，先用num[x-n] * x的蛮牛践踏，再加上num[x-n]后面的蛮牛冲撞。

代码：

#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
int num[N];
int main()
{
    ll n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        cin>>num[i];
    if(x>=n)
    {
        ll sum=0;
        for(int i=1;i<=n;i++)
            sum+=num[i];
        printf("%lld\n",sum);
        return 0;
    }
    sort(num+1,num+n+1);
    ll sum=num[n-x]*x;
    for(int i=(n-x)+1;i<=n;i++)
        sum+=num[i]-num[n-x];
    printf("%lld\n",sum);
    return 0;
}

C题
这题我是用两种不同的方法写的，但是大致的思路是一样的。

第一种——并查集

如果有对并查集不怎么懂的，可以去查一下百度，这里不作解释了（我绝对不是因为不知道怎么解释，才不说的）

首先用并查集找出所有的白区域域，然后再利用for循环遍历字符串str，如果碰到黑色的，就去判断加上该黑色的点和与黑色相连的白色点。如果是白色的，就看该白色的区域是不是最大的。

代码：

#include
using namespace std;
const int N= 1e6+10;
int cnt[N],fa[N];
char str[N];
vector node[N];
int father(int x)//寻找父节点 
{
    return x==fa[x]? x:fa[x]=father(fa[x]);
}
void unionn(int x,int y)
{
    int fx=father(x);
    int fy=father(y);
    if(fx!=fy)
    {
        fa[fx]=fy;
        cnt[fy]+=cnt[fx];//是以边加上根节点的值，因为是白色的边上有黑色的点，不是白色的根上有，这样做可以更好的判断最大值。 
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    cin>>str+1;
    for(int i=1;i<=n;i++)
        fa[i]=i,cnt[i]=1;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        node[x].push_back(y);
        node[y].push_back(x);
        if(str[x]=='W'&&str[y]=='W') unionn(x,y);//如果两点都是白色的区域，就把它们连接成一片区域 
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(str[i]=='W') res=max(res,cnt[father(i)]);
        else
        {
            int wi=1;
            for(int j=0;j<node[i].size();j++)
                if(str[node[i][j]]=='W') wi+=cnt[father(node[i][j])];//寻找黑点周围的白点区域 
            res=max(wi,res);
        }
    }
    cout<<res<<endl;
    return 0;
}

第二种

先找出这些边对应的根节点，然后在根节点上加上这些边的数量。以fa数组代表这些边所对应的根节点是什么，以cnt数组代表根节点上与它相连的白色边的数量。

我不知道我写得是否很看得懂，来个例子：

假设有这样的字符串BWWWWWWB

与之对应的fa数组和cnt数组为：

图片说明

代码：

#include
using namespace std;
const int N= 1e6+10;
int cnt[N],fa[N],pi[N];
char str[N];
vector node[N];
void find(int er,int fat,int root)
{
    if(fa[er]) return;//若改边被找过就退出 
    fa[er]=root;//er边的根节点root 
    cnt[root]++;//根节点root的数量 
    for(int i=0;i<node[er].size();i++)
    {
        if(str[node[er][i]]=='W'&&er!=fat)
        {
            find(node[er][i],er,root);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    cin>>str+1;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        node[x].push_back(y);
        node[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==0&&str[i]=='W')
        {
            find(i,0,i);
        }
    }
/*    printf("fa数组为：\n");
    for(int i=1;i<=n;i++)
        printf("%d ",fa[i]);printf("\n");
    printf("cnt数组为：\n");
    for(int i=1;i<=n;i++)
        printf("%d ",cnt[i]);printf("\n");*/
    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(str[i]=='W') res=max(res,cnt[fa[i]]);
        else
        {
            int wi=1;
            for(int j=0;j<node[i].size();j++)
                if(str[node[i][j]]=='W') wi+=cnt[fa[node[i][j]]];
            res=max(res,wi);
        }
    }
    cout<<res<<endl;
    return 0;
}

E题

有两种方法，一种是用STL中的stack，一种是枚举。

第一种——stack

额，本人不才，不知道怎么表述。

举个栗子：

假设我们有bfggfdd,这样的字符串str，用for循环将str装进stack中，

图片说明

如果将要装进的字符和栈中的一样，那就不装该字符并将栈中的这个删除。最后反向遍历，就好了。

代码：

#include
using namespace std;
stack  st;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    string s;
    cin>>s;
    int len=s.length();
    for(int i=0;i<len;i++)
    {
        if(st.empty())
        {
            st.push(s[i]);
        }
        else
        {
            char c=st.top();
            if(c==s[i]) st.pop();
            else st.push(s[i]);
        }
    }
    if(st.empty()) 
        printf("0\n");
    else
    {
        string res;
        while(!st.empty())
        {
            res+=st.top();
            st.pop();
        }
        int len=res.length();
        for(int i=len-1;i>=0;i--)
            cout<<res[i];
    }
    return 0;
}

第二种——枚举

这也有一个栗子，如果我们有这样的字符串str：bfggfdd
用for循环，遍历它们，当碰到s[i]==s[i+1]时，就进入cheak（）判断当这两个字符消去时剩下的字符串是不是还有相同的，如果没有了，返回寻找相同字符的前面的哪一个下标。

代码：

#include
using namespace std;
const int N=300000+10;
int p[N]; 
string s;
int cheak(int sta,int n)
{
    int L=sta,R=sta+1,t=0;
    while(L>=0&&R<=n&&s[L]==s[R])
    {
        p[L]=0;p[R]=0;
        while(!p[L])
            L--;
        R++;
    }
    p[L]=1,p[R]=1;
    return R;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int len;
    cin>>s;
    len=s.length();
    for(int i=0;i<len;i++)
    {
        if(s[i]!=s[i+1]) p[i]=1;
        else
        {
            i=cheak(i,len-1)-1;
        }
    }
    int t=0;
    for(int i=0;i<len;i++)
        if(p[i]) t=1,cout<<s[i];
    if(t==0) cout<<'0';
    return 0;
}

F题

取极限，对于最小隐藏的数都取1，对于最大隐藏的数都取5

代码：

#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll num[N];
int main()
{
    ll n,m;
    double x,y;
    cin>>n>>m;
    if(n==m)
    {
        x=1,y=5;
        printf("%.5lf %.5lf\n",x,y);
    }
    else
    {
        int a;
        double sum=0,xi,yi;
        for(int i=1;i<=n-m;i++)
        {
            cin>>a;
            sum+=a;
        } 
        xi=sum,yi=sum;
        for(int i=0;i<m;i++)
            xi+=1,yi+=5;
        xi/=(n),yi=yi/(n);
        printf("%.5lf %.5lf\n",xi,yi);
    }
    return 0;
}

G题

设
$图片说明$

由此可以知道F(i)是一个增函数，不知道的同学可以画画图，就知道了。因此可以有两种方法来求解这题，一个二分，一个三分。
从中找到一个i能够等于c。

第一种 —— 二分

我这里的二分是用递归的。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
ld a,b,c;

ld split(ld L,ld R)
{
    if((R-L)<=1e-8) return L;
    ld mid=(L+R)/2;
    ld res=pow(mid,a)+b*log(mid);
    if(res<c) return split(mid,R);//如果res<c，说明res应该还要大点，才能等于c，因此往中间值向上找 
    return split(L,mid);//反之，就往下找。 
}

int main()
{
    cin>>a>>b>>c;
    printf("%.7Lf\n",split(1,c));
    return 0;
}

第二种 —— 三分

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
ld a,b,c;

bool F(ld i)
{
    return pow(i,a)+b*log(i)<c;
}

int main()
{
    ld t=0,L=1,R=1e9,L_mid,R_mid;
    cin>>a>>b>>c;

    while((R-L)>1e-8)
    {
        t++;
        L_mid=(L+R)/2,R_mid=(L_mid+R)/2;
        if(t>1000) break;
         if(F(L_mid)) L=L_mid;
         else R=R_mid;
    }

    printf("%.7Lf\n",L_mid);
    return 0;
}

I题

这题也有两种解法（本人不才，只找到两种）。一种是用STL中vector，一种是对数组的下标进行操作。

第一种——vector

向量 vector 是一种对象实体, 能够容纳许多其他类型相同的元素, 因此又被称为容器。与string相同, vector 同属于STL(Standard Template Library, 标准模板库)中的一种自定义的数据类型, 可以广义上认为是数组的增强版。

在使用它时, 需要包含头文vector ,#include < vector>

容器与数组相比其优点在于它能够根据需要随时自动调整自身的大小以便容下所要放入的元素。

（更详细的，查一下百度）

代码：

#include
using namespace std;
const int N=1e6+10;
long long x[N],y[N];
vector num[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int a;
            cin>>a;
            num[i].push_back(a);
            x[i]+=a;
            y[j]+=a;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cout<<x[i]+y[j]-num[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

第二种

我在刚刚学二维数组的时候，我们的老师说过二维数组实际就是一维数组。

因此就用一维数组来保存这些数。
那么i/m就是行标
i%m就是列标。

代码：

#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll x[N],y[N];
ll num[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<(m*n);i++)
        cin>>num[i];
    for(int i=0;i<(m*n);i++)
    {
        x[i/m]+=num[i];
        y[i%m]+=num[i];
    }
    for(int i=0;i<(m*n);i++)
    {
        cout<<x[i/m]+y[i%m]-num[i]<<' ';
        if((i+1)%m==0) cout<<endl;
    }
    return 0;
}