竞赛讨论区 > 【题解】牛客小白月赛6
头像
LittleFall
编辑于 2018-08-21 04:19
+ 关注

【题解】牛客小白月赛6 精

题目比较基础，但涵盖的知识点很多，最后两道题是赛后写的。

完整代码请搜索LittleFall的提交记录

A-鲲

两人在周长l的圆环上比赛游泳一周，A的速度始终为a,B的速度为b，两人同时从起点同向出发，当两人圆周距离大于k时，B可以选择反向游，先回到起点的人胜。给出l,k,a,b,问两者回到起点的时间差。

A的到达时间恒定为l/a，B只有两种策略：1.一直向前，2.向前一段再向后。
若b>=a则B只能选择策略1，到达时间为l/b。
当b<a时，两者相距为k的时间为k/(a−b)，策略2总花费时间为2∗k/(a−b)。
选择策略2有一个条件，即B到达终点时A距离终点至少还有k,即2∗k/(a−b)∗a<=l−k


复杂度O(1) 

ll l = read(),k=read(),a=read(),b=read();
double tb = (double)l/b;
if( 2*k<l && b<a && 2*k*a<=(l-k)*(a-b) )
    tb = min(tb, 2.0*k/(a-b));
printf("%.2f\n", tb - (double)l/a );

B-鹏

n个整数的序列，求先上升后下降的段出现了几次。

判断上升，再判断下降，计数。
O(n) 

int n =read(),ans = 0;
    int now = read(),up=0;
    for(int i =1;i<n;i++)
    {
        int t=read();
        if(t>now)
            up=1;
        else if(t<now)
        {
            if(up==1)
            {
                up=0;
                ans++;
            }
        }
        now =t;
    }
    printf("%d\n",ans );

C-桃花

给出一棵树，求树的直径(最长的链)长度。

从根节点dfs一次，找到最远的点x。再从x开始dfs一次，找到最远的点y，则x到y是树的一条直径。
证明可以百度，大意是反证距离任意点最远的点都是直径的端点。
O(n) 

vector<int> save[M];
int dis[M];
int ans,xp = -1;

void find(int p)
{
    if(dis[p]>xp)
    {
        xp = dis[p];
        ans = p;
    }
    for(auto x:save[p])
    {
        if(dis[x]==-1)
        {
            dis[x] = dis[p] + 1;
            find(x);
        }
    }
}
int main(void)
{
    int n = read();
    for(int i=1;i<n;i++)
    {
        int a = read(),b=read();
        save[a].push_back(b);
        save[b].push_back(a);
    }
    memset(dis,-1,sizeof(dis));
    dis[1] = 0;
    find(1);
    memset(dis,-1,sizeof(dis));
    xp = -1;
    dis[ans] = 0;
    find(ans);
    printf("%d\n",xp+1 );

    return 0;
}

D-字符串丝带

开一个数组表示遍历到当前位置时出现过的各个字母数量，再开一个数组记录每个位置的答案。
O(n+m) 

char save[M];
int record[256];
int ans[M];
int main(void)
{
    int n = read(), m=read();
    scanf("%s",save+1);
    for(int i=1;save[i];i++)
    {
        record[save[i]]++;
        ans[i] = record[save[i]];
    }
    for(int i=0;i<m;i++)
    {
        printf("%d\n",ans[read()] );
    }
    return 0;
}

E-对弈

五子棋，给出下棋顺序，判断谁先赢。

每走一步需要判断输赢，我的方法是以当前走的棋子为中心判断左右9格，上下9格，左上右下9格，左下右上9格是否有连续的5个相同颜色棋子。将数组整体向右下平移即可不考虑边界。 

