ThinkofBlank

分类

未归档(4) 论文(10) 题单(1) 题解(90)

/ 注册

TA的专栏 8篇文章 0人订阅

ThinkofBlank’s

8篇文章 1220人学习

全部文章（共105篇）

Treepath 题解

一道简单的树形dp~ 求路径长度为偶数的路径数量，我们可以转化为求路径长度模2等于0的路径数量，这样就好做了~ 我们设表示i的子树中，到i的路径长度模2等于0的路径数量同理，就是模2等于1的路径数量了~ 我们想想转移：我们用的一个儿子来...

题解动态规划

2020-04-14

1 884

Running Median 题解

一.题目大意给你P组数据，先输出数据编号和(n+1)/2,再依次输出所有前i(i为奇数)个数的中位数，每10个数换一行二.题解求中位数，作为一枚偏爱权值线段树的菜鸡，于是，我直接码了一棵权值线段树，对于每个有询问的i，我们直接查询kth((i+1)/2)即可。不...

题解数据结构

2020-04-13

0 518

Xorto 题解

一.闲话检查n久，发现数组开小，难受至极qwq 本题解的做法较大佬做法比较复杂，不过好处在于，时空复杂度与的大小无关qwq 二.题解读题，发现题目要求有多少对区间满足两个不重叠非空区间异或和为0 因为有个众人皆知的东西：两个数异或和为0，当且仅...

题解数据结构

2020-04-13

0 709

NC201400 树学题解

一.题解这道题又是一道换根dp板子题，代码结构与 Accumulation Degree 这道题基本一致，唯一不同的就是转移了【不过转移的时候，因为方程的原因不需要特殊考虑叶节点】我们先套路的设表示以为根的子树中，所有点的深度和，现在，我们来想想转移。我们发现，如...

题解动态规划

2020-04-13

4 647

[Accumulation Degree]题解

换根dp板子题，首先，我们要想想如果根为1时，1的答案我们设表示以为根子树的中，若有无限流量，i点能往下流的最大流量。我们不难推出式子意义就是，我们知道一个儿子v可以向下流的最大流量是,我们最多可以向儿子v流的流量，所以我们最多向该儿子流的流量，所有儿子的这个值的和就是了特别的,若i是叶子的...

题解动态规划

2020-04-13

2 827

牛客练习赛61 A-E题解

一.闲话打了下比赛，把A-E做了后，看了下F，思考了一会儿，发现不可做，就来写题解辣，qwq 二.题解部分 A 打怪签到题，我的思路是先判断-1的情况（如果你可以一刀999秒掉小怪，由于你先手，那你就可以砍无数小怪了）然后，我们先计算出，砍完一只小怪，你扣的血，假设为x，这样，答案就是floo...

2020-04-10

2 986

二分图染色（弱化版）题解

乍看一下，此题貌似很简单，仔细一想，竟然完全不可做。。。然后，开始思考怎么搞这道题。。。首先，我们因为每个边都要染色，所以，我们不妨先给所有边都染上最没影响的颜色——绿色然后，我们只需考虑，将绿色的边改成红色或者蓝色即可~ 我们来推导一下如果既有蓝色，又有红色，尝试推导一下，发现情况太多，而...

数论

2020-04-10

3 911

题解 P3953 【逛公园】

为什么要topo排序呢？辣么判断复杂而且还容易出锅qwq（我太菜了）直接上tarjan就好了啊！这道题还是比较简单的，不过，如果我们dp方程没设好的话，在某些网站上就容易被卡（比如只有128MB的空间限制）我们观察题目，发现题目的K值很小，最大也就50，于是，我们可以从K...

2019-11-11

0 613

题解 P4980 【【模板】Polya定理】

【模板】Polya定理题解提供一个新算法。。。首先,我们来分析一下题目: 给一个有n个点的环图n种颜色，问本质不同的方案数那么，很明显的，这是一个polya定理（废话，题目名说明了一切）我们先来看看这道题的“操作”，很明显的操作就是只有一个——平移（有人说旋转，但我个人更喜欢看成平移。。。...

数论优化研究

2019-09-23

1 626

题解 P4461 【[CQOI2018]九连环】

题解 P4461 【[CQOI2018]九连环】由于各位大佬已经用各种方法,将公式推得我这里便不再过多阐述,我们来谈谈本题的实现~ 首先,我们先来看公式:$\lfloor\frac{2^{n+1}}{3}\rfloor$ 我们知道,因为n<=1e5，所以$|2^{n+1}|...

研究优化高精题解

2019-03-18

1 712