牛客小白月赛22补题

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

牛客小白月赛22比赛界面
小白月赛22题解

难度体验

签到：E.模拟、F.思维
简单：D.爆搜、G.暴力、J.大数模板
中级：A.STL、B.树形DP
困难：C.记忆化搜索、H.差分
压轴：I.计算几何

A.操作序列

题意

给出一个长度无限的数列，初始全部为零，有三种操作：

  • 增加操作：给下标为 $t$ 的数加 $c$。特别注意，如果在下标$[t-30,t+30]$
    内有不为零的数，增加操作无效。
  • 削减操作：让数列中下标最小的不为零数变为零。
  • 查询操作：查询数列中下标为$t$的数字是多少。

思路

STL模拟，用map维护实际数组，set维护非0数组的下标。

代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
map<int,int>mp;
set<int>st;//维护范围内非0数
map<int,int>::iterator it;
set<int>::iterator it2;
void add(int x,int c)
{
    bool flag=1;
    it2=st.lower_bound(x-30);
    for(set<int>::iterator it3=it2;it3!=st.end();it3++)
    {
        if(*it3<=x+30)
            return;
        else
            break;
    }
    if(mp[x]+c==0)
    {
        mp.erase(x);
        st.erase(x);
    }
    st.insert(x);
    mp[x]+=c;
}
int sub()
{
    if(st.empty())
        return 0;
    it=mp.begin();
    int ret=it->second;
    st.erase(st.begin());
    mp.erase(mp.begin());
    return ret;
}
int query(int x)
{
    it2=st.find(x);
    if(it2==st.end())//不在
        return 0;
    return mp[x];
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int n,t,c;
    scanf("%d",&n);
    while(n--)
    {
        char ch='?';
        scanf("%d%c",&t,&ch);
        if(ch==' ')
        {
            scanf("%d",&c);
            add(t,c);//a[t]+=c
            continue;
        }
        if(t==-1)
        {
            if(st.empty())
                printf("skipped\n");
            else{
                printf("%d\n",sub());
            }
        }
        else
            printf("%d\n",query(t));
    }
    return 0;
}

B.树上子链

题意

给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。

思路

前缀和，树形DP。
通过DFS维护根节点到节点x的前缀和，以及x节点到叶子结点的最大值与次大值。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
vector<int>G[maxn];
ll val[maxn],sum[maxn],dp[maxn],dp2[maxn],ans;
void dfs(int x,int fa)
{
    sum[x]=sum[fa]+val[x];
    dp[x]=val[x];
    dp2[x]=-inf;
    for(auto &v:G[x])
    {
        if(v==fa)
            continue;
        dfs(v,x);
        if(dp[v]+val[x]>dp[x])
        {
            dp2[x]=dp[x];
            dp[x]=dp[v]+val[x];
        }
        else
            dp2[x]=max(dp2[x],dp[v]+val[x]);
    }
    ans=max(ans,max(sum[fa]+dp[x],dp[x]+dp2[x]-val[x]));
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int n,u,v;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>val[i];
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    ans=val[1];
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}

C.交换游戏

题意

有12个孔，有些孔上面有障碍。
若如果相邻的三个孔有两个孔被遮挡，并且被遮挡的两个孔相邻，则可以将中间的障碍拿掉，并将一端的遮挡物移到另一端没有被遮挡的孔上面。
简单来说：将这三个孔的状态反转。
例如记x为障碍遮住的孔，o为未遮住的孔
oxx -> xoo，xxo -> oox

思路

