4 黑码

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 9k+

求割点,割边 tarjan 模板

观察DFS搜索树,我们可以发现有两类节点可以成为割点: 对根节点u,若其有两棵或两棵以上的子树,则该根结点u为割点; 对非叶子节点u(非根节点),若其中的某棵子树的节点均没有指向u的祖先节点的回边,说明删除u之后,根结点与该棵子树的节点不再连通;则节点u为割点。 对于根结点,显然很好处理;但是对于非叶子节点,怎么去判断有没有回边是一个值得深思的问题。我们用dfn[u]记录节点u在DFS过程中被遍历到的次序号,low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点(即DFS次

2020-05-11 23:52:35

欧拉路,求欧拉路 路径

小Ho:这个好像是一笔画问题哎,我们是在求一个方法能够一笔画出所有边吧?小Hi:没错,这就是一笔画问题,不过它更正式的名字叫做欧拉路问题。其定义是给定无孤立结点图G,若存在一条路,经过图中每边一次且仅一次,该条路称为欧拉路。小Ho:既然有名字,那就证明这东西有解咯?小Hi:没错,欧拉路是有判定条件的:一个无向图存在欧拉路当且仅当该图是连通的且有且只有2个点的度数是奇数,此时这两个点只能作为欧拉路径的起点和终点。若图中没有奇数度的点,那么起点和终点一定是同一个点,这样的欧拉路叫做欧拉回路

2020-05-09 16:02:48

hihocoder 1162 : 骨牌覆盖问题·三(四十三周)

方块问题的 最终形式 利用二进制进行状态转移,然后矩阵快速幂,[x][y] x为i-1列的状态,y为 i列状态, [x][y]能唯一标示所有的状态。时间限制:10000ms单点时限:1000ms内存限制:256MB描述前两周里,我们讲解了2xN,3xN骨牌覆盖的问题,并且引入了两种不同的递推方法。这一次我们再加强一次题目,对于给定的K和N,我们需要去求KxN棋盘的覆盖方案数。提示:KxN骨牌覆盖输入第1行:2个整数N。表示棋盘宽度为k,长度为N。2≤K≤7,1≤N≤100,

2020-05-09 15:20:18

prime 模板复习 hihocoder 1097

#1097 : 最小生成树一·Prim算法时间限制:10000ms单点时限:1000ms内存限制:256MB描述最近,小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod,在这个Mod中,玩家可以拥有不止一个城市了!但是,问题也接踵而来——小Hi现在手上拥有N座城市,且已知这N座城市中任意两座城市之间建造道路所需要的费用,小Hi希望知道,最少花费多少就可以使得任意两座城市都可以...

2020-05-07 19:34:32

spfa 模板复习 hicocoder 1093

时间限制:10000ms单点时限:1000ms内存限制:256MB描述万圣节的晚上,小Hi和小Ho在吃过晚饭之后,来到了一个巨大的鬼屋!鬼屋中一共有N个地点,分别编号为1..N,这N个地点之间互相有一些道路连通,两个地点之间可能有多条道路连通,但是并不存在一条两端都是同一个地点的道路。不过这个鬼屋虽然很大,但是其中的道路并不算多,所以小Hi还是希望能够知道从入口到出口的最短...

2020-05-07 11:51:59

leetcode 5403

5403. 有序矩阵中的第 k 个最小数组和难度困难6给你一个m* n的矩阵mat,以及一个整数k,矩阵中的每一行都以非递减的顺序排列。你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个最小数组和。示例 1:输入:mat = [[1,3,11],[2,4,6]], k = 5输出:7解释:从每一行中选出一个元素,前 k 个和...

2020-05-03 18:25:06

leetcode 5402(滑动窗口 + map)

5402. 绝对差不超过限制的最长连续子数组难度中等13给你一个整数数组nums,和一个表示限制的整数limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于limit。如果不存在满足条件的子数组,则返回0。解法1:滑动窗口 + map 因为map自动排好了最大最小值,时间复杂度 log#include <b...

2020-05-03 17:29:06

codeforces Nastya and Scoreboard(dp)

题意:0~9每个数字由不同数量位置的火柴棍组成,一共n组数字,让你添加k根火柴棍,使n组数字可以构造的最大的数。若不能构成任何数,那么输出 -1dp[i][j] 第i个数时,还剩下j个火柴棍,dp[i][j] = 1代表这个状态是可以构成的。那么初始值 dp[n+1][0] = 1代表 n+1个数时,剩下0个火柴棍的状态是1。从后往前推可以达到的状态,最后从前往后贪心得到结果。#incl...

2020-04-25 10:41:10

Replica set 的选举策略之一

首先介绍一下在replica set里分为三种节点类型:1primary 负责client的读写。2secondary作为热备节点,应用Primary的oplog读取的操作日志,和primary保持一致,不提供读写操作! secondary有两种类型: 1)normal secondary 随时和Primay保持同步, 2)delayed second...

