2020-03-22 00:33 字节跳动_客户端_iOS开发

关注

牛客小白月赛23解题报告

J.最大的差

题意：
给 $n$ 个数，找这 $n$ 个数其中两个数的最大差
题解：
签到题，排序一下最后一个减第一个

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    cout<<a[n-1]-a[0]<<endl;
    return 0;
}

E.A+B问题

题意：
给你一个值 $c$ ，让你找到在电脑编程运算中，有多少种在 $int$ 范围内的两个数的和等于 $c$
题解：
在电脑运算中，如果数位溢出 $int$ ，输出的结果依然会是一个 $int$ 内的数（即这个数去除溢出的位数的结果），所以不管c是多少，对于每个int内的数，都有一个数和他的和等于c，所以 $int$ 一共 $（1ll<<32）$ 个数，直接输出就行了

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=5e3+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cout<<(1ll<<32);
    return 0;
}

I.寻找子串

题意：
给一个字符串，找到最大字典序的子串
题解： $O(n^2)$ 直接暴力每次枚举每种字符串就可以

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=5e3+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    string s;
    cin>>s;
    int n=s.length();
    string ans;
    ans+='a';
    for(int i=0;i<n;i++){
        string t;
        t+=s[i];
        ans=max(ans,t);
        for(int j=i+1;j<n;j++){
            t+=s[j];
            ans=max(ans,t);
        }
    }
    cout<<ans<<endl;
    return 0;
}

B.阶乘

题意：
给一个正整数 $p$ ，求最小正整数 $n$
使得 $~n!~$ 是 $~p~$ 的倍数
题解：
首先分解质因子，如果某个质因子不只一个，就枚举该因子的倍数，看哪一个倍数的因子大于等于这个数，将他存下；
如果质因子只有一个，就可以直接存下。
然后将这些数取最大值，就是答案。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=5e3+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int p;
        cin>>p;
        map<int,int> m;
        int i;
        for(i=2;i<=sqrt(p);i++){
            while(p%i==0){
                m[i]++;
                p/=i;
            }
        }
        if(p>1)m[p]++;
        int ans=1;
        for(auto i:m){
            int a=i.fi,b=i.se;
            int tmp=0;
            while(b>0){
                tmp+=a;
                int x=tmp;
                while(x%a==0)x/=a,b--;
            }
            ans=max(tmp,ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

G.树上求和

题意：
有一棵包含 $n$ 个点， $n-1$ 条边的树
让你为每条边给定一个 $0~-n-1$ 的值
使得 $∀u∀v\sum.w(u,v)$ 最小

$w(u,v)$ 代表从u到v的简单路径中边权的和
题解：
由于 $n<=1e5$ ，所以不能暴力查找
所以我们分析每条边被计算的次数
对于每一条边，我们可以将这个边分成左边区域和右边区域，因为每两个点都会被计算一次，所以这个边的计算次数就是左边的点数乘上右边的点数，然后将这个值进行排序，计算次数多的赋小值。
然后说计算点数的方法：
先 $DFS$ 从结点 $1$ 开始搜索一遍，对于每个结点计算他有多少子结点。
然后再用一次 $DFS$ 分析每条边，同样是从结点1开始搜索，对于他的子结点所对应的那一边区域的点数就是刚才计算的这个子节点的子节点数，父亲结点所对应的那一边区域的点数n-这个子结点的子结点数（即刚才计算了的结点）
然后每次向下搜索的时候更新每次的子结点的值为n，最后就可以按找上面说的方法进行赋值计算了。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

ll dp[maxn];
vector<int> g[maxn];
vector<ll> vec;
void dfs(int u,int fa){
    dp[u]=1;
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u]+=dp[v];
    }
}
void dfs1(int u,int fa){
    for(auto v:g[u]){
        if(v==fa)continue;
        vec.pb((dp[u]-dp[v])*dp[v]);
        dp[v]=dp[u];
        dfs1(v,u);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,0);
    dfs1(1,0);
    ll ans=0;
    sort(all(vec));
    for(ll i=0;i<vec.size();i++){
        ans+=(n-i-1)*vec[i];
    }
    cout<<ans;
    return 0;
}

