A. Robin Helps

题意

每个人身上都有一点亡命之徒的影子，也有一点英雄的影子。

侠盗罗宾汉因劫富济贫而闻名于世。

罗宾遇到的 $n$ 人，上至 $1$ st，下至 $n$ th。第 $i$ 个人有 $a_i$ 金子。如果是 $a_i \ge k$ ，罗宾会拿走所有的 $a_i$ 金子；如果是 $a_i=0$ ，罗宾会给 $1$ 金子（如果他有的话）。罗宾开始时有 $0$ 金子。

求罗宾给了多少人黄金。

大概思路

根据题意模拟即可

参考代码

void solve() {
    i64 n, k;
    std::cin >> n >> k;
    i64 sum = 0;
    int cnt = 0;
    while (n--) {
        i64 x;
        std::cin >> x;
        if (x >= k) {
            sum += x;
        } else if (x == 0) {
            if (sum) sum--, cnt++; 
        }
    }
    std::cout << cnt << "\n";
}

B. Robin Hood and the Major Oak

题意

大橡树每年长出 $i^i$ 片新叶。它在 $1$ 年开始长出 $1$ 片叶子。

树叶在树上的寿命为 $k$ 年。换句话说， $i$ 年长出的叶子会在 $i$ 年和 $i+k-1$ 年之间持续生长。

罗宾认为偶数是幸运数字。请帮助罗宾判断这棵橡树在 $n$ 年的叶子数是否为偶数。

大概思路

$i^i$ 的奇偶性可转化为 $i$ 的奇偶性，所以这题实际上就是让我们判断， $ [n - k + 1, n] $ 区间之和的奇偶性。

参考代码

void solve() {
    i64 n, k;
    std::cin >> n >> k;

    std::cout << ((((n + n - k + 1) * k / 2) % 2 == 0) ? "YES" : "NO") << "\n";//等差数列求和
}

C. Robin Hood in Town

题意

镇上住着 $n$ 人。每个人的财富是 $a_i$ 金子。最富有的人又找到了一罐金子。

形式地说，找到 一个 $a_j=max(a_1, a_2, \dots, a_n)$ ，把 $a_j$ 改成 $a_j+x$ ，其中 $x$ 是在锅里找到的黄金的非负整数。如果有多个最大值，则可以是其中任意一个。

如果一个人的财富严格少于平均财富的一半，那么这个人就是不快乐的。

如果严格来说超过总人口 $n$ 的一半，那么罗宾汉就会出现。

求罗宾汉出现的最小值 $x$ ，如果不可能，则输出 $-1$ 。

$^{\text{∗}}$ 平均财富的定义是总财富除以总人口 $n$ ，即 $\frac{\sum a_i}{n}$ ，结果为实数。

大概思路

观察样例可知， $n = 1$ 或 $2$ 无解。当 $n > 2$ 时，稍微推导一下式子即可：

$$\frac{sum + x}{2n} > a_{\frac{n}{2}}$$ $$x > 2na_{\frac{n}{2}} - sum$$ $$x_{min} = 2na_{\frac{n}{2}} - sum + 1$$

其中 $a_{\frac{n}{2}}$ 表示原数组排序后的第 $\lfloor \frac{n}{2} \rfloor$ 个元素。

为了避免输出复制，可以让结果对0取个max。

参考代码

void solve() {
    int n;
    std::cin >> n;
    std::map<i64, i64> cnt;
    std::vector<i64> a(n);

    i64 sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a[i] = x;
        cnt[x]++;
        sum += x;
    }

    if (n <= 2) {
        std::cout << -1 << "\n";
        return;
    }

    std::sort(a.begin(), a.end());

    int mid = a[n / 2];

    std::cout << std::max(0ll, (2ll * mid * n - sum + 1)) << "\n";
}

D. Robert Hood and Mrs Hood

题意

罗宾的哥哥和母亲来访，罗宾可以为每位访客选择开始的日子。

所有日子的编号都是从 $1$ 到 $n$ 。来访者连续逗留 $d$ 天，其中所有的 $d$ 天必须在 $1$ 到 $n$ 之间。

罗宾总共计划了 $k$ 项风险 “工作”。其中 $i$ 项工作发生在 $l_i$ 天和 $r_i$ 天之间，即 $1 \le i \le k$ 天。如果某项工作在 $d$ 天中的任何一天进行，那么这次访问就会与这项工作重叠（重叠时间的长短并不重要）。

罗宾希望他弟弟的访问与最多的项不同工作重叠，而他母亲的访问与最少的项不同工作重叠。

