解题笔记

种树【贪心】

题目描述

某条街被划为 n 条路段，这 n 条路段依次编号为 1…n。每个路段最多可以种一棵树。现在居民们给出了 h 组建议，每组建议包含三个整数 b,e,t，表示居民希望在路段 b 到 e之间至少要种 t 棵树。这些建议所给路段的区间可以交叉。请问：如果要满足所有居民的建议，至少要种多少棵树。

输入格式

第一行为 n，表示路段数。

第二行为 h，表示建议数。

下面 h 行描述一条建议：b,e,t，用一个空格分隔。

输出格式

输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。

样例

思路

为了使得最终种的树数量最小，即尽可能让树种在区间重叠处。

将区间按照结尾排序，每次种树判断当前区间是否已经满足所需数量，若足够则跳过，否则从后往前填空种树。

CODE

const int N = 3e4 + 10;
bool vis[N] = {false};
struct node 
{
    int b, e, t;
}p[N];
bool cmp(node x, node y) {return x.e < y.e;}

void solve()
{
    int n, h, ans = 0;
    cin >> n >> h;
    for (int i=0;i<h;i++)
        cin >> p[i].b >> p[i].e >> p[i].t;
    sort(p, p + h, cmp);
    for (int i=0;i<h;i++)
    {
        int cnt = 0, st = p[i].e;
        for (int j=p[i].e;j>=p[i].b;j--)
            cnt += vis[j];
        p[i].t -= cnt;
        while (p[i].t > 0)
        {
            if (!vis[st])
                vis[st] = true, p[i].t --;
            st --;
        }
    }
    for (int i=1;i<=n;i++)
        ans += vis[i];
    cout << ans;
}

均分纸牌【贪心】

题目描述

有 $N$ 堆纸牌，编号分别为 $1,2,\ldots,N$ 。每堆上有若干张，但纸牌总数必为 $N$ 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 $1$ 堆上取的纸牌，只能移到编号为 $2$ 的堆上；在编号为 $N$ 的堆上取的纸牌，只能移到编号为 $N-1$ 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 $N=4$ 时， $4$ 堆纸牌数分别为 $9,8,17,6$ 。

移动 $3$ 次可达到目的：

从第三堆取 $4$ 张牌放到第四堆，此时每堆纸牌数分别为 $9,8,13,10$ 。
从第三堆取 $3$ 张牌放到第二堆，此时每堆纸牌数分别为 $9,11,10,10$ 。
从第二堆取 $1$ 张牌放到第一堆，此时每堆纸牌数分别为 $10,10,10,10$ 。

输入格式

第一行共一个整数 $N$ ，表示纸牌堆数。
第二行共 $N$ 个整数 $A_1,A_2,\ldots,A_N$ ，表示每堆纸牌初始时的纸牌数。

输出格式

共一行，即所有堆均达到相等时的最少移动次数。

样例 #1

4
9 8 17 6

提示

对于 $100\%$ 的数据， $1 \le N \le 100$ ， $1 \le A_i \le 10000$ 。

思路

对于第一堆纸牌，只能由第二堆纸牌多退少补，因此若其不为平均数，计数并从第二堆中解决。

在第一堆放置好后，其不会对其他堆牌造成影响，因此可将其“删去”，此时可将第二堆牌当成第一堆牌，按照上一行方式处理。

CODE

void solve()
{
    int n, sum = 0;
    cin >> n;
    vector<int> v(n + 1);
    for (int i=0;i<n;i++)
        cin >> v[i], sum += v[i];
    sum /= n;	// 平均数
    
    int cnt = 0;
    for (int i=0;i<n;i++)
        if (v[i] != sum)
            v[i + 1] -= sum - v[i], cnt ++;
    cout << cnt;
}

最小拦截系统【贪心、二分】

题目描述

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

输入格式

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

输出格式

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

样例

8 389 207 155 300 299 170 158 65

思路

坑点：有多组数据！！！！

两种方法

1.贪心

对于每颗导弹，找到已存在系统中能够拦截其的，拦截并更新该系统的可拦截量，若未找到，则新建一个系统，并更新为当前导弹高度。

2.贪心 + 二分

对于每颗导弹，二分已存在系统的最小的可拦截系统，拦截并更新该系统的可拦截量，若未找到，则新建一个系统，并更新为当前导弹高度。

CODE

