Nowcoder 练习赛61

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

比赛地址： https://ac.nowcoder.com/acm/contest/5026#question

官方题解： https://ac.nowcoder.com/discuss/405216?type=101&order=0&pos=1&page=1

题目比较的简单，做起来还算是比较舒服的—— 但是最后两个题目没做出来，不太行。题解还是一如既往的中规中矩，虽然说做起来或多或少都有些思路，有的题目应该还是有一些别的简单乱搞一些的办法来解决的；

夜。大雨，家里没水==

下次还是多打点天梯舒服一点……话说周日就要武大校赛了啊== 害，要好好打啊（）下面开始：

A - 打怪

非常简单，所有的怪的hp和atk是一样的。只需要计算你会挨它几下然后计算总伤害就可以了；因为要保证自己不死，所以还需要处理一下自己的余数；总而言之细心点准没错。

~~然后就吃了一发罚时，bksn~~

我的代码

这是比赛时交的代码：

#include <iostream>

using namespace std;

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

    int t, hp, atk, h, a;
    auto solve = [&]() -> int
    {
        int xx = h / atk;
        int yy = h - xx*atk;
        int tt = yy ? xx : xx-1;
        int dmg = a*tt;
        cerr << dmg << endl;
        if (!dmg) return -1;
        else return hp%dmg ? hp/dmg : hp/dmg-1;
    };

    cin >> t;
    while (t --)
    {
        cin >> hp >> atk >> h >> a;
        cout << solve() << endl;
    }

    return 0;
}

因为是直接写的所以就顾不上美观了（

B - 吃水果

算是一个贪心题吧。关于输入的两种水果的数量，设较多的那个是x，另一个是y；简单分析一下就可以得到下面几种情况：

x = y：直接吃就可以了，输出x；
x = 2y：消费1使得较少的翻倍，然后就变成情况1了，输出x+1；
x < 2y：可以先吃一点变成情况2，然后再吃完，输出x+1；
x > 2y：……一眼看不出来，那除了翻倍y别无他法——但是这样一定可以转化为上面某一种情况；

所以，分情况讨论完了之后就简单了：分情况判断完了返回不同的值就可以了；

此外，题解提了一句说因为规模比较小可以模拟。

我的代码

综上所述，除了第四种情况需要一个递归（甚至也不需要）之外无他；

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int solve(int n, int m)
{
    if (n == m) return n;
    int x = max(n,m), y = min(n,m);
    if (x == y<<1) return y<<1^1;
    else if (x < y<<1) return x+1;
    else return solve(x,y<<1)+1;
}

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

    int t, n, m;

    cin >> t;
    while (t --)
    {
        cin >> n >> m;
        cout << solve(n,m) << endl;
    }

    return 0;
}

图省事就没改成迭代了（

C - 选择题

稍微麻烦一点的题目。看题干还是比较容易想到是使用一个并查集，先把必须要答案相同的选择题合并起来，然后再分块搜索；心里想着最坏情况12个选择题全部独立，需要4¹²种情况绝对会T的……后来看看题目的样例，已经可以说是最坏情况了，因为有限制的存在，爆搜会剪枝——情况似乎大概也就369600大概的水平：3e5 << 5e8，所以大概还是可行的；实际上也是可行的就是了（就这？

题解的说法是使用DP——倒也不是没想到，甚至我的文件里还有注释掉了的写了一半的DP== 但是因为实在是有点麻烦，还是爆搜来的简单就偷懒没写了== 就结果而言是好的（

因为这个题n=12，实在是太小了（）题解里还说了一些在n更大的时候可以做的一些优化：

（多重背包问题）：如果数据量再大一点，可以把所有背包的体积的所有状态哈希一下，变成一个二维dp，再滚动一下第一维即可。

如果是使用DP来解的话，那就是比较经典的多重背包问题。我们定义 $dp[i][x_1][x_2][x_3][x_4]$ 是枚举了i个物品，四个背包（答案选项）已经使用了 $x_{1..4}$ 个的状态。那么转移就可以从其他不同背包转移过来，枚举所有的背包就可以了；因为每个背包有容量上限，所以有的情况是转移不了的，可以节约掉。

我的代码

比赛时直接莽了一波写了一个剪枝的暴力搜索；非常的丑陋但是因为不想重写了所以就这样：

#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <cstring>
#include <map>

using namespace std;

