CF1618G Trader Problem

原题链接 ← Click it
这题难产了快一个月终于决定要攻克下来

题目大意：现在你手里有\(n\)件物品，它们的价值分别是\(a_1,a_2,...,a_n\)，你现在可以和一个商人交换物品，他有\(m\)件物品，价值分别为\(b_1,b_2,...,b_m\)，价值为\(w\)的物品，最多可以与价值为\(w + k\)的物品交换，现在你有\(q\)次询问，每次询问一个\(k\)，问你可以交换到的总物品的价值最大值。

解题思路：考虑并查集维护每个物品能交换到的所以物品的集合，在每个集合中从大到小依次取出该集合中属于初始物品的个数个物品进行求和。优化1：对于任意的一个\(k\)，你对每一件物品询问它能交换到的价值最大值都需要从原始的价值出发，因为你不能保证下一次一定能从已经交换后的价值发出(时间复杂度\(O(qn^2)\))，所以考虑\(q\)次离线询问，对\(k_i\)进行排序后，每次询问都和合理利用上次询问的信息。优化2：因为每次询问合并的物品只需要满足和前一个相邻物品的差值 $ > k_{i - 1}\ &&\ <= k_i\(，所以可以对每个相邻物品的价值差进行排序，用双指针将每次询问需要进行合并的序号都加入队列。优化3：每次合并之后都需要对重新计算每个集合对答案的贡献，如果是减去合并前集合的贡献再加上合并后集合的贡献，时间复杂度达到\)O(n)\(，但是如果预先求前缀和，每次重新计算贡献的时间复杂度就达到了\)O(1)$。

参考代码：

typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f, N = 1e6 + 10;
struct DSU {
    int N;
    vector<int> pr, rnk;
    DSU(int n) : N(n) {
        pr.resize(N);
        rnk.resize(N);
        for(int i = 0; i < N; i ++) {
            pr[i] = i;
            rnk[i] = 1;
        }
    }
    int root(int x) {
        return pr[x] == x ? x : pr[x] = root(pr[x]);
    }
    bool same(int a, int b) {
        return root(a) == root(b);
    }
    bool unite(int a, int b) {
        int A = root(a), B = root(b);
        if(A == B) return 0;
        if(rnk[A] == rnk[B]) rnk[A] ++;
        else if(rnk[A] > rnk[B]) swap(rnk[A], rnk[B]);
        pr[A] = B;
        return 1;
    }
};
void solve() {
    int n, m, q; ll sum = 0;
    cin >> n >> m >> q;
    vector<PII> a(n + m);
    vector<ll> b(n + m + 1);
    vector<int> siz(n + m);//每个集合中属于初始物品的个数
    vector<PII> derta;
    for(int i = 0; i < n + m; i ++) {
        cin >> a[i].first;
        //标记初始物品，并求初始价值和
        if(i < n) {
            a[i].second = 1;
            sum += a[i].first;
        }
    }
    sort(a.begin(), a.end());
    for(int i = 0; i < n + m; i ++) {
        if(i) derta.push_back({a[i].first - a[i - 1].first, i});
        siz[i] += a[i].second;
    }
    for(int i = 1;i < n + m + 1; i ++) {
        b[i] = b[i - 1] + a[i - 1].first;
    }
    vector<PII> query(q);
    vector<vector<int>> qa(q);
    vector<ll> res(q);
    for(int i = 0; i < q; i ++) {
        cin >> query[i].first;
        query[i].second = i;
    }
    sort(query.begin(), query.end());
    sort(derta.begin(), derta.end());
    for(int i = 0, j = 0; i < q && j < n + m - 1; i ++) {
        while(j < n + m - 1 && derta[j].first <= query[i].first) {
            qa[i].push_back(derta[j].second);
            j ++;
        }
    }
    DSU tree(n + m);
    for(int i = 0; i < q; i ++) {
        int k = query[i].first, lx = query[i].second;
        for(auto x : qa[i]) {
            if(tree.unite(x - 1, x)) {
                sum -= b[x] - b[x - siz[x - 1]];
                int tmp = tree.root(x);
                sum += b[tmp + 1 - siz[tmp]] - b[tmp + 1 - siz[tmp] - siz[x - 1]];
                siz[tmp] += siz[x - 1];
            }
        }
        res[lx] = sum;
    }
    for(int i = 0; i < q; i ++) {
        cout << res[i] << '\n';
    }
}

