2022.7.18 "蔚来杯"2022牛客暑期多校训练营1 赛后总结

比赛成绩

AC：3

RANK：621

试题订正

A.Villages: Landlines

难度：easy

比赛时把它转化成区间覆盖问题，每个 $x_{i}$ , $r_{i}$ 可以转化为区间 $[x_{i} - r_{i}, x_{i} + r_{i}]$ ，所有线段按左端点排序，维护相交线段右端点最大值即可。

时间复杂度 $O (n l o g n)$ 。

考场AC代码：

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

const int MAXN=2e5+5;
struct node
{
    int l,r;
}p[MAXN];
bool cmp(node x,node y)
{
    return x.l<y.l;
}
int main()
{
    int n;
    cin>>n;
    int x,r;
    for(int i=1;i<=n;++i)
        scanf("%d %d",&x,&r),p[i].l=x-r,p[i].r=x+r;
    sort(p+1,p+n+1,cmp);
    int now=p[1].r;
    long long ans=0;
    for(int i=2;i<=n;++i)
    {
        if(p[i].l<=now) now=max(now,p[i].r);
        else ans+=p[i].l-now,now=p[i].r;
    }
    cout<<ans;
    return 0;
}

B.Spirit Circle Observation

难度：hard

C.Grab the Seat!

难度：medium-easy

按照题解说的，以 $(0, 1)$ 为端点维护一个斜率递增的折线图，以 $(0, m)$ 为端点维护一个斜率递减（即绝对值递增）的折线图，并维护行可行前缀，将这三者取 $m i n$ 即是答案。

注意一下精度问题，不然样例都过不了。

订正代码：

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

#define eps 1e-8
const int MAXN=2e5+5;
struct node
{
    int x,y;
}p[MAXN];
int a[MAXN],b[MAXN];
int main()
{
    int n,m,k,q;
    cin>>n>>m>>k>>q;
    for(int i=1;i<=k;++i) scanf("%d %d",&p[i].x,&p[i].y);
    int id,x,y;
    while(q--)
    {
        scanf("%d %d %d",&id,&x,&y);
        p[id]=(node){x,y};
        for(int i=1;i<=m;++i) a[i]=n,b[i]=n+1;
        for(int i=1;i<=k;++i) b[p[i].y]=min(b[p[i].y],p[i].x);
        double K=0;
        for(int i=1;i<=m;++i)
        {
            if(i==1) a[i]=min(a[i],b[i]-1);
            else
            {
                K=max(K,(double)(i-1)/b[i]);
                a[i]=min(a[i],(int)((i-1)*1.0/K-eps));
            }
        }
        K=0;
        for(int i=m;i>=1;--i)
        {
            if(i==m) a[i]=min(a[i],b[i]-1);
            else
            {
                K=max(K,(double)(m-i)/b[i]);
                a[i]=min(a[i],(int)((m-i)*1.0/K-eps));
            }
        }
        long long ans=0;
        for(int i=1;i<=m;++i) ans+=a[i];
        printf("%lld\n",ans);
    }
    return 0;
}

D.Mocha and Railgun

难度：easy

差不多是一道裸的计算几何吧，不用证明，直接猜测垂直与圆心连线的方向长度最大，而与圆心连线的方向长度最小。

考场没想明白，就两种情况取了个最大值。

考场AC代码：

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

int main()
{
    int T;
    cin>>T;
    int r,x,y,d;
    while(T--)
    {
        scanf("%d %d %d %d",&r,&x,&y,&d);
        double delta=sqrt((double)x*x+(double)y*y);
        double alpha;
        if(d>delta) alpha=acos(-1)-acos(((double)d+delta)/r)-acos(((double)d-delta)/r);
        else alpha=acos((delta-d)/r)-acos((delta+d)/r);
        double ans=alpha*r;
        alpha=asin((double)d/r);
        ans=max(ans,alpha*2*r);
        printf("%.8f\n",ans);
    }
    return 0;
}

E.LTCS

难度：hard

F.Cut

难度：hard

G.Lexicographical Maximum

难度：check-in

确实签到题，容易发现当前数字（假设有 $n$ 位），字典序大于 $n - 1$ 个 $9$ 的充要条件是该数字前 $n - 1$ 位全是 $9$ 。

考场AC代码：

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

int main()
{
    string str;
    cin>>str;
    int len=str.length();
    bool flag=0;
    for(int i=0;i<len-1;++i)
    {
        if(str[i]!='9')
        {
            flag=1;
            break;
        }
    }
    if(!flag) cout<<str;
    else 
        for(int i=0;i<len-1;++i) putchar('9');
    return 0;
}

