竞赛讨论区 > 【题解】牛客练习赛79
头像
hx073269
编辑于 2021-03-26 22:23
+ 关注

【题解】牛客练习赛79 精

前面的碎碎念：

首先感谢CoolGuang!、图书馆工作人员、(́安◞౪◟排‵)、UAENBGW、小薇的暖阳五位大佬在比赛内测时对各题目提出的改进意见。这场比赛除了F，前五题均是考察基础的算法与思维能力，也是希望各个段位的选手都有游戏体验，不会出现完全不能做的情况。
另外，因为本人的失误，导致A题有一组数据ai的范围大于1e9了，但是ai仍然小于等于2e9，属于int范围，因此在内测时未能及时发现。虽然这个错误估计影响不到多少人，不过本人在这还是向因为该原因而有了糟糕体验的同学道个歉。对不起，因为出题人的疏忽给您带了糟糕的比赛体验！！！对不起！！！对不起！！！
QAQ

正文部分：

A-炼金术师

考点：思维
如果有图片说明且图片说明，那么第i次染色肯定会被第j次染色覆盖，因此第i次染色就没有必要进行。所以我们设答案为ans，初值为0，然后从后往前遍历。用一个变量mx记录后缀max，每当mx被更新，就令ans++，最后输出ans即可。
时间复杂度：O(n)。
标程：

#include<bits/stdc++.h>
using namespace std;

int a[1000005];
int main()
{
    int i,mx,n,ans=1;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    mx=a[n];
    for(i=n-1;i>=1;i--)if(mx<a[i])ans++,mx=a[i];
    printf("%d\n",ans);
    return 0;
}

B-刀工对决

考点：数论
用变量time表示某一轮的最短时间，初值设为0。对于给出的a和b，首先让a和b分别整除他们的最大公约数。紧接着，若a和b中某个数字有质因子5，不断使用百穴菜刀直到其不能整除5，time加上其使用的次数。再分别计算a和b能不断整除3的次数，令time加上他们次数之差的绝对值即可。最后判断a和b此时是否都为1，若不为1则表明该轮测试无法完成。
通过以上方法求出每一轮的最短时间，加起来就可以得到最终答案。
时间复杂度：O(n图片说明log(max(a,b))。
标程：

#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n,a,b,t,s1,s2,ans=0;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&a,&b);
        s1=s2=0;
        t=gcd(a,b),a/=t,b/=t;
        while(a%5==0)a=a/5*3,ans++;
        while(b%5==0)b=b/5*3,ans++;
        while(a%3==0)a/=3,s1++;
        while(b%3==0)b/=3,s2++;
        ans+=abs(s1-s2);
        if(a!=1||b!=1){printf("-1\n");return 0;}
    }
    printf("%d\n",ans);
    return 0;
}

C-小G的GCD

考点：构造
我们考虑如何让GCD的调用次数最大化。
通过推理或者打表可以发现是这样的：1 2 3 5 8...
容易发现是斐波那契数列，那么我们只需要找到斐波那契所对应最大那项的深度或者理解成层数就可以了，具体可以见代码。
时间复杂度：O(log(n))。
标程：

#include<bits/stdc++.h>
using namespace std;

long long n,DP[95];
int main()
{
    int i;
    scanf("%lld",&n);
    DP[1]=DP[2]=1;
    for(i=3;;i++)
    {
        DP[i]=DP[i-1]+DP[i-2];
        if(DP[i]>n)break;
    }
    printf("%d\n",i-1);
    return 0;
}

D-回文字D

