数 据 结 构 题 树 点分治 P2634 [国家集训队]聪聪可可就是点分治，把长度对3的取模的剩余的个数取出来然后用1,2余数的合并成0的余数的，答案就是cnt[1]*cnt[2]*2+cnt[0]*cnt[0]，至于为什么0的不乘2，因为会重复统计（可能一开始走了左边那个点，然后后面右指针又指到了）（悲）然后gcd搞搞约分就ok了 树链剖分 l…

题面 题目描述 小 $T$ 打算在城市 $C$ 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 $T$ 希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市 C 的 $N$ 个建筑中，这 $N$ 个建筑通过恰好 $N$条双向道路连接起来，…

题面 题面描述 给定一个长度为$n$的序列$a_{1∼n}$。 $q$次询问，每次给出一个区间$[l,r]$，要求找出$[l,r]$的一个子区间$[l′,r′]$，满足它不包含$[l,r]$中所有种类的数，且它的长度$r′−l′+1$最大。你只需输出这个最大长度。 特别提醒，$[l′,r′]$可以是长度为$0$的空区间。 输入格式 第一行一个正整数…

前言 卧槽，距我上次更新博客已经整整1年了... 关于本人之前一直沉迷whk与fgo，久久未动OI和博客，眼看即将NOIP2021，所以我重新开始写博客记录一下我的康复训练之旅。 题目 题面描述 有一个$1∼n$的排列，其中有$m$个位置上的数缺失了。 已知这个排列的逆序对数恰好为$k$，求有多少种可能的排列。 输入格式 第一行两个正整数$n,k$…

前言 其实这篇文章早就想写了，只不过一直咕咕咕着，咕了一年（大雾。 现在对于斜率优化已经产生了十分深刻的李姐了，所以可以放心大胆地胡扯了。 正文 关于一个$DP$方程，如果它的形式如$F[i]=max(or min)(F[j]+(一堆只关于j的式子)+(一堆只关于i的式子))$那么这样我们是可以对其进行单调队列优化的，把复杂度降低一维。但是如果形式…

前言 这是我在中考结束后写的第一篇博客，关于中考他死了。 接下来还有FFT等一众博客要更新，只能慢慢来了。 部分算法为中考前集训学的，现在需要回忆下才能口胡出来，所以先更这篇昨天学习的容斥及广义容斥的姿势。 本文有部分参考于Parsnip的博文可以去他那里补充看看。 正文 容斥原理 这个大家或多或少都接触过，就是给出一些不同性质包含不同数量元素的集…

题面 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对$31011$的模就可以了。（具有相同权值的边不会超过10条） 思路 这题有点ex啊,不知道矩阵树定理或者最小…

题面 给出 $n$个互不包含的字符串，要求你求出一个最短的字符串 $S$，使得这 $n$ 个字符串在 $S$ 中总共至少出现$m$次，问 $S$ 最短是多少。 思路 把题目转化一下，求出$F[i][j]$表示把$S[j]$接在$S[i]$后面的代价，这个用$substr…

题面 FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点 自然是在牧场中现有的T(2 <= T <= 100)条跑道上。 农场上的跑道有一些交汇点，每条跑道都连结了两个不同的交汇点 I1_i和I2_i(1 <= I1_i <= 1,000; 1 <…

题面 给定矩阵A,B和模数p,求最小的x满足 A^x = B (mod p) 思路 一眼看去就是BSGS，很显然这个结论在矩阵中也同样适用，那么把乘法替换成矩阵乘法然后矩阵HASH判重即可。(就这么简单) 代码 #include<bits/stdc++.h> #define LL long long #define Mod 998244353…

前言 别问我为啥不和点分治写一块。。。内容过多了。。。所以分开写 正文 我们知道，在处理树上问题的时候，点分治是一个很好用的算法，但是倘若是多次询问或者是带修改操作，那么就需要重新点分治，这样的效率极其低下，那么我们就考虑重构这整棵树。把每个点与他的子树中的重心（或者假重心，可以看看我点分治那篇的最后update有提到）相连，也就是建father。…