F. Yet Another Segments Subset

题目链接： F. Yet Another Segments Subset

题意：

给定一些线段，问最多能够选出多少线段，使得选出的线段中，两两之间要么不相交（没有任何一个共同点），要么一个线段完全包含另一个线段。

解题思路：

首先要想到用区间 DP ，由于不相交和包含都是相对关系，与具体数值无关，可以用离散化坐标来处理数据较大的问题。

定义 $f[i][j]$ 为在所有 $[i,j]$ 范围内的线段中，符合题目要求的所有选法，属性是线段的最大数量。

题目说明了不会出现重复的线段，这就非常友好了。

首先 $f[i+1][j-1]$ 和 $f[i+1][j]$ 还有 $f[i][j-1]$ 可以直接更新 $f[i][j]$ ，因为它们是 $f[i][j]$ 的子集。

然后枚举以 $i$ 为起点的线段 $[i,r]$ ，用 $f[i][r]+f[r+1][j]$ 更新即可。

要注意到的是如果存在 $[i,j]$ 这样的线段，那么应该直接给 $f[i][j]$ 加 $1$ ，因为它包含了区间内所有的线段。

这里不用再枚举以 $j$ 为终点的线段了，因为回到 DP 的定义，其实已经包含在内了。

代码如下：

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T -- )
    {
        int n;
        cin >> n;
        vector<int> p;
        vector<pair<int, int>> seg(n);
        for (auto &[l, r] : seg)
        {
            cin >> l >> r;
            p.emplace_back(l);
            p.emplace_back(r);
        }
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end());
        int m = (int)p.size();
        vector<vector<int>> L(m + 1);
        for (auto &[l, r] : seg)
        {
            l = (int)(lower_bound(p.begin(), p.end(), l) - p.begin()) + 1;
            r = (int)(lower_bound(p.begin(), p.end(), r) - p.begin()) + 1;
            L[l].emplace_back(r);
        }
        vector<vector<int>> f(m + 5, vector<int>(m + 5));
        for (int len = 1; len <= m; len ++ )
            for (int i = 1; i + len - 1 <= m; i ++ )
            {
                int j = i + len - 1;
                f[i][j] = max(f[i + 1][j], f[i][j - 1]);
                f[i][j] = max(f[i][j], f[i + 1][j - 1]);
                int t = 0;
                for (auto &r : L[i])
                {
                    t |= (int)(r == j);
                    if (r + 1 <= j) f[i][j] = max(f[i][j], f[i][r] + f[r + 1][j]);
                }
                f[i][j] += t;
            }
        cout << f[1][m] << '\n';
    }
    return 0;
}

D. A Game with Traps

题目链接： D. A Game with Traps

题意：

一开始你和 $m$ 个士兵在数轴的 $0$ 位置，第 $i$ 个士兵的能力值是 $a_i$ ，数轴上有 $k$ 个陷阱，第 $i$ 个陷阱在 $l_i$ 上，你可以走到 $r_i$ 解除它，这个陷阱会对能力值小于 $d_i$ 的士兵产生影响，也就是说如果某个能力值小于 $d_i$ 的士兵需要走过这个陷阱的话，必须先解除这个陷阱。每走一步花费 $1$ 秒，你可以自己行动，也可以走到士兵所在的位置带士兵一起行动，问你在 $t$ 秒内，最多能够带多少个士兵到达 $n+1$ 位置。

解题思路：

首先二分带士兵的数量，如果当前带 $x$ 个士兵，那么一定要花费的时间是从起点到终点，也就是 $n+1$ ，那么处理每个陷阱的话，可以发现就是会在数轴上重复走一些来回，让这些重复的长度最小即可。

带能力值最大的 $x$ 个士兵显然会更好，然后找出所有会影响这些士兵的陷阱，对于每个陷阱，需要你自己走过去解除的路程是至少是 $2\times (r-(l-1))$ ，也就是两个 $[l-1,r]$ 区间，因此对于这些陷阱，做一次区间合并，求它们的交集的长度即可。

代码如下：

#include <tuple>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m, k, t;
    cin >> m >> n >> k >> t;
    vector<int> a(m + 1);
    // 坐标从 1 开始，二分时方便找到无解的情况
    a[0] = INF;
    for (int i = 1; i <= m; i ++ ) cin >> a[i];
    sort(a.rbegin(), a.rend());
    vector<tuple<int, int, int>> trap(k);
    for (auto &[l, r, d] : trap) cin >> l >> r >> d;
    auto check = [&](int x) -> bool
    {
        vector<pair<int, int>> seg;
        for (auto &[l, r, d] : trap)
            if (d > x)
                seg.emplace_back(l - 1, r);
        sort(seg.begin(), seg.end());
        // 区间合并求交集长度
        int len = 0, pos = -INF;
        for (auto &[l, r] : seg)
            if (r > pos)
            {
                if (l < pos) len += r - pos;
                else len += r - l;
                pos = r;
            }
        return len * 2 + n + 1 <= t;
    };
    int l = 0, r = m;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(a[mid])) l = mid;
        else r = mid - 1;
    }
    cout << r << '\n';
    return 0;
}

