【题解】牛客练习赛59

A：小乔和小灰灰

令表示字符串遍历到位置,与字符串匹配的最大长度。
令表示字符串遍历到位置,与字符串匹配的最大长度。
则转移为,。
最后判断最大长度是否与两个字符串的长度相等即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
char s[N];
string a="XiaoQiao";
string b="XiaoHuiHui";
int x,y;
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    assert(n>=1&&n<=1000);
    for(int i=1;i<=n;i++)
        assert(s[i]>='a'&&s[i]<='z'||s[i]>='A'&&s[i]<='Z');
    for(int i=1;i<=n;i++)
    {
        if(s[i]==a[x]) x++;
        if(s[i]==b[y]) y++;
    }
    if(x==a.size()&&y==b.size()) printf("Happy\n");
    else printf("emm\n");
}

B：牛能和小镇

题目显然是要我们求一颗最小生成树。我们把距离公式交换一下顺序：

令，那么两点之间的距离为。
我们把所有点按排一下序，相邻两点之间连一条边即可得到最小生成树，时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
ll a[N];
int main()
{
    scanf("%d",&n);
    assert(n>=1&&n<=100000);
    for(int i=1;i<=n;i++)
    {
        ll x,y;scanf("%lld%lld",&x,&y);
        assert(x>=1&&x<=100000);
        assert(y>=1&&y<=100000);
        a[i]=x*x*y+y*y*(y-2*x);
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=1;i<n;i++) ans+=a[i+1]-a[i];
    printf("%lld\n",ans);
}

C：装备合成

假设第一种装备合成了件，那么第二种装备可以合成件。朴素的做法是枚举，然后取最优答案，但是会。
于是考虑升级以上做法：
1.做一个假设，假设上述做法存在单调极值性，那么我们可以通过简单的三分做出来。
2.随机一些数据打表，打表后发现果然存在单调极值性，那么我们可以通过简单的三分做出来。
综上所述，我们可以对进行三分，单组数据的时间复杂度，总的时间复杂度

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;scanf("%d",&t);
    assert(t>=1&&t<=10000);
    while(t--)
    {
        int x,y;scanf("%d%d",&x,&y);
        assert(x>=1&&x<=1000000000);
        assert(y>=1&&y<=1000000000);
        int l=0,r=min(x/2,y/3);
        while(r-l>10)
        {
            int m1=l+(r-l)/3,m2=r-(r-l)/3;
            if(m1+min((x-2*m1)/4,y-3*m1)>m2+min((x-2*m2)/4,y-3*m2))
                r=m2;
            else l=m1;
        }
        int ans=0;
        for(int i=l;i<=r;i++)
            ans=max(ans,i+min((x-2*i)/4,y-3*i));
        printf("%d\n",ans);
    }
}

D：取石子游戏

首先，当是一定是必败态。
那么可以转移到的状态是和，即为必胜态。
只能转移到的状态为，即为必败态。
能转移到的状态为，为必胜态。
......
根据上述依次类推，可以发现必胜态和必败态是一段一段区间这样出现的，并且长度会不断增长，增长的长度与的幂次有关，那么我们记录每一段的头和尾打表，对于每个查询，二分一下在哪一段区间，根据状态输出答案即可。时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int tot;
ll s[N],e[N];
int main()
{
    s[++tot]=1;e[tot]=1;
    s[++tot]=2;e[tot]=3;
    while(true)
    {
        tot++;
        s[tot]=e[tot-1]+1;
        if(tot&1)
            e[tot]=e[tot-1]*2;
        else
            e[tot]=e[tot-1]*2+1;
        if(e[tot]>1e18) break;
    }
    int t;scanf("%d",&t);
    assert(t>=1&&t<=100000);
    while(t--)
    {
        ll n;scanf("%lld",&n);
        assert(n>=1&&n<=(ll)1000000000000000000);
        int pos=upper_bound(s+1,s+1+tot,n)-s-1;
        if(pos&1) printf("XiaoQiao\n");
        else printf("XiaoHuiHui\n");
    }
}

E：石子搬运

