首页 > 其他分享 >CF22

CF22

时间:2024-11-08 17:32:43浏览次数:1  
标签:题目 CF22 割点 叶子 任意 节点

博客没保存,速通

A

用 set 维护 ,把 1 去掉

B

\(O(n^4)\)

暴力枚举矩形,用二维前缀和判他是否全是0

C

v 是割点

易得构造一颗以 v 为根的菊花图,
剩下的边怎么消耗?

把下面的点相连,剩一个只与根相连的点(用于控制割点)

D

贪心
直接线段覆盖

E

首先,题目的翻译
https://www.luogu.com.cn/discuss/963676

考虑缩点,因为题目给的肯定有环,缩完点后就会变成一个森林,对于任意一个叶子节点,它肯定需要至少一条边成为它的入边,而对于任意一个根节点,它也至少需要一条边成为它的出边。所以就连叶子和根,剩下的就把自己的叶子指向自己的根

标签:题目,CF22,割点,叶子,任意,节点
From: https://www.cnblogs.com/Z-kazuha/p/18535517

相关文章

  • CF228E 题解
    CF228E题解题目简述给定一个\(n\)个点,\(m\)条边的无向图,每条边都为\(0\)或\(1\),可以进行若干次操作,与此点相连的所有点权值取反,求一种方案使得所有边都变为\(1\)。前置知识二分图二分图染色思路简述首先明白一点:对于同一条边,操作偶数次是没有必要的!因为最终会回......
  • CF22E 题解
    题面注意到题目给的图为基环树森林。因为一个(\(n>1\))的强连通图每个点都要有出度和入度,所以:对于每个基环树,叶子结点是没有入度的,所以一定要有一条从环上出发的路径经过这个点。对于基环树的环,注意到它缩点后没有出度,所以一定要有一条出边。注意到叶子结点的需求和根节点相反,......
  • CF222A Shooshuns and Sequence 题解
    分析这题是一个很水的题,就是对一个序列有$2$种操作方法,一种是对第$K$个数以前的数的第一个进行删除,另一个则是在整个序列后添加这第$K$个数,使得整个序列为同一个数字,显然,后者是无效操作,则只需要判断第$K$个数以后有无与第$K$个不同的数,有则无解,反之有解。若有解,然后再......
  • CF226E Noble Knight's Path
    重链剖分真可爱,数据结构真可爱。tags:\(\text{datastructures}\)\(\text{trees}\)$\color{red}{*2900}$洛谷CF给出一棵\(n\)个点的树,初始所有点为白色。还有\(q\)次操作,第\(i\)个操作发生在第\(i\)个时刻,初始状态时刻为\(0\)。每次操作为:\(1\textt......
  • CF227A Where do I Turn? 题解
    题目大意:\(A\),\(B\)在一条直线上。\(B\),\(C\)在一条直线上你从\(A\)走到了\(B\)去\(C\),问现在应该是直走、左转、还是右转。思路:分类讨论:分别求\(A\)到\(B\),\(B\)到\(C\)是什么方向,然后可得\(A\)到\(C\)的方向。Code:#include<bits/stdc++.h>usingnamesp......
  • Towers CF229D
    一个序列A,每次可以相邻的数相加为一个数字,求最少次数使得序列非降  f[i]=min{ f[j]+i-j-1} ,s[i]-s[j]>=s[j]-s[mn[j-1]] 维护下前缀最小值mn[i]......
  • 题解:【CF226D】The table
    题目链接调整构造。发现\(n\)和\(m\)较小只有\(100\),因此可以考虑尝试进行修改从而不断逼近答案。容易发现如果将某一行或列上的数字翻转,那么得到的新的和一定与原......
  • CF225 Round #139 题解
    比赛链接:https://codeforces.com/contest/225题解:A题意题//bySkyRainWind#include<bits/stdc++.h>#definemprmake_pair#definedebug()cerr<<"Yoshino\n"#de......
  • CF222C Reducing Fractions 题解
    虽然是朴素的筛法,但是跑的比希儿的Pollard-rho快。\(\mathcalO(n\sqrtn)\)的质因数分解是不行的,Pollard-rho的码量也过于麻烦,直接在线性筛里筛出每个数的最小质因子......