考点：动态规划+字符串hash
设DP[i]为前i个字母组成的字符串最少划分为DP[i]段，那么最终答案就是DP[n]，转移可以分为以下两种：
①因为长度小于D的字符串均为D型回文串，因此有DP[i]=min(DP[i],min(DP[i-1],DP[i-2],...,DP[i-D+1])+1)。这里可以使用一个单调队列维护定长区间最小值。
②定义一个位置i是“好的”，当且仅当[i-D+1,i]是回文串。若[i-D+1,i]区间是回文串，则令mi=min(mi,DP[i-D])；若不是，就令mi=INF。因为“好的”位置是连续的，所以我们直接让mi随着i的增大而更新，同时每次令DP[i]=min(DP[i],mi+1)即可。这里可以使用字符串hash预处理后快速判断回文串。
上面的思路比较自然，实际上可以发现DP数组是单调不减的，因此只需要求最小的l，使得[l,i]为D型回文串，那么令DP[i]=DP[l-1]+1即可。故我们不需要使用单调队列也可完成转移。
时间复杂度：O(n)。
标程1：

#include<bits/stdc++.h>
using namespace std;

unsigned long long ha1[10000005]={0},ha2[10000005]={0},pw=1,base=23333;
int Q[10000005],DP[10000005]={0};
char R[10000005];
int main()
{
    int i,n,D,r=0,f=0,mi=1e9;
    scanf("%d%d%s",&n,&D,R+1);
    if(D>n){printf("1\n");return 0;}
    for(i=1;i<=D;i++)pw=pw*base;
    for(i=1;i<=n;i++)ha1[i]=ha1[i-1]*base+R[i],ha2[i]=ha2[i-1]*base+R[n-i+1]; 
    for(i=1;i<=n;i++)
    {
        DP[i]=1e9;
        if(i<D)DP[i]=1;
        else
        {
            if(r>f)DP[i]=min(DP[i],DP[Q[f]]+1);
            if(ha1[i]-ha1[i-D]*pw==ha2[n-i+D]-ha2[n-i]*pw)mi=min(mi,DP[i-D]);
            else mi=1e9;
            DP[i]=min(DP[i],mi+1);
        }
        while(r>f&&DP[Q[r-1]]>=DP[i])r--;
        Q[r++]=i;
        while(r>f&&i-Q[f]+1>=D)f++;
    }
    printf("%d\n",DP[n]);
    return 0;
}

标程2：

#include<bits/stdc++.h>
using namespace std;

unsigned long long ha1[10000005]={0},ha2[10000005]={0},pw=1,base=23333;
int DP[10000005]={0};
char R[10000005];
int main()
{
    int i,n,D,l=1e9;
    scanf("%d%d%s",&n,&D,R+1);
    if(D>n){printf("1\n");return 0;}
    for(i=1;i<=D;i++)pw=pw*base;
    for(i=1;i<=n;i++)ha1[i]=ha1[i-1]*base+R[i],ha2[i]=ha2[i-1]*base+R[n-i+1];
    for(i=1;i<=n;i++)
    {
        DP[i]=1e9;
        if(i<D)DP[i]=1;
        else
        {
            if(ha1[i]-ha1[i-D]*pw!=ha2[n-i+D]-ha2[n-i]*pw)l=i-D+2;
            else l=min(l,i-D+1);
            DP[i]=DP[l-1]+1;
        }
    }
    printf("%d\n",DP[n]);
    return 0;
}

E-小G的数学难题

考点：动态规划+单调队列
暴力做法引入，设图片说明 表示

图片说明 时
的最小值
然后我们发现不用同时记录l和r，这样会很耗时。
所以我们考虑优化记录一个P，设图片说明 表示

时
的最小值
注意能有这个记录方式是因为图片说明这个关键条件，然后我们发现了一种O(P)的转移，总复杂度是O(n图片说明P图片说明P)。
我们用单调队列优化，对于每组数据DP的时间复杂度就是O(n图片说明P)，能通过此题。空间同理，我们可以滚动数组优化，来实现O(P)的空间复杂度。
时间复杂度：O(T图片说明n图片说明P)。
标程：

#include<bits/stdc++.h>
using namespace std;

