2006

P2501 [HAOI2006] 数字序列 题目描述 现在我们有一个长度为 \(n\) 的整数序列 \(a\)。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。 输入格式 第一行是一个整数，表示序列长度 \(n\)。 第二行有 \(n\) ......

如果数列 {p_n} 满足 P(X=i)=p_i（即 {p_n } 为 X 的概率质量函数 PMF 所构成的数列），那么有概率生成函数：F_X(x)=\sum^{+\infty}_{i=0}P(X=i)x^i，概率生成函数具有一些性质，这些性质可以简化我们做题时的一些推导…… ......

题目 神奇模拟题。最直接的做法就是每个石头暴力向下滚，有 \(60\) 分。但是大样例跑了 \(15s\)。稍微观察一下，会发现很多次循环都是在重复向下走到一格空位上，于是考虑优化：用 set 维护每一列的那些位置有障碍（包括石头），每次直接 lower_bound 跳到下一个位置，会快很多，大样例 ......

刘宏 计算机系统结构(第二版)尹朝庆主编 华中科技大学出版社 出版时间:2006年08月 刘宏 计算机系统结构(第二版)尹朝庆主编 华中科技大学出版社 出版时间:2006年08月 本书以提高计算机性能的并行化概念、方法和技术为主线，以计算机性能的分析计算方法为依托，介绍计算机系统结构的基本概念和基本 ......

原题链接：P6370 思路 题意不多赘述。 首先这道题的 \(60\) 分暴力很好打，直接按题目中的操作做即可，时间复杂度 \(O(nr)\)。 考虑优化暴力。我们会发现很多次石头的起始点为同一列的情况，其实每一次下落的轨迹是差不多的。具体来讲应该是第一次下落的轨迹一定包含了后面每一次的轨迹。所以我 ......