int max4(int a, int b, int c, int d)
{
    return max(a,max(b,max(c,d)));
}

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

    int na, nb, nc, nd, m;
    int x, y, p[13];
    for (int i = 0; i <= 12; ++ i)
        p[i] = i;
    function<int(int)> father = [&](int ii) -> int
    {
        if (p[ii] == ii) return ii;
        else return p[ii] = father(p[ii]);
    };
    auto join = [&](int x, int y)
    {
        int px = father(x),
                py = father(y);
        p[px] = py;
    };
    int num[13], cnt = 0, ans = 0;
    map<int,int> mm;

    function<int(int,int,int,int,int)> search =
            [&](int s, int a,int b, int c, int d) -> int
            {
                if (s == cnt) return 1;
                else if (num[s] > max4(a,b,c,d)) return 0;
                int ret = 0;
                if (a >= num[s]) ret += search(s+1,a-num[s],b,c,d);
                if (b >= num[s]) ret += search(s+1,a,b-num[s],c,d);
                if (c >= num[s]) ret += search(s+1,a,b,c-num[s],d);
                if (d >= num[s]) ret += search(s+1,a,b,c,d-num[s]);
                return ret;
            };

    cin >> na >> nb >> nc >> nd >> m;
    while (m --)
    {
        cin >> x >> y;
        join(x,y);
    }
    memset(num,0,sizeof num);
    for (int i = 1; i <= 12; ++ i)
    {
        if (!mm[father(i)])
            mm[p[i]] = ++cnt;
        ++ num[mm[p[i]]];
    }
    cout << search(1,na,nb,nc,nd) << endl;

    return 0;
}

使用并查集完了之后再统计一波——甚至还要为此开一个map是真的丑陋…… 虽然时间上大概是O(n)的而且n非常非常小，并不会带来什么影响但是还是丑陋== 下次还是少用点lambda表达式吧（

因为这个题目理论上是要DP搜索的，所以还是补了一下丑陋的DP代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <cstring>
#include <map>

using namespace std;
typedef long long longs;
typedef long double longd;

const int N = 2e6+5;
const int inf = 0x7fffffff;
const longs INF = 0x7fffffffffffffff;
const double eps = 1e-8;

int max4(int a, int b, int c, int d)
{
    return max(a,max(b,max(c,d)));
}

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

    int na, nb, nc, nd, m;
    int x, y, p[13];
    for (int i = 0; i <= 12; ++ i) p[i] = i;
    function<int(int)> father = [&](int ii) -> int
    {
        if (p[ii] == ii) return ii;
        else return p[ii] = father(p[ii]);
    };
    auto join = [&](int x, int y)
    {
        int px = father(x), py = father(y);
        p[px] = py;
    };
    int num[13], cnt = 0, ans = 0;
    map<int,int> mm; int f[13][13][13][13][13];

    auto dp = [&]
    {
        memset(f, 0, sizeof(f)); f[0][0][0][0][0] = 1;
        for (int i = 1; i <= cnt; ++ i)
            for (int a = 0; a <= na; ++ a)
                for (int b = 0; b <= nb; ++ b)
                    for (int c = 0; c <= nc; ++ c)
                        for (int d = 0; d <= nd; ++ d)
                        {
                            auto &xx = num[i];
                            if (a + xx <= na) f[i][a+xx][b][c][d] += f[i-1][a][b][c][d];
                            if (b + xx <= nb) f[i][a][b+xx][c][d] += f[i-1][a][b][c][d];
                            if (c + xx <= nc) f[i][a][b][c+xx][d] += f[i-1][a][b][c][d];
                            if (d + xx <= nd) f[i][a][b][c][d+xx] += f[i-1][a][b][c][d];
                        }
        return f[cnt][na][nb][nc][nd];
    };

    cin >> na >> nb >> nc >> nd >> m;
    while (m --)
    {
        cin >> x >> y;
        join(x,y);
    }
    memset(num,0,sizeof num);
    for (int i = 1; i <= 12; ++ i)
    {
        if (!mm[father(i)])
            mm[p[i]] = ++cnt;
        ++ num[mm[p[i]]];
    }
    cout << dp() << endl;

    return 0;
}

至于背包的状态的哈希那就没有做了。

D - 最短路

这样的题目不出意外应该是第三次遇到了——一种显而易见的套路就是正向反向最短路，然后枚举要”修改“的边，根据最短路求出的值快速计算新值，从而进行判断；而且这个题目也没有像洛谷那个题目那样卡了遍历，可以说没有什么路子都是套路了。

关于判断的部分：首先我们可以求出原来的最短路；然后可以快速算出来的新路长度，一定是包含反转后的这条路的最短路——其他的路要不不变，要不变了也不是最短路。所以：如果它可以更新最短路，那么最短路显然变短；否则，一定不会存在其他的路可以更新最短路。

