ThinkofBlank

题解

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

/ 注册

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

Rabbit的字符串题解

题目大意：给你一个串，问你这个串现在的顺序是不是不是最小表示法的串做法：一开始打算暴力，但是仔细想想，发现，暴力很可能卡成,导致凉凉。【比如给一个长度为n的串里面的每个字母都一样】一般来说，这道题应该属于字符串类型，需要使用字符串算法。但是！作为一个菜鸡，怎么会打字符串算法呢？/x所以，这里...

优化题解研究

2020-04-17

2 753

牛客练习赛61 F苹果树题解

一.闲话学了淀粉质有一年多了，期间基本没用过，又因为当时是直接背的代码，导致打比赛的时候对这道题根本无从下手，甚至都没想到是淀粉质qwq 然后，今天去学了一下淀粉质，发现原理和实现特别简单，快速码了个模板后，又去顺带学了下点分树，就来搞这道题了。。。二.题解这道题，我们看数据范围，发现成熟度的...

优化题解数据结构

2020-04-17

0 732

NC14731 逆序对题解

这是一道很明显的排列组合题先看题，他叫我们求所有长度为n的01串的逆序对数之和那么，我们可以考虑计算每个位置与它之前的位置所产生的贡献：第1个位置一定不会与之前的位置产生贡献，所以可以不管对于第x(x!=1)个位置，它要和它前面的位置产生贡献的话，那么这个位置上的数就一定得是0，而它前面的就...

数论优化题解

2020-04-15

1 615

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

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

题解优化

2020-04-15

8 798

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

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

优化题解动态规划

2020-04-15

7 1102

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

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

数论优化研究

2019-09-23

1 626

题解 P3423 POI2005BAN-Bank Notes

本题有两个问，第一个是求最少硬币数，第二个则是求方案(翻译竟然没写。。。)。首先，我们来解决第一问。我们可以很容易想出，这是一个dp，我们设dp[i]表示凑出面值i最少需要多少个硬币，然后打个多重背包就好了。。。于是你就T了。。。对于多重背包，我们通常使用一种手段:二进制拆分...

题解优化动态规划

2019-01-21

0 563

题解 P4461 【[CQOI2018]九连环】

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

研究优化高精题解

2019-03-18

1 712