俞越201811161904122

分类

DS(1) 数论(2) 未归档(9) 组合数学(1) 胡扯(10) 记录(1)

/ 注册

全部文章（共13篇）

降智时刻

dijkstra算法在求最短路时不能有负权边，原因是贪心会挂。同样的最长路时不能有正权边。要用势能把负权边消除。势能只需要满足：若存在，则。有时可以快速算出。

2021-05-21

0 341

Notes

计数技巧：（转化计数对象）注意到一个树上连通块满足|V| − |E| = 1 ，而空集满足 |V| − |E| = 0 。所以只需要用合法的点数减去合法的边数即可。bool化int。权值化组合意义（如：枚举点集 etc.）差分（>=<=x）（好处：化01，etc.) 考虑贪心策略...

2021-05-21

0 348

Summary till 5.14

交互题 1. LOJ2398. 「JOISC 2017 Day 3」自然公园有一棵树，需要通过至多45000次Ask操作确定这棵树的形态。 Ask(x,y,P)表示只通过集合P中的点x和y是否连通。每个点的度数至多为7。 n≤1400 general idea 维护一个连通块，和其一个生成树的拓...

2021-05-14

0 666

2021-04-04

全局平衡二叉树构建通过对重链建立适当的二叉树达到的树高应用 ddp ???

2021-04-05

0 359

2021-03-02

范德蒙特卷积部分和对于n,m,k,多次给定a,求上式组合意义为个球放进个盒子中，前个盒子中球的个数的方案数。考虑第k个球，一定在前a个盒子中的某一个枚举第k个球的位置得前缀和即可

2021-03-02

0 393

2020-11-22

求有向图强连通子图的optimization问题的时候，可以尝试ear decomposition 有向图G强联通，当且仅当G存在subsgraph G'，使得G'能被ear decomposition GymC

2020-11-22

1 454

2020-10-29

总长固定的字符串集的长度种类数 ac自动机的fail树上，每个节点到根的路径上最多有个有用节点

2020-10-29

0 440

2020-08-30

链接1链接2通过消元，转化为与之互为相似矩阵的上海森堡矩阵，完成内求解矩阵的特征多项式。由此，可以优化向量×矩阵的p次幂的问题，估计时间复杂度为，没问题。

2020-08-30

0 434

2020-08-20

计数的一点感悟：对于不明朗的概念计数，如计数+-1序列的，可以通过找特征点来计数，如上例，可以枚举的点，可以证明这样的有且只有一个并且能取到最值，如此使题目变得有特征便于计数。

2020-08-20

1 399

2020-08-19

Almost retired NOI2020 R.I.P. 一种求解“多终止条件游戏的期望 ”的思想和方法挂个链接思想将规则改变为单个终止条件，计算每个终止条件最先出发的概率，最后即可另一种思路：建立与的关系，前者就是后者减去一些不合法的情况，列方程求解。

2020-08-19

1 616