Nowcoder 练习赛59

按照惯例，开始之前先码一下比赛的一些相关链接：

比赛地址： https://ac.nowcoder.com/acm/contest/4743
官方题解： https://ac.nowcoder.com/discuss/381692?type=101&order=0&pos=1&page=1

这次题目可以说是优化DP/树形数据结构专场？六个题目很大一部分都可以使用优化DP的方法来解决。但是总体感觉还是题目没有出好，很多的题目只要你思维敏捷也能方便的使用其他的方法解决。

嘛……毕竟是马后炮，怎么说都是可以的（不过有一说一，从七点发呆到九点错过比赛时间，比赛结束之后立马补题倒也是有点真实==

不过比起打休闲，还是打天梯技术进步的更快，所以还是多打比赛，少自己补题休闲的好；虽然就算是事后自己做，结果好像也没做出来几个题目就是了==

A - 字符串

签到题，直接找就行。

我的代码

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;
typedef long long longs;

string s;
char xq[] = "XiaoQiao";
char xhh[] = "XiaoHuiHui";

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>s;
    auto x = s.find('X');
    if(x==string::npos) // 必须的
    {
        cout<<"emm";
        return 0;
    }
    int ca = 1, cb = 1;
    int lim = s.length();
    for (int i = x; i < lim; ++ i)
    {
        if(s[i]==xq[ca]) if(xq[ca]) ++ca;
        if(s[i]==xhh[cb]) if(xhh[cb]) ++cb;
    }

    if(xq[ca] || xhh[cb]) cout<<"emm";
    else cout<<"Happy";

    return 0;
}

唯一的笔记就是string::npos不能忽视，还是要进行特判的。

B - 修路

签到题，排个序然后累加得到的就是最小生成树。

题目中的那个费用整理一下合并就可以得到费用至于每个小镇相关，而和哪两个小镇无关。

我的代码

#include <iostream>
#include <cstdlib>
#include <algorithm>

#define fee(a,b) (abs(f[a]-f[b]))

using namespace std;
typedef long long longs;

const int N = 1e5+5;

int n;
longs f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;
    longs x,y;
    for(int i = 1; i <= n; ++ i)
    {
        cin>>x>>y;
        f[i] = y*(x-y)*(x-y);
    }
    sort(f+1,f+1+n);
    longs ans = 0;
    for(int i = 1; i < n; ++ i)
        ans += f[i+1]-f[i];
    cout<<ans;

    return 0;
}

C - 买装备

首先两种装备的消耗是给死了的。所以可以列方程，这恰好是二元一次不等式，可以线性规划。但是线性规划因为是一个浮点数，所以可能存在误差，需要对规划结果周围的数字进行一下判定，同时也需要特判解出负数的情况；

当然，因为题目写死了数据的原因，易得这个问题的单调极值性，那就可以三分来做了；同样是为了保险起见，区间缩小到一定范围就遍历求解比较就行。

如果不给死的话就是一个典型DP，但是这题目既然写死了还多组数据，显然就不是DP了。

我的代码

线性规划法：单次询问 O(1)

#include <iostream>
#include <algorithm>

#define getN(m) min(y-3*(m),(x-2*(m))>>2)

using namespace std;
typedef long long longs;

longs solve(int x, int y)
{
    longs m = (4ll*y-x)/10ll;
    longs n = getN(m);
    if(m <= 0 || n <= 0)
        return max(min(x>>1,y/3),min(x>>2,y));
    longs ans = max(m+n,m+1+getN(m+1));
    return max(ans,m-1+getN(m-1));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    longs t,x,y;
    cin>>t;
    while(t--)
    {
        cin>>x>>y;
        cout<<solve(x,y)<<endl;
    }

    return 0;
}

三分答案法：单次复杂度 O(log n)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long longs;

int x,y;