这题难点在理解题意。没有任何技术含量：( 题目分析：1.“可持续发展”到底什么意思？Make ends meet.也就是说能养活的那些人一年消耗的等于地球一年产生的。 2.题中为什么要给x,a,y,b？为了求等量关系。注意，这里"x 亿人生活 a 年，或供 y 亿人生活 b 年"用的是地球新生的资源 ......

lxl 上课讲的题，来写个题解。 样例很强，赞美 lxl！青蛙，呱 ????。 \(\text{rldcot} = \text{range lca depth count on tree}\)。/yiw（猜的）。 题目传送门 给出一棵 \(n\) 个点的有根树。定义 \(\text{LCA}(x,y ......

[Luogu P4548 CTSC2006] 歌唱王国 提前约定：\(\text{border}\) 指的是公共前后缀。 题意 一个无限长的字符串 \(S\)，其中每个字符都是 \([1,n]\) 中的一个随机整数，求对于给定的字符串 \(t\)，\(S\) 中包含 \(t\) 的最短前缀的期望长度 ......

看到不好维护的取模相关信息，想到根号分治。设值域为 \(V\)，根号分治的阈值为 \(B\)。 对于模数不超过 \(B\) 的情况，我们需要利用情况数为 \(O(B)\) 这一性质。在每次插入元素时动态维护所有情况的答案，查询时查表回答即可。 对于模数超过 \(B\) 的情况，我们需要利用商数个数为 ......

P7880 [Ynoi2006] rldcot 题意 区间虚树数颜色。 题解 十分好的一道题目，绕来绕去又绕回最初的思路了。 首先考虑怎么写出 \(O(nq)\) 的暴力，显然就是扫描树上的每一个点，然后判断有没有点跨子树。 然后考虑到我们求的是虚树颜色数，所以考虑莫队，删除和插入都可以通过找前驱和 ......

给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。 |x| 的值定义为： 如果 x >= 0 ，那么值为 x 。如果 x < 0 ，那么值为 -x 。 示例 1： 输入：nums = [1,2, ......

P1060 [NOIP2006 普及组] 开心的金明 简单的01背包问题 点击查看代码 #include<bits/stdc++.h> using namespace std; int f[30005]; int main() { int n, m; cin >> n >> m; for (int ......

先来看第一问。 发现直接做要考虑两数中间的数能否变得合法，所以按套路将 \(a_i\) 减去 \(i\)，这样就只要变成单调不降，只要两数合法中间的数就一定能变得合法。考虑不改变的那些数，它们一定单调不降，所以答案就是序列总长度减去最长不下降子序列的长度。 接下来看第二问，尝试观察一些性质： 可能有 ......

原题 是思路非常值得学习的一道题 第一问： 首先我们感性上觉得这题应该和LIS有一点关系，但里面有一点问题： 17 50 50 50 18 如果我们求LIS的话，我们会认为只需要改掉50 50 50即可，但其实我们只改掉这些数，我们是无法做到让数单增的 我们发现这个限制写成数学语言即为：\(a_i ......

题目链接1、题目链接2 注意到这道题本质就是一个矩形求和矩形赋值的操作。其中满足：对于任意一个点，每次赋予的权值是单调递增的。 这看起但就像是一个二维线段树能做的范畴。但是众所周知，二维线段树的外层无法进行标记上传操作（无法 pushup），故而这题我们考虑标记永久化。同时，为了简化问题，我们先关心 ......

# luogu P2322 [HNOI2006] 最短母串问题 [题目链接](https://www.luogu.com.cn/problem/P2322) 思路比较的简单的 dp 题。 首先看数据范围，$n \leqslant 12,len\leqslant50$ 应该是状压没跑了。 考虑设 $f ......

## 题目大意 给定 $N$ 对数据，每对数据包含两个整数 $A_i$ 和 $B_i$，表示这一对数据的 $v_i$ 的范围：$A_i \leq v_i \leq B_i$。又将这 $N$ 对数据分为 $P$ 组，其中 $K_i$ 表示第 $i$ 组数据中有多少对数据。 我们设第 $i$ 组数据中将 ......

[Problem](https://www.luogu.com.cn/problem/P1064) ### Analysis 我们发现如果忽略主从关系，那这道题就是一个裸的 01 背包问题。 主从关系处理也非常简单，借鉴 [P2014 选课](https://www.luogu.com.cn/pro ......

题目链接：[https://www.luogu.com.cn/problem/P2503](https://www.luogu.com.cn/problem/P2503) 模拟退火 + 贪心。 ```c++ #include using namespace std; int n, m, a[22], ......

# 赵神牛的游戏 ## 题目描述 在 DNF 中，赵神牛有一个缔造者，他一共有 $k$ 点法力值，一共有 $m$ 个技能，每个技能耗费的法力值为 $a_i$，可以造成的伤害为 $b_i$，而 boss 的体力值为 $n$，请你求出它放哪个技能，才可以打死 boss。 当然，赵神牛技术很菜，他一局只放 ......

## 思路 ### 01背包模版题，唯一不同的是加了一个条件就是价格与重要度的乘积。 转移方程为：```dp[j]=max(dp[j],dp[j-w[i]]+w[i]*v[i]);``` 这里加了滚动数组优化。 ## 代码 ```cpp #include #define ll long long # ......

# [P2458 保安站岗](https://www.luogu.com.cn/problem/P2458) **思路：** 树形DP 三个状态： - dp[i][0]：节点 i 位置放保安的最小花费 - dp[i][1]：节点 i 位置不放保安，但被子节点的保安看守 - dp[i][2]：节点 i ......

首先我们定义“圈”为与原点距离相等的点集。 ``` . . . 3 . . . . . 3 2 3 . . . 3 2 1 2 3 . 3 2 1 0 1 2 3 . 3 2 1 2 3 . . . 3 2 3 . . . . . 3 . . . ``` ### 暴力： 把圈放到堆里，然后每次取出代 ......

[洛谷传送门](https://www.luogu.com.cn/problem/P4548 "洛谷传送门") 结论：答案为 $\sum\limits_{s_{1 \sim k} = s_{m - k + 1 \sim m}} n^k$。 记一下两种理解方法。 假设有人开了一个赌场，每一秒钟有一位赌 ......

[P4645 [COCI2006-2007#3] BICIKLI](https://www.luogu.com.cn/problem/P4645 "P4645 [COCI2006-2007#3] BICIKLI") 题意：求一张 $n$ 个点的**有向**图中 $1$ 号点到 $2$ 号点的路径数。 ......

###### ~~该s的背包~~ # [NOIP2006 普及组] 开心的金明 ## 题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过$N$元钱就行”。今天一早金明就 ......

题目传送门：[link](https://www.luogu.com.cn/problem/P2596)。 ## FHQ-Treap 解题的关键在于如何来求出一本书上面有多少本书，但考虑到我们里面没有像权值一样的东西来让我们用按值分裂来完成这个操作，所以考虑用按排名分裂来实现。 我们按照先后顺序把所 ......

题意翻译 【题目描述】 三个整数分别为 A,B,CA,B,C。这三个数字不会按照这样的顺序给你，但它们始终满足条件：A < B < CA ......

//[POI2006] OKR-Periods of Words:https://www.luogu.com.cn/problem/P3435 //题意就是求每个子串的最小公共前后缀,也就是让我们的next数组缩到最小就可以 //这里要记忆化一下,枚举到i的时候可以直接跳到j,减少枚举次数 #inc ......

我们先不考虑 $dep$ 的问题，先来研究有多少种不同的 $lca(i,j)$。 考虑改询问为贡献，计算一个 $l$ 可以成为哪些 $(i,j)$ 的 lca。这个东西可以写成若干个点对对吧，倘若我们忽略掉一共有 $O(n^2)$ 个点对的事实的话，我们的问题就转化成了有若干个被染成某些颜色的区间， ......