Taxi

题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7172

题目大意：给定 n 个点的坐标 (x,y) 和权值 w，多次询问，每次给一个点的坐标，求该点到其它点 $min(|x_q-x_i|+|y_q-y_q|,w_i)$ 的最大值

解题思路：如果不考虑 w 的限制，就是一个经典问题，问一个点到其它点的最远曼哈顿距离

$\begin{aligned} &max(|x-x_i|+|y-y_i|)\\ =&max(x-x_i,-x+x_i)+max(y-y_i,-y+y_i)\\ =&max(x-x_i+y-y_i,x-x_i-y+y_i,-x+x_i+y-y_i,-x+x_i-y+y_i)\\ =&max(x+y-x_i-y_i,x-y-x_i+y_i,-x+y+x_i-y_i,-x-y+x_i+y_i) \end{aligned}$

只需要记录 $-x_i-y_i,-x_i+y_i,x_i-y_i,x_i+y_i$ 的最大值，然后就可以 $O(1)$ 查询某个点到其它点的最大值

考虑 w 的限制，按照 w 从小到大排序，预处理出每个后缀 $-x_i-y_i,-x_i+y_i,x_i-y_i,x_i+y_i$ 的最大值，对于每次询问，考虑任意一个点 k，如果设 d 为查询点到 $[k,k+1,k+2,...n]$ 曼哈顿距离的最大值，那么就只有两种情况

$w_k<d$ ，也就是说 k 前面点的贡献都小于 $w_k$ ，那么更新答案后新的区间就是 $[k+1,n]$
$w_k \ge d$ ，也就是说 k 后面点的贡献都小于 $d$ ，那么更新答案后新的区间就是 $[1,k-1]$

因此可以二分这个 k ，时间复杂度为 $O(nlog_n)$

struct node {
    int x, y, w;
};
int n, q;
node a[N];
int mx[N][4];
void solve() {
    cin >> n >> q;
    mx[n][0] = mx[n][1] = mx[n][2] = mx[n][3] = INT_MIN;
    lep(i, 0, n - 1) cin >> a[i].x >> a[i].y >> a[i].w;
    sort(a, a + n, [](const node& A, const node& B) { return A.w < B.w; });
    rep(i, n - 1, 0) {
        mx[i][0] = max(mx[i + 1][0], a[i].x + a[i].y);
        mx[i][1] = max(mx[i + 1][1], a[i].x - a[i].y);
        mx[i][2] = max(mx[i + 1][2], -a[i].x + a[i].y);
        mx[i][3] = max(mx[i + 1][3], -a[i].x - a[i].y);
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        int l = 0, r = n - 1, ans = INT_MIN;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int k = max({-x - y + mx[mid][0], -x + y + mx[mid][1],
                         x - y + mx[mid][2], x + y + mx[mid][3]});
            if (a[mid].w < k) {
                l = mid+1;
                ans = max(ans, a[mid].w);
            } else {
                r = mid-1;
                ans = max(ans, k);
            }
        }
        cout << ans << endl;
    }
}

Slayers Come

题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7154

题目大意：给定长度为 n 的怪物序列，每个怪物都有攻击力 $a_i$ 和生命值 $b_i$ ,你有 m 个技能，每个技能可以直接击败位置为 $x_i$ 的怪物，以及两个参数 $l_i$ 和 $r_i$ ，当一个怪物被击败时，它会攻击它两边的怪物，造成的伤害为 $a_i-l_i$ 和 $a_i+r_i$ ，只有当伤害大于等于怪物的生命值时才可以击败怪物，问击败所有的怪物至少一次有多少种方案数

解题思路：显然每个技能都有一个可以攻击的范围，考虑向右的情况， $a_i-b_{i+1} \ge r[j]$ 时，怪物 i+1 才可以被技能 j 击败，因此可以对 $a_i-b_{i}$ 从大到小排序，r 也从大到小排序，这样保证如果怪物 i 被技能 j 击败，那么 j 之后的技能都可以击败怪物 i 了，就可以使用并查集查询每个技能攻击范围的最右边，左边反之亦然

那么原问题就变成了有 n 个点，m 个区间，选取任意的区间覆盖 $[1,n]$ 的方案数。动态规划求解，将区间按照 r 从小到大排序，定义 $dp[i]$ 表示覆盖 $[1,i]$ 的方案数，加入一个区间 $[l,r]$ 时

