倒着讲。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];
}
};