方差 题解noip 2021

P9847 [ICPC2021 Nanjing R] Crystalfly 你说得对，但是刻晴更可爱捏 翻译 给定一个 \(n(1\le n\le10^5)\) 个节点的树，每个节点上有 \(a_i\) 只晶蝶。派蒙最初在 \(1\) 号节点，并获得 \(1\) 号节点的所有晶蝶，接下来每一秒她可以 ......

[USACO23FEB] Equal Sum Subarrays G 题解 题目链接 \(O(n^5)\) 暴力 显然，如果修改 \(a_i\) 的值，只会影响包含 \(a_i\) 的区间的区间和。于是对于每个 \(a_i\)，可以将所有区间分成两类，即包含 \(a_i\) 的区间和不包含 \(a_ ......

题目链接 luogu atcoder 分析 令 \(k=\left \lfloor \frac{n}{2} \right \rfloor\) 对于第三个条件,只需要满足 \(\sum_{i=1}^{k+1}a[i]<\sum_{i=n-k+1}^{n}a[i]\) 即可 有一个 \(trick\)： ......

Yet Another Array Counting Problem 给你一个长度为 \(n\) 的序列和一个数 \(m\)，求有多少个长度为 \(n\) 的序列 \(b\) 满足： \(\forall i \in [1, n], b_i \in [1, m]\)。 对于每个区间 \([l, r]\ ......

P4435 [COCI2017-2018#2] Garaža 给你一个长度为 \(n\) 的序列 \(a\)，单点改，查询区间 \(\gcd\) 不为 1 的子区间个数。 \(n, Q \le 10^5, a_i \le 10^9\)。 先看单次全局查询怎么做。考虑一个分治，每次我们要计算跨过分治中 ......

补补以前懒得总结的零碎东西。 kruskal 重构树 使用条件：求无向图中两点之间所有路径的最大边权的最小值 构造： 依 kruskal 得到最小生成树 从小到大考虑生成树中的边 \((u, v)\) 对于 \((u, v)\)，新建一个结点，作为重构树中 \(u, v\) 的父结点 该结点的点权为 ......

Link SPOJ1805 HISTOGRA - Largest Rectangle in a Histogram Question 在一条水平线上有 \(n\) 个高为 \(a_i\) 的矩形，求包含于这些矩形的最大子矩形面积。 Solution 我们定义 \(L_i\) 表示有 \(a_i\) ......

注意到当前移动到的位置并不重要，重要的是经过的点数和 \(1\) 所在强连通分量大小，因此把它们放进状态里：设 \(f_{i,j,k}\) 表示进行 \(i\) 次移动，经过了 \(j\) 个不同的点，此时 \(1\) 所在的强连通分量大小为 \(k\) 的方案数。 考察下一次移动到的点的情况： 没 ......

2023NOIP A层联测30 总结 \(T1\) 给定一个序列 \(a\) ，有 \(m\) 次操作\(l , r , v\) ，表示将 \([l , r]\) 内的每个 \(a_i\) 变为 \(\max (a_i , v)\) \(n \le 10^5 , m\le 10^7\) 看到 \(n ......

容易想到将询问离线下来，按 \(v\) 从大到小排序，这样后面的修改一定不会对前面的修改造成影响。然后可以用并查集把已修改过的点缩起来。注意到 \(m\) 会到 \(2\times 10^7\)，应该使用基数排序，复杂度为 \(\mathcal O(\frac{m \max{v_i}}{base} ......

[LNOI2014] LCA 题目描述 给出一个 \(n\) 个节点的有根树（编号为 \(0\) 到 \(n-1\)，根节点为 \(0\) ）。 一个点的深度定义为这个节点到根的距离 \(+1\)。 设 \(dep[i]\) 表示点 \(i\) 的深度，\(\operatorname{LCA}(i, ......

T1 贪心地找到和最大的组的较大数删除是最优选择，因此开线段树维护全局最大数，并单点更新指定位置的值。 参考代码 展开代码 #include<bits/stdc++.h> using namespace std; #define fi(l,r) for(int i=l;i<=r;++i) #defi ......

T1 KAMEN 只能说一言难尽。 60pt暴力模拟每一个石头往下掉的情况。 在这里，我并没有打暴力，而是用set存储了每一列的X和O的石子分布情况。当前节点的位置在(x, y)，寻找x列中比y大的第一个位置在ny(这里可以用upper_bound)，那么石子在这一列能往下掉到的位置就是（x, ny ......

只能说相当套路的一道题目。 对于区间异或和，我们不妨先做一遍区间前缀异或和，记作 \(sum_i\)，表示 \(a_1\sim a_i\) 的异或和，那么区间 \([l,r]\) 的异或和即可转化为 $sum_r \bigoplus sum_{l-1} $，那么我们呢只需对 \(n+1\) 个数字进 ......

题意简述 Kelly 寄出去 \(n\) 封邀请函，但她希望只有小于等于 \(m\) 个人收到他们自己的邀请函（即有至少 \(n-m\) 个人收到了别人的邀请函）。 思路形成 容易发现，这道题是一个典型的错排题，我们只需要分别求出 \(n-m\) 个元素到 \(n\) 个元素的错排即可。 接下来为错 ......

P4755 Beautiful Pair 给你一个长度为 \(n\) 的序列 \(a\)，求有多少个区间 \([l, r]\) 满足 \(a_l \cdot a_r \le \max_{i = l}^r a_i\)。 \(n \le 10^5, a_i \le 10^9\)。 首先按最大值位置分治。 ......

【题解】CF1891E - Brukhovich and Exams https://www.luogu.com.cn/problem/CF1891E 我们考虑把区间分段：若两个相邻的数不互素，中间分开；若两个相邻的数中有且仅有一个 \(1\)，中间分开。那么我们得到了两种区间：全 \(1\) 区间 ......

[COCI2021-2022#4] Izbori 题目描述 Malnar 先生正在竞选县长，这个县一共有 \(n\) 栋房屋，每栋房屋里都住着一位居民。Malnar 先生知道，选举的赢家不一定是最好的候选人，而是在选举前举办的宴会最好的候选人。因此，在选举前几天，他将邀请第 \(l\) 至 \(r( ......

Factor-Free Tree 当一棵二叉树中的每个节点的权值都与它所有祖先的权值互质时，我们称它为 factor-free tree。 给你一棵按照中序遍历的顺序的权值序列 \(a\)，求这个序列是否对应这一棵 factor-free tree。 如果是就输出每个节点的父亲。 \(n \le 1 ......

题目大意 有一个 \(n \times n\) 的地图，每个格子里有一个袋鼠，要想让所有的袋鼠都到 \((a,b)\) 这个点。你有 \(4\) 种操作，分别为 U，D，L，R。分别可以让每只袋鼠都往上下左右移动，如果某只袋鼠越界了，也就是超出地图，则不移动。求操作序列。注意，操作序列长度不超过 \ ......

思路 这题数据范围小，暴力就可以了。 首先我们用 map 来统计每个人的下标，用 \(bk_{i,j}\) 表示第 \(i\) 个人第 \(j\) 题是否知道答案。 对于每次合作交流，暴力修改就可以了，先统计出两个人的下标，假设一个为 \(x\)，另一个为 \(y\)。 然后，如果 \(bk_{x, ......

题意 有一个商店和 \(N\) 名员工，其中第 \(i\) 名员工在第 \(1 \sim A_i\) 天工作，在第 \(A_i + 1 \sim 2 \times A_i\) 休息，接下来每 \(A_i\) 天改变一次状态。 每一天你都可以选择一名来上班的员工并为其颁一个奖，求使得每名员工都获得至少 ......

Special Segments of Permutation 给你一个排列 \(p\)，求有多少个区间 \([l, r]\) 满足 \(p_l + p_r = \max_{i \in [l, r]} p_i\)。 \(n \le 2 \times 10^5\)。 按最大值分治，记当前的分治中心为 ......

首先将边反向，再按 \(r\) 从大到小排序，这样可以使得答案的转移没有后效性。 令 \(ans_i\) 表示 \(i\) 这个点最少有多少资产方能无限地走下去。（初值为 \(inf\) ） 依次枚举每一条边。（令 \(u\) 为这条边的起点，\(v\) 为这条边的终点） 首先对现在的图进行一遍 t ......

Min + Sum 给你两个序列 \(a\)、\(b\) 和 \(S\)，求满足一下条件的区间 \([l ,r]\) 的数量： \(\sum_{i = l}^r b_i + \min_{i = l}^r a_i \le S\)。 \(n \le 2 \times 10^5\)。 考虑按最小值分治，即 ......

题意 给定一张有向图，询问将每条有向边反向过后整个图的强连通分量的个数是否发生改变。 数据范围：$n\le 1000,m\le 200000$。 思路 分类讨论，讨论强连通分量是增加了还是减少了，假设修改的边是 $u\to v$。 强连通分量减少 因为只修改了一条边，所以强连通分量减少的情况肯定是 ......

2023NOIP A层联测30 A. 草莓列车 目录2023NOIP A层联测30 A. 草莓列车题目大意思路code 题目大意 给定一个序列 \(a\) ，有 \(m\) 次操作，将 \([l , r]\) 的每个 \(a_i\) 变为 \(max (a_i , v)\) \(n \le 10 ^ ......

思路 带权并查集模板。 如果对于一个三元组 \((a,b,c)\) 如果它能够添加到 \(S\) 中一定满足如下条件中的一条： \(X_a,X_b\) 满足其中有一个是「不确定」的。在这里 ......

Day -4 17 号我们就要出发。 好快啊。 写了博客，并不是很全，打算回来继续完善。 想起之前有个 dfs 序求 lca 的坑还没填完。 呃等我以后直接重构吧。 看了辰星凌的DP优化，打算板刷一下题。 UVA 的题在 \(4\) 发 UKE 后终于 AC。 给老师批了卷子。 NOIP 很快就到了 ......

「GLR-R3」惊蛰 题目背景 「微雨众卉新，一雷惊蛰始」 中午，休息室，阿绫肩膀上。 “我有一个愿望，参加全国音乐祭，获奖，和阿绫一起，摆脱这训练的苦海。” “为热爱而到来，为抽身而努力……吗”。 正午的阳光渗过窗帘，抚上困倦的人儿的脸颊。天依的左手悄悄搭上阿绫怀里的吉他， “铮——” 蛰虫被雷声 ......