唯一有些担心的是：如果这些更新是累计的更新的话，这种针对一条边修改的套路就会失效。方法……等我想出来再说吧（

题解分析

题解里最后提了一句，问应该如何判断修改单边之后，判断最短路长度是否不变的做法。

解决这个问题之前，我们应该先意识到：如果最短路因为单边修改而缩短，那么显然这样就可以；但是如果单边的修改破坏了原有最短路，我们并不能直接看出增长之后的最短路的长度——于是就不能判定不变了。

我的代码

使用dijkstra正反扫描最短路，然后针对询问进行O(1)的查询。

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

using namespace std;
typedef long long longs;

struct edge
{
    int u, v, w, next;
    edge() = default;
    edge(int u, int v, int w, int next)
            : u(u), v(v), w(w), next(next) {}
};

const int N = 1e5+5, M = 2e5+5;

int n, m;

namespace FWS
{
    int head[N];
    int tail[N];
    int tot;
    edge ee[M*2];

    void init()
    {
        memset(head, -1, sizeof(int)*(n+1));
        memset(tail, -1, sizeof(int)*(n+1));
        tot = 0;
    }

    void addedge(int u, int v, int w)
    {
        ee[tot] = edge(u,v,w,head[u]);
        head[u] = tot ++;
        ee[tot] = edge(v,u,w,tail[v]);
        tail[v] = tot ++;
    }
}

namespace dij
{
    using namespace FWS;

    bool vis[N];
    longs ds[N], dt[N];

    void dijkstra(int goal)
    {
        priority_queue<pair<longs ,int>> q;
        int* li = goal == n ? tail : head;
        longs* dis = goal == n ? dt : ds;

        q.push(make_pair(0, goal));
        memset(vis,0, sizeof(bool)*(n+1));
        memset(dis,0x3f, sizeof(longs)*(n+1));
        dis[goal] = 0;
        while (!q.empty())
        {
            int u = q.top().second; q.pop();
            if (vis[u]) continue; vis[u] = true;
            for (int c = li[u]; ~c; c = ee[c].next)
            {
                edge& e = ee[c];
                int v = e.v;
                if (dis[v] >= dis[u] + e.w)
                    q.push(make_pair(
                            -(dis[v] = dis[u] + e.w),
                            v
                    ));
            }
        }
    }
}

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

    int u, v, c;
    int x, q;

    cin >> n >> m;
    FWS::init();
    while (m --)
    {
        cin >> u >> v >> c;
        FWS::addedge(u,v,c);
    }
    dijkstra(1); dijkstra(n);
    const longs shortest = dij::ds[n];

    cin >> q;
    while (q --)
    {
        cin >> x;
        auto& ii = FWS::ee[(x-1)<<1];
        longs to = dij::ds[ii.v] + dij::dt[ii.u] + ii.w;
        if (to < shortest) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

一直抄板子一直爽

E - 字符串

这个题目做的有点憋屈……最后一个多小时几乎都砸在这个题目上：我一直觉得这个题目是KMP，然而我对于KMP的next数组理解的并没有那么的透彻（~~除了板子一无所有~~）；最后就演变成了对着log打出来的next数组找规律，嗯……找规律……属实离谱（

然而，标答给的算法是二分答案+DP——看似奇妙又显而易见，啊这……

我也许是受了吹水群里一波接着一波的KMP的影响吧。但是这个题目真的不能使用KMP吗……就算是不能使用KMP也应该有一个反例来证明才是。我想通了就再这里写清楚好了。

题解分析

显然，这个问题相当于求解：字符串s中有k个相同的子串p，要求使得 x = p.length() 最大化；显然这个x，又具有显而易见的二分单调性——x的极限值之下均可行，以上均不可行；问题转化为寻找简单的验证x是否可行的方法——然而这又可以使用~~显而易见的~~DP完成，于是就大概有做这个题的思路了。

那么这个DP具体应该怎么操作呢：直接比较字符串，且不说是不是会暴毙，想想都觉的丑陋== 这个时候就可以使用万能的hash——将所有的长度为m的子串hash化，然后使用map储存hash-dp键值对；具体的操作方法如下：

开dp数组和map：map用来存储长度为x且 hash code 为h的字符串在已经扫描过的部分中最后一次出现的位置，用开头的下标表示；dp[i]的含义是下标i开头的（长度为x）字符串在子串[begin, i + x]中出现的最大次数；知道定义之后，操作就比较的简单了：从头扫描到尾，当扫描的部分长度大于x的时候，就每次将长度为x后缀计算hash放进map中，并且标记它的开头位置；然后计算从i开始的长度为x的子串的哈希：如果这个哈希还没出现在map中，那么它出现了一次，暂且可以标记dp[i] = 1；否则，它可以从上次出现的位置转移过来，这个位置就是被map记录的位置。

然后我们二分这个x，check当子串长度为x时所有字串出现的最大次数是否能够超过k即可；特别注意要特判0——因为0不是一个字符串，上述统计方法无法正常转移，会统计出确定值1.（其实应该是∞）

想想都觉得这个hash-dp十分的诡异……如果这真的是唯一做法那我认了（但其实这题还可以使用后缀数组

我的代码

真的是debug到吐血——这样的经历说明了一件事情：标准是根据算法来的，而不是个人喜好来的== 比如这字符串哈希，一般最好是字符串存储在[1 … n]的下标，用[L, R]来标记子串比较方便自然。然而我采用经典的[0 … n)、[L, R)标记法，就会导致一堆情况要特判（

#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cstring>

using namespace std;
typedef unsigned long long ulongs;

const int N = 2e6+5;

int n, k; char s[N];
int ff[N];

namespace StringHash
{
    const int __base = 6151;
    const int __offset = 97;
    ulongs pow[N], var[N];

    int __idx(const char ch)
    {
        return ch - 'a' + 1;
    }

    void init(const char* s)
    {
        pow[0] = 1; var[0] = __idx(s[0]) + __offset;
        int n = strlen(s);
        for (int i = 1; i < n; ++ i)
        {
            pow[i] = pow[i - 1] * __base;
            var[i] = var[i - 1] * __base + __idx(s[i]) + __offset;
        }
    }

    ulongs getHashCode(int l, int r)
    {
        if (l == r || !r) return 0ull;
        auto __elim = l ? var[l - 1] : 0ull;
        return var[r - 1] - __elim * pow[r - l];
    }
}

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

    auto check = [&](int mid) -> bool
    {
        if (mid == 0) return true;
        using StringHash::getHashCode;
        static unordered_map<ulongs, int> map;
        int ret = 0, lim = n - mid;
        for (int i = 0; i <= lim; ++ i)
        {
            if (i - mid >= 0) map[getHashCode(i - mid, i)] = i - mid;
            ulongs hashcode = getHashCode(i, i + mid);
            ff[i] = map.count(hashcode) ? ff[map[hashcode]] + 1 : 1;
            ret = max(ret, ff[i]);
        }
        map.clear();
        return ret >= k;
    };

    cin >> n >> k >> s;
    StringHash::init(s);

    int ll = 0, rr = n, ans = 0;
    check(0);
    while (ll <= rr)
    {
        int mm = ll + rr >> 1;
        if (check(mm)) ans = mm, ll = ++ mm;
        else rr = -- mm;
    }
    cout << ans << endl;

    return 0;
}

