头像

kulukulu二十代




离线:21小时前


最近来访(7)
用户头像
冷冷月光
用户头像
桂花煮柚子
用户头像
joylie
用户头像
yxc
用户头像
benno0812
用户头像

活动打卡代码 AcWing 237. 程序自动分析

AcWing 237. 程序自动分析

题目类型

  1. 离散化
  2. 并查集

题目链接

https://www.acwing.com/problem/content/239/

思路

此题是NOI的一道题,掌握的话确实不难,而且感觉这题出的非常好,是并查集的经典题

  1. 由于该题数据是1e9 强行开1e9会TLE或者MLE,实际上用到最多只有只有2e5,所以使用离散化(这里不需要排序关系,使用哈希表)
  2. 所有等式相当于并查集合并,所有不等式相当于并查集查询
  3. 所以处理所有 等式
  4. 再查询所有 等式,如果出现两个数在不同集合,说明存在冲突

AC代码

// 题目数据是1e9 可以用离散化缩小到2e6 (最关键在这步,否则会TLE)
// 将相等的式子 合并方式 
// 将不等的式子 查询方式
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N = 2e6 + 10;
int n, m;
int p[N];
unordered_map<int, int> S;

struct Query
{
    int x, y, e;
}query[N];

int get(int x)
{
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        n = 0;
        S.clear();
        scanf("%d", &m);
        for (int i = 0; i < m; i ++)
        {
            int x, y, e;
            scanf("%d%d%d", &x, &y, &e);
            // 离散化处理
            query[i] = {get(x), get(y), e};
        }

        // 初始化并查集
        for (int i = 1; i <= n; i ++ ) p[i] = i;

        // 先处理合并
        for (int i = 0; i < m; i ++ )
        {
            if (query[i].e == 1)
            {
                int pa = find(query[i].x), pb = find(query[i].y);
                if (pa != pb) p[pa] = pb;
            }
        }

        // 再处理查询
        bool has_conflict = false;
        for (int i = 0; i < m; i ++ )
        {
            if (query[i].e == 0)
            {
                int pa = find(query[i].x), pb = find(query[i].y);
                if (pa == pb)
                {
                    has_conflict = true;
                    break;
                }
            }
        }
        if (has_conflict) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}



AcWing 237. 程序自动分析

题目类型

  1. 离散化
  2. 并查集

题目链接

https://www.acwing.com/problem/content/239/

思路

此题是NOI的一道题,掌握的话确实不难,而且感觉这题出的非常好,是并查集的经典题

  1. 由于该题数据是1e9 强行开1e9会TLE或者MLE,实际上用到最多只有只有2e5,所以使用离散化(这里不需要排序关系,使用哈希表)
  2. 所有等式相当于并查集合并,所有不等式相当于并查集查询
  3. 所以处理所有 等式
  4. 再查询所有 等式,如果出现两个数在不同集合,说明存在冲突

AC代码

// 题目数据是1e9 可以用离散化缩小到2e6 (最关键在这步,否则会TLE)
// 将相等的式子 合并方式 
// 将不等的式子 查询方式
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N = 2e6 + 10;
int n, m;
int p[N];
unordered_map<int, int> S;

struct Query
{
    int x, y, e;
}query[N];

int get(int x)
{
    if (S.count(x) == 0) S[x] = ++ n;
    return S[x];
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        n = 0;
        S.clear();
        scanf("%d", &m);
        for (int i = 0; i < m; i ++)
        {
            int x, y, e;
            scanf("%d%d%d", &x, &y, &e);
            // 离散化处理
            query[i] = {get(x), get(y), e};
        }

        // 初始化并查集
        for (int i = 1; i <= n; i ++ ) p[i] = i;

        // 先处理合并
        for (int i = 0; i < m; i ++ )
        {
            if (query[i].e == 1)
            {
                int pa = find(query[i].x), pb = find(query[i].y);
                if (pa != pb) p[pa] = pb;
            }
        }

        // 再处理查询
        bool has_conflict = false;
        for (int i = 0; i < m; i ++ )
        {
            if (query[i].e == 0)
            {
                int pa = find(query[i].x), pb = find(query[i].y);
                if (pa == pb)
                {
                    has_conflict = true;
                    break;
                }
            }
        }
        if (has_conflict) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}



AcWing 1252. 搭配购买

题目类型

  1. 并查集
  2. 01背包

题目链接

https://www.acwing.com/problem/content/1254/

思路

