倒着讲。Profile Here。

Question D Count Number of Possible Root Nodes

题意

给定一个n个节点的无根树，Bob同学对这个无根树的父子关系进行m次猜测，每次猜测u为v的父亲(注意不是祖先)，由于这个树是没有根的，并不能确定每个节点之间的父子关系。求这n个节点分别当无根树的根的这些情况中，Bob同学猜测正确次数超过k次的情况有多少？

($n\le 1e5, m\le 1e5, k \le m$)

题解

首先我们需要会判断以一个固定节点为根时候，在$O(n+m)$的时间复杂度内完成对Bob所有猜测对当前固定根是否满足的求解过程。这个过程如果你想到了一些LCA的事情（倍增、Tarjan），这说明你和我一样没认真读题，导致把题目想的非常复杂！题意里也强调了，只是猜测是不是父亲，不是祖先关系！父子关系就简单多了！你可以在一次dfs遍历的过程中完成这个过程，因为有父子关系的两个点一定是相邻的，正好就是我们dfs遍历的过程。

但是如果这样枚举n次，时间复杂度是$O(nm+n^2)$，这个时间范围是不对的。由于父子关系是节点的邻居关系，我们应该比较自然能想到换根dp：即，我们考虑如果存在u<->v的一条边，我们已知刚才以u为根节点时候猜测正确的条数，现在想求以v为根节点时正确的条数，这两个之间一定存在很紧密的关系，思考这两者之间的差异。发现u转移到v的时候，只会改变u和v两个节点之间的父子关系，其他的完全不影响！

所以我们只需要看看猜测列表里如果：
- 存在(u, v)，就-1，因为即将变成错的；
- 存在(v, u)，就+1，因为即将变成对的。

代码如下

const int maxn = 1e5 + 10;
class Solution {
public:
    int n;
    vector<int> edges[maxn];
    set<pair<int, int>> st;
    int res = 0;
    map<int, int> mp_ans;

    void dfs1(int now, int fm){
        res += st.count({fm, now}) > 0;
        for(auto &nto : edges[now]){
            if(nto != fm){
                dfs1(nto, now);
            }
        }
    }

    void dfs2(int now, int fm){
        if(mp_ans.find(now) == mp_ans.end())
            mp_ans[now] = res;
        for(auto &nto : edges[now]){
            if(nto != fm){
                res += st.count({nto, now}) > 0, res -= st.count({now, nto}) > 0;
                dfs2(nto, now);
                res -= st.count({nto, now}) > 0, res += st.count({now, nto}) > 0;
            }
        }
    }

    int rootCount(vector<vector<int>>& e, vector<vector<int>>& g, int k) {
        n = e.size() + 1;
        for(auto &it : e)
            edges[it[0]].push_back(it[1]), edges[it[1]].push_back(it[0]);
        for(auto &it : g)
            st.insert({it[0], it[1]});
        int root = 0; res = 0;
        dfs1(root, -1);
        dfs2(root, -1);

        int ret = 0;
        for(int i = 0; i < n; i++){
            // cout << i << " :" << mp_ans[i] << endl;
            ret += mp_ans[i] >= k;
        }
        return ret;
    }
};

Question C Count Ways to Group Overlapping Ranges

题意

给定一个长为n(n<1e5)的数组ranges，每个元素(start_i, end_i)表示一个区间的开始和结束，你需要将这个ranges数组分成两部分，保证：

• 每个range元素属于唯一的部分
• 任意两个重叠的区间属于相同的部分

注意两个区间只要有一个整数同时属于这两个区间就称为重叠。问有多少种分割ranges数组的方式，方案数模(1e9+7)。

题解

可以不难感觉到是把区间先分成组内不冲突的组，再把组随意放到两个部分中的过程。具体一点，就是区间组内部元素有相交关系，而区间组之间两两互不相交（两个区间组不相交就定义为这个区间组内的所有小区间都不相交）。而有了这样的区间组，每个区间组就可以没有任何限制的放到两个部分中，因此假定区间组总量为tot，方案数就是$2^tot$。

下面就是求解区间组的过程。先把所有区间按照左端点排序，然后从左到右线性扫一次所有区间就行了。

typedef long long ll;
const ll MOD = 1e9 + 7;

struct line{
    int x, y;
};

bool comp(line l1, line l2){
    if(l1.x != l2.x) return l1.x < l2.x;
    else return l1.y > l2.y;
}

class Solution {
public:
    int countWays(vector<vector<int>>& ranges) {
        int n = ranges.size();
        ll ret = 1;
        vector<line> v;
        for(auto &it : ranges) v.push_back({it[0], it[1]});
        sort(v.begin(), v.end(), comp);
        ll tot = 0, res = -1;
        for(int i = 0; i < n; i++){
            ll nx = v[i].x, ny = v[i].y;
            if(nx > res){
                tot += 1, res = max(res, ny);
            }
            else{
                res = max(res, ny);
            }
        }

        for(int i = 0; i < tot; i++){
            ret *= 2, ret %= MOD;
        }
        return ret;
    }
};

Question B Count Total Number of Colored Cells

题解

找规律

typedef long long ll;
class Solution {
public:
    long long coloredCells(int n) {
        ll ret = 2ll * n * (n - 1) + 1;
        return ret;
    }
};

Question A Split With Minimum Sum

题解

贪心，大的数位尽量放在低位。

class Solution {
public:
    int splitNum(int num) {
        int nums1 = 0, nums2 = 0;
        string s = to_string(num);
        sort(s.begin(), s.end());
        int n = s.length(), res[2] = {0, 0}, flag = 0;
        for(int i = 0; i < n; i++){
            res[flag] *= 10, res[flag] += (s[i] - '0'), flag = !flag;
        }
        return res[0] + res[1];
    }
};