ThinkofBlank

题解

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

/ 注册

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

牛客算法周周练2 D小H和游戏题解

我们读题，发现，每次轰炸只对距离不超过2的点造成影响，那么，我们可以考虑，直接计算每个距离x不超过2的点对x造成的贡献。于是，我们初步考虑，对于每个x，我们将所有距离x不超过2的点的答案加1即可但，不难发现，这是很容易被卡的，举个例子如果一棵树中2-n的父亲都是1的话，那么，每有一个点被轰炸，我...

题解优化

2020-04-15

8 794

牛客算法周周练2 C完全平方数题解

比A还签到的签到题。。。求l-r的完全平方数的个数我们按套路将询问拆成两个询问: 求0-r的完全平方数的个数和0-l-1的完全平方数的个数那么，我们需要解的就是求0-x的完全平方数的个数注意到,l可能为0，所以，可能有个询问是求0-(-1)的完全平方数的个数，这个时候特判即可那么，我们来看...

数论题解

2020-04-15

0 738

牛客算法周周练2 B Music Problem 题解

转化题意：给你n个数，问你是否能选出若干个数使得数字的和为3600的倍数（至少选一个）一开始，我打的01背包，dp[i]表示和模3600为i的方案数一开始，dp[0]为1，不难发现，若dp完后，dp[0]>1的话，就表示存在和为3600，不过，我们计算下复杂度：很明显，对于此题是过不...

优化题解动态规划

2020-04-15

7 1100

牛客算法周周练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 709

NC201400 树学题解

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

题解动态规划

2020-04-13

4 647

[Accumulation Degree]题解

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

题解动态规划

2020-04-13

2 827