H.Fly

难度：medium-hard

I.Chiitoitsu

难度：medium-easy

一道基础的期望dp考场居然没推出来。

最优策略即使手上一部分单牌不打出来等对子，一部分可以随便丢弃。

设 $f_{s,r}$ 表示当前手上有 $s$ 张单牌（ $s$ 一定为奇数），牌堆剩余 $r$ 张牌。

递推方程即为：

$f_{s,r}=\begin{cases}\dfrac{3}{r}+\dfrac{r-3}{r}(f_{1,r-1}+1)&s=1\\\dfrac{3s}{r}(f_{s-2,r-1}+1)+\dfrac{r-3s}{r}(f_{s,r-1}+1)&s>1\end{cases}$

化简得：

$f_{s,r}=\begin{cases}1+\dfrac{r-3}{r}f_{1,r-1}&s=1\\1+\dfrac{3s}{r}f_{s-2,r-1}+\dfrac{r-3s}{r}f_{s,r-1}&s>1\end{cases}$

订正代码：

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

const int MOD=1e9+7;
map<string,bool>vis;
int f[15][150];
int quick_pow(int a,int b)
{
    if(!b) return 1;
    int tmp=quick_pow(a,b>>1);
    tmp=(long long)tmp*tmp%MOD;
    if(b&1) tmp=(long long)tmp*a%MOD;
    return tmp;
}
int inv(int x)
{
    return quick_pow(x,MOD-2);
}
int main()
{
    
    ios::sync_with_stdio(false);
    for(int s=1;s<=13;s+=2)
    {
        for(int r=1;r<=123;++r)
        {
            if(s==1) f[s][r]=(1LL+(long long)(r-3)*f[s][r-1]%MOD*inv(r)%MOD)%MOD;
            else f[s][r]=(1LL+((long long)s*3*f[s-2][r-1]%MOD+(long long)(r-3*s)*f[s][r-1]%MOD)*inv(r)%MOD)%MOD;
        }
    }
    int T;
    cin>>T;
    string ch;
    int tmp=0;
    while(T--)
    {
        vis.clear();
        cin>>ch;
        int len=ch.length(),s=0;
        for(int i=0;i<len;i+=2)
        {
            string now="";
            now+=ch[i],now+=ch[i+1];
            if(vis[now]) --s;
            else vis[now]=1,++s;
        }
        printf("Case #%d: %d\n",++tmp,f[s][123]);
    }
    return 0;
}

J.Serval and Essay

难度：medium

根据题解里的引理及证明（虽然我不会证），我们可以写出启发式合并。

每次一直尝试当前节点 $i$ 是否能和所有父节点合并（当且仅当所有父节点已经合并且没与 $i$ 合并），这样我们就可以得到一个森林。

森林中最大子树的大小即为答案。

PS：题解说用set优化，其实没有必要，vector已经够了，节点合并用并查集实现，顺便维护下信息即可。

订正代码：

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

const int MAXN=2e5+5;
vector<int>ins[MAXN];
int fa[MAXN],cnt[MAXN];
bool vis[MAXN];
int find(int x)
{
    return (fa[x]==x)?x:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    cnt[y]+=cnt[x],fa[x]=y,vis[x]=1;
}
bool check(int x)
{
    if(vis[x] || ins[x].empty()) return 0;
    int now=-1,si=ins[x].size();
    for(int i=0;i<si;++i)
    {
        if(now==-1) now=find(ins[x][i]);
        else if(now!=find(ins[x][i])) return 0;
    }
    if(now==x) return 0;
    return 1;
}
int main()
{
    int T;
    cin>>T;
    int n,m,tmp=0;
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i) fa[i]=i,cnt[i]=1,vis[i]=0,ins[i].clear();
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&m);
            int x;
            for(int j=1;j<=m;++j)
            {
                scanf("%d",&x);
                ins[i].push_back(x);
            }
        }
        while(true)
        {
            bool flag=0;
            for(int i=1;i<=n;++i)
            {
                if(check(i))
                {
                    flag=1;
                    merge(i,find(ins[i][0]));
                }
            }
            if(!flag) break;
        }
        int ans=1;
        for(int i=1;i<=n;++i) ans=max(ans,cnt[i]);
        printf("Case #%d: %d\n",++tmp,ans);
    }
    return 0;
}

K.Villages: Landcircles

难度：very-hard