做题日志

huanxiong_2022 · 2023-07-02 20:52:48 · 个人记录

2023.07.02

CF_59E : Shortest Path

• 类型：最短路

• 实现：Dijstra

• 难点：

  1. 路径处理：path[u][v] = pa ，递归输出
  2. 三元组处理：map存储数字哈希，判断三元组是否成立

2023.07.03

洛谷P3203 : 弹飞绵羊

• 类型：分块

• 易错：

  1. 关于 l 的 块位置 的判断，采取 \dfrac{l}{len} 的方式，非必要不更改

2023.07.04

洛谷P1903 数颜色

• 类型：带修莫队，莫队套值域分块

• 易错：

  1. 建议修改时传值而非编号

  2. 注意t和lr是否都满足，都满足才修改

2023.07.19

洛谷P6175 无向图的最小环问题

• 类型：最短路—— Floyd 求最小环

• 实现： 若最小环为 i - j - k ，且 i，j 间仅隔 一个点 k ,则有 i - j 为 dis(i,j), i-k ，j-k 均为直接连边，所以环长为:

  ans=min(ans,dis[i][j]+mp[j][k]+mp[k][i]);

• 易错：dis 的维护过程中，由 i-j 维护 i-k-j 时，i-k 与 j-k 不一定直接相连， 所以应写作

  dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

CF14D Two Paths

• 类型：树——断边直径

• 思路：由于两直径无交点，可视作断边后在两棵树上分别求直径

• 易错：在写双 dfs 时，分清变量含义，切忌照抄。

另附离奇代码(tips: d <- diameter,直径)

dep[v]=0;int dia1=dfs2( dfs1(u,v) ,0 )-1;

洛谷P2738 篱笆回路

• 类型：最小环

• 难点：建图

  解决方法：先确定是否有关联，再确定关联方向，最后类 Tarjan 将篱笆端点缩成单点

• 易错：求最小环的上下界：

  for(int i=1;i<k;i++)for(int j=i+1;j<k;j++)

  i\in[1,k)$，$j\in[i+1,k)

洛谷P1099 树网的核

• 类型：树——直径

• 难点：细节

• 易错：

  1. 在直径上打 vis 时，注意当 i 到 s 时 fa[i] 已经为 0 ，循环条件应为 i 而非 fa[i] .
  2. 注意双向判断最长，否则会使 ans 为 0 .
  3. 注意 l,r 关联 costl,costr ,先改点再判费用.

  另，从pa开始反向和判 ww>s 作用相同,因为从 pa 向外走一定不如走两边更优

  2023.07.20

洛谷P2491 消防

洛谷U89620 树网的核加强版

三倍经验

注意修改前的判断，判断下一步而非当前步：

            if(ds[u]-ds[son[l]]+costr>s)break;
            l=son[l];
            costl=ds[u]-ds[l];

洛谷P5536 核心城市

• 类型：树——直径相关

• 思路：设 dis[i] 表示编号为 i 的点不选时产生的贡献。若能选，一定从直径中点或中点所在边两端开始选，且在选择 dis 小的点前一定应该且可以将 dis 更大的点选完。

• 易错：注意当从 dia.u,dia.pa 开始，互为父节点搜索时，若 u 恰为直径中点，则 dis[u] 比实际大1。

• 求直径模板dfs：

  int dfs1(int u,int pa)
  {
  fa[u]=pa;
  int res=u;
  for(int i=head[u];i;i=e[i].nxt)
  {
      int v=e[i].to;
      if(v==pa)continue;
      dep[v]=dep[u]+e[i].w;
      int vv=dfs1(v,u);
      if(dep[res]<dep[vv])res=vv;
  }
  if(flag)
  {
   ………………
  }
  return res;
  }

CF1406C Link Cut Centroids

• 类型：树——重心

• 思路：若要使两重心变为一重心，应将一重心的某一叶节点移至另一重心

• 易错：需要进行边的切断与连接时，注意合法性

2023.07.22

CF708C Centroids

• 类型：树——重心，dp

• 思路：找重心，以重心为根更新；dp[u] 表示，以重心为根节点的树中， u 的子树外的最大且不超过 \dfrac{n}{2} 的可分割子树

• 易错：当重复更新时，若更新不为重赋值注意清空

2023.07.23

洛谷P6374 树上询问

• 类型：树——LCA

• 易错：注意c在链上，在中间和在两端三种状态结果两两不同，需要各自判断

  即 n-sz[son],sz[c]-sz[son],sz[a,b]

洛谷B3611 【模板】传递闭包

• 类型：传递闭包模板

• 实现：bitset 优化 Floyd

洛谷P4306 连通数

• 法一：传递闭包（需要 O2 优化）

• 法二：Tarjan 缩点

  法1： 枚举 i 是否能到达 j 法2： n^2 dfs （TLE）

2023.07.25

洛谷P4437 求和

• 类型：LCA ，前缀和

洛谷P3258 松鼠的新家

• 类型：LCA ，树上差分

洛谷P2323 公路修建问题

• 类型：生成树

• 法一：二分答案

• 法二：贪心(?)

2023.07.26

洛谷P5960 【模板】差分约束算法

• 类型：图——差分约束

• 易错：注意超级源点增加的路径长和边数，数组别开小