记忆化搜索
将状态看作二进制，枚举计算每一种组合的答案，$O(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
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
bool vis[1<<13];
int ans[1<<13];
void dfs(int x)
{
    if(vis[x])
        return;
    vis[x]=1;
    int cnt=0;
    for(int i=1;i<=(1<<11);i<<=1)
        if(x&i)
            cnt++;
    ans[x]=cnt;
    for(int i=3,t1=1,t2=2,t3=4;i<=12;i++,t1<<=1,t2<<=1,t3<<=1)
    {//分别为这三个位的状态
        if((x&t2)&&!((x&t1)&&(x&t3))&&((x&t1)||(x&t3)))
        {
            if(x&t1)
            {
                dfs(x-t2-t1+t3);
                ans[x]=min(ans[x],ans[x-t2-t1+t3]);
            }
            else{
                dfs(x-t2-t3+t1);
                ans[x]=min(ans[x],ans[x-t2-t3+t1]);
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    for(int i=0;i<(1<<12);i++)//预处理
        dfs(i);
    int t;
    string s;
    cin>>t;
    while(t--)
    {
        cin>>s;
        int now=0;
        for(auto &ch:s)
        {
            now<<=1;
            if(ch=='o')
                now|=1;
        }
        cout<<ans[now]<<endl;
    }
    return 0;
}

D.收集纸片

题意

我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。
假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。
你只能沿着 x 轴或 y 轴方向移动：从位置 (i,j) 移动到相邻位置 (i+1,j)，(i-1,j)，(i,j+1) 或 (i,j-1) 距离增加 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
struct node
{
    int x,y;
} a[15];
int n,sx,sy,ans;
int dis(int x1,int y1,int x2,int y2)
{
    return abs(x1-x2)+abs(y1-y2);
}
int dis(int s,int t)
{
    if(s==0)//s是起点
        return abs(sx-a[t].x)+abs(sy-a[t].y);
    return abs(a[s].x-a[t].x)+abs(a[s].y-a[t].y);
}
bool vis[maxn];
//queue<int>q;
void dfs(int t,int tim,int tot)
{
    if(tim==n)
    {
        ans=min(ans,tot+dis(sx,sy,a[t].x,a[t].y));
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(i,tim+1,tot+dis(t,i));
            vis[i]=0;
        }
    }
}
int main()
{
    int t,r,c;
    cin>>t;
    while(t--)
    {
        cin>>r>>c>>sx>>sy>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i].x>>a[i].y;
        ans=inf;
        dfs(0,0,0);
        cout<<"The shortest path has length "<<ans<<endl;
    }
    return 0;
}

E. 方块涂色

签到题

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,m,r,c;
    while(cin>>n>>m>>r>>c)
    {
        cout<<(n-r)*(m-c)<<endl;
    }
    return 0;
}

F. 累乘数字

签到题，有点小思维

代码

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()
{
    string n;
    ll d;
    while(cin>>n>>d)
    {
        cout<<n;
        while(d--)
            cout<<"00";
        cout<<endl;
    }
    return 0;
}

G.仓库选址

思路

比赛时没开这题……$O(n^4)$无脑暴力做

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=105,inf=0x3f3f3f3f,mod=1000000007;
int mp[maxn][maxn];
int dis(int x1,int y1,int x2,int y2)
{
    return abs(x1-x2)+abs(y1-y2);
}
int main()
{
    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>m>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>mp[i][j];
        int ans=inf;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                int now=0;
                for(int k=1;k<=n;k++)
                    for(int l=1;l<=m;l++)
                        now+=mp[k][l]*dis(i,j,k,l);
                ans=min(ans,now);
            }
        cout<<ans<<endl;
    }
    return 0;
}

H.货物种类

比赛时看了题目想了树套树的假做法，觉得空间复杂度炸裂+难写就没继续想……

题意

n个仓库，编号从1到n。
当购进某种货物的时候，商家会把货物分散的放在编号相邻的几个仓库中。
当所有货物购买完毕，存放货物种类最多的仓库编号为多少？

思路

离散化，差分，看代码

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
struct ope
{
    int l,r,g;
    ope(int l,int r,int g):
        l(l),r(r),g(g){}
};
vector<int>des,be[maxn],ed[maxn];
int res[maxn];
int main()
{
    vector<ope>op;
    int n,m,l,r,d,cnt=0;
    cin>>n>>m;
    while(m--)
    {
        cin>>l>>r>>d;//[l,r]存入货物d
        op.push_back(ope(l,r,d));
        des.push_back(d);
    }
    sort(des.begin(),des.end());//对货物去重
    des.erase(unique(des.begin(),des.end()),des.end());
    for(auto &i:op)
    {
        i.g=lower_bound(des.begin(),des.end(),i.g)-des.begin()+1;
        be[i.l].push_back(i.g);
        ed[i.r].push_back(i.g);
    }
    int ans=0,num=0,now=0;
    for(int i=1;i<=n;i++)
    {//now维护i的货物种类数
        for(int j:be[i])//[i,?]范围的货物j
        {
            if(!res[j])//该区域初次被j覆盖
                now++;
            res[j]++;//res是一个差分数组
        }
        if(now>ans)
        {
            ans=now;
            num=i;//种类最多的货舱
        }
        for(int j:ed[i])//[?,i]范围的货物
        {
            res[j]--;
            if(!res[j])//该区域不再被j覆盖
                now--;
        }
    }
    cout<<num<<endl;
    return 0;
}

