Luogu

[Link](https://www.luogu.com.cn/problem/P6816) **题意** 给定一个小写字母串 $s$，求： - 有多少字符串 $t$ 可以超出头尾地，可重复地覆盖 $s$。 - 在上面的条件下，最短的 $t$；如果有多个，输出字典序最小的。 $|s| \leq 2 ......

[TOC] # 题目描述 [P4069 [SDOI2016] 游戏](https://www.luogu.com.cn/problem/P4069) > 一棵树，树上有 $n$ 个节点，最初每个节点上有$1$个数字：$123456789123456789$。有两种操作： $\centerdot$选择 ......

[TOC] # 题目大意 [题目链接](https://www.luogu.com.cn/problem/P3733 "题目链接") >给出一张 $n$ 个点 $m$ 条边的连通无向图，边带边权 $w_i$ 。有以下三种操作，共 $q$ 次： $\centerdot$在点 $x,y$ 之间加入一条边 ......

[Link](https://www.luogu.com.cn/problem/P4711) 一道简单的模拟题，评绿可能有点高了。 因为没有括号嵌套，难度瞬间降了一个档次，我们直接对着化学式扫一遍即可。 若扫到左括号，说明接下来都是在括号内的，我们标记一下。 若扫到大写字母，说明出现了一个新的元素， ......

题目传送门：[luogu P2324 [SCOI2005] 骑士精神](https://www.luogu.com.cn/problem/P2324) # 题意  # 分析 数据范围比较小，适合搜索 ......

原题：[P9474 [yLOI2022] 长安幻世绘](https://www.luogu.com.cn/problem/P9474 "P9474 [yLOI2022] 长安幻世绘") 看到很多大佬的题解直接讲了做法，本蒟蒻看得不是很懂，调了很久才把这题做出来，于是写了这篇比较详细的题解谈一下我做这 ......

题目传送门：[P3203 [HNOI2010] 弹飞绵羊](https://www.luogu.com.cn/problem/P3203) # 题意 $n$ 个数，满足 $i #define int long long using namespace std; const int N = 2e5 + ......

# 区间方差 [link](https://www.luogu.com.cn/problem/P5142) 线段树大水题（确信） 这道题没有区间修改，所以我们不用写懒标记 ~~所以出题人听我说谢谢你~~，想写懒标记的去[这道题](https://www.luogu.com.cn/problem/P1 ......

# 有线电视网 ## 题目描述 某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费 ......

[原题链接](https://www.luogu.com.cn/problem/P4552 "原题链接") 第一步对于学过差分的人应该不难想 定义差分数组 $dis \quad s.t. \quad dis[i] = a[i] - a[i-1] $ 那么不难发现问题一只要让 $dis[2] ... ......

小清新 prufer 序列。 > 给定 $n,m$，求 $n$ 个点且最大度数为 $m$ 的有标号无根树个数。 看到度数，不难想到 prufer 序列。 众所周知，prufer 序列给出了长度为 $n-2$ 值域为 $n$ 的序列与带标号无根树的双射。某个点的度数为 $d_u$，那么 $u$ 在 p ......

upd 2023/3/16：更改了时间复杂度的错误。 ~~其实是暴力。~~ 因为这是模板题，所以模板的前置知识也要讲。 - 前置知识：FWT 计算或卷积。 这里只需要掌握快速计算或卷积的方法，所以内容较少。如果向了解更多（比如异或卷积）的话可以去 [P4717](https://www.luogu. ......

简单题。 发现 $m$ 很小，所以一个箱子可以用一个二进制数 $a_i$ 表示，值域 $w=2^{20}$。然后就变成取出若干个 $a_i$ 使得或起来为全集的方案数。 将所有 $a_i$ 按位取反，即求若干个 $a_i$ 与起来为空集的方案数，就是[这题](https://www.luogu.co ......

### 题意： 给定长度为 $n$ 的序列 $a_i$，$m$ 次操作，操作分为 $3$ 种： 1. 给定两个整数 $l,r$，翻转区间 $[l,r]$。即 $a_l,a_{l+1},...,a_r\to a_r,a_{r-1},...,a_l$。 2. 给定三个整数 $l,r,d$，对于 $i\i ......

$T$ 是节点数为 $n$ 的那棵树，$T'$ 是 Trie 树。带 $'$ 的，比如 $\text{dep}'_u$，表示 Trie 上的信息（注意到 $\text{dep}'$ 要从 $0$ 开始），不带的表示原树。$[u,v]$ 表示 $u\to v$ 的路径，$S$ 是原树上无序点对的全集。 ......

考虑枚举选出来 $i$ 个**没气**的篮球，那么答案可以表示成： $$\text{ans}=\frac{1}{\dbinom{n}{k}}\sum\limits_{i=0}^{k}\dbinom{m}{i}\dbinom{n-m}{k-i}i^L$$ 注意到这里的组合数 $\dbinom{n}{m ......

这里只讲[加强版](https://www.luogu.com.cn/problem/CF280D)，这是严格弱化。 结论是贪心。每次取出最大和连续子段，目前答案加上这个子段和，然后再把这个子段取反（相反数T），然后求整个过程答案的最大值。 考虑费用流模型。对于 $i\le n$，$S\to i$ ......

你也许说得对，但我是真看不懂第一篇题解那个答案式子…… 预处理是差不多的。 设 $f_u$ 表示从 $u\to fa(u)$ 的期望步数，$g_u$ 为 $fa(u)\to u$ 的期望步数，$d_u$ 为 $u$ 的度数。 那么显然有： $$f_u=\frac{1}{d_u}\left(1+\su ......

好像有道题是求生成树权值和的和的，考虑 $\sum\limits_{T}\sum\limits_{e\in E(T)}w_e$ 咋做。 每条边给一个边权 $v_e(x)=1+w_ex$，然后跑矩阵树： $$\text{ans}=[x]\sum\limits_{T}\prod\limits_{e\in ......

赛时因为 T4 这题一眼没看，事后发现真的神仙。 简化题面后条件为： 1. 所有点出度为 $1$。 2. 从所有点走出去都能走到环上。 不难发现条件仅为判断所有点出度为 $1$，即判断是否是一个**内向基环树森林**。 再看操作： 1. 删掉一条边 $(u,v)$ 2. 对于 $u$，将所有边 $( ......

考场花了一张 A4 的草稿纸在这题上面……还导致 T4 没时间调了。 你要是想看我 T4 挂的多惨可以去看[ T4 题解](https://www.luogu.com.cn/blog/Ender32k/p8819-ti-xie)。 不难发现其实就是给一个 $a_1,a_2,...,a_n$ 和一个 ......

写一下题解，顺便纪念一下考场上少加一个等号挂 100 分的事实。 比今年简单的 csps 不多了……希望 noip 不要寄成这个狗样。 如果说错了请线下打我。 考虑搬到序列上的做法，即给你 $w_1,w_2,...,w_n$，求 $(l,r)$ 中取若干数，构造序列 $p_1=l,p_m=r,\fo ......

分块，但是带 $\log$。 先离散化，然后值域就变成 $O(n)$ 的了。 我们先对每个点维护一个 `bitset`，那么显然答案就是 $u$ 到 $v$ 路径上所有点的 `bitset` 或起来后 $1$ 的个数。 然后可以树链剖分，把链拍成序列，并且对树链剖分后的 `dfs` 序维护 $\sq ......

## solution 开题显然是个树形 dp，只不过在树形 dp 上又增加了背包问题。 我们不妨将每个走廊看成一个点，把交叉口看成边（当然也可以把交叉口看成点，不过写起来麻烦一些），于是就转化为了一棵二叉树。 我们设 $f_{i,j}$ 表示以 $i$ 为根的子树内，花费了不超过 $j$ 时间，能 ......

题目说给定 $n$ 个点 $n$ 个关系，也就是 $n$ 条边，显然是基环树，又因为没有规定一定连通，于是我们可以将题目简化为给定一个基环树森林，点有点权，相邻的两个点不能同时选，问最大点权和。 ### part1 我们先考虑如果没有环，只是树，该怎么做。 这一部分很简单，令 $f_{i,0/1}$ ......

[Problem](https://www.luogu.com.cn/problem/P1168) ### Description 题目描述非常简洁，不作解释。 ### Solution 题目要求对前奇数项求中位数？朴素的做法是暴力，但是范围1e5显然T。这里主要介绍一种堆顶堆的做法。 堆顶堆是什么 ......

这题看着很吓人实则很简单。求输出层，正着求很麻烦，因为知不道谁连向这个点，所以可以反向建边，反着求。 拓扑+dfs，时间复杂度 $\text{O(n + m)}$ ```C++ #include #include #include #define N 105 #define M (N * N / 2 ......

[题面传送门](https://www.luogu.com.cn/problem/P8923) 这不是保序回归板子吗（ 首先你拿保序回归通法做这个题那是一点前途没有，所以你考虑一点更优秀的方法。 众所周知保序回归 $L_{2k+1}$ 问题可以slope trick。考虑设 $f_{i,j}$ 表示 ......

# Luogu 1366 有序表的合并 [link](https://www.luogu.com.cn/problem/P1366) 做法：双指针 注意：这两个数列都有序 代码： ```cpp #include #include #include #include typedef long long ......

title: 洛谷-模板题 date: 2019-07-10 21:01:25 tags: [luoguOJ,Cpp,Algorithm] mathjax: true # [**P3383** 【模板】线性筛素数](https://www.luogu.org/problemnew/show/P338 ......