void solve()    // 贪心 + 二分 O(nlogn)
{
    int n;
    while (cin >> n)
    {
        vector<int> v(n);
        for (auto &x : v)   cin >> x;
        vector<int> a;
        for (auto x : v)
        {
            auto it = lower_bound(all(a), x);
            if (it != a.end())  *it = x;
            else    a.push_back(x);
        }
        cout << a.size() << _endl;
    }
}

void solve()    // 贪心 O(n ^ 2)
{
    int n;
    while (cin >> n)
    {
        vector<int> v(n);
        for (auto &x : v)   cin >> x;
        vector<int> a;
        for (auto x : v)
        {
            bool ok = false;
            for (auto &cur : a)
                if (cur >= x)
                {
                    cur = x;
                    ok = true;
                    break;
                }
            if (!ok)    a.push_back(x);
        }
        cout << a.size() << _endl;
    }
}

合唱队形【dp】

题目描述

$n$ 位同学站成一排，音乐老师要请其中的 $n-k$ 位同学出列，使得剩下的 $k$ 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 $k$ 位同学从左到右依次编号为 $1,2,$ … $,k$ ，他们的身高分别为 $t_1,t_2,$ … $,t_k$ ，则他们的身高满足 $t_1< \cdots <t_i>t_{i+1}>$ … $>t_k(1\le i\le k)$ 。

你的任务是，已知所有 $n$ 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式

共二行。

第一行是一个整数 $n$ （ $2\le n\le100$ ），表示同学的总数。

第二行有 $n$ 个整数，用空格分隔，第 $i$ 个整数 $t_i$ （ $130\le t_i\le230$ ）是第 $i$ 位同学的身高（厘米）。

输出格式

一个整数，最少需要几位同学出列。

样例

8
186 186 150 200 160 130 197 220

提示

对于 $50\%$ 的数据，保证有 $n \le 20$ 。

对于全部的数据，保证有 $n \le 100$ 。

思路

分别从两边进行一次DP求最长上升子序列，列出两个DP数组可以发现

// 对样例进行解释
f[i]   1 1 1 2 2 1 3 4 
g[i]   3 3 2 3 2 1 1 1
f+g-1  3 3 2 4 3 1 3 4

f[i] + g[i] - 1即为以 v[i] 为中心，能满足题目条件的最长序列长度。

因此，遍历一次，找到最大值 mx ，n - mx 为所求。

CODE

void solve()
{
    int n;  cin >> n;
    vector<int> v(n), f(n, 1), g(n, 1);
    for (auto &x : v)   cin >> x;
    
    for (int i=0;i<n;i++)
        for (int j=0;j<i;j++)
            if (v[i] > v[j])
                f[i] = max(f[i], f[j] + 1);

    for (int i=n-1;i>=0;i--)
        for (int j=n-1;j>i;j--)
            if (v[i] > v[j])
                g[i] = max(g[i], g[j] + 1);

    int ans = ll_MAX - 1;
    for (int i=0;i<n;i++)
        ans = min(ans, n - f[i] - g[i] + 1);
    cout << ans;
}

Invoking the Magic【并查集+离散化】

题目描述

BaoBao是一个懒惰的男孩。他有n双不同颜色的袜子，每个月都会洗一次。在洗衣机里，这些袜子会被混在一起。

因为有太多需要配对的袜子，BaoBao将整个袜子配对过程分为两个阶段。

在第一阶段，BaoBao随机地将袜子配对。然后在第二阶段，BaoBao重复以下操作，直到所有袜子都配对成功：BaoBao选择一些袜子的配对，把它们放入他的魔法洗涤盆中，并施展他的魔法。如果在使用魔法时，魔法洗涤盆中的袜子可以完美配对，那么魔法洗涤盆会自动为BaoBao配对它们。然而，如果它们不能配对（这意味着洗涤盆中至少有一只颜色独特的袜子），魔法盆会爆炸，而BaoBao必须防止这种情况发生。

BaoBao的魔法是有限的，在第一阶段之后，他需要知道他需要成功配对所有袜子所需的魔法洗涤盆的最小容量。洗涤盆的容量是BaoBao一次最多可以放入的袜子对数。

输入格式

输入包含多个测试用例。输入的第一行包含一个正整数 $T$ ( $1\leq T\leq 50$ )，表示测试用例的数量。

对于每个测试用例，输入的第一行包含一个整数 $n$ ( $1\leq n\leq10^5$ )，表示袜子对的数量。