const int INF=2e9+5;
int a[1005],b[1005],c[1005],Q[10005],DP[1005][10005];
int main()
{
    int i,j,n,l,r,rear,front,pos,P,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&P);
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        for(i=1;i<=n;i++)scanf("%d",&b[i]);
        for(i=1;i<=n;i++)scanf("%d",&c[i]);
        for(i=0;i<=n;i++)
            for(j=0;j<=P;j++)DP[i][j]=INF;
        DP[0][0]=0;
        for(i=1;i<=n;i++)
        {
            rear=front=pos=0;
            for(j=0;j<=P;j++)
            {
                DP[i][j]=DP[i-1][j],l=j-b[i],r=j-a[i];
                while(pos<=r)
                {
                    if(DP[i-1][pos]<INF)
                    {
                        while(rear>front&&DP[i-1][Q[rear-1]]>DP[i-1][pos])rear--;
                        Q[rear++]=pos;
                    }
                    pos++;
                }
                while(rear>front&&Q[front]<l)front++;
                if(rear>front)DP[i][j]=min(DP[i][j],DP[i-1][Q[front]]+c[i]);
            }
        }
        if(DP[n][P]<INF)printf("%d\n",DP[n][P]);
        else printf("IMPOSSIBLE!!!\n");
    }
    return 0;
}

F-牛牛的robot

