牛客小白月赛22补题

发表于 更新于 分类于 阅读次数：

待补完……
牛客小白月赛23
官方题解

签到题：J.真.签到
简单题：E.蒙一发，I.大暴力
中等题：B.质因数分解+二分，G.图论+组合数学，H.贪心

A.膜法记录

题意

$n$行$m$列的矩阵上面有一些点，你最多可以划掉$a$行$b$列，请问是否存在方法划掉网格上所有点。

思路

$n$范围非常小，考虑二进制状压枚举消灭的行，再暴力统计剩下的列，复杂度$O(2^nnm)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
char s[22][maxn];
ll cnt[maxn];
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,n,m,a,b;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>a>>b;
        for(int i=1;i<=n;i++)
            cin>>s[i]+1;
        bool flag=0;
        for(int i=0;i<(1<<n);i++)
        {//枚举选了哪a行
            if(__builtin_popcount(i)!=a)//统计i有多少位为1
                continue;
            int tot=0;//有敌人的列
            for(int j=1;j<=m;j++)
            {//第j列是否有残余敌人
                for(int k=1;k<=n;k++)
                {
                    if(((1<<(k-1)))&i)//这一行被消灭
                        continue;
                    if(s[k][j]=='*')
                    {
                        tot++;
                        if(tot>b)
                            goto label;
                        break;//少打break改了一年
                    }
                }
            }
            label:
            if(tot<=b)
            {
                flag=1;
                break;
            }
        }
        cout<<(flag?"yes":"no")<<endl;
    }
    return 0;
}

附赠测试数据

答案全部为yes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
999
2 2 0 0
..
..
2 3 0 2
.*.*
.*.*
2 3 2 0
**.*
*.*.
3 3 1 2
***
*.*
*.*
2 4 1 2
.*.*
*.*.
3 3 2 2
****
*.*.
.*.*
3 3 2 2
****
*.*.
****
4 4 3 2
***.
.***
.*.*
*.*.

B.阶乘

题意

给定整数$p$，找到最小的$n$，使$n!$为$p$的倍数

思路

质因子分解+二分。
对于$p$的每一个质因子$i$，$p$可以分解出$cnt$个$i$，则在区间$[2,n]$上因子$i$的数量$tot$一定大于$cnt$。
于是可以想到去二分这个区间端点，记端点为$x$。
那么如何统计$[2,x]$上有多少个因子$i$呢，简单画下图可以发现规律：从$0$开始，每隔$i$距离就会有一个$i$，每隔$i^2$会额外多出一个$i$，每隔$i^3$又会额外多出一个$i$……
这应该可以用等比数列计算，这里我用的是暴力求法。
答案就是每次二分出来的区间最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    ll t,p;
    cin>>t;
    while(t--)
    {
        cin>>p;
        ll ans=1;
        for(ll i=2;i*i<=p;i++)
        {
            ll cnt=0;
            while(p%i==0)
            {
                cnt++;
                p/=i;
            }
            ll l=1,r=cnt*i,now=cnt*i;
            while(l<=r)
            {//mid为区间端点,tot为因子数量
                ll mid=l+r>>1,tot=0,st=i;
                while(st<=mid)
                {
                    tot+=mid/st;
                    st*=i;
                }
                if(tot>=cnt)
                    now=mid,r=mid-1;
                else
                    l=mid+1;
            }
            ans=max(ans,now);
        }
        if(p>=1)
            ans=max(ans,p);
        cout<<ans<<endl;
    }
    return 0;
}

E.A+B问题

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int c;
    cin>>c;
    cout<<4294967296<<endl;
    return 0;
}

G.树上求和

题意

有一棵包含$n$个节点和$n-1$条边的树，规定树链$(u,v)$为树上从$u$到$v$的简单路径。
树的每条边上都有一个正整数，这个正整数被称作这条边的颜色，规定一条树链的权值$w(u,v)$为这条树链上所有边的颜色的代数和。
而整棵树的权值为所有不同的树链的权值的代数和。
已知所有边的颜色集合恰好为$1$到$n-1$这$n-1$个不同的正整数，请你为每条边安排一种颜色，使得这棵树的权值尽量小，并输出这个最小权。

思路