C2. Power Transmission (Hard Edition)

题目链接： C2. Power Transmission (Hard Edition)

题意：

给定若干个点，求两点形成的所有直线有多少对是相交的。

解题思路：

这题思路不难，主要是想记录一下处理直线和斜率的方法。

首先直线可以表示成 $ax-by=c$ 的形式，对于两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$ ，它们所形成的直线的 $a=y_1-y_2$ ， $b=x_1-x_2$ ，因此斜率就可以用一个数对 $(a,b)$ 来表示，简化成互质的形式，而且规定 $a>0$ ，如果 $a=0$ ，规定 $b>0$ 。

用一个 map 存储每种斜率存在哪些偏移量 $c$ ，也就是用一个 map 套一个 set ，对于相同斜率、相同偏移量的直线来说，它们是等价的，因此只统计第一条等价的直线即可。

代码如下：

#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    for (auto &[x, y] : p) cin >> x >> y;
    int tot = 0;
    long long res = 0;
    map<pair<int, int>, set<long long>> mp;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < i; j ++ )
        {
            auto [x1, y1] = p[i];
            auto [x2, y2] = p[j];
            int a = y1 - y2, b = x1 - x2;
            int g = __gcd(a, b);
            a /= g, b /= g;
            if (a < 0 || a == 0 && b < 0)
            {
                a = -a;
                b = -b;
            }
            pair<int, int> slope = {a, b};
            long long c = (long long)a * x1 - (long long)b * y1;
            if (!mp[slope].count(c))
            {
                // 所有直线减去与当前直线平行的直线
                res += tot - (int)mp[slope].size();
                tot ++ ;
                mp[slope].insert(c);
            }
        }
    cout << res << '\n';
    return 0;
}

G. To Go Or Not To Go?

题目链接： G. To Go Or Not To Go?

题意：

给定一个 $n \times m$ 矩阵，有些点是普通点，有些是特殊点，有些是不可达点，可以直接从一个特殊点走到另一个特殊点，如果从 $(x_1,y_1)$ 走到 $(x_2,y_2)$ ，花费 $g[x_1][y_1]+g[x_2][y_2]$ ，也可以从某个点走到与它相邻的四个点（非不可达点），花费为 $w$ ，问从左上角走到右下角的最小距离。

解题思路：

一开始用迪杰斯特拉，但认真计算过后发现边的数量其实很大，并不能这么搞。

首先要发现的是，如果通过特殊点穿越了两次，那么其实不如直接一次穿越，因此如果用了特殊点，最多只会用一次。

可以把路径分成两种情况，一种是没有用特殊点，这种直接用宽搜就行，第二种是用了一次特殊点的。

第二种的路径其实可以看成这样，通过若干次普通走法走到一个特殊点 $(x_1,y_1)$ ，花费了 $dist1[x_1][y_1]\times w$ ，穿越到另一个特殊点 $(x_2,y_2)$ ，花费了 $g[x_1][y_1]+g[x_2][y_2]$ ，走到终点，花费了 $dist2[x_2][y_2]\times w$ ，其中 $dist1$ 是起点到所有点的距离， $dist2$ 是终点到所有点的距离。

要想令 $dist1[x_1][y_1]\times w+g[x_1][y_1]+g[x_2][y_2]+dist2[x_2][y_2]\times w$ 尽量小，那么就令 $dist1[x_1][y_1]\times w+g[x_1][y_1]$ 尽量小，同时令 $dist2[x_2][y_2]\times w+g[x_2][y_2]$ 尽量小，直接枚举两部分的最小值即可。

注意事项：

因为数据较大，为了方便处理无解的情况， 宽搜时边权设为 $1$ ，具体计算的时候再乘上 $w$ 。

代码如下：

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const long long INF = 4e18;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    long long w;
    cin >> n >> m >> w;
    vector<vector<int>> g(n, vector<int>(m));
    vector<pair<int, int>> portal;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            cin >> g[i][j];
            if (g[i][j] > 0)
                portal.emplace_back(i, j);
        }
    auto bfs = [&](int sx, int sy, vector<vector<int>> &dist)
    {
        dist[sx][sy] = 0;
        vector<pair<int, int>> q;
        q.emplace_back(sx, sy);
        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        for (int qq = 0; qq < (int)q.size(); qq ++ )
        {
            auto [x, y] = q[qq];
            for (int i = 0; i < 4; i ++ )
            {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;
                if (g[tx][ty] == -1 || dist[tx][ty] != -1) continue;
                dist[tx][ty] = dist[x][y] + 1;
                q.emplace_back(tx, ty);
            }
        }
    };
    vector<vector<int>> dist1(n, vector<int>(m, -1));
    bfs(0, 0, dist1);
    vector<vector<int>> dist2(n, vector<int>(m, -1));
    bfs(n - 1, m - 1, dist2);
    long long res = INF;
    if (dist1[n - 1][m - 1] != -1) res = dist1[n - 1][m - 1] * w;
    long long mn1 = INF, mn2 = INF;
    for (auto &[x, y] : portal)
        if (dist1[x][y] != -1)
            mn1 = min(mn1, dist1[x][y] * w + g[x][y]);
    for (auto &[x, y] : portal)
        if (dist2[x][y] != -1)
            mn2 = min(mn2, dist2[x][y] * w + g[x][y]);
    res = min(res, mn1 + mn2);
    if (res == INF) res = -1;
    cout << res << '\n';
    return 0;
}