为罗宾的哥哥和母亲的来访寻找合适的开始日期。如果有多个合适的日期，选择最早的一个。

大概思路

滑动窗口维护区间最大值即可。（但是似乎看到了更优雅的实现？）

参考代码

void solve() {
    int n, d, k;
    std::cin >> n >> d >> k;

    std::vector<std::pair<i64, i64>> a(k);
    for (auto &[l, r] : a) {
        std::cin >> l >> r;
    }

    std::sort(a.begin(), a.end());

    int mxp = 1, mip = 1;
    int mxv = 0, miv = 1e9;

    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    int j = 0;
    for (int i = 1; i <= n; i++) {
        while (q.size() && q.top() <= i - d) q.pop();

        while (j < k && a[j].first <= i) {
            q.push(a[j++].second);
        }

        if (i >= d && (int)q.size() > mxv) {
            mxv = q.size();
            mxp = i - d + 1;
        }
        if (i >= d && (int)q.size() < miv) {
            miv = q.size();
            mip = i - d + 1;
        }
    }
    std::cout << mxp << " " << mip << "\n";
}

优雅的前缀和做法

void solve() {
    int n, d, k;
    cin >> n >> d >> k;
 
    vector<int> a(n + 2), b(n + 2);
    for (int i = 0; i < k; i++) {
        int l, r;
        cin >> l >> r;
        a[l]++;//到目前为止，总共开始的任务量
        b[r + 1]++;//到目前为止，总共已经结束的任务量
    }
 
    for (int i = 1; i <= n + 1; i++) {
        a[i] += a[i - 1];
        b[i] += b[i - 1];
    }
 
    int x = 0, y = 0, mx = 0, mn = inf;
 
    for (int i = 1; i + d - 1 <= n; i++) {
        int cur = a[i + d - 1] - b[i];//这样一减，就能知道当前区间有多少个任务
 
        if (cur > mx) {
            mx = cur;
            x = i;
        }
        if (cur < mn) {
            mn = cur;
            y = i;
        }
    }
 
    cout << x << " " << y << "\n";
}

E. Rendez-vous de Marian et Robin

题意

旅行网络由 $n$ 个顶点和 $m$ 条边组成，顶点从 $1$ 到 $n$ 。 第 $i$ 条边连接顶点 $u_i$ 和 $v_i$ ，需要花费 $w_i$ 秒（所有 $w_i$ 都是偶数）。玛丽安从顶点 $1$ 开始，罗宾从顶点 $n$ 开始。

此外， $n$ 个顶点中的 $h$ 个顶点都有一匹马可用。玛丽安和罗宾都是优秀的骑手，可以在短时间内（即 $0$ 秒）骑上马。骑马时，行进时间减半。一旦上马，马匹就能在剩余的路程中持续奔跑。相遇必须在顶点（即不在边上）。任何一方都可以选择在任何顶点上等待。

输出罗宾和玛丽安最早相遇的时间。如果顶点 $1$ 和 $n$ 断开，则输出 $-1$。

大概思路

对1和n分别跑一遍dijkstra，dijkstra稍微改一下写法，如果遇到了有马的位置，对于之后的转移，转移的路径长度都减半。

因为 任何一方都可以选择在任何顶点上等待。 所以跑完dijkstra之后，对每个节点求两人到达的时间的最大值可以得到在该节点相遇的最短时间。然后找到这个最短时间的最小值即可。

参考代码

void dijkstra(int s, const std::vector<std::vector<std::pair<int, i64>>>& edg, std::vector<std::array<i64, 2>>& dis, std::vector<bool>& hs) {
    auto cmp = [&](const auto& a, const auto& b) {
        return std::make_pair(dis[a.first][a.second], a) < std::make_pair(dis[b.first][b.second], b);
    };
    std::set<std::pair<int, int>, decltype(cmp)> q(cmp);
    
    dis[s][0] = 0;
    q.insert({s, 0});
    
    while (q.size()) {
        auto [now, hsbefore] = *q.begin();
        q.erase(q.begin());
        
        bool hsnow = (hsbefore || hs[now]);
        for (auto &[nxt, w] : edg[now]) {
            i64 d = hsnow ? w / 2 : w;
            if (dis[nxt][hsnow] > dis[now][hsbefore] + d) {
                q.erase({nxt, hsnow});//刷新
                dis[nxt][hsnow] = dis[now][hsbefore] + d;
                q.insert({nxt, hsnow});//insert的时候，会根据cmp自动排序位置
            }
        }
    }
}

