首页 > 其他分享 >2024.2.21游记

2024.2.21游记

时间:2024-02-21 23:00:44浏览次数:33  
标签:2024.2 21 int LCA mid ++ edge ans 游记

首先, 文对于 线段 \([A, B]\), \([C, D]\) 什么时候相交。 \(B\) 为 \(A\) 的祖先, \(D\) 为 \(C\) 的祖先

相交有一种情况, 在 \([A, B]\) 上有一个分叉, 连接 \(C\), 然后分叉上面为 \(D\), 这是候, 就会发现 \(B\) 是 \(C\) 的祖先, \(D\) 是 \(A\) 的祖先

代码形式

LCA(B, C) == B && LCA(D, A) == D

NOIP2015 运输计划

可以二分一个答案 \(x\), 显然, \(x\) 具有单调性。 \(x\) 越多越合法

对于一个长度 \(>\) \(x\) 的答案, 要求出一个这些线段都能到达的边, 求边的最大值, 求完之后判读合法

时间复杂度 \(O(N log V)\)

对于某一些题, 时限为 \(1s\), 要用一些卡常技巧

  • 二分上界为 \(\sum w_i\)
  • vector 建图转成链式前向星
  • 每一次二分都跑一遍 DFS 常数太大, 先跑一遍记录 DFS 序, 每一次从后往前做转移
  • 用一个数组存下线段段点的 \(LCA\), 不用每一次都重新算
#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int l, r, mid, dep[N], f[19][N], dist[N], a[N], b[N], u, v, w, k, len, Max, n, m, ans[N], lca[N], ok, head[N], tot;

struct Node{
  int v, w;
};

struct Edge{
  int v, w, net;
}e[N * 2];

vector<int>edge;

void dfs(int x, int fa){
  dep[x] = dep[fa] + 1;
  edge.push_back(x);
  f[0][x] = fa;
  for(int i = 1; i <= 18; ++i){
    f[i][x] = f[i - 1][f[i - 1][x]];
  }
  for(int i = head[x]; i; i = e[i].net){
    auto v = e[i].v, w = e[i].w;
    if(v != fa){
      dist[v] = dist[x] + w;
      dfs(v, x);
    }
  }
}

int LCA(int x, int y){
  if(dep[x] < dep[y]){
    swap(x, y);
  }
  k = dep[x] - dep[y];
  for(int i = 18; ~i; i--){
    if(k & (1 << i)){
      x = f[i][x];
    }
  }
  if(x == y){
    return x;
  }
  for(int i = 18; ~i; i--){
    if(f[i][x] != f[i][y]){
      x = f[i][x], y = f[i][y];
    }
  }
  return f[0][x];
}

bool C(int t){
  for(int i = 1; i <= n; ++i){
    ans[i] = 0;
  }
  len = 0;
  Max = -1;
  for(int i = 1; i <= m; ++i){
    if(dist[a[i]] + dist[b[i]] - 2 * dist[lca[i]] > t){
      len++;
      ans[a[i]]++, ans[b[i]]++, ans[lca[i]] -= 2;
    }
  }
  for(int i = edge.size() - 1; ~i; i--){
    int x = edge[i];
    for(int i = head[x]; i; i = e[i].net){
      auto v = e[i].v, w = e[i].w;
      if(f[0][x] != v){
        if(ans[v] == len){
          Max = max(Max, w);
        }
        ans[x] += ans[v];
      }
    }
  }
  if(Max == -1){
    return 0;
  }
  for(int i = 1; i <= m; ++i){
    if(dist[a[i]] + dist[b[i]] - 2 * dist[lca[i]] - Max > t){
      return 0;
    }
  }
  return 1;
}

void add_edge(int u, int v, int w){
  e[++tot] = {v, w, head[u]}, head[u] = tot;
}

signed main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i < n; ++i){
    cin >> u >> v >> w;
    add_edge(u, v, w);
    add_edge(v, u, w);
    ok += w;
  }
  dfs(1, 0);
  for(int i = 1; i <= m; ++i){
    cin >> a[i] >> b[i];
    lca[i] = LCA(a[i], b[i]);
  }
  l = 0, r = ok;
  while(l < r){
    mid = (l + r) >> 1;
    if(C(mid)){
      r = mid;
    }
    else{
      l = mid + 1;
    }
  }
  cout << l;
  return 0;
}