longs check(longs m)
{
    longs n = min((x-(m<<1))>>2, y-3*m);
    return m+n;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;
    while(t--)
    {
        cin>>x>>y;
        
        int l = 0;
        int r = max(min(x/2,y/3),min(x/4,y));
        while(r-l>10)
        {
            int t = (r-l)/3;
            int m1 = l+t, m2 = r-t;
            if(check(m1) > check(m2)) r = m2;
            else l = m1;
        }
        longs ans = 0;
        for(int i=l;i<=r;++i)
            ans = max(ans,check(i));
        cout<<ans<<endl;
    }

    return 0;
}

理论上是一个DP，但是这个DP你就挂了==

D - 石头游戏

异想天开的找规律，你不死谁死呢（叹气

玩家先手，如果是1，根据游戏定义那必败；那么因为大家都会采用最优战略，所以只要能转移到1的状态的状态就是必胜态；相反的，如果一个状态是必败态，那么它能转移到的状态一定都是必胜态；

所以，设每一个状态有效区间是[s,e]，从必败转移到必胜的区间就是[e+1,2e+1]（或者[2s,2e+1]），从必胜转移到必败就是[e+1,2e]。显然，必胜-必败区间是相互交错的。

得到了推导式，就可以算出包含输入的上限1e18的所有区间的状态。输入之后查询属于的区间后输出结果就可以。因为区间是翻倍的所以会指数级别增长，推导大约只需要进行64轮就可以完成所需要的预处理。

我的代码

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long longs;

const int N = 100;
const int M = 64;

longs st[N], ed[N];

void preProcess()
{
    st[0] = ed[0] = 1;
    for(int i = 1; i <= M; ++i)
    {
        st[i] = ed[i-1] + 1;
        ed[i] = (ed[i-1]<<1) + (i&1);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    preProcess();

    int t;
    longs n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int s = upper_bound(st,st+M,n) - st;
        if(s&1) cout<<"XiaoQiao"<<endl;
        else cout<<"XiaoHuiHui"<<endl;
    }

    return 0;
}

E - 搬石头

看起来贼像一个贪心，甚至还能装模做样大胆地猜出几个结论：贪，你接着贪——贪完你就去世了==

首先对于一堆确定数量的石头，分成x次搬运成本最低的方法显然是平均分配。但是要注意如果分配出0的话就没有意义了。

然后就是贪心的不正确性：大堆的石头分成多份可能比好几堆小的分成两份带来的收益大。所以这需要DP：将两堆石头分成m份带来的最优解是可以由两堆石头不同的分割方案递推而来的；这个时候还需要引入虚堆标记，有些麻烦。

计算单堆石头的所有分割方案的成本是O(n)，再加上虚堆求出整个石头堆的最佳方案的成本就是O(n³)。嗯其实还可以接受，如果数据量不是特别大的话；

但是这个题目不仅要分配方案，这堆石头还在不停的变化；每次变化都是要重新DP才能得到最优解的，这样整体的复杂度就变成了O(n⁴)了，这可不就凉凉==

刚才提到了DP是需要虚点的，所以可以利用线段树的思想，维护一个区间；每一次的石头堆的变化相当于单点修改；这样的话可以节约相当一部分的资源，每一次单点修改就是使用O(n)重新计算一堆石头的所有分割方案，然后更新相关联的区块的DP。线段树的单点修改的复杂度是O(nlog n)，加上这次的修改复杂度就是O(n²log n)，再算上修改次数就是O(n³log n)，差不多可以接受了。

虽然线段树的常数大的离谱，但是因为跑不满等诸多原因，这个题目还是可以勉勉强强的卡过去的。

社区讨论

这道题由很多大佬认为线段树过于愚蠢，可以使用其他优秀的办法来解决；可是又语焉不详，叫人听的半懂不懂的。因为我不是大佬，所以我只能爬简单的做一些大佬语录。如果之后了解了这些做法~~还记得这里的话~~就再更新了。

查.无.此.人. 4# ： E题怎么做都比题解优吧闵可夫斯基和n^3 贪心每次取变化量最小的n^2log😑
boxxxx 15# ： E题裸dp每次是n^{3,但是可以3分优化成n}2logn ……

三分我或多或少能理解…… 但是三分优化的DP是什么操作我就不得而知了（

我的代码

这就是题解的线段树代码