const int go[4][2] = {{1,1},{0,1},{1,0},{-1,1}};
//1,1 - n,n对应 5,5 - n+4,n+4, 所有棋子横纵坐标+4
int save[M][M];
int main(void)
{
    int n=read(),m=read();
    int ans = 0, ansstep = m, player = -1; //1表示htbest,-1表示whz
    for(int step = 1;step<=m; step++)
    {
        player *= -1;
        int x=read()+4,y=read()+4;
        save[x][y] = player;
        for(int k = 0;k<4;k++)
        {
            int px = x - 4*go[k][0], py = y-4*go[k][1];
            int lx = 0,alx = 0;
            for(int cnt = 0;cnt<9;cnt++)
            {
                if(save[px][py]==player)
                {
                    lx++;
                    alx = max(alx,lx);
                }
                else
                {
                    lx = 0;
                }
                px +=go[k][0],py+=go[k][1];
            }
            if(alx>=5)
            {
                ans = player;
                ansstep = step;
                goto end;
            }
        }
    }
    end:
    if(ans==0)
        printf("UNK %d\n",m);
    else if(ans==1)
        printf("HtBest %d\n",ansstep );
    else
        printf("WHZ %d\n",ansstep );
    return 0;
}

F-发电

1e6个元素，1e6个操作，三种：1.单点乘，2.单点除，3.区间求积，模1e9+7输出

树状数组改造一下，将加换成乘，0换成1，加上取模，求区间积时用之后的除以之前的。
除以一个数就是乘以它的逆元，用费马小定理。

复杂度O(nlogn) 

class BinTree: vector<ll>
{
public:
    explicit BinTree(int k = 0) //默认初始化一个能保存k个元素的空树状数组
    {
        assign(k + 1, 1); //有效下标从1开始，0仅作逻辑用处
    }
    int lowbit(int k){return k & -k;}
    ll sum(int k)//求第1个元素到第n个元素的和
    {
        return k > 0 ? (sum(k - lowbit(k)) * at(k))%MOD : 1;
    }
    int last()//返回最后一个元素下标
    {
        return size() - 1;
    }
    void add(int k, ll w) //为节点k加上w
    {
        if(k > last())return;
        at(k) *= w;
        at(k) %= MOD;
        add(k + lowbit(k), w);
    }
};

ll power(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)   ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}
ll inv(ll a){
    return power(a, MOD - 2);
}


int main(void)
{
    int n=read(),m=read();
    BinTree bt(n);
    while(m--)
    {
        int op=read(),x=read(),y=read();
        if(op==1)
            bt.add(x,y);
        else if(op==2)
            bt.add(x,inv(y));
        else
        {
            ll ans = bt.sum(y) * inv(bt.sum(x-1)) % MOD;
            cout<<ans<<endl;
        }
    }

    return 0;
}

G-指纹锁

维护一个存储着值在1e7以内的集合，1e6个操作，包括三种：
1.添加x，若集合内有值与x相差k以内，忽略本次操作；
2.删除x，删除集合内所有与x相差k以内的数；
3.查询x，如果集合内有与x相差k以内的数则输出Yes，否则输出No.

用set，预先添加一个特别大的数如1e9+7，如果lower_bound(x-k)<=x+k，说明集合内有值与x相差k以内。

复杂度O(nlogn) 

set<int> st;
int select(int val)
{
    auto it = st.lower_bound(val);
    if(it==st.end()) return MOD;
    return *it;
}
int main(void)
{
    int m=read(),k=read();
    char op[10];
    int val;
    for(int i = 0 ;i<m;i++)
    {
        scanf("%s%d",op,&val);
        if(op[0]=='a')
        {
            if(select(val-k) > val+k)
                st.insert(val);
        }
        else if(op[0]=='d')
        {
            int pval = select(val-k);
            while(pval<=val+k)
            {
                st.erase(pval);
                pval = select(val-k);
            }
        }
        else
        {
            printf("%s\n",select(val-k)<=val+k?"Yes":"No" );
        }

    }

    return 0;
}

H-挖沟

