方差 题解noip 2021

#6029. 「雅礼集训 2017 Day1」市场 题目描述 数据范围1e5 题解 对于这种数据貌似可以快速缩小的题目，我们可以用势能分析来证明其某暴力或者什么做法的复杂度。 设某节点的势能函数是点内数的极差，每次除一个数极差一定会减半，总共会被除 $\log$ 次。 然而有特殊情况，如果考虑下取整 ......

题目描述 Alice 和 Bob 在玩一个游戏。 游戏在一棵有 $n$ 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 $123456789123456789$。 有时，Alice 会选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$ ......

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

注意到对于全局最小值 $x$ ，一旦我们可以合并它，我们一定会优先合并，因此 $x$ 和与 $x$ 相邻且更靠近起点的位置构成一个决策整体，定义为广义节点。 合并一个广义节点的贡献为 $x\times sz+c$，然后会让 $x\gets x+a$。 考虑比较先后合并两个广义节点 $x,y$ 的决策 ......

「八云紫」无数次痛苦地询问，为什么我们还活着？ ……而「古明地恋」从不会回答。 恋恋闭上了觉之眼。 思路 容斥 + dp. $\gcd$ 相关，考虑 $\mu$ 反演或者 $\varphi$ 反演。 本质上都和容斥差不多，不如直接一步到位考虑容斥。 把权值拆成 $\gcd$ 和对应的方案数两部分，考 ......

题目背景 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。 题目描述 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中 ......

比赛链接：Dashboard - 2022年中国大学生程序设计竞赛女生专场 - Codeforces A. 减肥计划（模拟） 模拟，如果队列第一个人体重是最大的了，则这个人的位置不会再变，直接输出即可。 #include <bits/stdc++.h> using namespace std; us ......

思考如何将到 $u$ 距离短的和到 $v$ 距离短的节点分别处理出来。发现对于一次询问 $(u,v)$，可以将所有节点分成三类： 除 $u$ 和 $v$ 的 LCA 的子树外的所有节点。 将 $u$ 至 $v$ 的最短路径的最中间的边删掉后组成的两棵树中的其中一棵树中的所有节点。 不属于以上两类节点 ......