接下来的 $n$ 行，第 $i$ 行（ $1\leq i\leq n$ ）包含两个整数 $a_i$ 和 $b_i$ ( $1\leq a,\ b\leq 2^{30}$ )，表示第一阶段后第 $i$ 对袜子的颜色。保证每只袜子都恰好有一只颜色相同的袜子。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示魔法洗涤盆的最小容量。

样例

注意

在示例中，BaoBao可以先把这三对袜子放入魔法洗涤盆： $\{1,2\}\{2,3\}\{1,3\}$ ，然后它们将配对成 $\{1,1\}\{2,2\}\{3,3\}$ 。然后，他可以把 $\{4,5\}\{4,5\}$ 放入魔法洗涤盆，它们将配对成 $\{4,4\}\{5,5\}$ 。因此，容量为 $3$ 时可以成功配对所有袜子。通过穷举可以证明，容量为 $2$ 时无法成功配对。

思路

啊哈，这道题让我第一次尝到了#define int long long的苦果！！

压线通过

题目其实挺简单的，就是并查集求合并后各个集合中元素的最大个数。但应该注意到的是，袜子的颜色并非由1到n，因此需对其进行离散化。（似乎使用map离散化的时间很长）。此外， find过程中，还需要进行路径压缩，否则会导致单枝过长（类似链表？！！）。

CODE

// 不可define int long long
struct DSU
{
    vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {init(n);}
    
    void init(int n) 
    {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }
    
    int find(int x) 
    {
        if (x != f[x])
            return f[x] = find(f[x]);
        return x;
    }
    
    bool same(int x, int y) {return find(x) == find(y);}
    