首先，让我们看看问题不修改的话我们怎么做。
设表示第堆石子搬运次需要的最小代价。对于单堆石子，最优的策略是把个石子均分在次搬运上。可以证明这是最优的策略：
假设这样产生的花费为，而每次搬运的个数都为，我们把某次搬运的个数，加到另一次搬运上，重新计算的花费为，对于任意的，一定有，那么花费增加了。
再考虑两堆石子，我们知道和，另表示两堆搬运次全部搬完的代码，有。
如果没有修改，我们从前往后遍历进行得出答案，这样单次处理的时间复杂度为。如果处理次，因为同阶，时间复杂度为，但复杂度太高会得到。
注意到本题每次仅修改一个点，那么是否可以把稍做修改，使得每次修改后可以快速得出答案呢？这显然是可以的，考虑堆石子，我们先合并的答案，再合并的答案，再将和的答案合并，这不影响最终的结果。
这样，我们可以采用分治的思想来进行（类似于线段树），因为最多个结点，所以初始化的时间复杂度为。，但对于后面的每次修改，就相当于线段树单点修改，单点修改的时间复杂度为，总的时间复杂度，发现这样复杂度其实也挺大的，但别忘了还有一个小技巧优化，利用优化后时间跑不满，足以通过这道题。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=405;
int n,m,q,sum,a[N],len[N<<2];
ll dp[N<<2][N];
void update(int k)
{
    memset(dp[k],inf,sizeof(dp[k]));
    int ls=k<<1,rs=k<<1|1;
    for(int i=len[ls];i<=m;i++)
        for(int j=len[rs];i+j<=m;j++)
    {
        dp[k][i+j]=min(dp[k][i+j],dp[ls][i]+dp[rs][j]);
    }
}
void build(int l,int r,int k)
{
    len[k]=r-l+1;
    if(l==r)
    {
        memset(dp[k],inf,sizeof(dp[k]));
        for(int i=1;i<=min(a[l],m);i++)
        {
            dp[k][i]=a[l]/i;
            dp[k][i]=a[l]%i*(dp[k][i]+1)*(dp[k][i]+1)+(i-a[l]%i)*dp[k][i]*dp[k][i];
        }
        return;
    }
    int m=l+r>>1;
    build(l,m,k<<1);build(m+1,r,k<<1|1);
    update(k);
}
void fix(int l,int r,int k,int x)
{
    if(l==r)
    {
        memset(dp[k],inf,sizeof(dp[k]));
        for(int i=1;i<=min(a[l],m);i++)
        {
            dp[k][i]=a[l]/i;
            dp[k][i]=a[l]%i*(dp[k][i]+1)*(dp[k][i]+1)+(i-a[l]%i)*dp[k][i]*dp[k][i];
        }
        return;
    }
    int m=l+r>>1;
    if(x<=m) fix(l,m,k<<1,x);
    else fix(m+1,r,k<<1|1,x);
    update(k);
}
int main()
{
    scanf("%d%d",&n,&m);
    assert(n>=1&&n<=400);
    assert(m>=n&&m<=400);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),assert(a[i]>=1&&a[i]<=100000),sum+=a[i];
    build(1,n,1);
    scanf("%d",&q);
    while(q--)
    {
        int x,v;scanf("%d%d",&x,&v);
        assert(x>=1&&x<=n);assert(v>=1&&v<=100000);
        sum-=a[x];
        sum+=v;
        a[x]=v;
        fix(1,n,1,x);
        printf("%lld\n",dp[1][min(sum,m)]);
    }
}

F：小松鼠吃松果

对于第个松果，其落地的时间为，那么如果小松鼠吃了第个松果还能吃第个松果，当且仅当松果的落地时间大于等于松果且他们的落地时间之差大于等于其横向距离。接下来，我们默认为。将所有松果按落地时间排序，我们可以得到一个简单的，对于排序后的松果，有对于所有的满足，这样的时间复杂度为，我们会得到。
考虑把条件拆分一下

如果


注意到此时一定满足

如果


注意到此时一定满足

令，。对于同时满足和的，就是可以转移的，这变成了一个二维偏序关系，于是可以排序后用树状数组维护，时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node
{
    int t,p,w;
    bool operator<(const node&o)const
    {
        return t==o.t?p<o.p:t<o.t;
    }
}a[N];
int n,m,num,pos[N],b[N],hs[N];
ll t[N];
ll query(int x)
{
    ll ans=0;
    while(x)
    {
        ans=max(ans,t[x]);
        x-=x&-x;
    }
    return ans;
}
void add(int x,ll v)
{
    while(x<=n)
        t[x]=max(t[x],v),x+=x&-x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&pos[i]),hs[i]=pos[i];
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].t,&a[i].p,&a[i].w),a[i].t+=b[a[i].p];
    for(int i=1;i<=n;i++)
    {
        int x=a[i].t-pos[a[i].p],y=a[i].t+pos[a[i].p];
        a[i].t=x;
        a[i].p=y;
        hs[i]=y;
    }
    sort(hs+1,hs+1+n);
    ll ans=0;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        int pos=lower_bound(hs+1,hs+1+n,a[i].p)-hs;
        ll dp=query(pos)+a[i].w;
        ans=max(ans,dp);
        add(pos,dp);
    }
    printf("%lld\n",ans);
}