书架p2596 2006 zjoi

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

## 题目描述 九条可怜是一个喜欢算法的女孩子，在众多算法中她尤其喜欢深度优先搜索（DFS）。 有一天，可怜得到了一棵有根树，树根为 $\mathit{root}$，树上每个节点 $x$ 有一个权值 $a_x$。 在一棵树上从 $x$ 出发，寻找 $y$ 节点，如果使用深度优先搜索，则可描述为以下演 ......

# [ZJOI2010]排列计数 ## 题目描述 称一个 $1 \sim n$ 的排列 $p_1,p_2, \dots ,p_n$ 是 Magic 的，当且仅当 $$\forall i \in [2,n],p_i > p_{\lfloor i/2 \rfloor}$$ 计算 $1 \sim n$ 的 ......

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

# [POI2006] OKR-Periods of Words ## 题面翻译 对于一个仅含小写字母的字符串 $a$，$p$ 为 $a$ 的前缀且 $p\ne a$，那么我们称 $p$ 为 $a$ 的 proper 前缀。 规定字符串 $Q$（可以是空串）表示 $a$ 的周期，当且仅当 $Q$ 是 ......

标签:子集反演,动态规划 # [ZJOI2016]小星星 ## 题目描述 小 Y 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 $n$ 颗小星星，用 $m$ 条彩色的细线串了起来，每条细线连着两颗小星星。 有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 $n-1$ 条 ......

dp 套 dp 经典例题。 这种题一般都是给你一个奇怪的合法条件，然后去做一些计数之类的东西，直接设计状态很不好做。我们考虑先设计一个判定合法的 dp，以这个 dp 的状态和结果作为状态去 dp。 更一般的，我们发现 dp 的过程有初始状态和终止状态，转移看成有向边，可以建出一个自动机来。dp 套 ......

# [[NOIP2006 普及组] 开心的金明](https://www.luogu.com.cn/problem/P1060 "[NOIP2006 普及组] 开心的金明") ## 题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对 ......

### 题意: 有个n个骑士,每个骑士都有且仅有一个自己最厌恶的骑士,现在需要选出一批骑士,要求每个骑士在其中都不会碰上自己最厌恶的骑士,请输出能有的最大战力和 ### 思路: 该题和没有上司的舞会非常相似,可以逆序查找讨厌当前骑士的所有骑士,靠构造带根节点的数来求出每个连通块的最大战力 ### 遇 ......

Internal Server Error: /lotus/sectors/getAll/129/ Traceback (most recent call last): File "/root/.cache/pypoetry/virtualenvs/lotus-mammoth-backend-BC7 ......

P3345 [ZJOI2015]幻想乡战略游戏 这道题还是比较有意思的,做了一个比较长的时间,但是点分树实在是太毒瘤了,所以记录一下线段树的做法。 题面 给一棵树,有边权,每次修改一个点的点权,修改完后输出所有点到这棵树的带权重心的贡献,即$\sum dis_i\times val_i$ 题解 考虑 ......

最近使用django在做一个定时任务场景，采用的是gjango-apscheduler模块，出现了一个问题，我的定时场景是每天的8点和17点启动一个任务，但是每次只能第一次生效，第二天就会出现2006，server has gone away这个错误，看到错误的第一反应就是数据库服务挂了？？因为看详 ......

ZJOI2018 树- 节点 1 作为树的根。- 对于 $i \in [2, n]$ ，独立地从 $[1, i)$ 中等概率随机选取一个节点作为 $i$ 的父亲。通过上面的方法独立的随机生成 $k$ 棵 $n$ 个节点的有根树 $T_1$ 至 $T_k$ ，他们两两同构的概率是多少。denote $ ......

传送门 简化题意 给你 $m$ 个码头，码头之间有双向边连接，$n$ 天，其中一些码头在某些天会不可用，这 $n$ 天都要有一条从 $1$ 到 $m$ 的路，每一次更换道路会需要 $k$ 的代价，求这 $n$ 天每天从 $1$ 到 $m$ 的距离之和与更改道路的价值之和的最小值。 Solution ......

# 简化题意 给你 $m$ 个码头，$n$天，其中一些码头在某些天会不可用，这 $n$ 天都要有一条从 $1$ 到 $m$ 的路，每一次更换道路会需要 $k$ 的代价，求这 $n$ 天每天从 $1$ 到 $m$ 的距离之和与更改道路的价值之和的最小值。 # Solution 首先我们能想到一个 ......

