【上分日记】377场周赛(图论 + dp)

2023-12-31 17:43:15

前言

?本场周赛,后两题都涉及到了图论的最短路径(克鲁斯卡尔算法)的知识,恰巧又没学过,所以博主本周基本都在补图论的知识,所以这场周赛的题解虽迟但到。

?这场周赛,博主也只写出一题,第二道还超时了(hhh,菜鸡勿喷)。下面博主就来总结一下,没写出来的三道题。

正文

  • 如果有图论知识欠缺的,可看博主总结的这篇博客:图论与并查集

1.2975. 移除栅栏得到的正方形田地的最大面积


  • 注意事项:

?博主在做这道题时,就没有分析好题,长和宽独立可以分别枚举,而博主直接N3 暴力枚举,结果很显然超时了。

?我们先来分析一下,为什么长和宽可以分别进行枚举?

?要移除栅栏得到正方形,可以转换为横着取出两根栅栏,其差作为长,竖着取出两根栅栏作为宽,围成面积,且长与宽相等,求其面积。

  • 因此,横着取两根栅栏和竖着取两根栅栏是互不影响的,因此独立。

  • 题目思路:
  1. 我们可以 暴力枚举 横着取出两根栅栏其形成的差作为长 的所有可能。
  2. 接着 暴力枚举 竖着 取出两根栅栏形成的差作为宽 的所有可能。
  3. 求两个集合相同元素的最大值。

  • 实现代码:
class Solution 
{
public:
    const int MOD = 1e9 + 7;
    int maximizeSquareArea(int m, int n, vector<int>& hFences,
     vector<int>& vFences) 
    {
        //将水平的栏杆与垂直的栏杆分别求出,并求出并集的最大值。    
        unordered_set<int> rows,cols;
        //将所有栏杆都扔进数组,先进行一步预处理。
        hFences.push_back(1);
        hFences.push_back(m);
        vFences.push_back(1);
        vFences.push_back(n);
        sort(hFences.begin(),hFences.end());
        sort(vFences.begin(),vFences.end());
        int hsz = hFences.size();
        int vsz = vFences.size();

        //将边长的所有可能性暴力枚举出来。

        //长
        for(int i = 0; i < hsz; i++)
        {
            for(int j = i + 1; j < hsz; j++)
            {
                rows.insert(hFences[j] - hFences[i]);
            }
        }
        //宽
        for(int i = 0; i < vsz; i++)
        {
            for(int j = i + 1; j < vsz; j++)
            {
                cols.insert(vFences[j] - vFences[i]);
            }
        }
        // 求出并集的最大值。
        long long edge = INT_MIN;
        for(long long val : rows)
        {
            if(cols.count(val))
            {
               edge = max(edge,val);
            }
        }  

        if(edge == INT_MIN)
        {
            //说明没有。
            return -1;
        }
        
        return (edge * edge) % MOD;
    }   
};

2.2976. 转换字符串的最小成本 I


  • 注意细节:
  1. 因为只有26个小写字母,我们只需开26*26的矩阵即可(映射一下)。
  2. orignal [ i ] -> change [ i ], 需花费 cost[ i ] 中可能存在重复的,比如同时存在a->b,花费 2,和 a->b 花费 3 ,此时求最短路径我们需要挑出最小的作为路径。
  3. 对于相同元素之间的路径,无需进行花费,所以路径我们需初始化为0。
  4. 分析图为有向图。
  • 题目思路:
  1. 用二维矩阵(26 * 26)存放 字母1 到 字母 2的最短路径。
  2. 对角线初始化为0,即相同元素之间最小路径的花费为0。
  3. 用弗洛伊德算法,根据 orignal,change,cost[ i ] 求出最短路径。
  4. 根据最短路径的矩阵,用source 和 target 求出转换的最小成本。

  • 实现代码:
class Solution {
public:
    long long minimumCost(string source, string target, 
    vector<char>& original, vector<char>& changed, 
    vector<int>& cost) 
    {
        vector<vector<int>> min_dst(26,vector<int>(26,INT_MAX));
        //对角线初始化为0,因为 a->a的最小成本是0
        for(int i = 0; i < 26; i++)
            min_dst[i][i] = 0;
        //剩下的从original[i]->changed[i]
        //细节:可能存在相同的,因此要从相同中选出最小的那一个。
        for(int i = 0; i < original.size(); i++)
        {
            int o_i = original[i] - 'a';
            int c_i = changed[i] - 'a';
            min_dst[o_i][c_i] = min(min_dst[o_i][c_i],cost[i]);
        }
        
        //用弗洛伊德算法,求出多源最短路径
        for(int k = 0; k < 26; k++)
        {
            for(int i = 0; i < 26; i++)
            {
                for(int j = 0; j < 26; j++)
                {
                    if(min_dst[i][k]!= INT_MAX && 
                    min_dst[k][j] != INT_MAX)
                    {
                    	min_dst[i][j] = min(min_dst[i][j], 
                    	min_dst[i][k] + min_dst[k][j]);
                    }
                        
                }
            }
        }

        //最后求直接遍历求解即可
        long long ans = 0;
        for(int i = 0; i < source.size(); i++)
        {
            int s_i = source[i] - 'a';
            int t_i = target[i] - 'a';
            if(min_dst[s_i][t_i] == INT_MAX)
                return -1;
            else
                ans += min_dst[s_i][t_i];
        }
        return ans;
    }
};

3.2977. 转换字符串的最小成本 II


  • 说明:

?博主看题解都感觉吃力,因为连字典树都还没有用过,还得先去补一补字典树的知识。有需要的C友,可以看下面的视频与习题快速了解字典树。


  • 细节: original[i] 与 change[i] 的字符串可能完全不相同,因此我们初始化的矩阵为 original.size() + change.size();

  • 题目思路:
  1. 借助字典树,将字符串依次生成编号,即将字符串转化为点。
  2. 用二维矩阵存放 字符串1 到 字符串2的最短路径。
  3. 对角线初始化为0,即相同字符串之间最小路径的花费为0。
  4. 用弗洛伊德算法,根据 orignal,change,cost[ i ] 求出最短路径。
  5. 使用记忆化搜索 —— dp, 求出以 i 为起点的用source[i]之后的字符串 转换为 target[i]即之后的字符串 的最小成本。

  • 实现代码:
//字典树的结点,本题用于生成字符串的下标。
struct Node
{
    Node* arr[26] = {nullptr};
    int _id = -1;
};