#include <iostream>
#include <cstring>
#include <algorithm>

#define cline(x) memset(x,0x3f,sizeof(longs)*(m1))

using namespace std;
typedef long long longs;

const int N = 405;
const longs INF = 0x3f3f3f3f3f3f3f3f;

longs f[N<<2][N];
int wide[N<<2];
int n,m,li,m1;
int a[N];
int sum = 0;

void update(int line)
{
    cline(f[line]);
    const int l = line<<1;
    const int r = l^1;
    int p;
    for(int i = wide[l]; i <= m; ++ i)
        for(int j = wide[r]; (p = i+j) <= m; ++ j)
            f[line][p] = min(f[line][p], f[l][i]+f[r][j]);
}

void calculate(int num, int index)
{
    cline(f[index]);
    const int lim = min(li,a[num]);
    for(int i = 1; i <= lim; ++i)
    {
        const longs val = a[num] / i;
        const longs mod = a[num] % i;
        f[index][i] = mod*(val+1)*(val+1) + (i-mod)*val*val;
    }
}

void build(int l, int r, int index)
{
    wide[index] = r - l + 1;
    if(l==r)
    {
        calculate(l,index);
        return;
    }
    int m = l+r>>1;
    build(l, m, index << 1);
    build(m+1, r, index << 1 ^ 1);
    update(index);
}

void modify(int l, int r, int index, int x)
{
    if(l==r)
    {
        calculate(l,index);
        return;
    }
    int m = l+r>>1;
    if(x <= m) modify(l, m, index << 1, x);
    else modify(m+1, r, index << 1 ^ 1, x);
    update(index);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    li = m-n+1;
    m1 = m+1;
    for(int i = 1; i <= n; ++ i)
    {
        cin>>a[i];
        f[i][1] = a[i]*a[i];
        sum += a[i];
    }
    build(1,n,1);

    int q,x,v;
    cin>>q;
    while(q--)
    {
        cin>>x>>v;
        sum += v-a[x];
        a[x] = v;
        modify(1,n,1,x);
        cout<<f[1][min(m,sum)]<<endl;   // 总数不超过x的石头不会被分为超过x堆
    }

    return 0;
}

一个特别的小细节就是要注意到分割成0是无意义的，因此需要一直统计sum

F - 吃果果

相当于说，告诉你所有的果子落地的时间和位置，当然还有营养；问你应该怎么吃才能获得最大的营养。

显然题目开始之前，先根据时间排序。对于 j > i，如果吃到了第i个果果还能吃到第j个，那么两者的时间差一定大于距离；但是因为果果有不同的营养价值，所以还是不能贪，需要DP（话说就算全是1，似乎还是要DP……）。i和j都是n的复杂度，O(n²)对于本题1e5的数据会自动暴毙==

然后接下来的部分就是题解的申必优化：

对于位置 pi ≥ pj：能吃到的条件就可以化为 ti - pi ≥ tj - pj
对于位置 pi ≤ pj：能吃到的条件就可以化为 ti + pi ≥ tj + pj

记 Xi = ti - pi，Yi = ti + pi；再利用树套树来优化DP的转移过程，就可以把时间复杂度降低到 O(nlog²n)，就可以卡过这个题目了=

说实话我还没学树套树，不是很能理解这种做法；那就学完了在更新好了（

事后分析

这其实是一个二位偏序的问题。题解使用的算法是一种叫做树套树的在线算法：但是常数大的离谱，模板也很长。如果出错的话后果不堪设想== 但是也是可以做的。可是题目并不是要求强制在线，所以可以使用一些高效率的离线算法来解决。不仅写代码更好写，也不容易出错，时间复杂度还更低。

这个题目的离线算法Tag： CDQ分治，带权LIS

我的代码

还没写呢（

总的来说这次的题目主要还是用来优化写代码的熟练度，以及各种树形数据结构的使用== 当然也见识到了各种DP的常见优化。在这个的指引下，又可以学习一些新的知识了。不也挺好吗（所以说不仅要补题，还要补的是基本功和知识储备啊==