「ZJOI2015」地震后的幻想乡 题意：给定一张图，每条边的边权在 $[0,1]$ 中随机，求最小生成树的最大边权的期望。其中这个很重要：对于 $n$ 个 $[0,1]$ 之间的随机变量，第 $k$ 小的那个的期望值是 $\frac{k}{n+1}$ 那暴力就很容易了，假设我们已经按边权从小到大排 ......

首先转化一下答案： 根据提示，发现其实只需要求出 $e_i$ 对应的排名 $rk_i$ 就可以得出其期望值 $\frac{rk_i}{m + 1}$ 所以只需要求排名的期望，最后答案除上 $m + 1$ 就行了 不难想到能把期望值拆成 $\sum_{k = 1} ^ m P(k)\times k$， ......

线性规划做法 同时也作为线性规划对偶的一个小小的学习笔记。 以下 $\cdot$ 表示点积，$b,c,x,y$ 是行向量。 $A$ 是矩阵，对于向量 $u,v$ 若 $\forall i,u_i\leq v_i$ 则称 $u\leq v$，$\geq$ 同理。 线性规划标准型： $$ \max c\ ......

$\color{purple}\text{P2596 [ZJOI2006]书架}$ 解题方法 考虑使用 $\text{FHQ}$ 平衡树 ，我们只使用编号，而不使用权值，平衡树上的先序遍历即为书的放置顺序。 $\text{Query}$ ：这是最简单的操作，直接查询即可。 $\text{Ask}$： ......

题目描述 给出 $n$ 个数 $q_1,q_2, \dots q_n$，定义 $$F_j~=~\sum_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}~-~\sum_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - ......

Operating Systems Semester-1 2023COMP2006 - Operating SystemsCURTIN UNIVERSITYSchool of Electrical Engineering, Computing and Mathematical SciencesDis ......

题目链接：1105. 填充书架 方法一：记忆化搜索 解题思路 $dfs(i)$：从 $i$ 到 $n - 1$ 书放置的最小高度总和； 对于每一层：枚举当前层放置从 $i$ 开始的书，放置几本时整体的高度最优，按题目要求，必须是从 $i$ 开始的连续几本书，当前层的高度取最优方案中书的最高值； 返回 ......

P5327 [ZJOI2019] 语言 题目描述 九条可怜是一个喜欢规律的女孩子。按照规律，第二题应该是一道和数据结构有关的题。 在一个遥远的国度，有 $n$ 个城市。城市之间有 $n - 1$ 条双向道路，这些道路保证了任何两个城市之间都能直接或者间接地到达。 在上古时代，这 $n$ 个城市之间处 ......

SPEC2006的学习与总结 摘要 最近特别想进行一些性能验证工作. 所以研究了spec2006 然后想整理一下之前的内容. 想着将内容整理一下. 这次主要是抄别人的. 知识来源: https://blog.csdn.net/wkl_venus/article/details/127688671 获 ......

第一天开始刷题，难度还是有的，磨了2个小时，写了三个题，这次先写一个最简单的题的题解。 #include <bits/stdc++.h> using namespace std; int n; int a[101], b[101]; int main(){ cin >> n; int cnt=0; ......

[ZJOI2007] 时态同步-错题重解 题目描述 小$Q$在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字$1,2,3…$.进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线 ......

SPECCPU2006的学习与使用 摘要 这个周末问题不是很多, 陪孩子写作业时顺便研究了下SPEC2006 虽然比较落后了. 但是总比没有要强一些. 其实集团有资源, 但是联系不到人, 只能自己学习和研究了. 找了很多华为博客上面的知识点. 但是依旧有很多问题 想着先总结这, 希望有时间慢慢完善 ......

正赛在 2023.4.1 - 2023.4.2。 愚人节省选。挨创。 前情提要：$\rm NOIP$ $\rm297pts$ 苟上 ZJ 队线。 其实前面一长串（Day $-25\sim-5$）是纪中集训游记。 Day $-26$ THUPC 初赛，打拉垮了。 Day $-25$ 飞去中山纪中集训。 ......

NOIP 挂成了答辩，没上队线。ZJ-018。 4.1 t1 签到，几分钟搞完过了。 t2 想了想感觉没那么简单。不会圆方树，就在 dfs 树上想。找了找性质，看起来可以 DP，编了个看起来很对的 $\Theta(n \sqrt n)$ 做法。写的时候总感觉有点难受，不过显然不能摆，所以还是继续写下 ......

这些测试成绩基本上是本人自己测试的结果。下表中有来自spec官网的两个成绩，因为测试年份较早，系统环境和编译器都较老，测试成绩本人实测的还差，所以仅作为参考。部分测试启用了自动并行和附加的优化库，是为了追求较好的测试成绩，体现的不是普通用户系统环境和常规应用软件的性能水平。国产CPU任重道远，从当前 ......