2020-04-20 12:33:41

codeforces D Xenia and Colorful Gems

给 t给 nr,ng,nb三种宝石数量nr个宝石的价值ng个宝石的价值nb个宝石的价值每种宝石各取一个,使 (xx-yy)^2+ (xx-zz)^2 + (yy-zz)^2 最小展开,有 2(xx + yy + zz) - 2xy - 2xz - 2yz 最小 由不等式可知 xx==yy==zz最小,答案为0则推 当xyz 差值最小的时候 答案最小 所以 分别对三种...

2020-04-16 11:45:43

codeforces E2. Three Blocks Palindrome (hard version)

给你一个序列,你要可以在这些序列中进行删除操作,最后这个序列形成abaabaaba回文序列,并且a,ba,ba,b中的数字要一样,问这个的序列最长的长度是多少。分析:收尾两边同时逐一增加某字符,然后和中间相同字符个数,拼接起来,找到最大值#include <bits/stdc++.h>using namespace std;#define fi first#define...

2020-04-15 16:30:50

leetcode1406. 石子游戏 III 零和博弈

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出...

2020-04-12 18:22:33

leetcode 5383. 给 N x 3 网格图涂色的方案数

你有一个 n x 3的网格图 grid,你需要用 红,黄,绿三种颜色之一给每一个格子上色,且确保相邻格子颜色不同(也就是有相同水平边或者垂直边的格子颜色不同)。给你网格图的行数 n。请你返回给grid涂色的方案数。由于答案可能会非常大,请你返回答案对10^9 + 7取余的结果。示例 2:输入:n = 2输出:54示例 3:输入:n = 3输出:246示例...

2020-04-12 17:01:24

codeforces 632C Eugene and an array

给定长度为n的序列,定义序列a为“好的”,当且仅当,a的子段中不存在sum值为0。那么根据题意,若sum[a[i]]在i前面存在,那么这样的序列只能最后一次取到sum[a[i]]的下标k以后,数量为i - k。#include <bits/stdc++.h>using namespace std;#define fi first#define se second#d...

2020-04-09 12:41:57

codeforces 1332C K-Complete Word

K-Complete Wordtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputWord????sof length????nis called????k-complete if????sis a palindrome...

2020-04-01 14:32:04

codeforces 1332D 构造

小明有一个动态规划程序是为了解决一个矩阵只能往右走或者往下走相与的最大值 是 dp[i][j] = max(dp[i-1][j] & a[i][j], dp[i][j - 1]&a[i][j]) ,然后说这个程序是错的,有真正的对的答案,给一个k 是 这个错误答案与正答的差值,让构造这个矩阵只要给一条有k的路,但是动态规划程序是不会走这条路的矩阵即可构造3*3 矩阵 ...

2020-04-01 14:04:03

codeforces E. Tree (lca 求最小公共祖先)

E. Tree Queriestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a rooted tree consisting of????nvertices numbered fr...

2020-03-27 10:48:24

codeforces627 div3 D Pair of Topics(树状数组+离散化)

D. Pair of Topicstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe next lecture in a high school requires two topics to be dis...

2020-03-12 23:31:36

codeforces 627 div3 E. Sleeping Schedule

E. Sleeping Scheduletime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputVova had a pretty weird sleeping schedule. There areℎhhour...

2020-03-12 23:21:36

hdu 5583 Kingdom of Black and White(水题)

In the Kingdom of Black and White (KBW), there are two kinds of frogs: black frog and white frog.NowNNfrogs are standing in a line, some of them are black, the others are white. The total strength ...

2020-02-27 11:15:28

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。