头像

ITNXD




离线:3天前



ITNXD
17天前

详细请查看注释内容

参考代码:

typedef long long LL;
const LL mod = 1e9 + 7, INF = 1e18;
/*
    不能二分每个包裹放到哪个箱子,数量级太高!

    反过来可以这样:

    二分每个箱子在包裹序列的位置(小于等于该箱子的最后一个包裹位置)

    二分出来的每个箱子位置,可以将该包裹序列分为若干段,每一段都应该放入其之后的最近的箱子内!

    总浪费空间:要减去所有包裹的总尺寸sum,再加上每种箱子的尺寸乘以其使用的数量!

    时间复杂度:由于箱子总数量为1e5,因此最对会进行1e5log1e5次运算!

    注意:防止爆int,使用LL
*/

class Solution {
public:
    int minWastedSpace(vector<int>& a, vector<vector<int>>& bs) {
        sort(a.begin(), a.end());

        // 包裹尺寸总和
        LL sum = 0;
        for(int i = 0; i < a.size(); i ++) sum += a[i];

        int n = a.size();
        LL res = INF;
        for(auto &b : bs){
            sort(b.begin(), b.end());
            // 若最大箱子尺寸都小于包裹尺寸,则直接跳过
            if(b.back() < a.back()) continue;

            // t初值先将所有包裹尺寸减去
            LL last = -1, t = -sum;
            // 二分每个箱子在包裹序列的位置(小于等于该箱子的最后一个包裹位置)
            for(auto x : b){
                int l = last, r = n - 1;
                while(l < r){
                    int mid = l + r + 1 >> 1;
                    if(a[mid] <= x) l = mid;
                    else r = mid - 1;
                }
                // 该箱子无处可放,直接跳过
                if(r == last) continue;
                // 累加区间[last + 1, r]使用的x类型尺寸的箱子的总空间
                t += (r - last) * x;
                // 更新区间左端点
                last = r;
            }
            // 更新答案
            res = min(res, t);
        }
        if(res == INF) return -1;
        return res % mod;
    }
};



ITNXD
17天前
typedef long long LL;
const LL mod = 1e9 + 7, INF = 1e18;
/*
    不能二分每个包裹放到哪个箱子,数量级太高!

    反过来可以这样:

    二分每个箱子在包裹序列的位置(小于等于该箱子的最后一个包裹位置)

    二分出来的每个箱子位置,可以将该包裹序列分为若干段,每一段都应该放入其之后的最近的箱子内!

    总浪费空间:要减去所有包裹的总尺寸sum,再加上每种箱子的尺寸乘以其使用的数量!

    时间复杂度:由于箱子总数量为1e5,因此最对会进行1e5log1e5次运算!

    注意:防止爆int,使用LL
*/

class Solution {
public:
    int minWastedSpace(vector<int>& a, vector<vector<int>>& bs) {
        sort(a.begin(), a.end());

        // 包裹尺寸总和
        LL sum = 0;
        for(int i = 0; i < a.size(); i ++) sum += a[i];

        int n = a.size();
        LL res = INF;
        for(auto &b : bs){
            sort(b.begin(), b.end());
            // 若最大箱子尺寸都小于包裹尺寸,则直接跳过
            if(b.back() < a.back()) continue;

            // t初值先将所有包裹尺寸减去
            LL last = -1, t = -sum;
            // 二分每个箱子在包裹序列的位置(小于等于该箱子的最后一个包裹位置)
            for(auto x : b){
                int l = last, r = n - 1;
                while(l < r){
                    int mid = l + r + 1 >> 1;
                    if(a[mid] <= x) l = mid;
                    else r = mid - 1;
                }
                // 该箱子无处可放,直接跳过
                if(r == last) continue;
                // 累加区间[last + 1, r]使用的x类型尺寸的箱子的总空间
                t += (r - last) * x;
                // 更新区间左端点
                last = r;
            }
            // 更新答案
            res = min(res, t);
        }
        if(res == INF) return -1;
        return res % mod;
    }
};



ITNXD
17天前

详细请查看注释内容

参考代码:

class Solution {