图论+组合数学
可以发现每一条边的贡献=经过次数*该边权值，于是可以按经过次数贪心地分配$[0,n-1]$。
处理每一条边时，可以以该边为分界线，将图分为左右两部分，该边的经过次数即为左面节点个数，右面节点个数(因为每两个点之间都要走一次)
若使用以点代边的做法代码会更简洁。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
vector<int>G[maxn];
struct edge
{
    int u,v;
    edge(int u,int v):
        u(u),v(v){}
};
ll siz[maxn];
void dfs(int x,int fa)
{
    siz[x]=1;
    for(auto &v:G[x])
    {
        if(v==fa)
            continue;
        dfs(v,x);
        siz[x]+=siz[v];
    }
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int n,u,v;
    cin>>n;
    vector<edge> es;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
        es.push_back(edge(u,v));
    }
    dfs(1,0);
    vector<ll> vec;
    for(auto &e:es)
    {
        ll now=min(siz[e.u],siz[e.v]);
        vec.push_back(now*(n-now));
    }
    sort(vec.begin(),vec.end());
    ll ans=0;
    for(int i=0;i<n-1;i++)
    {//n-1个,从小到大
        ans+=vec[i]*(n-i-1);
    }
    cout<<ans<<endl;
    return 0;
}

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

题意

有一个容量为$2^{30}$的背包，和$m$件物品，第$i$件物品的体积为$c_i$你需要从中选出若干件，使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性，那就是$c_i$都是2的幂。

思路

贪心，暴力
从幂为30开始找，找不到到下一级去找。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
int k[maxn];
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,m;
    cin>>t;
    while(t--)
    {
        cin>>m;//最终合成出来30
        vector<int>st[32],ans;
        for(int i=1;i<=m;i++)
        {
            cin>>k[i];
            st[k[i]].push_back(i);
        }
        bool flag=0;
        for(ll i=29,need=2;i>=0;i--,need<<=1)
        {
            if(st[i].size()>=need)
            {
                flag=1;
                for(int j=0;j<need;j++)
                {
                    ans.push_back(st[i][j]);
                }
                break;
            }
            else{
                ans.insert(ans.end(),st[i].begin(),st[i].end());
                need-=st[i].size();
            }
        }
        if(!flag)
            cout<<"impossible"<<endl;
        else{
            sort(ans.begin(),ans.end());
            for(int i=1;i<=m;i++)
            {
                if(lower_bound(ans.begin(),ans.end(),i)!=ans.end()&&*lower_bound(ans.begin(),ans.end(),i)==i)
                    cout<<1;
                else
                    cout<<0;
            }
            cout<<endl;
        }
    }
    return 0;
}

I.寻找子串

题意

给定字符串$s$，请你找出字典序最大的子串

思路

没什么好说的，暴力就行。
这题我交了七次才过，因为一个$j$打成$i$了。
题解的思路是直接找字典序最大的后缀串，这个做法更好。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005,inf=0x3f3f3f3f,mod=1000000007;
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    string s,rec,ans;
    while(cin>>s)
    {
//        cin>>s;
        ans=s;
        vector<int>st[30];
        for(int i=0;i<s.length();i++)
            st[s[i]-'a'].push_back(i);
        for(int i=25;i>=0;i--)
        {
            if(st[i].empty())
                continue;
            for(auto &j:st[i])//该字母起始位置
            {
                bool flag=0;
                for(int k=0;k<ans.length()&&j+k<s.length();k++)
                {
                    if(s[j+k]>ans[k])
                    {
                        flag=1;
                        break;
                    }
                    else if(s[j+k]<ans[k])
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag)
                    ans=s.substr(j);
            }
            if(!ans.empty())
                break;
        }
        cout<<ans<<endl;
    }
    return 0;
}

J.最大的差

题意

给定$n$个数字，请你从中选出两个数字，使得这两个数字的差尽量大，输出这个最大的差。

思路

真.签到题
集合中最大-最小即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
int main()
{
    int n,mi=INT_MAX,ma=INT_MIN;
    cin>>n;
    for(int i=1,tmp;i<=n;i++)
    {
        cin>>tmp;
        mi=min(mi,tmp);
        ma=max(ma,tmp);
    }
    cout<<ma-mi<<endl;
    return 0;
}