tag：并查集、双指针、前缀和、贪心、离线询问

推荐这些技术文章：

Educational Codeforces Round 129(补题)

C. Double Sort
题意
让我们对两个数组进行排序，每次进行排序要同时将a,b数组同时进行排序，问能不能将数组变为非递减数组
算法(前缀和+手动模拟排序)
我们先找出每个数在数组的位置的范围，每个数在分别的数组上面的位置相对是稳定的，如果对应位置的ai,bi范围相交，那么我们就可以去max(l1,l2),即可。找位置可以使用前缀和找出。
C++
// Problem: C. Doubl...

王道机试指南题解（C/C++版）

第 2 章 经典入门
一 排序
例 2.1 排序

代码 2.1
冒泡排序（时间复杂度 \(O(n^2)\)）
#include <iostream>
using std::cin; using std::cout; using std::endl;

#include <vector>
using std::vector;

#include <algorith...

2022 Google Kick Start Round C

New Password

题意
给一个字符串，问最少几步能补到满足下列条件：

长度至少为7
至少有一个小写字母
至少有一个大写字母
至少有一个数字
至少有一个特殊符号

思路
先补充到满足后面4个条件，大概就是每种类型的字符没有的话就随便加一个。
现在只可能不满足长度条件，可以添加任意字符知道长度大于等于7。

AC代码
// Problem: New Password
// Cont...

Educational Codeforces Round 129 (Rated for Div. 2) A-D

Educational Codeforces Round 129 (Rated for Div. 2) A-D
A
题目
https://codeforces.com/contest/1681/problem/A
题解
思路
知识点：贪心。
先手的一方拥有大于等于对方最大牌的牌即可获胜，所以考虑取两组牌各自的最大值进行比较。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码
#i...

2019-2020 XX Open Cup, Grand Prix of Korea

2019-2020 XX Open Cup, Grand Prix of Korea
比赛收获
本场贡献：et3_tsy ：G提供了思路，过了H，H爆了int，贡献WA一发，J有想法，调了1hr后，发现在特例情况复杂度退化，假了
​ 1427314831a：过了A
​ Ryker0923 ：过了G，提供了A的思路
一共三道题
总结：本场暴露两个问题：
1）后期乏力
前两个小时过了...

Educational Codeforces Round 129 (Rated for Div. 2)

Educational Codeforces Round 129 (Rated for Div. 2)
https://codeforces.com/contest/1681
A. Game with Cards
直接比较最大的谁更大，谁就是赢家。
相等情况下，先手胜
#include <bits/stdc++.h>

using namespace std;

void solve...

牛客挑战赛60

比较简单的签到题

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
int T;
ll gcd(ll aa,ll bb){
if(bb)return gcd(bb,aa%bb);
return aa;
}
int main(...

Educational Codeforces Round 129 (Rated for Div. 2) A - D 题解

传送门
A. Game with Cards
看最大的在谁那，谁就赢
如果最大的都一样，则先手赢
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#i...

[ABC252EX] K-th Beautiful Necklace 题解

Meet in the middle+Trie
Statement
给定 \(n\) 个珠子，每一个有颜色 \(d_i\) 和权值 \(v_i\) ，颜色有且仅有 \(C\) 种，并且保证每一个颜色至少出现一次
每次可以选出 \(C\) 个不同颜色的珠子，定义权值是所选珠子的异或和
求第 \(K\) 大权值
\(C\le n\le 70,v_i\le 2^{60},K\le 10^{18}\)
...

UVA1589 象棋 Xiangqi

这题考察我们的大脑体力，非常难调，我花了2小时，要是在区域赛里做着题，我碰都不碰，没有大样例非常难受。
分析如下：

中国象棋，见百度百科
就是考虑当前情况下将军是不是已经给将死了

考虑：

飞将
将军吃掉了红色棋子的情况
马脚问题
将军只能在一定的区域内移动
注意边界情况
善用工具来debug，我用了udebug，里面有一个大样例，cmd我是可以看到输入的，但吞了我一部分输出，搞得我虚空调试...