这个代码的上一个版本也AC了，但是使用Valgrind分析发现有一处[-1]的越界访问，就离谱（

F - 林檎树

唔姆……看了下答案，我完全没有想对== 但是出于学习目的，还是把我的一些想法在这里记录一下好了：

首先肯定建树，然后用一个set维护苹果的成熟度和位置；这样每次新建苹果就会变成向set中插入节点，找到所有符合条件的苹果就变成STL的两个bound；求到一个苹果的距离就等于说是带权LCA，在所有的苹果里求一个最小值就好办了；除了带权LCA之外的都可以用STL轻松实现，美滋滋（

看起来十分的美好，但是可能被一些极端的数据卡掉——如果所有的苹果都落在了符合条件的区间内的话，就算题目给了4s也会被活活卡死== 因为没有写这只是推测，但是至少说明这个算法还需要进一步的优化或者说根本就不行。

然而……

事实上，当我找了半个小时发现我并没有现成的、完成度比较好的带权LCA板子之后我就放弃写这题了（

题解分析

要想做这个题，首先你要先学会线段树和点分治。~~明白，这就去学习点分治（~~

我的代码

后记

虽然这场打的还算是比较顺利的，但是实际上还是并不理想；之后的准备，一方面是要多整一点模板：有了想法却没有优秀的板子支撑实在是太令人心痛了（）平时算法学习还是要注意理解——甚至到现在我还是觉得，E题可以通过魔改KMP利用next数组求解==

比赛是打不完的，今晚（明天凌晨）的cf教育场，明天AtCoder和洛谷的公开赛，后天的武大校赛…… 既来之则安之，砥砺前行，尽心尽力完成每一个题目吧。

又及：Typora里的排版到博客上渲染不了内联CSS有些难受……<br/>强制换行就很蠢（

2020-4-11　1:11:11　雨未停