    /*
        两种操作顺序互不影响,因此考虑第一种操作结束后的情况:

        偶数:(直接枚举)
            1010...10
            0101...01

            res = min(l[0][n - 1], l[1][n - 1]);

        奇数:(前两种情况直接枚举)
            1010...01
            0101...10

            res = min(l[0][n - 1], l[1][n - 1]);

            (后两种借助预处理前缀和数组解决)
            010101... 11 01 
            101010... 00 10

            对于后两种情况可以枚举11和00的位置来进行选择!

        我们可以使用前后缀分解思路来预处理几个数组:
            l[0][i]:表示[0, i]区间01(从左到右)相间的最少操作次数
            l[1][i]:表示[0, i]区间10(从左到右)相间的最少操作次数
            r[0][i]:表示[i, 0]区间01(从右到左)相间的最少操作次数
            r[1][i]:表示[i, 0]区间10(从右到左)相间的最少操作次数

        因此后两种情况最终答案就是:res = min(res, l[0][i] + r[1][i + 1], l[1][i] + r[0][i + 1]);
    */
public:
    int minFlips(string s) {
        int n = s.size();
        vector<int> l[2], r[2];
        l[0] = l[1] = r[0] = r[1] = vector<int>(n);
        // 预处理l[0][i],l[1][i]
        for(int i = 0; i < 2; i ++)
            for(int j = 0, c = 0, k = i; j < n; j ++, k ^= 1){
                if(k != s[j] - '0') c ++;
                l[i][j] = c;
            }
        // 预处理r[0][i],r[1][i]
        for(int i = 0; i < 2; i ++)
            for(int j = n - 1, c = 0, k = i; j >= 0; j --, k ^= 1){
                if(k != s[j] - '0') c ++;
                r[i][j] = c;
            }

        // 偶数的两种情况的最小值
        if(n % 2 == 0) return min(l[0][n - 1], l[1][n - 1]);
        else {
            // 奇数的前两种情况
            int res = min(l[0][n - 1], l[1][n - 1]);
            // 枚举11或00出现位置
            for(int i = 0; i + 1 < n; i ++){
                res = min(res, l[0][i] + r[1][i + 1]);
                res = min(res, l[1][i] + r[0][i + 1]);
            }
            return res;
        }
    }
};



ITNXD
17天前
class Solution {

    /*
        两种操作顺序互不影响,因此考虑第一种操作结束后的情况:

        偶数:(直接枚举)
            1010...10
            0101...01

            res = min(l[0][n - 1], l[1][n - 1]);

        奇数:(前两种情况直接枚举)
            1010...01
            0101...10

            res = min(l[0][n - 1], l[1][n - 1]);

            (后两种借助预处理前缀和数组解决)
            010101... 11 01 
            101010... 00 10

            对于后两种情况可以枚举11和00的位置来进行选择!

        我们可以使用前后缀分解思路来预处理几个数组:
            l[0][i]:表示[0, i]区间01(从左到右)相间的最少操作次数
            l[1][i]:表示[0, i]区间10(从左到右)相间的最少操作次数
            r[0][i]:表示[i, 0]区间01(从右到左)相间的最少操作次数
            r[1][i]:表示[i, 0]区间10(从右到左)相间的最少操作次数

        因此后两种情况最终答案就是:res = min(res, l[0][i] + r[1][i + 1], l[1][i] + r[0][i + 1]);
    */
public:
    int minFlips(string s) {
        int n = s.size();
        vector<int> l[2], r[2];
        l[0] = l[1] = r[0] = r[1] = vector<int>(n);
        // 预处理l[0][i],l[1][i]
        for(int i = 0; i < 2; i ++)
            for(int j = 0, c = 0, k = i; j < n; j ++, k ^= 1){
                if(k != s[j] - '0') c ++;
                l[i][j] = c;
            }
        // 预处理r[0][i],r[1][i]
        for(int i = 0; i < 2; i ++)
            for(int j = n - 1, c = 0, k = i; j >= 0; j --, k ^= 1){
                if(k != s[j] - '0') c ++;
                r[i][j] = c;
            }

        // 偶数的两种情况的最小值
        if(n % 2 == 0) return min(l[0][n - 1], l[1][n - 1]);
        else {
            // 奇数的前两种情况
            int res = min(l[0][n - 1], l[1][n - 1]);
            // 枚举11或00出现位置
            for(int i = 0; i + 1 < n; i ++){
                res = min(res, l[0][i] + r[1][i + 1]);
                res = min(res, l[1][i] + r[0][i + 1]);
            }
            return res;
        }
    }
};



ITNXD
17天前
class Solution {
public:
    int reductionOperations(vector<int>& a) {
        sort(a.begin(), a.end());
        int res = 0;
        for(int i = 1, s = 0; i < a.size(); i ++){
            if(a[i] != a[i - 1]) s ++;
            res += s;
        }
        return res;
    }
};



ITNXD
17天前
class Solution {
public:
    vector<vector<int>> rotate(vector<vector<int>> a){
        auto b = a;
        int n = a.size();
        for(int i = 0; i < n; i ++)
            for(int j = 0, k = n - 1; j < n; j ++, k --)
                b[i][j] = a[k][i];
        return b;
    }

    bool findRotation(vector<vector<int>>& a, vector<vector<int>>& b) {
        for(int i = 0; i < 4; i ++){
            a = rotate(a);
            if(a == b) return true;
        }
        return false;
    }
};