本题是并查集和01背包问题的结合
1. 先用并查集把捆绑消费的物品合并成一个集合,注意除了维护好并查集p[N]数组,还要维护好w[N]和v[N]
2. 再使用01背包问题解决

AC代码

#include <iostream>
#include <cstring>

using namespace std;
const int N = 10010;
int p[N];
int n, m, vol;
int w[N], v[N];
int f[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}


int main()
{
    cin >> n >> m >> vol;

    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        int pa = find(a), pb = find(b);
        if (pa != pb) // 将捆绑消费的商品放一块 合并成一个商品
        {
            v[pb] += v[pa];
            w[pb] += w[pa];
            p[pa]  = p[pb];
        }
    }

    // 01背包
    for (int i = 1; i <= n; i ++)
    {
        // 判断是否是一个完整商品 只有根节点才是完整商品
        if (p[i] == i)
        {
            for (int j = vol; j >= v[i]; j--)
            {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        }
    }

    cout << f[vol] << endl;
    return 0;
}


活动打卡代码 LeetCode 37. 解数独

LeetCode 37. 解数独

题目类型

  1. 暴搜
  2. dfs

题目链接

https://leetcode.cn/problems/sudoku-solver/submissions/

思路

  1. 对每个没放数的格子,从1-9dfs枚举
  2. 选择某个数i的时候 判断rows[x][i] cols[y][i] cells[x / 3][y / 3][i]的状态
  3. 以上判断如果为false,回溯;为true,继续搜索下一个点(x, y + 1)

AC代码

class Solution {
public:
    // 行 列 小方格的枚举每个数的状态
    bool rows[9][9], cols[9][9], cells[3][3][9]; 
    void solveSudoku(vector<vector<char>>& board) {
        memset(rows, false, sizeof rows);
        memset(cols, false, sizeof cols);
        memset(cells, false, sizeof cells);

        // 初始化
        for (int i = 0; i < 9; i ++)
        {
            for (int j = 0; j < 9; j ++)
            {
                if (board[i][j] != '.')
                {
                    int t = board[i][j] - '1';
                    rows[i][t] = cols[j][t] = cells[i / 3][j / 3][t] = true;

                }
            }
        }
        // 从(0, 0)开始填
        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>> &board, int x, int y)
    {
        if (y == 9) y = 0, x ++;
        if (x == 9) return true;

        // 如果该位置已经有数了 则换下一个位置
        if (board[x][y] != '.') return dfs(board, x, y + 1);
        // 否则这个位置可以插入,枚举一下
        for (int i = 0; i < 9; i ++)
        {
            if (!rows[x][i] && !cols[y][i] && !cells[x / 3][y / 3][i])
            {
                rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = true;
                board[x][y] = '1' + i;
                if (dfs(board, x, y + 1)) return true;
                // 回溯
                board[x][y] = '.';
                rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = false;
            }
        }
        return false;
    }
};



LeetCode 37. 解数独

题目类型

  1. 暴搜
  2. dfs

题目链接

https://leetcode.cn/problems/sudoku-solver/submissions/

思路

  1. 对每个没放数的格子,从1-9dfs枚举
  2. 选择某个数i的时候 判断rows[x][i] cols[y][i] cells[x / 3][y / 3][i]的状态
  3. 以上判断如果为false,回溯;为true,继续搜索下一个点(x, y + 1)

AC代码

class Solution {
public:
    // 行 列 小方格的枚举每个数的状态
    bool rows[9][9], cols[9][9], cells[3][3][9]; 
    void solveSudoku(vector<vector<char>>& board) {
        memset(rows, false, sizeof rows);
        memset(cols, false, sizeof cols);
        memset(cells, false, sizeof cells);

        // 初始化
        for (int i = 0; i < 9; i ++)
        {
            for (int j = 0; j < 9; j ++)
            {
                if (board[i][j] != '.')
                {
                    int t = board[i][j] - '1';
                    rows[i][t] = cols[j][t] = cells[i / 3][j / 3][t] = true;

                }
            }
        }
        // 从(0, 0)开始填
        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>> &board, int x, int y)
    {
        if (y == 9) y = 0, x ++;
        if (x == 9) return true;

        // 如果该位置已经有数了 则换下一个位置
        if (board[x][y] != '.') return dfs(board, x, y + 1);
        // 否则这个位置可以插入,枚举一下
        for (int i = 0; i < 9; i ++)
        {
            if (!rows[x][i] && !cols[y][i] && !cells[x / 3][y / 3][i])
            {
                rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = true;
                board[x][y] = '1' + i;
                if (dfs(board, x, y + 1)) return true;
                // 回溯
                board[x][y] = '.';
                rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = false;
            }
        }
        return false;
    }
};



