回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共270篇）

CodeForces - 518D Ilya and Escalator

题意：有n个人在电梯外等待，每隔一秒会有p的概率有一人进入电梯，问t秒后电梯中人数的期望题解：概率dp但是接触概率的题很少，对于求期望自己一无所知dp[i][j]表示i秒后电梯中有j人的概率j=0时，该秒无人进入,dp[i][j]+=dp[i-1][j] * (1-p)0<j<n时...

**** 概率dp

2020-11-17

1 709

E2. Daleks' Invasion (medium)

题意：ｎ个点，ｍ个边，生成一个最小生成树，问对于不在最小生成树的边将其边权最大改为多少后，最小生成树可以包含该边输出ｍ－（ｎ－１）个答案如果ｎ＝＝ｍ－１的话，不需要输出任何东西题解：这个题和CodeForces - 609E 是完全一样的，就是输出不一样，换了问法，代码改改就能过题解链接对于不...

最小生成树 ***** lca

2020-11-17

2 586

CodeForces - 609E Minimum spanning tree for each edge

题意：有个无向图，问在必选第i条边的情况下，最小生成树是多少？i会枚举每一个边题解：最小生成树好求，Kruskal即可我们记录最小生成树的值为len对于边(u,v),如果(u,v)是最小生成树的边，那直接输出答案len如果不是的话，我们就要去掉最小生成树中从u到v的路径上权值最大的边mlen，...

最小生成树 ***** lca

2020-11-17

2 708

CodeForces - 86D Powerful array

题意：求区间[l,r]内每个数出现次数的平方*这个数，然后求和是多少 num(i)为i出现的次数题解: 暴力固然不可行其实这个题不难看出有莫队的感觉，之前做过统计数字出现次数的题，就是用莫队，把那个add和del改一改就行不过这个题有点恶心，卡常我们一般块的大小时用sqrt(n)来决定，这个要...

优化 *** 莫队算法

2020-11-16

2 549

CodeForces - 514C Watto and Mechanism

题意：先给n个字符串(由a，b,c组成)，再给m个查询，问存不存在和n个中的某一个只差一个字符(0 ≤ n ≤ 3·10, 0 ≤ m ≤ 3·10) 题解： n和m都很大有两种做法：hash和字典树就是很暴力的做法把模板串整体哈希并记录值然后依次改变目标串的每一位，改成a~c，然后查看是否存储过...

字典树 *** hash

2020-11-16

1 668

二数

来源：牛客网：题目描述我们把十进制下每一位都是偶数的数字叫做“二数”。小埃表示自己很聪明，最近他不仅能够从小数到大：2,3,4,5....，也学会了从大数到小：100,99,98...，他想知道从一个数开始数最少的数就得到一个二数。但是聪明的小森已经偷偷在心里算好了小埃会数到哪个二数，请你求出...

构造思维模拟 ***

2020-11-16

2 797

Kingdom's Power(2020ccpc qinhuangdao)

题目描述： Alex is a professional computer game player. These days, Alex is playing a war strategy game. The kingdoms in the world form a rooted tree. Alex...

树型dp ****

2020-11-13

2 1340

Exam Results

题目描述 Professor Alex is preparing an exam for his students now. There will be n students participating in this exam. If student i has a good mindset, h...

思维题尺取法

2020-11-13

2 597

7-7 Good Number

Alex loves numbers. Alex thinks that a positive integer x is good if and only if [⌋ divides x. Can you tell him the number of good positive integers w...

思维题分块

2020-11-13

2 602

7-6 Friendly Group

题目描述 Professor Alex will organize students to attend an academic conference. Alex has n excellent students, and he decides to select some of them (pos...

并查集

2020-11-13

2 1100