考点：闵可夫斯基和
给你n个二维向量，查询m次，每次问你是否存在一个长度为n，绝对值小于等于1的实数序列满足，如果存在的话需要输出方案。
首先想这么一个问题，如果给定了这n个向量，那么二维坐标上面哪些点是可以达到的，哪些不可达到？
纸上画一画就能发现，当这n个向量确定的时候，可以达到的点构成一个线段或者凸多边形。并且这个几何图形是中心对称的。
当你发现这个结论以后其实这个题就能做了，想办法随便贪心一个方向走到最远，然后乱搞把这个凸包给搞出来就行了。
std用的是一个稍微冷门一点的计算几何算法，闵可夫斯基和。如果之前没听说这个东西的同学可以先花个10~20分钟百度一下相关博客，它的算法原理和求解过程并不复杂，实际上只是一个级角排序然后按顺序裹一圈凸包而已。
闵可夫斯基和：
这个算法有两种比较常见的题目类型
第一类是纯计算几何求解向量平移问题、向量叠加问题的可行域。本题也是属于这一类的问题，比较典型的例题有：
JSOI2018:战争
BZOJ2564: 集合的面积
第二类是做单调DP斜率优化的时候，与分治类，合并类算法结合的时候，需要合并两个或者多个决策凸包。比较典型的例题有：
BZOJ3252:攻略
CF1019E:Raining season（这个题还是我写的第一篇博客：https://blog.nowcoder.net/n/d3fdd3dffd6f4165aa6ba606befbdd17
当然，还有一些抖机灵的考察方法，比如CF有个题是问你两个凸包的闵可夫斯基和凸包上的顶点数目。显然的结论是闵可夫斯基和凸包的顶点数目=本质不同的单位向量数目=向量角的种类数。
题解：
首先将输入进来的所有向量按照级角排序整理好，然后包出一个凸包。（如果所有向量共线可以特殊讨论）
然后显然，对于凸包上的每一个顶点，你在求凸包的时候可以同步更新一个仅有1和-1组成的答案序列。
那么更进一步，如果查询位于凸包两个顶点组成的一条边缘线段上，答案显然是除了当前枚举到的向量以外，其他向量的答案序列仍然由1和-1组成。所以可以调整当前向量的权值为[-1,1]中的一个值，使查询点在该线段上滑动，当权值为-1时位于某一端，当权值为1时位于另一端。
如此，当查询的点位于凸包边缘的答案就可以求解了。
当查询点位于凸包内部时，可以适当进行放缩变换，这样就可以构造出所有可行点的答案。
题外话：
如果刨去各种排序的复杂度，把输入进来的查询也按照级角整理好，可以双指针划窗将求解的复杂度优化到O(n+m)（见std），但是由于要求输出方案，所以不管你这部分处理是二分，甚至再暴力一点每次都重新求一下。复杂度都是O(n图片说明m)的。
这里为什么不把题出成只输出yes,no不带方案的原因是感觉这样题目太板了，听着就有原题。（即便没有原题，其代码也和 JSOI2018:战争 ，没有太大区别，区别也仅在数学模型和前期处理上）这样的话感觉会有好一点，更有趣一点（并没有）。
时间复杂度：O(n图片说明m)。
标程：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
struct point
{
    long long x,y;
    point (long long _x = 0,long long _y = 0)
    {
        x = _x;
        y = _y;
    }
};
typedef point vect;
vect operator + (const vect &a,const vect &b)
{
    return vect (a.x+b.x,a.y+b.y);
}
vect operator - (const point &a,const point &b)
{
    return vect (a.x-b.x,a.y-b.y);
}
bool operator < (const point& a,const point& b)
{
    if(a.x!=b.x)
    return a.x<b.x;
    return a.y<b.y;
}
long long dot(vect a,vect b)
{
    return a.x*b.x+a.y*b.y;
}
long long cross(vect a,vect b)
{
    return a.x*b.y-b.x*a.y;
}
struct node
{
    vect v;
    int id;
    node(vect _v=vect(0,0),int _id=0)
    {
        v=_v;
        id=_id;
    }
};
pair<double,double> get_line_intersection(point p1,point p2,point p3,point p4)
{
    vect v=p2-p1;
    vect w=p4-p3;
    vect u=p1-p3;
    double t=1.0*cross(w,u)/cross(v,w);
    return make_pair(p1.x+v.x*t,p1.y+v.y*t);
}
double dis(double X,double Y)
{
    return sqrt(X*X+Y*Y);
}
point P;
vect V,a[MAXN];
vector<node>arr[2],query[2];
int coef[MAXN],n,m;
bool flag[MAXN];
vector<vector<double> >ans;
bool cmp(const node &A,const node &B)
{
    return cross(A.v,B.v)>0;
}
bool checkLine()
{
    for(int i=0;i<n;++i)
    {
        if(i&&cross(a[i],a[i-1]))return false;
    }
    return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        scanf("%lld %lld",&a[i].x,&a[i].y);
    }
    if(!checkLine())
    {
        for(int i=0;i<n;++i)
        {
            V=a[i];
            coef[i]=1;
            if(vect(-V.x,-V.y)<V)V=vect(-V.x,-V.y),coef[i]*=-1;
            P=P+V;
            arr[0].push_back(node(vect(-2*V.x,-2*V.y),i));
        }
        sort(arr[0].begin(),arr[0].end(),cmp);

        for(int i=0;i<n;++i)
        {
            arr[1].push_back(node(vect(-arr[0][i].v.x,-arr[0][i].v.y),arr[0][i].id));
        }
        scanf("%d",&m);
        ans.resize(m);
        for(int i=0;i<m;++i)
        {
            scanf("%lld %lld",&V.x,&V.y);
            if(V.x==0&&V.y==0)
            {
                ans[i].resize(n,0);
                flag[i]=true;
                continue;
            }
            long long temp=cross(P,V);
            if(temp>0)
            {
                query[0].push_back(node(V,i));
            }
            else if(temp<0)
            {
                query[1].push_back(node(V,i));
            }
            else
            {
                if(dot(P,V)>0)
                {
                    query[0].push_back(node(V,i));
                }
                else
                {
                    query[1].push_back(node(V,i));
                }
            }
        }
        sort(query[0].begin(),query[0].end(),cmp);
        sort(query[1].begin(),query[1].end(),cmp);
        ///debug();
        int pin=0;
        for(int i=0;i<arr[0].size();++i)
        {
            point NextP=P+arr[0][i].v;
            //cout<<"now : "<<P.x<<" "<<P.y<<"Next : "<<NextP.x<<" "<<NextP.y<<endl;
            while(pin<query[0].size() && cross(query[0][pin].v,NextP)>=0)
            {
                /// solve
                //cout<<"solve id : "<<query[0][pin].id<<endl;
                pair<double,double> realCross=get_line_intersection(point(0,0),query[0][pin].v,NextP,P);
                double k=dis(query[0][pin].v.x,query[0][pin].v.y)/dis(realCross.first,realCross.second);
                double k2=dis(realCross.first-P.x,realCross.second-P.y)/dis(arr[0][i].v.x,arr[0][i].v.y);
                //cout<<realCross.first<<" "<<realCross.second<<" k: "<<k<<" k2: "<<k2<<endl;
                if(k<=1)
                {
                    for(int j=0;j<n;++j)
                    {
                        if(j!=arr[0][i].id)
                        {
                            ans[query[0][pin].id].push_back(coef[j]*k);
                        }
                        else
                        {
                            ans[query[0][pin].id].push_back(coef[j]*k*(-2*k2+1));
                        }
                    }
                    flag[query[0][pin].id]=true;
                }
                else
                {
                    flag[query[0][pin].id]=false;
                }
                ++pin;
            }
            P=NextP;
            coef[arr[0][i].id]*=-1;
        }
        pin=0;
        for(int i=0;i<arr[1].size();++i)
        {
            point NextP=P+arr[1][i].v;
            //cout<<"now : "<<P.x<<" "<<P.y<<"Next : "<<NextP.x<<" "<<NextP.y<<endl;
            while(pin<query[1].size() && cross(query[1][pin].v,NextP)>=0)
            {
                /// solve
                //cout<<"solve id : "<<query[1][pin].id<<endl;
                pair<double,double> realCross=get_line_intersection(point(0,0),query[1][pin].v,NextP,P);
                double k=dis(query[1][pin].v.x,query[1][pin].v.y)/dis(realCross.first,realCross.second);
                double k2=dis(realCross.first-P.x,realCross.second-P.y)/dis(arr[1][i].v.x,arr[1][i].v.y);
                //cout<<realCross.first<<" "<<realCross.second<<" k: "<<k<<" k2: "<<k2<<endl;
                if(k<=1)
                {
                    for(int j=0;j<n;++j)
                    {
                        if(j!=arr[1][i].id)
                        {
                            ans[query[1][pin].id].push_back(coef[j]*k);
                        }
                        else
                        {
                            ans[query[1][pin].id].push_back(coef[j]*k*(-2*k2+1));
                        }
                    }
                    flag[query[1][pin].id]=true;
                }
                else
                {
                    flag[query[1][pin].id]=false;
                }
                ++pin;
            }
            P=NextP;
            coef[arr[1][i].id]*=-1;
        }
    }
    else
    {
        for(int i=0;i<n;++i)
        {
            V=a[i];
            coef[i]=1;
            if(vect(-V.x,-V.y)<V)V=vect(-V.x,-V.y),coef[i]*=-1;
            P=P+V;
        }
        scanf("%d",&m);
        ans.resize(m);
        for(int i=0;i<m;++i)
        {
            scanf("%lld %lld",&V.x,&V.y);
            if(cross(P,V))
            {
                flag[i]=false;
            }
            else
            {
                double f;
                if(dot(P,V)>=0)f=1;
                else f=-1;
                double k=dis(V.x,V.y)/dis(P.x,P.y);
                if(k<=1)
                {
                    for(int j=0;j<n;++j)
                    {
                        ans[i].push_back(coef[j]*k*f);
                    }
                    flag[i]=true;
                }
                else
                {
                    flag[i]=false;
                }
            }
        }
    }
    for(int i=0;i<m;++i)
    {
        if(flag[i])
        {
            printf("yes\n");
            for(int j=0;j<n;++j)
            {
                printf("%.8f%c",ans[i][j],j==n-1?'\n':' ');
            }
        }
        else
        {
            printf("no\n");
        }
    }
    return 0;
}
2025最新求职资料大礼包领取
真题
历年笔试真题附答案
作业帮2021校园招聘-动画设计师
2022年星环科技秋招笔试算法题
【2020】自如秋招产品经理-B卷
全部 >
面经
面试常考问题整理
23届联想面经分享： 秋招上岸
管理类双非硕的23秋招记录＆反思
Springboot全套注解解析《看不懂算我输》
全部 >
内推
员工内推码获取
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

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

本文相关内容

等你来战

查看全部

热门推荐

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”