1 W_Zifan

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 37w+

[kosaraju算法] POJ 2186 Popular Cows

题面link  给定一个有向图,问有几个结点,图中的任意结点都可以到达?(1≤n≤1e41≤ n ≤ 1e41≤n≤1e4)分析  若是知道了图中的强连通分量,将一个强连通分量缩成一个点的话,那么原图可以变成是一个DAG(有向无环图)。若是只有一个结点出度为0,那么其它结点都可以到达这个点;若是有大于一个,那么就不存在任何结点都可以到达的点了。  所以我们可以用 kosaraju 算法求出强连通分量,进行缩点,然后求出出度为0的缩点判断答案。  kosaraju算法的步骤是:①正向建图和反向建图

2020-08-01 10:55:53

2020牛客暑假多校第五场补题

比赛链接:link题目B Boruvka算法&异或字典树   B Boruvka算法&异或字典树   题意是说给定了一棵树,每条边都有一个权值,我们可以进行删边或者增边操作,每次需要保证操作后所有点是连通的,并且保证若是存在环,环上所有值异或和为0。求最小权值和。   由异或的性质可知,从某个顶点 iii 到顶点 jjj 若是有连边,这个连边的值是确定的;若是我们确定了某一个点的值,其他点的值也可以确定下来,路径异或就可以转成顶点异或。比如我们假定 111 号结点的值为 000

2020-07-30 21:28:06

2020牛客暑假多校第三场补题

比赛链接:link题目G STL中list的使用   G STL中list的使用   题意是说对于一张图有 nnn 个点,mmm 条边,一开始每个点自为一个 groupgroupgroup,我们现在有 qqq 次操作,每次操作选定 groupgroupgroup 的编号为 oio_ioi​,若是 oio_ioi​ 组没有点,则不发生变化,否则与 oio_ioi​ 组的点相连的点若是属于其他组 ojo_joj​,则 ojo_joj​ 组的点并入 oio_ioi​, ojo_joj​ 变空。全部操作之后

2020-07-23 18:20:06

2020牛客多校第四场 H Harder Gcd Problem

H   (只会做3题所以在比赛的时候就开始写题解了 )   题意是说对于 1,2....n1, 2....n1,2....n,找到最多的数对 (i,j)(1≤i,j≤n)(i, j) (1 ≤ i, j≤ n)(i,j)(1≤i,j≤n) (一个数字只能出现在一个数对里),满足 gcd(i,j)>1gcd(i, j) > 1gcd(i,j)>1。      经过简单分析,我们发现 111 不行,也易得大于 n/2n / 2n/2 的质数也不行,那其他的数能不能互相两两成对呢?我是这

2020-07-20 17:00:15

2020牛客暑假多校第二场补题

J   题意是说一开始给你一个排列 {1,2,3...n}\{1, 2, 3...n\}{1,2,3...n},经过 kkk 次置换,变成 {a1,a2....an}\{a_1, a_2....a_n\}{a1​,a2​....an​},问若是将原来的排列只置换一次,会变成什么?(1≤n≤1e51 ≤ n ≤ 1e51≤n≤1e5, kkk 为质数)      首先什么是排列的置换呢?根据抽象代数里的定义,一个集合的排列置换是自身对自身的一个双射。 这可以理解成将一个排列的元素打乱顺序,得到一个新的排

2020-07-16 20:21:48

[组合容斥] 美团2017年CodeM大赛 二分图染色

题面   link 给定一个完全二分图,图的左右两边的顶点数目相同,都是 nnn。我们要给图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。  &emsp计算所有满足条件的染色的方案数,并对 109+710^9+7109+7 取模,其中 n≤1e7n ≤ 1e7n≤1e7。分析   其实这题涂成绿色可以看成不涂,我们只需要考虑涂成红色和蓝色的情况。   经过简单思考,我们发现只涂一种颜色是比较简单的,若是一边顶点数是 nnn,则只涂一种颜色

2020-07-12 22:30:28

[组合数学] NC13611树 (逆元的计算)

题面   link 有一颗树,树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的,当且仅当对于所有相同颜色的点对(x,y),x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。    其中,n,k≤300n, k ≤ 300n,k≤300分析   若是从某个根节点在dfs 或者 bfs 过程中统计,是非常麻烦的事。子结点和父亲一个颜色,这种情况还比较简单,若是不同颜色,则其兄弟结点也不能和该子结点一个颜色(因为这两者通过父结点连接),这样整个过程就不好计算了。   或许可以换