    bool merge(int x, int y) 
    {
        x = find(x);
        y = find(y);
        if (x == y) 
            return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {return siz[find(x)];}
};

void solve()
{
    int n, cnt = 1;
    cin >> n;
    DSU dsu(n);
    map<int, int> change;
    for (int i=0;i<n;i++)
    {
        int a, b;
        cin >> a >> b;
        if (change[a] == 0) change[a] = cnt ++;
        if (change[b] == 0) change[b] = cnt ++;
        dsu.merge(change[a], change[b]);
    }

    int mx = ll_MIN;
    for (int i=1;i<=n;i++)
        mx = max(mx, dsu.size(dsu.find(i)));
    cout << mx << _endl;
}

小红的约数【数论（逆元+简单数学推导）】

题目描述

对于一个正整数 $n$ 和一个非负整数 $d$ ，定义 $f_d(n)$ 为 $n$ 的所有约数的 $d$ 次方之和。如 $f_3(10) = 1^3 + 2^3 + 5^3 + 10^3$ 。

现给定 $n, d$ ，求 $f_d(n)$ 的值。由于答案可能很大，输出答案对 $10^9 + 7$ 取模的结果。

输入格式

由于 $n$ 可能很大，所以给出 $n$ 的质因数分解式。
$n = \prod_{i = 1}^w p_i^{a_i}$

第一行输入一个正整数 $w$ 和一个非负整数 $d$ 。
接下来 $w$ 行，每行输入两个正整数 $p_i, a_i$ 。
保证 $p_i$ 为素数且互不相同。

对于全部的测试点，保证 $1 \leq w \leq 10^5, 0 \leq d \leq 10^9, 2 \leq p_i \leq 10^9, 1 \leq a_i \leq 10^9$ 。

输出格式

输出 $f_d(n)$ 对 $10^9 + 7$ 取模的结果。

样例

2 3
2 1
5 1

说明

$f_3(10) = 1^3 + 2^3 + 5^3 + 10^3 = 1134$ 。

思路

坑点警告 ：当 $d==0$ 时，下式中各小项均为1，结果即是 ${\textstyle \prod_{i=1}^{w}(a_i+1)}$ 。

依题意，有

$n=p_1^{a1}⋅p_2^{a2}⋅p_3^{a3}...p_w^{aw}$

因此，如下公式展开各项即为n的所有因子

$(1+p_1^1+p_1^2+...+p_1^{a_1})(1+p_2^1+p_2^2+...+p_2^{a_2})...(1+p_w^1+p_w^2+...+p_w^{a_w})$

题目所求为 $f_d(n)$ （ $n$ 的所有约数的 $d$ 次方之和）

即 $[1^d+(p_1^1)^d+(p_1^2)^d+...+(p_1^{a_1})^d][1^d+(p_2^1)^d+(p_2^2)^d+...+(p_2^{a_2})^d][1^d+(p_w^1)^d+(p_w^2)^d+...+(p_w^{a_w})^d]$

对于每个中括号的一项，通过等比数列公式加逆元算出，将各个中括号结果相乘即是答案。

令 $q=p_i^{d}$ ，则有 $f_d(n)={\prod_{i=1}^{w}\frac{(1-q^{a_i+1})}{1-q}}={\prod_{i=1}^{w}[(1-q^{a_i+1})\cdot inv(1-q)]}$

CODE

const int MOD = 1e9 + 7;
int qpow(int a, int b)
{
    int tmp = 1;
    a %= MOD;
    while (b)
    {
        if (b & 1)
            tmp = tmp * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return tmp;
}
int inv(int x) { return qpow(x, MOD - 2);}

void solve()
{
    int w, d, ans = 1;
    cin >> w >> d;
    
    auto cal = [&](int p, int a) -> int
    {
        int q = qpow(p, d);
        return (qpow(q, a + 1) - 1) * inv(q - 1) % MOD;
    };

    for (int i=1;i<=w;i++)
    {
        int p, a;
        cin >> p >> a;
        ans = ans * (d ? cal(p, a) : a + 1) % MOD;
    }
    cout << ans;
}

嘤嘤不想求异或喵【找规律+异或法则】

题目描述

嘤嘤有两个整数 $l,r$ ，她想知道区间 $[l,r]$ 所有整数的异或和是多少喵~。

输入格式

第一行输入一个正整数 $T(1 \leq T \leq 2 \times 10^5)$ ，表示询问次数。

接下来T行，每行输入两个正整数 $l,r(1 \leq l \leq r \leq 10^{18})$ 表示询问。

输出格式

对于每个询问，在一行中输出一个整数表示答案。

样例

1
3
0

思路

由于异或的性质(同一个数异或两次为0)

因此 $l\oplus (l+1)\oplus (l+2)\oplus···r = [1\oplus 2\oplus 3···(l-1)][1\oplus 2\oplus 3···r]$

由此，问题转化为了求1到x的异或和。

通过打表可观察到（第i行表示xorSum(1,i)）: 异或和四项为一个循环，分别是1, x + 1, 0, x

CODE

void solve()
{
    int l, r;
    cin >> l >> r;
    
    auto xorSum = [&](int r) -> int
    {
        array<int, 4> a = {r, 1, r + 1, 0};
        return a[r % 4];
    };

    cout << (xorSum(l - 1) ^ xorSum(r)) << _endl;
}

区间权值【前缀和+找规律+双指针】

题目描述

小 Bo 有 $n$ 个正整数 $a_1...a_n$ ，以及一个权值序列 $w_1...w_n$ ，现在他定义 $f(l,r)=(\sum_{i=l}^{r}a_i)\times w_{r-l+1}$
现在他想知道 $\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r)$ 的值，需要你来帮帮他
你只需要输出答案对 $10^9+7$ 取模后的值

输入格式

第一行一个正整数 $n$
第二行 $n$ 个正整数 $a_1...a_n$
第三行 $n$ 个正整数 $w_1...w_n$

输出格式

对于每个询问，在一行中输出一个整数表示答案。

样例

3
1 1 1
1 1 1

思路

$\sum_{i=l}^{r}a_i$ 表示连续（r - l + 1 = k）项，要求 $\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r)$ ，可以发现，

当 k = 1 or k = n 时, 数组 a 每一项均只被计算了一次

当 k = 2 or k = n - 1 时, 数组 a 除了a[1] 和 a[n], 其余项又被多计算了一次

当 k = 3 or k = n - 2 时, 数组 a 除了a[1] 、 a[2] 和 a[n - 1]、 a[n], 其余项又被多计算了一次

因此，利用双指针，每次多加指针包含区间的和，乘以两边的权值。

CODE

const int MOD = 1e9 + 7;

void solve()
{
    int n;  cin >> n;
    vector<int> a(n + 1), w(n + 1), pre(n + 1, 0);
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
        pre[i] = (pre[i - 1] + a[i]) % MOD;
    }
    for (int i=1;i<=n;i++)  cin >> w[i];

    int l = 1, r = n, ans = 0, cur = 0;
    while (l <= r)
    {
        cur = (cur + pre[r] - pre[l - 1] + MOD) % MOD;
        ans = (ans + cur * w[l] % MOD) % MOD;
        if (l != r)
            ans = (ans + cur * w[r] % MOD) % MOD;
        l ++, r --;
    }
    cout << ans;
}

