ThinkofBlank

题解

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

/ 注册

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

牛客算法周周练2 A相反数题解

签到题发现，n的范围很小，所以不需要高精。。。我们直接将n的每一位提取出来，再倒序合并成一个新数，将新数和原数相加即可~ 代码： #include<bits/stdc++.h> using namespace std; const int N=9; int sav[N],e; int...

题解

2020-04-15

0 571

黑白树题解

一道贪心题~ 首先，我们将所有点分为已被覆盖点和未被覆盖点。那么首先，因为叶子节点是必选的，所以我们先将叶子节点选中，然后，就会产生若干被覆盖点，然后，由于选了一个点后，会导致这个点到根（1号点）的路径上的若干点被覆盖，所以，如果是在同一个祖先关系的链上的话，我们发现，我们可以贪...

题解动态规划

2020-04-14

0 716

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 710

NC201400 树学题解

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

题解动态规划

2020-04-13

4 647

[Accumulation Degree]题解

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

题解动态规划

2020-04-13

2 827

题解USACO14DEC Piggyback_Silver

此题其实比较水的。。。首先我们来分析题目，我们假设，贝茜和艾尔西在i点相遇后贝西开始扛艾尔西，那么代价为多少呢？显然，代价=贝茜到i点的最小代价+艾尔西到i点的最小代价+贝茜和艾尔西一起到n点的最小代价。我们分开解决，首先贝茜到i点的最小代价=走的最少步数*b，而走的步数，我...

图论题解

2018-12-24

0 547

题解 P3792 【由乃与大母神原型和偶像崇拜】

这题，主要是维护平方和来判断区间是否连续，但这里任然有两个问题： 1.值域为1e9，极限下，long long是一定会爆炸的 2.正如讨论区的，平方和可以被hack 那么该如何解决这个问题呢？我的想法是——离散化！离散化后，值域的极限就在1e6，假设这5e5个数，每...

数据结构题解

2018-12-23

1 697

带修改的主席树 P2617 Dynamic Rankings

一:前置芝士: 1.树状数组(不会树状数组来打这个?(大雾 ) 2.主席树（不会主席树来打这个?(巨雾 ) 3.前缀和 (不会前缀和来打这个?(神雾） 4.权值线段树 (不会权值线段树来打这个?(仙雾) ) 5.看这篇文章的你需要用主席树将求区间kth练得比较熟，并且要理解其原理。二:分(che...

题解理解主席树

2019-01-13

1 737