Preface 有趣的一道 ds，赛后不看题解做出来了。 Solution 首先有一个性质：$\varphi(x)$ 经过 $\mathcal{O}(\log x)$ 次迭代后变为 $1$。 证明： 若 $x$ 为奇数，$\varphi(x)=x\sum_{i=1}^{k}\frac{p_i-1}{ ......

在中国的 IT 环境里，大多数场景下，学习算法的目的在于通过笔试算法题。 但算法书林林总总，有时候乱花渐欲迷人眼。 杜甫有诗云：读书破万卷，下笔如有神。不管选择哪本书，只要深入学习，分层次，逐层进阶，一定可以将算法攻克。 笔者强烈推荐一个 Github 开源项目 LeetCode-Go，你不仅可以把 ......

深度学习基础入门篇[六]：模型调优，学习率设置（Warm Up、loss自适应衰减等），batch size调优技巧，基于方差放缩初始化方法。 ......

首先观察这个奇怪的子树为 $1$ 或 $-1$ 的限制。 看不出来性质，润了。 我们不如直接把 $A$ 树和 $B$ 树拆开，变成两棵树，然后在树上留一下匹配的性质。 第一，我们对着样例构造一下，发现似乎有解的样例都有 $abs(X_i)\le 1$ 的解。 这就提示我们猜用 $-1,0,1$ 就够 ......

计数数列个数，要满足能划分为若干个两端相等区间。 首先容易想到DP。 我想的是按段分阶段转移，显然不行，因为很容易算重，一个数列能有多种划分方案则会被算多次。 因此直接计数数列的每位，$g(i,j)$表示前$i$位有$j$种值存在位置的前一个数列满足条件的合法序列方案数，$f(i,j)$则为不合法序 ......

T1 给定一个序列，问有多少个区间的众数次数>=k sol:考虑two-pointer。枚举左端点，寻找最小的右端点是的众数次数>=k 推导后发现需要支持以下功能 1.增加某一个数的出现次数 2.减少某一个数的出现次数 3.查询众数的出现次数（即出现次数最多的数字的出现次数） 这些功能可以抽象化可以 ......

有 n 个同学（编号为 1 到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti​ 的同学。 游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以... ......

# [NOIP2009 普及组] 多项式输出 ## 题目描述 一元 $n$ 次多项式可用如下的表达式表示： $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,a_n\ne 0$$ 其中，$a_ix^i$ 称为 $i$ 次项，$a_i$ 称为 $i$ 次项的系 ......

比赛链接：https://codeforces.com/gym/104081 目前就做了 8 题，里面还有 4 个水题…… 水题：ACEG，模拟题意即可，C 和 E 有一些细节。不想写题解了 F 首先目标是如何将这 9 个数分组，由于答案一定存在，考虑随机化，固定 $a_1 \in S_1$，然后随 ......

机器翻译 单向链表，如果 $i$ 在内存里，那么用 $nxt[i]$ 来记录他的下一个单词，每次要插入的时候，如果当前链表的长度小于 $m$，那么直接把他插入的末尾，如果等于 $m$，就把链表的第一个从链表里弹出来，再把这个元素加进去。 $Code :$ #include <bits/stdc++. ......

首先，我们来思考我们要构造的是什么。 我们要构造的是一个无论怎样操作字典序都会变小的序列，且这个序列的字典序是最小的。 然后考虑字典序会变大的条件。 如果字典序变大了，那么一定是在前 $i-1$ 位不变的前题下，$i$ 位的变大了。那么变大的一定是从后面来的。 而我们考虑所有的数对 $(a_i,a_ ......

写点题目转换下心情吧 A-CAPS LOCK 大水题 B-Yellow and Red Card 大水题 C-Four Variables 给定一个数$N$，问有多少个有序正数数组$(A,B,C,D)$，满足$A\times B+C\times D=N$。 这题荒芜的大脑拒绝思考，看着复杂度不超，写 ......

赛时开始一眼线段树分治，交了几发都 T 了，就意识到事情不对。后来想了想发现势能分析不能带撤销。。。 后来加了一些不能改变复杂度假了的优化，没过之后就自闭跑路了。。。 赛后听别人说了个楼房重建就明白怎么做了。 首先，我们离线下来把 $a$ 排序，去重（这样方便一点，不然权值线段树上的空节点得特判）， ......

首先，我们来证明一个引理： 若最优解中，最终串中的字符 $j$ 在最早来自原串中的字符 $i$（显然，$i\le j,s_i=t_j$），则称 $j$ 的匹配是 $i$，则在所有的匹配方案中，$t_j$ 会在全串存在匹配的前提下尽量选择 $|i-j|$ 最小的的 $s_i$ 进行匹配。 我们可以运用 ......

可以使用 Python 的统计模块 statistics 来计算列表的均值、方差、中位数等,下面是一些示例代码： import statistics # 定义一个列表 my_list = [1, 2, 3, 4, 5] # 计算均值 mean = statistics.mean(my_list) p ......

P2680 NOIP2015 提高组 运输计划 最小化最长的路径，考虑二分答案。 问题转化成检验删去一条边的边权后，最长路径权值能否不超过 $x$。 考虑没删边权时，原先那些不超过 $x$ 的路径，删去边权后肯定不会影响，直接忽略。 考虑原先比 $x$ 长的那些路径。我们期望删边权后这些路径全部变短 ......

传送门 CF1033G Chip Game 题目大意 有 $n$ 个石子堆，每堆有 $a_i$ 个石子。A 与 B 轮流取，A 每次只能取 $x$ 个，B 每次只能取 $y$ 个。 求对于所有 $x,y \in [1,m]$，A 必胜、B 必胜、先手必胜和后手必胜的数量。 $n \le 100,m ......

[SCOI2013]密码 Fish是一条生活在海里的鱼。有一天他很无聊，就到处去寻宝。他找到了位于海底深处的宫殿，但是一扇带有密码锁的大门却阻止了他的前进。 通过翻阅古籍，Fish 得知了这个密码的相关信息： 该密码的长度为N。 密码仅含小写字母。 以每一个字符为中心的最长回文串长度。 以每两个相邻 ......

Cool Slogans 给定一个字符串 $S$，要求构造字符串序列 $s_1,s_2,\ldots,s_k$，满足任意 $s_i$ 都是 $S$ 的子串，且任意 $i\in[2,n]$，都有 $s_{i-1}$ 在 $s_i$ 中出现了至少 $2$ 次（可以有重叠部分，只要起始、结尾位置不同即可） ......

源码如下： #include <stdlib.h> #include <unistd.h> #include <stdio.h> #include <string.h> void getpath() { char buffer[64]; unsigned int ret; printf("input ......

E. Replace the Numbers 1900 思维 https://codeforces.com/problemset/problem/1620/E 题解：正着做比较困难，我们可以考虑从后往前做。一个数会被变成什么样子是取决于其后的2操作。2操作可以等价为一个变换，而位置越后的2操作相较前 ......

Triangle题解 前情提要 看博不点赞，ac少一半 小插曲 因为找不到题解差点心态炸了，还好有大佬指点，我来造福想不出这道题的人啦 题目描述：给你一个无向图，让你数里面三角形的个数，其中三角形三个顶点a,b,c序号要满足a<b<c 思路 很明显，暴力直接n* n *n,这里考虑优化、 首先枚举其 ......