Final Boss【二分/set/优先队列】

题面描述

你正在面对你最喜欢的游戏中的最终 BOSS。敌人的生命值是 $h$ 。你的角色有 $n$ 攻击。第 i 次攻击会对 BOSS 造成 $a_i$ 伤害，但冷却时间为 $c_i$ 个回合，也就是说，如果你当前的回合为 $x$ ，那么下一次可以使用该攻击的时间为 $x + c_i$ 个回合。每个回合，你都可以一次性使用当前未冷却的所有攻击。如果所有攻击都处于冷却状态，则本回合什么也不做，跳到下一回合。

最初，所有攻击都不在冷却时间内。要花多少回合才能打败 BOSS？当 BOSS 的生命值为 $0$ 或更低时，它就被打败了。

输入格式

第一行包含 $t$ ( $1 \leq t \leq 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含两个整数 $h$ 和 $n$ ( $1 \leq h, n \leq 2 \cdot 10^5$ ) - BOSS 的血量和你的攻击次数。

每个测试用例的第 $2$ 行包含 $n$ 整数 $a_1, a_2, ..., a_n$ ( $1 \leq a_i \leq 2 \cdot 10^5$ ) - 你的攻击伤害。

每个测试用例的第 $3$ 行包含 $n$ 个整数 $c_1, c_2, ..., c_n$ ( $1 \leq c_i \leq 2 \cdot 10^5$ ) - 你的攻击冷却时间。

保证所有测试用例中的 $h$ 和 $n$ 之和不超过 $2 \cdot 10^5$ .

输出格式

对于每个测试用例，输出一个整数，即击败 BOSS 所需的最少回合数。

样例

8
3 2
2 1
2 1
5 2
2 1
2 1
50 3
5 6 7
5 6 7
50 3
2 2 2
3 3 3
90000 2
200000 200000
1 1
100000 1
1
200000
6 7
3 2 3 2 3 1 2
6 5 9 5 10 7 7
21 6
1 1 1 1 1 1
5 5 8 10 7 6

1
3
15
25
1
19999800001
1
21

提示

对于第一个测试用例，你可以在第一个回合使用攻击1和2，总共造成3点伤害，从而击败Boss。

对于第二个测试用例，你可以在3回合内打败Boss，使用以下攻击方式：

第1回合：使用攻击1和2，对Boss造成3点伤害。Boss剩余2点生命值。

第2回合：使用攻击2，对Boss造成1点伤害。Boss剩余1点生命值。

第3回合：使用攻击1，对Boss造成2点伤害。Boss剩余−1点生命值。由于其生命值小于或等于0，你击败了Boss。

对于第六个测试用例：记得使用64位整数，因为答案可能会很大。

思路

标准的次次做，次次错【无奈…😔】

法一：【二分答案】

二分打败BOSS所需轮数，对于每次的check，判断每个技能能够使用多少次，伤害累加，若是超过BOSS的hp，则当前轮数可行。

！！需注意的是：伤害值非常大且二分初始值很大时候，多个技能的伤害总和可能超过 long long 的范围，因此需要在遍历技能过程中判断当前敌人hp 是否已经小于等于0，即 BOSS 已死。！！

法二：【优先队列】

用优先队列pair装每个技能的编号和下次可使用的第x轮。

首先，将所有节能技能全都放在优先队列里面，此时设置的下次可使用的第x轮为1。

只要 BOSS hp > 0, 从优先队列顶端取出技能，BOSS 受伤，血量降低，将该技能重新放回优先队列，更新下次可使用时间为当前时间+冷却时间。

CODE

void solve()	// 二分答案
{
    int h, n;
    cin >> h >> n;
	vector<int> a(n), c(n);
    for (int i=0;i<n;i++)   cin >> a[i];
    for (int i=0;i<n;i++)   cin >> c[i];
    int l = 1, r = 1e13, mid;
    
    auto check = [&](int x) -> bool
    {
        int hp = h;
        for (int i=0;i<n;i++)
        {
            if (hp / a[i] < (x + c[i] - 1) / c[i])
                return true;
            hp -= (x + c[i] - 1) / c[i] * a[i];
            if (hp <= 0)
                return true;
        }
        return hp <= 0;
    };
    
    while (l < r)
    {
        mid = (l + r) >> 1;
        cerr << mid << _endl;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << _endl;
}

void solve()	// 优先队列
{
    int hp, n;
    cin >> hp >> n;
    vector<int> a(n), c(n);
    for (auto &x : a)   cin >> x;
    for (auto &x : c)   cin >> x;
    auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {return a.first > b.first;};
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
    for (int i=0;i<n;i++)
        q.push({1, i});

    int cur = 0;
    while (hp > 0)
    {
        auto [t, id] = q.top(); q.pop();
        cur = t;
        hp -= a[id];
        q.push({cur + c[id], id});
    }
    cout << cur << _endl;
}

Chords【化曲为直+括号匹配（栈）】

题面描述

有 $2n$ 个点等距离地分布在一个圆上，从一个点开始顺时针以 $1$ 到 $2n$ 编号。

现在有 $n$ 条弦，第 $i$ 条弦连接点 $a_i$ 和 $b_i$ ，保证所有 $a_1,\cdots,a_n,b_1,\cdots,b_n$ 不同。

判断弦之间是否有交点。

输入格式

输入以以下格式从标准输入给出：

$N$

$A_1\quad B_1$

$A_2\quad B_2$

$\vdots$

$A_N\quad B_N$

输出格式

如果弦之间有交点，则打印Yes；否则打印No。

样例

Yes

如图所示，弦1（连接点1和3的线段）和弦2（连接点4和2的线段）相交，因此打印Yes。

No

如图所示，弦之间没有交点，因此打印No。

Yes

提示

$2\leq\ N\ \leq\ 2\times\ 10^5$
$1\leq\ A_i,B_i\ \leq\ 2N$
$A_1,\dots,A_N,B_1,\dots,B_N$ 都是不同的
所有输入值均为整数

思路

将环拉成直线，判断是否存在区间相交。（利用栈）

CODE

void solve()
{
    int n;  cin >> n;
    map<int, int> mmap;
    for (int i=0;i<n;i++)
    {
        int a, b;
        cin >> a >> b;
        mmap[a] = b, mmap[b] = a;
    }
    stack<int> st;
    for (int i=1;i<=2*n;i++)
        if (st.empty() || st.top() != mmap[i])  st.push(i);
        else    st.pop();
    cout << (st.empty() ? "No" : "Yes");
}

小明打联盟【贪心/背包】

题目描述

小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：

1.乌鸦坐飞机释放时间：x 固定伤害值：a

2.蜘蛛吃耳屎释放时间：y 固定伤害值：b

3.饿狼前进释放时间：z 固定伤害值：c

他还有一个大招，其释放的时间是一个区间 $[L, R]$ ，可以在区间内任意时间点释放出技能，其如果在 $L+i$ 时刻释放技能，其能够打出的伤害值为: $tmp + A * i$

这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）, $A$ 是一个常数。

小明很喜欢研究连招使得在有限的时间内打出最高的伤害，现在他想要在 $T$ 长度单位时间内打出最高的伤害，问这个最大伤害值。

输入格式

本题包含多组数据。
输入格式为：
$T$
$x\quad a$
$y\quad b$
$z\quad c$
$L\quad R\quad temp\quad A$
数据范围：
$1\leq T\leq1e5$
$1\leq x,y,z,L,R\leq T$
$L\leq R$
$1\leq a,b,c,temp,A\leq 1e5$

输出格式

输出包含一行，输出能够打出的最高伤害值。

思路

【多组样例！！】

【似乎背包不是正解？！】，赛时WA了几发，最后的AC程序运行时长是1700ms。

法一：贪心

将所有技能（包括不同蓄力时间的大招）全都塞到一个vector里，按照技能的性价比（ $\frac{伤害}{释放时间}$ ）由大到小排序。

只要时间还够释放前面的技能就释放，不够了再看下一个技能。

法二：背包（完全背包）（不推荐）

将所有技能（包括不同蓄力时间的大招）全都塞到一个vector（可选列表）中，完全背包选择出规定t的最大方案。

样例

CODE

void solve()	// 贪心
{
    int n;
    int l, r, tmp, a;
    auto cmp = [&](pair<int, int> x, pair<int, int> y) {return (x.second * 1.0 / x.first) > (y.second * 1.0 / y.first);};
    while (cin >> n)
    {
        vector<pair<int, int>> v(3);
        for (auto &x : v)   cin >> x.first >> x.second;
        cin >> l >> r >> tmp >> a;
        for (int i=l;i<=r;i++)
            v.push_back({i, tmp + (a * (i - l))});
        sort(all(v), cmp);

        int hp = 0;
        for (auto [cost, damag] : v)
        {
            int t = n / cost;
            hp += damag * t;
            n %= cost;
        }
        cout << hp << _endl;
    }
}

void solve()
{
    int n, l, r, tmp, a;
    while (cin >> n)
    {
        vector<pair<int, int>> v(3);
        for (auto &x : v)   cin >> x.first >> x.second;
        cin >> l >> r >> tmp >> a;
        for (int i=l;i<=r;i++)
            v.emplace_back(i, tmp + (a * (i - l)));
        vector<int> dp(n + 1);
        for (auto [cost, damag] : v)
            for (int j=cost;j<=n;j++)
                dp[j] = max(dp[j], dp[j - cost] + damag);
        cout << dp[n] << _endl;
    }
}

Cheering up the Cow G【最小生成树】

题目描述

约翰有 $N$ 个牧场，编号依次为 $1\sim N$ 。每个牧场里住着一头奶牛。连接这些牧场的有 $P$ 条道路，每条道路都是双向的。第 $j$ 条道路连接的是牧场 $S_j$ 和 $E_j$ ，通行需要 $L_j$ 的时间。两牧场之间最多只有一条道路。约翰打算在保持各牧场连通的情况下去掉尽量多的道路。

约翰知道，在道路被强拆后，奶牛会非常伤心，所以他计划拆除道路之后就去忽悠她们。约翰可以选择从任意一个牧场出发开始他维稳工作。当他走访完所有的奶牛之后，还要回到他的出发地。每次路过牧场i的时候，他必须花 $C_i$ 的时间和奶牛交谈，即使之前已经做过工作了，也要留下来再谈一次。注意约翰在出发和回去的时候，都要和出发地的奶牛谈一次话。请你计算一下，约翰要拆除哪些道路，才能让忽悠奶牛的时间变得最少？

输入格式

* Line $1$ : Two space-separated integers: $N$ and $P$

* Lines $2\sim N+1$ : Line $i+1$ contains a single integer: $C_i$

* Lines $N+2\sim N+P+1$ : Line $N+j+1$ contains three space-separated integers: $S_j$ , $E_j$ , and $L_j$

输出格式

* Line 1: A single integer, the total time it takes to visit all the cows (including the two visits to the cow in your sleeping-pasture)

样例

思路

若只考虑行走时间作为权值，会存在有的牛需要非常长的时间"安慰"，最终得出错误答案（以行走时间走最短路，再dfs遍历所有点，尝试找最小值）。

因此，需要将"安慰奶牛"和行走一起作为边的权值（往返该条边及安慰该条边两端的奶牛），得到的最小生成树还需要加上最小的安慰奶牛时间（以该点作为起点）。

CODE

struct DSU
{
    vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {init(n);}
    
    void init(int n) 
    {
        f.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }
    
    int find(int x) 
    {
        while (x != f[x])
            x = f[x] = f[f[x]];
        return x;
    }
    
    bool same(int x, int y) {return find(x) == find(y);}
    
    bool merge(int x, int y) 
    {
        x = find(x);
        y = find(y);
        if (x == y) 
            return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {return siz[find(x)];}
};
struct node
{
    int st, to, len;
    bool operator<(const node y)  const {return len < y.len;}
};

const int N = 1E4 + 10;
bool vis[N];

void solve()
{
    int n, m, mn = ll_MAX - 1;
    cin >> n >> m;
    DSU dsu(n);
    vector<int> time(n + 1);
    vector<node> v;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i=1;i<=n;i++)
    {
        cin >> time[i];
        mn = min(time[i], mn);
    }
    for (int i=0;i<m;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({a, b, c * 2 + time[a] + time[b]});
    }
    sort(all(v));
    auto Kruskal = [&]() -> int
    {
        int ans = 0, cnt = 0;
        for (int i=0;i<(int)v.size();i++)
        {
            auto cur = v[i];
            if (!dsu.same(cur.st, cur.to))
            {
                cnt ++;
                ans += cur.len;
                dsu.merge(cur.st, cur.to);
                adj[cur.st].push_back({cur.to, cur.len});
                adj[cur.to].push_back({cur.st, cur.len});
            }
        }
        return (cnt == n - 1 ? ans : -1);
    };
    cout << Kruskal() + mn;
}