C.完全图

题意：
给一个包含 $n$ 个点的完全图，删去 $m$ 条边
最多可以分成几个连通分量
题解：
首先贪心一下，删边的时候的最大情况就是每次删出来一个点成为独立点，每个点连了 $n-1$ 条边，删去之后该完全图变成了一个包含 $n-1$ 个点的完全图，然后不断循环这个操作
所以每次删边的数量就是$ $n-1+n-2+......+n-i>=m$ $然后找到$ i $的最小值，然后$ (i+1) $就是最后的答案由于$ n,m<=1e18 $数据相当大，不能循环遍历所以采用二分，但是这样的操作可能会导致爆$ longlong $刚好牛客支持__int128所以就可以用一下防止爆其实也可以不用，因为这个值只是刚好超出m，但是要确保二分的值能够到达m，计算一下二分的右边界就可以了，这样只用$ longlong$也可以得出答案

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){

        ll n,m;
        cin>>n>>m;
        ll l=1,r=n,ans=0;
        while(l<=r)
        {
            __int128 mid=l+r>>1;
            __int128 x=(mid-1)*n-mid*(mid-1)/2;
            if(x<=m) ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

H.奇怪的背包问题增加了

题意：
一个背包的容量为 $2^{30}$
给你 $m$ 个数 $k_i$ ，代表m个物品，每个物品的体积 $c_i=2^{k_i}$
问是否能恰好装满，如果恰好装满需要用哪几件物品
题解：
用一个数组表示每次缺的体积，比如一开始缺的是 $30$ ，如果没有 $30$ ，就需要 $2$ 个 $29$ 来凑够 $30$ ，所以现在把缺 $30$ 归零， $29$ 所缺的数 $+=2*30$ 所缺的数，以此类推
然后和排好序的物品比较，如果存在这个体积的物品，就标记需要这件物品，如果这个物品的数量超过所需的数量，然后就可以将所有所需的标记后输出答案了，如果枚举每个物品到最后还有缺的体积，那就是不可能达成。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int a[maxn],b[maxn],ans[maxn],cnt[40];
bool cmp(int i,int j){
    return a[i]>a[j];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            b[i]=i;
            ans[i]=0;
        }
        sort(b+1,b+1+n,cmp);
        memset(cnt,0,sizeof cnt);
        cnt[30]=1;
        for(int i=1,j=30;i<=n&&j>=0;){
            if(a[b[i]]!=j)cnt[j-1]+=cnt[j]*2,cnt[j]=0,j--;
            else {
                cnt[j]--,ans[b[i]]=1;
                i++;
                if(!cnt[j])break;
            }
        }
        bool f=0;
        for(int i=0;i<=30;i++)if(cnt[i])f=1;
        if(f)cout<<"impossible"<<endl;
        else{
            for(int i=1;i<=n;i++)
                cout<<ans[i];
            cout<<endl;
        }
    }
    return 0;
}

A.膜法记录

题意：
有一个 $n*m$ 大小的网格，其中存在一些敌人
牛牛可以进行 $a$ 次整行消除和 $b$ 次整列消除
问牛牛能否歼灭所有敌人
题解：
由于 $n$ 的范围相当小
所以可以直接考虑用二进制枚举行消除的情况
在行消除之后看剩下的敌人所需要的列消除是否超过b次

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

char g[30][maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n,m,a,b;
        cin>>n>>m>>a>>b;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>g[i][j];
        bool f=0;
        for(int st=0;st<(1<<n);st++){
            if(__builtin_popcount(st)!=a)continue;
            int cnt=0;
            for(int j=0;j<m;j++){
                bool f1=0;
                for(int i=0;i<n;i++)
                    if(!((st>>i)&1)&&g[i][j]=='*')f1=1;
                if(f1==1)cnt++;
            }
            if(cnt<=b){f=1;break;}
        }
        if(f)cout<<"yes";
        else cout<<"no";
        cout<<endl;
    }
    return 0;
}