2020-07-09 21:52:13

[树上倍增] LCA问题与ST表的使用

先理解LCA模板    7月伊始,这次决定好好学习一下LCA以及ST表的使用。所以呢,先从解决LCA问题说起。      在有根树中,两个结点 u,vu, vu,v 的公共祖先中距离最近的那个被称为最近公共祖先(LCA, Lowest Common Ancestor)。比如在下图中,根是结点8,LCA(3, 11) = 10, LCA(15, 12) = 4。   在有根树中由于根的存在,结点与根结点的最短路径长度为这个结点的深度(depth)。那么,如果 LCA(u,v)=wLCA(u,v) =

2020-07-04 23:22:48

[区间dp] NC13230合并回文子串

题面link   输入两个字符串A和B( ∣A∣,∣B∣<50|A|, |B| < 50∣A∣,∣B∣<50 ),合并成一个串C,属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。   我们定义字符串的价值为其最长回文子串的长度(回文串表示从正反两边看完全一致的字符串,如"aba"和"xyyx")。需要求出所有可能的C中价值最大的字符串,输出这个最大价值。  分析  若是这题暴力把所有合成的 C 串找出来,则共有 C1

2020-07-01 22:05:35

[离散化dp] NC19809 growth

题面link   一开始有属性a和b,这两个属性初始的时候均为0,每一天可以让a涨1点或b涨1点。我们共有 nnn 种奖励,第i种奖励有 xi,yi,zix_i,y_i,z_ixi​,yi​,zi​ 三种属性,若 a≥xia≥ x_ia≥xi​ 且 b≥yib≥ y_ib≥yi​,则弱弱在接下来的每一天都可以得到 ziz_izi​ 的分数。   问 mmm 天以后弱弱最多能得到多少分数,其中 1≤n≤1000, 1≤m≤2e9, xi,yi≤1e91 ≤ n ≤ 1000, \ 1

2020-06-30 23:08:08

[建图思想] 2020上理校赛E Eight Digital Games

题面link  给定一个长为 n(n≤1e5)n (n ≤ 1e5)n(n≤1e5) 的只含数字1 - 8的字符串,每出现一个逆序对 (a,b)(a, b)(a,b) (其中b>ab > ab>a) 就会有 Pa,bP_{a, b}Pa,b​ 的 cost, 比如字符串 855118551185511 的 cost 为 2×P8,5+2×P8,1+4×P5,12 × P_{8, 5} + 2 × P_{8, 1} + 4 × P_{5, 1}2×P8,5​+2×P8,1​+4×P

2020-06-06 12:17:39

[分组背包] 牛客练习赛22C(bitset优化)

题面link  一共有 n个数,第 i 个数是 xix_ixi​ ,xix_ixi​ 可以取 [li,ri][l_i , r_i][li​,ri​] 中任意的一个值。设 S=∑xi2S = \sum{{x_i}^2}S=∑xi​2, 求 S 种类数。  分析  这一题主要用的是分类背包的思想,dp[i][j]dp[i][j]dp[i][j]表示的是考虑到第iii个区间,S是否能取到jjj,取到为1,取不到为0。  进行三重循环遍历(第一层区间数nnn,第二层jjj的取值可以到达n3n^3n3,

2020-05-23 10:45:08

[贪心算法] NC50439 优先队列+贪心

题面link  在一个游戏中,需要在n个士兵中选出一些士兵组成一个团,第i个士兵的战力为v[i],团的战力是团内所有士兵的战力之和。但是这些士兵有特殊的要求:如果选了第i个士兵,这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵,就没有这个限制。) 问团的战力最大为多少。  数据范围: n(1≤n≤105,1≤v≤109,1≤s≤n)n(1≤n≤10^5, 1≤v≤10^9,1≤s≤n)n(1≤n≤105,1≤v≤109,1≤s≤n)  分析  若是某个方案选取的其中一个士兵,其限制为 s

2020-05-19 23:09:43

[并查集] POJ2492 (带权并查集)

题面BackgroundProfessor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite ge...

2019-10-28 14:59:41
勋章 我的勋章
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。