LeetCode 35. 搜索插入位置

题目类型

二分

题目链接

https://leetcode.cn/problems/search-insert-position

思路

使用二分搜素比较简单 直接AC,这里只讲搜索左边界的思路(对应是AC代码1),右边界的思路(对应AC代码2)

  1. 使用二分搜索≤target数的位置l
  2. 如果target > nums[l],则插入位置为l+1,否则为l

AC代码1

// 二分写法一:
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (target > nums[l]) return l + 1;
        else return l;
    }
};

AC代码2

// 二分写法二
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        if (target <= nums[r]) return r;
        else return r + 1;
    }
};


活动打卡代码 LeetCode 35. 搜索插入位置

LeetCode 35. 搜索插入位置

题目类型

二分

题目链接

https://leetcode.cn/problems/search-insert-position

思路

使用二分搜素比较简单 直接AC,这里只讲搜索左边界的思路(对应是AC代码1),右边界的思路(对应AC代码2)

  1. 使用二分搜索≤target数的位置l
  2. 如果target > nums[l],则插入位置为l+1,否则为l

AC代码1

// 二分写法一:
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (target > nums[l]) return l + 1;
        else return l;
    }
};

AC代码2

// 二分写法二
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        if (target <= nums[r]) return r;
        else return r + 1;
    }
};


活动打卡代码 AcWing 1250. 格子游戏

#include <iostream>

using namespace std;
const int N = 40010;
int p[N];
int n, m;

int get(int x, int y)
{
    return x * n + y;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    // 初始化并查集
    for (int i = 0; i < n * n; i ++ ) p[i] = i;

    int res = 0;
    for (int i = 1; i <= m; i ++)
    {
        int x, y;
        char d;
        cin >> x >> y >> d;

        x --, y --;
        int a = get(x, y);
        int b;
        if (d == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);

        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            res = i;
            break;
        }
        else 
        {
            p[pa] = pb;
        }
    }

    if (res) cout << res << endl;
    else cout << "draw" << endl;
    return 0;
}



LeetCode 31. 下一个排列

题目类型

  1. 数组
  2. 找规律题

题目链接

https://leetcode.cn/problems/next-permutation/

思路

建议画图用例子模拟

[2 3 5 4 1] => [2 4 1 3 5]

  1. 先用指针k从后往前找,找到第一个不满足nums[k - 1]>nums[k]的位置,即k即往后的都为降序
  2. 如果k在nums起始位置,则将整个数组反转,否则执行3
  3. 用指针t从指针k所在位置往右寻找,找到第一个大于nums[k-1]的数,此时整个数为nums[t - 1]
  4. 并且将nums[k-1]和nums[t - 1]互换
  5. 将k后面的序列反转

AC代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        // 2 3 5 4 1
        // 此时处于5这个位置
        while (k > 0 && nums[k - 1] >= nums[k]) k --;
        // 整个序列都是降序
        if (k <= 0) 
        {
            reverse(nums.begin(), nums.end());
        }
        else
        {
            int t = k;
            while (t <= nums.size() - 1 && nums[t] > nums[k - 1]) t ++;
            swap(nums[k - 1], nums[t - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};


活动打卡代码 LeetCode 31. 下一个排列

LeetCode 31. 下一个排列

题目类型

  1. 数组
  2. 找规律题

题目链接

https://leetcode.cn/problems/next-permutation/

思路

建议画图用例子模拟

[2 3 5 4 1] => [2 4 1 3 5]

  1. 先用指针k从后往前找,找到第一个不满足nums[k - 1]>nums[k]的位置,即k即往后的都为降序
  2. 如果k在nums起始位置,则将整个数组反转,否则执行3
  3. 用指针t从指针k所在位置往右寻找,找到第一个大于nums[k-1]的数,此时整个数为nums[t - 1]
  4. 并且将nums[k-1]和nums[t - 1]互换
  5. 将k后面的序列反转

AC代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        // 2 3 5 4 1
        // 此时处于5这个位置
        while (k > 0 && nums[k - 1] >= nums[k]) k --;
        // 整个序列都是降序
        if (k <= 0) 
        {
            reverse(nums.begin(), nums.end());
        }
        else
        {
            int t = k;
            while (t <= nums.size() - 1 && nums[t] > nums[k - 1]) t ++;
            swap(nums[k - 1], nums[t - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};