void solve() {
    int n, k, h;
    std::cin >> n >> k >> h;
    std::vector<bool> hs(n);
    
    while (h--) {
        int x;
        std::cin >> x;
        x--;
        hs[x] = 1;
    }
    
    std::vector<std::vector<std::pair<int, i64>>> edg(n);
    
    while (k--) {
        int x, y, w;
        std::cin >> x >> y >> w;
        x--; y--;
        edg[x].push_back({y, w});
        edg[y].push_back({x, w});
    }
    
    std::vector<std::array<i64, 2>> d1(n, {(i64)1e18, (i64)1e18}), d2(n, {(i64)1e18, (i64)1e18});
    
    dijkstra(0, edg, d1, hs);
    dijkstra(n - 1, edg, d2, hs);
    
    auto get = [&](int i) {
        return std::max(std::min(d1[i][0], d1[i][1]), std::min(d2[i][0], d2[i][1]));
    };
    
    i64 ans = 1e18;
    for (int i = 0; i < n; i++) {
        ans = std::min(ans, get(i));
    }
    std::cout << (ans == (i64)1e18 ? -1 : ans) << "\n";
}

非常抽象的维护

    auto cmp = [&](const auto& a, const auto& b) {
        return std::make_pair(dis[a.first][a.second], a) < std::make_pair(dis[b.first][b.second], b);
    };
    std::set<std::pair<int, int>, decltype(cmp)> q(cmp);

可以在每次insert时，按照外部提供的数据结构重新排序。（应该是O(logn)的）

F. Sheriff’s Defense

题意

诺丁汉郡长在建造营地时考虑到了策略问题，因此，从 $1$ 到 $n$ 正好有 $n$ 个营地和 $n-1$ 条小路，每条小路都连接着两个营地。从任何一个营地都可以到达另一个营地。每个营地 $i$ 最初都有 $a_i$ 枚金币。

现在的情况是，所有营地都会被罗宾摧毁。警长可以从每个相邻的营地减去正好 $c$ 金子来强化营地，并用这些金子为营地建造更好的防御工事。强化一个营地不会改变自身的金币，只会改变其相邻营地的金币。一个营地的金币可以是负数。

罗宾汉发动攻击后，所有经过强化的营地都会幸存下来，其他营地则会被摧毁。

在罗宾汉攻击后，如果郡长最优化地强化了他的营地，他的幸存营地最多能保留多少黄金？

当且仅当存在一条连接 $a$ 和 $b$ 的小路时， $a$ 营地与 $b$ 营地相邻。只有被加强的营地才算作答案，其他营地都会被摧毁。

大概思路

树上dp，设 $dp[i][1]$ 表示，对于第 $i$ 个节点，保留该处的金币时，最多能保留多少金币； $dp[i][0]$ 表示，对于第 $i$ 个节点，不保留该处的金币时，最多能保留多少金币。

那么转移方程如下：

$$ dp[now][0] += \max(dp[nxt][0], dp[nxt][1]); $$ $$ dp[now][1] += \max(dp[nxt][0], dp[nxt][1] - 2 * c); $$

记得每次转移前先初始化 $dp[now][0] = 0$, $dp[now][1] = val[i]$。

参考代码

void solve() {
    int n, c;
    std::cin >> n >> c;
    std::vector<int> val(n + 1);

    for (int i = 1; i <= n; i++) {
        std::cin >> val[i];
    }

    std::vector<std::vector<int>> edg(n + 1);
    for (int i = 1; i < n; i++) {
        int x, y;
        std::cin >> x >> y;

        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    std::vector<std::array<i64, 2>> dp(n + 1);
    auto dfs = [&](auto&& self, int now, int from) -> void {
        dp[now][0] = 0;
        dp[now][1] = val[now];
        for (auto &nxt : edg[now]) {
            if (nxt == from) continue;
            self(self, nxt, now);

            dp[now][0] += std::max(dp[nxt][0], dp[nxt][1]);
            dp[now][1] += std::max(dp[nxt][0], dp[nxt][1] - 2 * c);
        }
    };

    dfs(dfs, 1, -1);
    i64 ans = std::max(dp[1][0], dp[1][1]);
    std::cout << ans << "\n";
}

G. Milky Days

待补

H. Robin Hood Archery

题意

从 $1$ 到 $n$ ，一排有 $n$ 个目标。当玩家射中目标 $i$ 时，他们的得分就会增加 $a_i$ ，而目标 $i$ 则会被摧毁。游戏由多个回合组成，轮流进行。罗宾汉总是先开始游戏，然后是警长，以此类推。游戏一直持续到所有目标被摧毁为止。两名玩家开始时的得分都是 $0$ 。

游戏结束时，得分最高的玩家获胜，其他玩家失败。如果双方得分相同，则为平局，没有输赢。在每个回合中，玩家可以射击任何之前没有射击过的目标。双方都以最佳方式进行游戏，尽可能获得最高分。

诺丁汉郡长怀疑自己可能会输掉游戏！这种情况不能发生，您必须帮助警长。警长会提出 $q$ 个问题，每个问题都指定了 $l$ 和 $r$ 。这意味着游戏只能以目标 $l, l+1, \dots, r$ 进行，因为其他目标会在游戏开始前被警长删除。

对于每个询问 $l$ ， $r$ ，判断警长在只考虑目标 $l, l+1, \dots, r$ 的情况下能否不输游戏。

大概思路

稍微分析一下可知，先手优势特别大，后手只能平局或者输。那么什么时候平局？当然是区间内每种数的数量都为偶数的时候。也就是说，这题实际上是在问你：区间内每种数的数量是否都为偶数

参考代码

两种实现，一种是无脑写的莫队，复杂度 $O(n\sqrt n)$ ；另一种是神奇的随机异或哈希。

随机异或哈希

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

u64 RND[1000001];

void pre() {
    for (int i = 1; i <= 1000000; i++) RND[i] = rng();
}

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<u64> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    
    for (int i = 1; i <= n; i++) {
        a[i] = RND[a[i]];
        a[i] ^= a[i - 1];
    }

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        l--;
        std::cout << ((a[r] ^ a[l]) == 0 ? "YES" : "NO") << "\n";
    }
}