$dp[r]+=\sum_{l-1}^{r} dp[i]\\dp[i]_{0\le i\le l-2}=dp[i]*2$

用区间求和，区间乘法，单点加法的线段树维护即可

ll fa[N];
ll get(ll x) {
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
void merge(ll x, ll y) { fa[get(x)] = get(y); }
struct w {
    ll v, id;
};
struct node {
    ll x, l, r, id;
};
ll n, m, a[N], b[N], f[N];
w c[N];
node que[N];
PII s[N];
struct seg {
    ll x, y;
    ll v, mul, ad;
};
seg t[N << 2];

void update(ll bh) {
    t[bh].v = t[bh << 1].v + t[(bh << 1) + 1].v;
    t[bh].v %= p;
}

void push(ll bh)  
{
    ll lc = bh << 1;
    ll rc = (bh << 1) + 1;
    if (t[bh].mul != 1 || t[bh].ad != 0) {
        t[lc].v = ((t[lc].v * t[bh].mul) % p +
                   ((t[lc].y - t[lc].x + 1) * t[bh].ad) % p) %
                  p;
        t[lc].mul = (t[bh].mul * t[lc].mul) % p;
        t[lc].ad = (t[lc].ad * t[bh].mul) % p + t[bh].ad;
        t[lc].ad %= p;

        t[rc].v = ((t[rc].v * t[bh].mul) % p +
                   ((t[rc].y - t[rc].x + 1) * t[bh].ad) % p) %
                  p;
        t[rc].mul = (t[bh].mul * t[rc].mul) % p;
        t[rc].ad = (t[rc].ad * t[bh].mul) % p + t[bh].ad;
        t[rc].ad %= p;

        t[bh].ad = 0;
        t[bh].mul = 1;
    }
    return;
}

void build(ll bh, ll l, ll r) {
    t[bh].x = l;
    t[bh].y = r;
    t[bh].mul = 1;
    t[bh].ad = 0;
    if (l == r) {
        t[bh].v = f[l] % p;
        return;
    }
    ll mid = (l + r) >> 1;
    build(bh << 1, l, mid);
    build(bh << 1 | 1, mid + 1, r);
    update(bh);
}

void add(ll bh, ll l, ll r, ll val) {
    push(bh);
    if (t[bh].x >= l && t[bh].y <= r) {
        t[bh].ad += val;
        t[bh].ad %= p;
        t[bh].v = (t[bh].v * t[bh].mul % p +
                   ((t[bh].y - t[bh].x + 1) * t[bh].ad) % p) %
                  p;
        return;
    }
    ll mid = (t[bh].x + t[bh].y) >> 1;
    if (l <= mid) add(bh << 1, l, r, val);
    if (r > mid) add((bh << 1) + 1, l, r, val);
    update(bh);
}

void multi(ll bh, ll l, ll r, ll val) {
    push(bh);
    if (t[bh].x >= l && t[bh].y <= r) {
        t[bh].mul *= val;
        t[bh].mul %= p;
        t[bh].v = (t[bh].v * t[bh].mul % p +
                   ((t[bh].y - t[bh].x + 1) * t[bh].ad) % p) %
                  p;
        return;
    }
    ll mid = (t[bh].x + t[bh].y) >> 1;
    if (l <= mid) multi(bh << 1, l, r, val);
    if (r > mid) multi((bh << 1) + 1, l, r, val);
    update(bh);
}

ll ask(ll bh, ll l, ll r) {
    push(bh);
    if (t[bh].x >= l && t[bh].y <= r) return t[bh].v % p;
    ll ans = 0;
    ll mid = (t[bh].x + t[bh].y) >> 1;
    if (l <= mid) ans += ask(bh << 1, l, r);
    if (r > mid) ans += ask((bh << 1) + 1, l, r);
    return ans % p;
}

void solve() {
    cin >> n >> m;
    lep(i, 1, n) cin >> a[i] >> b[i];
    lep(i, 1, n - 1) {
        c[i].v = a[i] - b[i + 1];
        c[i].id = i;
    }
    lep(i, 1, m) {
        cin >> que[i].x >> que[i].l >> que[i].r;
        que[i].id = i;
    }
    lep(i, 1, n) fa[i] = i;
    sort(c + 1, c + n, [](const w& A, const w& B) { return A.v > B.v; });
    sort(que + 1, que + 1 + m,
         [](const node& A, const node& B) { return A.r > B.r; });
    int i = 1, j = 1;
    while (j <= m) {
        if (c[i].v >= que[j].r && i < n) {
            merge(c[i].id, c[i].id + 1);
            i++;
        } else {
            s[que[j].id].se = get(que[j].x);
            j++;
        }
    }
    lep(i, 2, n) {
        c[i].v = a[i] - b[i - 1];
        c[i].id = i;
    }
    lep(i, 1, n) fa[i] = i;
    sort(c + 2, c + n + 1, [](const w& A, const w& B) { return A.v > B.v; });
    sort(que + 1, que + 1 + m,
         [](const node& A, const node& B) { return A.l > B.l; });
    i = 2, j = 1;
    while (j <= m) {
        if (c[i].v >= que[j].l && i <= n) {
            merge(c[i].id, c[i].id - 1);
            i++;
        } else {
            s[que[j].id].fi = get(que[j].x);
            j++;
        }
    }
    sort(s + 1, s + 1 + m,
         [](const PII& A, const PII& B) { return A.se < B.se; });
    lep(i, 1, n + 1) f[i] = 0;
    f[1] = 1;
    build(1, 1, n + 1);
    lep(i, 1, m) {
        add(1, s[i].se + 1, s[i].se + 1, ask(1, s[i].fi, s[i].se + 1) % p);
        if (s[i].fi >= 2) multi(1, 1, s[i].fi - 1, 2);
    }
    cout << ask(1, n + 1, n + 1) % p << endl;
}

388535 (Hard Version)

题目链接：https://codeforces.com/contest/1658/problem/D2

题目大意：给定 l 和 r，再给定数组 a ,数组 a 中的元素是由 l 到 r 的一个排列依次异或 x 得到的，求出 x 的值

解题思路：由于原数组是一个排列，因此数组 a 中的元素互不相同，因此可以枚举 x ，只要 x 异或 $a_i$ 的最大值等于 r ，最小值等于 l ，那么这个 x 就满足条件，可以用 0-1 字典树维护，至于枚举 x ，由于存在 $a_i\oplus x=l$ ，所以 $x=a_i \oplus l$ ，时间复杂度为 $O(17n)$

int l, r;
int a[N];
int net[N][2], cnt, num[N];
void init() {
    net[0][0] = net[0][1] = 0;
    cnt = 1;
}
void insert(int n) {
    int cur = 0;
    for (int i = 31; i >= 0; --i) {
        int bit = n >> i & 1;  // 求出当前位并插入
        if (!net[cur][bit]) {
            net[cnt][0] = net[cnt][1] = 0;
            net[cur][bit] = cnt++;
        }
        cur = net[cur][bit];
    }
    num[cur] = n;
}
int find_max(int x)  // 找到与x异或最大的那个数
{
    int cur = 0;
    for (int i = 31; i >= 0; --i) {
        int bit = x >> i & 1;
        if (net[cur][bit ^ 1])  // 优先走与当前位不同的路径
            cur = net[cur][bit ^ 1];
        else
            cur = net[cur][bit];
    }
    return x ^ num[cur];
}
int find_min(int x)  // 找到与x异或最小的那个数
{
    int cur = 0;
    for (int i = 31; i >= 0; --i) {
        int bit = x >> i & 1;
        if (net[cur][bit]) // 优先走与当前位相同的路径
            cur = net[cur][bit];
        else
            cur = net[cur][bit ^ 1];
    }
    return x ^ num[cur];
}
void solve() {
    init();
    cin >> l >> r;
    lep(i, l, r) cin >> a[i], insert(a[i]);
    lep(i, l, r) {
        int x = a[i] ^ l;
        if (find_max(x) == r && find_min(x) == l) {
            cout << x << endl;
            return;
        }
    }
}

Bitwise Queries (Easy Version && Hard Version)

题目链接：https://codeforces.com/contest/1451/problem/E2

题目大意：交互题，给定一个长度为 $n(4\le n\le 2^{16})$ 的隐藏数组 a，数组元素值未知，保证 n 为 2 的幂次方，数组值的大小在 $[0,n-1]$ 之间。有三种类型的查询

$AND\ i \ j$ ，查询 $a[i]\&a[j]$ 的值 $(i\ne j)$
$OR \ i \ j$ ，查询 $a[i]|a[j]$ 的值 $(i\ne j)$
$XOR\ i \ j$ ，查询 $a[i]\oplus a[j]$ 的值 $(i\ne j)$

找出数组所有元素的值，Easy 版本查询次数为 n+2，Hard 版本查询次数为 n+1

解题思路：

Easy：因为存在异或查询，如果知道任意一个数的具体数值，异或一下就可以得到其它数值的大小，根据 $a+b=a\oplus b+2(a\&b)$ ，可以用六次操作得到三个方程式，算出三个数的具体大小，但这样的总操作次数为 n+3 次，考虑异或的传递性 $a\oplus b \oplus b \oplus c=a\oplus c$ ，可以优化掉一次，满足 n+2 次查询

Hard:上述方法只需在 $n\ge3$ 的情况便可以使用，但没有用题目的特殊条件: 保证 n 为 2 的幂次方，数组值的大小在 $[0,n-1]$ 之间。根据此条件可以将原数组分成以下两种情况：

数组的元素互不相同，意味着 $[0,n-1]$ 各出现一次，对于 $2\le i \le n$ ，先查询 $(1,i)$ 的异或值，由于数组元素互不相同，必定存在一个下标 j ，满足 $a[1]\oplus a[j]=n-1$ ,那么可以直接得到 $a[1]|a[j]=n-1,a[1]\&a[j]=0$ ，此时只需要再找到一个下标不同于 1 和 j 的下标 k，查询 $(j,k)$ 和 $(1,k)$ 的或值或与值，就可以得到 $1,j,k$ 这三个数的具体数值，然后通过一开始的异或值，便可以在 n+1 次查询得到所有元素的值
数组中出现重复元素，依然对于 $2\le i \le n$ ，先预处理 $(1,i)$ 的异或值，由于存在重复元素，一定至少存在两个下标 j 和 k ，满足 $a[1]\oplus a[j]=a[1] \oplus a[k]$ ，那么只需要查询 $(j,k)$ 和 $(1,j)\ or\ (1,k)$ 的或值或与值，得到 $1,j,k$ 这三个数的具体数值，查询次数依然也是 n+1 次

int get_or(int a, int b) {
    cout << "OR " << a << " " << b << endl;
    int d;
    cin >> d;
    return d;
}
int get_and(int a, int b) {
    cout << "AND " << a << " " << b << endl;
    int d;
    cin >> d;
    return d;
}
int get_xor(int a, int b) {
    cout << "XOR " << a << " " << b << endl;
    int d;
    cin >> d;
    return d;
}
int n;
int v[N], d[N];
vector<int> id[N];
void solve() {
    cin >> n;
    lep(i, 2, n) d[i] = get_xor(1, i);
    int flag = 0;
    int l = 0, r = 0;
    lep(i, 2, n) { id[d[i]].emplace_back(i); }
    for (auto i : id) {
        if (i.size() >= 2) {
            flag = 1;
            l = i[0];
            r = i[1];
            break;
        }
    }
    if (flag) {
        int x = get_and(1, l);
        int y = get_and(l, r);
        int a = d[l] + 2 * x;
        int b = 2 * y;
        v[1] = (2 * a - b) / 2;
        lep(i, 2, n) v[i] = d[i] ^ v[1];
    } else {
        int k = 0;
        lep(i, 2, n) {
            if (d[i] == n - 1) {
                k = i;
                break;
            }
        }
        int j = 0;
        lep(i, 2, n) {
            if (i != k) {
                j = i;
                break;
            }
        }
        int x = get_and(1, j);
        int y = get_and(j, k);
        int a = d[j] + 2 * x;
        int b = (d[j] ^ d[k]) + 2 * y;
        int c = d[k];
        v[1] = (a - b + c) / 2;
        lep(i, 2, n) v[i] = d[i] ^ v[1];
    }
    cout << "! ";
    lep(i, 1, n) cout << v[i] << " ";
    cout << endl;
}

Algorithm Solution

Algorithm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

September 2022 Algorithm Solution 上一篇

July 2022 Algorithm Solution 下一篇

August 2022 Algorithm Solution

Taxi

Slayers Come

388535 (Hard Version)

Bitwise Queries (Easy Version && Hard Version)