class Solution {
public:
    long long minimumCost(string source, string target, 
    vector<string>& original, vector<string>& changed, 
    vector<int>& cost) 
    {

        //第一步:先将字符串用生成编号(下标表示)

        /*
            此处 original 与 changed 数组的字符串可能完全不同,
            因此最多能生成 original.size() + changed.size() 
            个字符串的编号。 
        */
        int sz = original.size() + changed.size();
        vector<vector<int>> dst(sz, vector<int>(sz,INT_MAX));

        /*
            此处将字典树进行初始化,并给出字符串转换的生成函数。
        */
        int id = 0; //最后的id即为生成字符串的个数。
        Node* root = new Node;
        auto GetStrIndex = [&](string& str)->int
        {
            Node* cur = root;
            for(char ch : str)
            {
                if(!cur->arr[ch - 'a'])
                {
                    cur->arr[ch - 'a'] = new Node;
                }
                cur = cur->arr[ch - 'a'];
            }

            //此处的cur,即为单词的结尾,我们要给一个编号,且要判重。
            if(cur->_id < 0)
            {
                cur->_id = id++;
            }
            return cur->_id;
        };

        /*
            用字典树初始化路径矩阵。且需注意,这里的路径可能会重复,
            因此需要取出最小的。
        */

        /* 
            先对对角线的元素初始化为0
        */
        for(int i = 0; i < sz; i++)
        {
            dst[i][i] = 0;
        }
        for(int i = 0; i < original.size(); i++)
        {
            int o_i = GetStrIndex(original[i]);
            int c_i = GetStrIndex(changed[i]);

            dst[o_i][c_i] = min(dst[o_i][c_i],cost[i]);
        }

        // 第二步:用弗洛伊德算法,求出任意两点之间的最短路径
        for(int k = 0; k < id; k++)
        {
            for(int i = 0; i < id; i++)
            {
                /*
                    if(dst[i][k] == INT_MAX)
                        continue;

                    //不加此优化会慢上三倍作用。
                */ 
                for(int j = 0; j < id; j++)
                {
                    if(dst[i][k] != INT_MAX && dst[k][j] != INT_MAX)
                        dst[i][j] = min(dst[i][j],
                        dst[i][k] + dst[k][j]);
                }
            }
        }

        //第三步:使用记忆化搜索(dp),遍历求出以i为起点转换为target的最小成本。

        //此处需要开辟一个数组,用于保存以i为起点的转换为target的最小成本
        int ssz =  source.size();
        vector<long long> start(ssz,-1);
        /*细节:此处需使用包装器可让lambda表达式用于递归 */
        function<long long(int)> dfs = [&](int i)->long long
        {
            if(i == ssz)
                return 0;
            long long &ret = start[i];
            /*
                此处ret如果不为-1,则说明已经找到了,无需再进行找,
                直接返回即可。
            */
            if(ret != -1)
            {
                return ret; 
            }
            /*
                先对ret进行初始化为 LONG_LONG_MAX / 2,
                当取不到时我们返回此结果即可
            */
            ret = LONG_LONG_MAX / 2;
            /* 
              分情况:
                    1.source[i] == target[i],可以不进行修改,
                      此时可能 dfs(i+1)为最小成本
                    2.以i为起点的往后的字符串也有可能为最小成本。
                    因此需要取两种情况的最小值
            */
            if(source[i] == target[i])
                ret = dfs(i+1);
            /*
                遍历之后的字符串, 即[i,j]之间的字符串看是否存在最短的路径
            */
            Node* sstr = root,*tstr = root; 
            for(int j = i; j < ssz; j++)
            {
                int sstr_j = source[j] - 'a';
                int tstr_j = target[j] - 'a'; 
                sstr = sstr->arr[sstr_j];
                tstr = tstr->arr[tstr_j];
                if(sstr == nullptr || tstr == nullptr)
                {
                    //说明之后也不可能存在字符串,直接break即可
                    break;
                }
                else if(sstr->_id < 0 || tstr->_id < 0)
                {
                    //说明还没有取到字符串
                    continue;
                }
                else
                {
                    int sstr_id = sstr->_id;
                    int tstr_id = tstr->_id;
                    /*
                     因为有可能都在source和change数组中,
                     因此我们还需判断一下。
                    */
                    if(dst[sstr_id][tstr_id] != INT_MAX)
                    {
                        ret = min(ret,
                        dst[sstr_id][tstr_id] + dfs(j+1));
                    }
                }
            }
            return ret;
        };
        long long answer = dfs(0);
        return answer < LONG_LONG_MAX / 2 ? answer : -1;
    }
};
  • 说明:本题解主要参考灵神的题解,并进行了较为详细的注释。
  • 补充语法细节:这里的lambda 之所以 封装成 function 包装器的形式,是为了在让lambda表达式在内部调用自己,即能够递归。

总结

  1. 第一题的代码主要使用了暴力枚举 + unordered_set进行实现,总的时间复杂度为O(N2)。
  2. 第二题的代码主要使用了弗洛伊德算法,求最短路径。
  3. 第三题在第二题的基础上,用字典树对字符串进行编号,通过弗洛伊德算法进而求最短路径,然后用记忆化搜索求出字符串转换的最短路径。
  • 本场周赛主要用到算法知识:弗洛伊德算法 + 字典树 + dp。

  • 本篇文章的分析到这里就结束了,如果感到有所收获,不妨点个赞鼓励一下吧!

后文

?我是舜华,期待与你的下一次相遇!

文章来源:https://blog.csdn.net/Shun_Hua/article/details/135316395
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。