莫队

struct MD {//区间本质不同数的奇偶性（离线莫队）（其实直接随机异或哈希即可O(n)解决，写莫队只是为了稍微练一下莫队）
    struct query {
        int id;
        int l;
        int r;
    };
    std::vector<query> q;//m + 1
    std::vector<int> a;//n + 1
    int n, m, block;
    
    //[Editable] 你想维护的各种信息
    std::vector<std::string> ans;
    std::vector<int> cnt; 
    int bad = 0;

    void add(int v) {//[Editable] 维护添加操作
        if (cnt[v] & 1) bad--;
        else bad++;
        cnt[v]++;
    }
    void del(int v) {//[Editable] 维护删除操作
        if (cnt[v] & 1) bad--;
        else bad++;
        cnt[v]--;
    }
    
    void init(const std::vector<int> &A, const std::vector<std::pair<int, int>> &Q) {//初始化（一般不变）（传入数组下标都从0开始，询问数组的元素范围:[1, n]）
        n = A.size();
        a.resize(n + 1);

        block = std::sqrt(n);
        for(int i = 1; i <= n; i++) a[i] = A[i - 1];
        
        m = Q.size();
        q.resize(m);

        //[Editable] 维护信息初始化
        cnt = A;
        std::sort(cnt.begin(), cnt.end());
        cnt.erase(std::unique(cnt.begin(), cnt.end()), cnt.end());
        std::map<int, int> mp;
        for (int i = 0; i < cnt.size(); i++) {
            mp[cnt[i]] = i;
        }
        for (int i = 1; i <= n; i++) {
            a[i] = mp[a[i]];
        }
        ans.resize(m + 1);
        cnt.clear();
        cnt.resize(mp.size());
        //==========================//

        for(int i = 0; i < m; i++) {
            q[i].id = i;
            q[i].l = Q[i].first;
            q[i].r = Q[i].second;
        }
        std::sort(q.begin(), q.end(), [&](query a, query b) {//按块排序
            int al = a.l / block, bl = b.l / block;
            int ar = a.r / block, br = b.r / block;
            if(al != bl) return al < bl;
            return ar < br;
        });
    }
 
    void work() {//[Editable] 处理答案
        int l, r, cl, cr;
        cr = 1;
        cl = 1;
        add(a[1]);
        for(int i = 0; i < m; i++)
        {
            l = q[i].l, r = q[i].r;
            while(cr < r) add(a[++cr]);
            while(cl > l) add(a[--cl]);
            while(cr > r) del(a[cr--]);
            while(cl < l) del(a[cl++]);
            //[Editable] 统计答案
            ans[q[i].id] = (bad == 0 ? "YES" : "NO");
        }
    }
    
    std::string getans(int i) {//按询问下标获取答案
        return ans[i];
    }
};

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for (auto &i : a) std::cin >> i;

    std::vector<std::pair<int, int>> qry(q);

    for (auto &[l, r] : qry) {
        std::cin >> l >> r;
    }
    
    MD md;
    md.init(a, qry);
    md.work();

    for (int i = 0; i < q; i++) {
        std::cout << md.getans(i) << "\n";
    }
}