活动打卡代码 AcWing 3628. 边的删减

ITNXD
17天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PII;

const int N = 1e5 + 10, M = 2e5 + 10;

int h[N], e[M], w[M], id[M], ne[M], idx;
LL dist[N];
bool vis[N];
int n, m, k;
vector<int> res;

/*
    最短路树的概念:根据每个点可以由哪个点更新可以建立一颗根节点为1号点的树!(若一个点可以由多个点更新则只保留一条边即可!)

        本题目要求最多保留k条边,使得这些点对应的最短路距离dist[i]不变!

    放到最短路树上来看,就是从中选择不少于k条边,使得这些点的dist数组尽可能不变!

    最短路树一个性质:叶子节点都是由其父节点更新而来,因此我们可以直接从根节点开始找到联通的k条边即可!
*/

// a->b的边,边权为c, 边下标为d
void add(int a, int b, int c, int d){
    e[idx] = b, w[idx] = c, id[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while(heap.size()){
        auto t = heap.top(); heap.pop();

        int ver = t.second, distance = t.first;
        if(vis[ver]) continue;
        vis[ver] = true;

        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

// 从根节点1号点开始搜索整个 最短路树
void dfs(int u){
    // 最多保留k条边
    if(res.size() >= k) return;

    vis[u] = true;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        // dist[j] == dist[u] + w[i],说明j是从u更新而来的,u是j的父节点
        if(!vis[j] && dist[j] == dist[u] + w[i]){
            // 最多保留k条边
            if(res.size() < k) res.push_back(id[i]);
            dfs(j);
        }
    }
}

int main(){
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= m; i ++){
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c, i), add(b, a, c, i);
    }

    dijkstra();

    memset(vis, 0, sizeof vis);
    dfs(1);

    cout << res.size() << endl;
    for(auto x : res) cout << x << " ";
    return 0;
}



ITNXD
17天前

详细请查看注释内容

参考代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PII;

const int N = 1e5 + 10, M = 2e5 + 10;

int h[N], e[M], w[M], id[M], ne[M], idx;
LL dist[N];
bool vis[N];
int n, m, k;
vector<int> res;

/*
    最短路树的概念:根据每个点可以由哪个点更新可以建立一颗根节点为1号点的树!(若一个点可以由多个点更新则只保留一条边即可!)

        本题目要求最多保留k条边,使得这些点对应的最短路距离dist[i]不变!

    放到最短路树上来看,就是从中选择不少于k条边,使得这些点的dist数组尽可能不变!

    最短路树一个性质:叶子节点都是由其父节点更新而来,因此我们可以直接从根节点开始找到联通的k条边即可!
*/

// a->b的边,边权为c, 边下标为d
void add(int a, int b, int c, int d){
    e[idx] = b, w[idx] = c, id[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while(heap.size()){
        auto t = heap.top(); heap.pop();

        int ver = t.second, distance = t.first;
        if(vis[ver]) continue;
        vis[ver] = true;

        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

// 从根节点1号点开始搜索整个 最短路树
void dfs(int u){
    // 最多保留k条边
    if(res.size() >= k) return;

    vis[u] = true;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        // dist[j] == dist[u] + w[i],说明j是从u更新而来的,u是j的父节点
        if(!vis[j] && dist[j] == dist[u] + w[i]){
            // 最多保留k条边
            if(res.size() < k) res.push_back(id[i]);
            dfs(j);
        }
    }
}

int main(){
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= m; i ++){
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c, i), add(b, a, c, i);
    }

    dijkstra();

    memset(vis, 0, sizeof vis);
    dfs(1);

    cout << res.size() << endl;
    for(auto x : res) cout << x << " ";
    return 0;
}


活动打卡代码 AcWing 3627. 最大差值

ITNXD
17天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int w[N];

int main(){
    int T; cin >> T;
    while(T --){
        int n, k; cin >> n >> k;
        for(int i = 0; i < n; i ++) cin >> w[i];
        sort(w, w + n);
        LL res = w[n - 1];
        for(int i = n - 2, j = 0; i >= 0 && j < k; i --, j ++) res += w[i];
        cout << res << endl;
    }
    return 0;
}


活动打卡代码 AcWing 3626. 三元一次方程

ITNXD
18天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
    int T; cin >> T;
    while(T --){
        int n; cin >> n;
        bool flag = false;
        for(int x = 0; x * 3 <= n; x ++){
            for(int y = 0; y * 5 + x * 3 <= n; y ++)
                if((n - x * 3 - 5 * y) % 7 == 0){
                    cout << x << " " << y << " " << (n - x * 3 - 5 * y) / 7 << endl;
                    flag = true;
                    break;
                }
            if(flag) break;
        }
        if(!flag) cout << -1 << endl;
    }
    return 0;
}