F2. Guess the K-th Zero (Hard version)

题目链接： F2. Guess the K-th Zero (Hard version)

题意：

交互题，给定一个 $01$ 序列，多次询问，每次询问第 $k$ 个 $0$ 的位置，一次询问处理完了以后，这次询问的第 $k$ 个 $0$ 变成 $1$ 。

解题思路：

如果只有一次询问，那直接用类似于快排找第 $k$ 大数的思想，很容易做，关键在于处理每次询问会变化这个问题。

可以用一个类似于线段树的思想，用一棵二叉树来维护整个数组的信息，处理每次询问的时候，随着二分的区间不断缩小，同时也维护二叉树的区间，如果当前区间的二叉树已经有信息了，那就不用询问了，否则才询问。

每次询问得到了结果，再从二叉树的底部往上，将更新的信息加上。

虽然会发现二叉树上有一半的节点维护的信息是不完整的，因为没有针对这些区间进行询问，但二分的过程自始至终是一样的，这些信息不完整的区间可以由另一半有完整信息的区间计算得到。

代码如下：

#include <vector>
#include <iostream>

using namespace std;

int ask(int l, int r)
{
    cout << "? " << l << ' ' << r << endl;
    cin >> r;
    return r;
}

void answer(int x)
{
    cout << "! " << x << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, T;
    cin >> n >> T;
    vector<int> tr(1 << 20, -1);
    while (T -- )
    {
        int k;
        cin >> k;
        int l = 1, r = n, p = 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            p = (p << 1);
            if (tr[p] == -1) tr[p] = ask(l, mid);
            int zero = (mid - l + 1) - tr[p];
            if (zero >= k) r = mid;
            else
            {
                k -= zero;
                p |= 1;
                l = mid + 1;
            }
        }
        answer(r);
        while (p)
        {
            tr[p] ++ ;
            p = (p >> 1);
        }
    }
    return 0;
}

E. Phoenix and Computers

题目链接： E. Phoenix and Computers

题意：

给定 $n$ 台电脑，每台电脑可以手动开启，如果与某台电脑相邻的两台电脑都开着，那么它会自动开，要开启所有电脑，求手动开启电脑的顺序有多少种。

解题思路：

如果有长度为 $len$ 的电脑，要求全部手动开，可以算出这样的方案有 $2^{len-1}$ 种。

定义 $f[i][j]$ 为前 $i$ 台电脑都开启，且有 $j$ 台电脑是自动开启的所有方案，属性是方案数。

首先 $f[i][0]$ 表示所有都是手动开，因此 $f[i][0]=2^{i-1}$ 。

然后在 $[1,i]$ 范围内枚举 $j$ ，再在 $[2,i-1]$ 枚举一个 $pos$ ，表示最右边的自动开的电脑位置，此时以 $pos$ 为分界线，前面一段是 $f[pos-1][j-1]$ ，后面一段是 $len=i-pos$ 台全部用手动开的电脑，方案数是 $2^{len-1}$ ，总共需要手动开的电脑是 $i-j$ 台，因此可以在这 $i-j$ 步中选择 $len$ 步去开最后一段的电脑，因此 $f[i][j]$ 就是所有 $f[pos-1][j-1]\times 2^{len-1} \times C^{len}_{i-j}$ 之和。

代码如下：

#include <iostream>

using namespace std;

const int N = 2010;

int n, mod;
int f[N][N];
int fact[N], infact[N];

int qp(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (long long)res * a % mod;
        a = (long long)a * a % mod;
        b >>= 1;
    }
    return res;
}

int C(int a, int b)
{
    if (a < b) return 0;
    else return (long long)fact[a] * infact[b] % mod * infact[a - b] % mod;
}

void init(int n)
{
    fact[0] = infact[0] = 1;
    fact[1] = infact[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        fact[i] = (long long)fact[i - 1] * i % mod;
        infact[i] = (long long)(mod - mod / i) * infact[mod % i] % mod;
    }
    for (int i = 2; i <= n; i ++ ) infact[i] = (long long)infact[i] * infact[i - 1] % mod;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> mod;
    init(N - 1);
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        f[i][0] = qp(2, i - 1);
        for (int j = 1; j <= i; j ++ )
            for (int pos = 2; pos < i; pos ++ )
            {
                int len = i - pos;
                f[i][j] = (f[i][j] + (long long)qp(2, len - 1) * f[pos - 1][j - 1] % mod * C(i - j, len) % mod) % mod;
            }
    }
    int res = 0;
    for (int j = 0; j <= n; j ++ ) res = (res + f[n][j]) % mod;
    cout << res << '\n';
    return 0;
}