牛客小白月赛 126

写一些奇奇怪怪的题解

B 小红写谱

（暴力解法）

发现相同的数字放在一起显然会使答案最优，那么不同的数字呢？注意到 $a_i$ 的范围是 $1 \le a_i \le 8$ ，我们直接暴力预处理，用 $mask$ 来进行位存取，之后查询答案即可。时间复杂度为 $O(T + 2^8 \times 8)$ 。

int ans[1 << 9];
void build(){
    for(int i = 0;i < (1 << 9);i++)    ans[i] = INT_MAX;
    for(int mask = 1;mask < (1 << 9);mask++){
        vector<int> p;
        for(int i = 1;i <= 8;i++){
            if(mask & (1 << i)){
                p.push_back(i);
            }
        }
        if(p.empty()) continue;
        if(p.size() == 1){
            ans[mask] = 0;
            continue;
        }
        sort(p.begin(), p.end());
        int t = INT_MAX;
        do{
            int tmp = 0;
            for(int i = 0;i < p.size() - 1;i++){
                tmp += min(abs(p[i] - p[i + 1]), 8 - abs(p[i] - p[i + 1]));
            }
            t = min(t, tmp);
        }while(next_permutation(p.begin(), p.end()));
        ans[mask] = t;
    }
}
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    int mask = 0;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        mask |= (1 << a[i]);
    }
    cout << ans[mask] << "\n";
}

D 小红越级（easy）

解法一：差分（同题解）

alt

如图，考虑除了 $a$ 和 $b$ 左右两端的 $0$ 以外，其余位置都是 $1$ 的贡献，那我们可以利用差分数组进行累加 $1$ 的处理。时间复杂度为 $O(T \times (n + q))$ 。

#define MAXN 200005
int arr[MAXN];

void clear(int n){
    for(int i = 1;i <= n;i++){
        arr[i] = 0;
    }
}
void setNum(int l, int r, int num, int n){
    if(l < 1 || r < 1 || l > n || r > n || r < l)    return;
    arr[l] += num;
    arr[r + 1] -= num;
}
void build(int n){
    for(int i = 2;i <= n;i++){
        arr[i] += arr[i - 1];
    }
}
void solve(){
    int n, q;
    cin >> n >> q;
    clear(n);
    for(int i = 0;i < n;i++){
        int a, b;
        cin >> a >> b;
        int mn = min(a, b);
        int mx = max(a, b);
        setNum(1, mn - 2, 1, n);
        setNum(mn + 2, mx - 2, 1, n);
        setNum(mx + 2, n, 1, n);
    }
    build(n);
    for(int i = 0;i < q;i++){
        int x;
        cin >> x;
        cout << arr[x] << " ";
    }    cout << "\n";
}

解法二： $\text{set}$

对于每个位置 $x$ ，我们查询 $[x - 1, x + 1]$ 里包含了哪些下标，这些下标的贡献是 $0$ ，那么对于 $x$ 位置的答案就是 $n$ 减去贡献的下标个数。

用类似邻接表的方式存取下标，然后用 $\text{set}$ 维护即可。预处理每个位置的答案，可以做到时间复杂度为 $O(T\times (n \times logn + q))$ 。

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n), b(n), ans(n + 1);
    vector<vector<int>> pos(n + 1);
    for(int i = 0;i < n;i++){
        cin >> a[i] >> b[i];
        pos[a[i]].push_back(i);
        pos[b[i]].push_back(i);
    }
    for(int x = 1;x <= n;x++){
        set<int> st;
        if(x - 1 >= 1){
            for(int l : pos[x - 1]){
                st.insert(l);
            }
        }
        for(int m : pos[x]){
            st.insert(m);
        }
        if(x + 1 <= n){
            for(int r : pos[x + 1]){
                st.insert(r);
            }
        }
        ans[x] = n - st.size();
    }
    for(int i = 0;i < q;i++){
        int x;
        cin >> x;
        cout << ans[x] << " ";
    }    cout << "\n";
}

G 小红越级（hard）

alt

如图，类似 $\text{easy}$ 的解法，我们考虑除了 $a$ 和 $b$ 以外，其余位置都是公差为 $1$ 或 $-1$ 的等差数列递增贡献，那我们可以利用等差数列差分数组进行处理。时间复杂度为 $O(T \times (n + q))$ 。

using ll = long long;
#define MAXN 200005
ll arr[MAXN];

void clear(int n){
    for(int i = 1;i <= n + 2;i++){
        arr[i] = 0;
    }
}
void setNum(int l, int r, ll s, ll e, ll d, int n){
    if(l < 1 || r < 1 || l > n || r > n || r < l)    return;
    arr[l] += s;
    arr[l + 1] += d - s;
    arr[r + 1] -= d + e;
    arr[r + 2] += e;
}
void build(int n){
    for(int i = 2;i <= n;i++){
        arr[i] += arr[i - 1];
    }
    for(int i = 2;i <= n;i++){
        arr[i] += arr[i - 1];
    }
}
void solve(){
    int n, q;
    cin >> n >> q;
    clear(n);
    for(int i = 0;i < n;i++){
        int a, b;
        cin >> a >> b;
        int mn = min(a, b);
        int mx = max(a, b);
        if(mn != 1)
            setNum(1, mn - 1, mn - 2, 0, -1, n);
        int len = mx - mn;
        if(len % 2 == 1){
            setNum(mn + 1, mn + len / 2, 0, len / 2 - 1, 1, n);
            setNum(mx - len / 2, mx - 1, len / 2 - 1, 0, -1, n);
        }else{
            setNum(mn + 1, mn + len / 2, 0, len / 2 - 1, 1, n);
            setNum(mx - len / 2 + 1, mx - 1, len / 2 - 2, 0, -1, n);
        }
        if(mx != n)
            setNum(mx + 1, n, 0, n - mx - 1, 1, n);
    }
    build(n);
    for(int i = 0;i < q;i++){
        int x;
        cin >> x;
        cout << arr[x] << " ";
    }    cout << "\n";
}