I.工具人

思路

一句话题解+玄学代码看了我一晚上……
计算出每个点可以被射中的角度范围，放到循环数组里按角度排序。
枚举所有点作为起点，贪心地求出最小开枪数。

还是不很理解

下面这个代码大概就是照着题解敲了一遍并加上自己的理解，并且在核心代码有这么一行

1
cnt+=rec.size();//这里写成cnt+=rec.size()?1:0更好理解

如果换成

1
2
if(rec.size())
    cnt++;

同样可以过，而且更好理解。
比较疑惑为什么按题解的写法可以保证最后数组中元素数量不大于1，如果有大佬会的话请务必在下面留言教教本菜鸡QAQ

代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
const double eps= 1e-8,pi=acos(-1);
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
struct node
{
    int type,id;
    double angle;
    node (int a,double b,int c):
        type(a),id(c),angle(fmod(b+2*pi,2*pi)){}
    bool operator <(const node &b)
    {
        if(abs(angle-b.angle)>eps)//角不相等
            return angle<b.angle;
        else
            return type<b.type;
    }
};
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,n,d,c;
    cin>>t;
    while(t--)
    {
        cin>>n>>d;//数量n,有效半径d
        vector<node> v;
        for(int i=c=0;i<n;i++)
        {
            double x,y;
            cin>>x>>y;
            if(x*x+y*y<=d*d+eps)
                continue;//随便开一枪就能打中
            double a=atan2(y,x);//(x,y)弧度角
            double t=asin(d/sqrt(x*x+y*y));//确定角度范围
            v.push_back(node(0,a-t,c));//角度在[a-t,a+t]即可打中
            v.push_back(node(1,a+t,c++));
        }
        if(c==0)
        {//所有的点都能随便开一枪就打中
            cout<<1<<endl;
            continue;
        }
        sort(v.begin(),v.end());
        int ans=c;//当前至少开c枪
        for(int i=0;i<v.size();i++)
        {//枚举第一枪位置
            int cnt=0;
            vector<bool>vis(c,0);
            vector<int>rec;
            for(int k=0;k<v.size();k++)//贪心求开多少枪
            {//以i开始向后的k个元素为j
                int j=(i+k)%v.size();
                if(v[j].type==0)//进入点j区域
                {
                    vis[v[j].id]=1;
                    rec.push_back(v[j].id);
                }
                else if(vis[v[j].id])//j区域结束
                {//要离开该点范围了,必须开一枪,同时击中rec中所有元素
                    cnt++;
                    for(int l:rec)
                        vis[l]=0;
                    rec.clear();
                }
            }
            cnt+=rec.size();//这里写成cnt+=rec.size()?1:0更好理解
            //如果有剩余元素就要开一枪崩掉,没有的话就不必开枪
            //至于为什么题解可以这么写,我也想知道...
            ans=min(ans,cnt);
        }
        cout<<ans<<endl;
    }
    return 0;
}

J.计算A+B

题目没啥好说的，一个裸的大数板子

思路

大数加法

代码

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
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
const int Length=10005;
string add(const string &a,const string &b)//加
{
    string ans;
    int na[Length]={0},nb[Length]={0};
    int la=a.size(),lb=b.size();
    for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
    for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
    int lmax=la>lb?la:lb;
    for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
    if(na[lmax]) lmax++;
    for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int n;
    string s;
    cin>>n;
    while(n--)
    {
        cin>>s;
        string a,b;
        bool flag=0;
        for(auto &ch:s)
        {
            if(ch=='+')
            {
                flag=1;
                continue;
            }
            if(!flag)
                a+=ch;
            else
                b+=ch;
        }
        if(a.empty()||b.empty())
            cout<<"skipped"<<endl;
        else{
            cout<<add(a,b)<<endl;
        }
    }
    return 0;
}