标签:2024.2,21,int,LCA,mid,++,edge,ans,游记
From: https://www.cnblogs.com/liuyichen0401/p/18026390

相关文章

  • 2024年2月21号题解
    106.从中序与后序遍历序列构造二叉树力扣题目链接解题思路找到根节点在中序序列的位置计算左子树的节点个数开辟一个节点,并把根节点的值赋值给这个节点根节点的左孩子和右孩子重复上面几个步骤代码实现/***Definitionforabinarytreenode.*structTreeNode{......
  • 24_02_21
    24_02_21梦熊临沂集训Day-7雪非常大,跟手指头差不多深,很软。下的时候像撒沙子一样沙沙沙的,声音挺大关于模拟赛给我整不会了......,暴力不会打,正解想不出来......赛后发现T2接近正解,差一个光速幂(写在题解里了)其他暴力有不少是DP,还要多练……奇怪的经验string比......
  • 24/02/21 染色问题
    题目描述给定一棵\(n\)个节点的树,你想把编号为\(i\)的叶子节点染成\(a_i\)的颜色。你本来可以一个节点一个节点的涂,但你觉得这样太慢了,你决定这样染色:选择一个节点\(x\)和一种颜色\(c\),然后把这个颜色的颜料桶直接倒在节点\(x\)上,使\(x\)的所有子树都染成\(c\)......
  • 2.21闲话 & solution『 有没有/谁/能够代替我』
    上午有唐氏模拟赛,100/0/0/20,rk7/15,鉴定为最唐的一次T1签到题,思路很简单题面ame是一个可爱的女孩子,她想要你帮她排序。给定\(4\timesn\)个数,要求将其分为\(n\)组,使得对于每组四个数,所有组中的\(|a\timesb-c\timesd|\)和最大,求最大和。排序,对于前\(2n\)大的,尽量把大......
  • 中央财经大学 &2023 百度之星决赛游记
    榜题解12.29收拾东西的时候发现装不下,强行塞到双肩包+单肩包里了第一次尝试在电脑上下打印订单,然后下去发现机器坏了。。。12.30打印机还是坏的,本来就起得不早。。。去12宿楼底打印的时候还被宿管认出来了,问我是哪个宿舍的,有点震惊7.30出发,8.30到天津站,9.30到北京南......
  • [SWPUCTF 2021 新生赛]ez_unserialize
    概括这是一道PHP反序列化的CTF赛题,本意是想用这道题对PHP反序列化进行一定的学习。过程我们打开赛题,看看内容 没有发现什么东西,看看他的页面代码  根据他的提示,感觉是存在一个robots.txt文件的,尝试访问一下。 进去看看。 果然如此我们来分析一下这段代码<......
  • Solution Set【2024.2.21】
    [ARC162C]MexGameonTree可以发现若Bob在某个节点填了值\(K\),那么会直接导致其根链上的所有节点均不可能满足要求。因此若某个节点的子树内有不小于两个空位,那么Alice一定无法使该子树满足要求。若某节点子树内有一个空位且可以通过填上这一空位使其合法,那么Alice可......
  • 2024年2月21日——霜雪落满头,也算共白首
    今天上午寒霜又镀遍了世界大地上遍布着一层浅金色的冰壳,清晨的天色昏暗无光,一夜的风雨,早已在低温的作用下凝固,碧绿的春叶,枯寒的枝干,全部裹上了透明的镀层,连汽车都被冰封。深呼出一口气,在阳光下又变成了洁白的辰龙吐雾。中午回家的路上,抬头看向天空,一粒粒白色水晶,肆无忌惮......
  • 闲话2.21
    摆摆摆......
  • idea创建spring项目的时候只有java 21和17
    1.问题我们在用IDEA创建一个spring项目时,发现java版本只能选用java21,java17,导致我们的jdk版本无法选择jdk1.8(我最常用的版本)2.解决参考:idea创建项目的时候只有java21和17原因是spring2在23年11月24日停止维护了,所以通过spring来创建,没有spring2,只有spring3+,最低jdk版本也是1......