最小生成树。
按最小生成树做AC了，但是题目中说要求∑d[i][j]最小，我无法证明这个问题可以转换成最生成树问题。

Kruskal,O(ElogE) 

struct Edge
{
    int x,y,p;
}save[M];
int fa[M];
int getfa(int p)
{
    return p==fa[p]?p:fa[p]=getfa(fa[p]);
}
int main(void)
{
    int n=read(),m=read();
    for(int i=0;i<m;i++)
    {
        save[i].x=read();
        save[i].y=read();
        save[i].p=read();
    }
    sort(save,save+m,[](Edge &a,Edge &b){return a.p<b.p;});
    for(int i =1;i<=n;i++)
        fa[i]=i;
    int ans = 0;
    for(int i=0;i<m;i++)
    {
        int x= getfa(save[i].x),y=getfa(save[i].y);
        if(x!=y)
        {
            ans+=save[i].p;
            fa[y]=x;
        }
    }
    cout <<ans<<endl;

    return 0;
}

I-公交线路

给出一张图，求s点到t点的最短距离

dijkstra
复杂度O(N^2) 

//链式前向星
int tot = 0;
int fst[N];
int pnt[M],nxt[M],pri[M];
void add(int x, int y, int prior)
{
    pnt[++tot] = y;
    pri[tot] = prior;
    nxt[tot] = fst[x];
    fst[x] = tot;
}

//dijkstra
int dis[N],vis[N];

int main(void)
{
    #ifdef _LITTLEFALL_
    freopen("in.txt","r",stdin);
    #endif

    int n=read(),m=read(),s=read(),t=read();
    for(int i =0;i<m;i++)
    {
        int x = read(),y=read(),p=read();
        add(x,y,p);
        add(y,x,p);
    }
    //dijkstra
    memset(dis,0x3f,sizeof(dis));
    dis[s] = 0, vis[s]=1;
    int now = s;
    while(now!=t)
    {
        for(int i = fst[now];i;i=nxt[i])
        {
            int y = pnt[i];
            dis[y] = min(dis[y],dis[now]+pri[i]);
        }
        int xm = INT_MAX, tmp = 0;
        for(int i =1;i<=n;i++)
            if(vis[i]==0&&dis[i]<xm)
                tmp = i, xm = dis[i];
        now = tmp;
        vis[now] = 1;
    }
    printf("%d\n",vis[t]?dis[t]:-1 );
    return 0;
}

J-洋灰三角

给定n，k，p，数列，求an的前n项和Sn
（感谢我的大佬队友们帮我想清了公式）

如果k=1，那么an = 1+(n-1)p，等差数列，Sn = n+pn(n-1)/2
否则，，等比数列，最后算得


同样需要快速幂和逆元，复杂度O(1) 


ll power(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)   ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}
ll inv(ll a){
    return power(a, MOD - 2);
}
int main(void)
{
    #ifdef _LITTLEFALL_
    freopen("in.txt","r",stdin);
    #endif

    ll n = read(),k=read(),p=read();
    if(k==1)
        cout<<(n+p*n*(n-1)/2)%MOD<<endl;
    else
    {
        ll kn = power(k,n);
        ll ans = kn*k + (p-1)*kn - (n*p+1)*k + (n-1)*p+1;
        ans = (ans%MOD+MOD)%MOD;
        ans = ans * inv( (k-1)*(k-1) ) %MOD;
        cout <<ans<<endl;
    }

    return 0;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
度小满校招数据库工程师第2批
图森未来2020校招笔试卷（三）
【2022】Shopee秋招提前批SRE笔试
全部 >
面经
面试常考问题整理
面试真题：经典海量数据处理题最详解析（下）
23届联想面经分享： 秋招上岸
Springboot全套注解解析《看不懂算我输》
全部 >
内推
员工内推码获取
体验中心实习生招募 - 淘天集团
【美团】校招社招内推，所有岗位，进度可查，消息必回
携程内推携程内推码
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(0) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”