方差 题解noip 2021

# [rt](https://www.luogu.com.cn/problem/P9779)# 题目##### 有一道共 n 个选项的不定项选择题，它的答案至少包含一个选项，由于题目与选项的内容晦涩难懂，你打算通过尝试每一种可能的答案来通过这道题。##### 初始时所有选项都没有被勾选，你可以执行任 ......

[国家集训队] middle 题目描述 一个长度为 \(n\) 的序列 \(a\)，设其排过序之后为 \(b\)，其中位数定义为 \(b_{n/2}\)，其中 \(a,b\) 从 \(0\) 开始标号，除法下取整。 给你一个长度为 \(n\) 的序列 \(s\)。 回答 \(Q\) 个这样的询问：\ ......

定义 \(path(x,y,z)\) 表示 从 \((0,0,0)\) 走到 \((x,y,z)\) 的方案数。 显然的经过容斥得到，若 \(r1\le r2,c1\le c2,h1\le h2\)，则 \(ans=path(n,m,w)-path(r1,c1,h1)\times path(n-r1 ......

我们注意到对如图倒三角形上的所有点操作都会影响到目标点。 那么我们可以维护两个前缀和，第一个前缀和表示如下的点是否操作 第二个前缀和表示这些点是否操作 这样我们求出了前缀和之后，将两个前缀和异或一下就知道该点是否要操作了。 #include<bits/stdc++.h> using namespac ......

非常好题目。 思路 考虑题目需要求一个连通块的背包。 点分治是平凡的，很容易想到，因为要统计的东西恰好可以把树分成几段。 但点分治操作时的背包确实卡了一下。 以前也没有见过这样的做法。 我们考虑如果直接做树上背包的话。 复杂度是绝对受不了的。 因为合并两个多重背包是基于值域的。 无法体现在树上的优势 ......

Preface 合肥前的最后一场VP了，本来计划是我和祁神两个人打，但后面徐神还是来救场了 然后这场我们过的最难的两题都是徐神切的，直接给我们抬进Au区了属于是 而且徐神最后也差一点写出G（TLE on 72），同时也一眼秒了D（没时间写了），看来这场让三个徐神来打感觉10题随便出线了 A. A B ......

原题 我认为这道题非常困难 码量并不大 可是需要很多次思维跳跃 题意 题意概述： 给定非严格递增序列 \(a_{n}\) 可以进行若干次操作，求序列方差的最小值的\(n^2\)倍 方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2 ......

比赛链接:arc168 A 题意： 读入一个由<和>构成的字符串，在最开始，最后，字符之间可以填上任意数字，任意两个相邻数字之间必须满足字符代表的大小关系。求问最后填入的数字组成的数组最少有多少对逆序对。 题解： 签到。 <可以不去考虑，因为不会对答案造成影响。 >如果不是在连续段内，也可以不去考虑 ......

Day -3： 模拟赛怎么折磨难啊 /fn/fn/fn 随便写了一点，喵喵喵。 Day -2： 模拟赛怎么还是这么难啊 /ll 写了 T1， 然后开摆，喵喵喵。 Day -1： 坐高铁去上饶，路上随便看了点题。 下午躺在床上不知道干啥。 晚上启动雀，和 7Kbyte 哥哥打了半局，不小心截了 7Kb ......

赛时看 T1/2/4 都是一眼就会了。 T3 的部分分性质提示太强，画了个网格图证明了一下大概就会做了。 然后玩了 2h+ win7 自带游戏（扫雷，Purble Place），靠着运气过了两把扫雷高级 出来听说 T3 是原题，想起了 GP of Korea. Cactus Competition， ......

原题链接 我曾经写题时有个疑惑，那就是会不会算力恢复之后大于最大算力？ 其实不会，把消耗的算力想象成占领，恢复算力想象成撤离，不管怎么恢复，领地都是那个领地。 #include<bits/stdc++.h> using namespace std; int power[200005]={0}; st ......

Ball in Berland - 洛谷 题意 在毕业典礼上，有​个男孩和​个女孩准备跳舞，不是所有的男孩和女孩都准备结伴跳舞。 现在你知道​个可能的舞伴，你需要选择其中的两对，以便使没有人重复地出现在舞伴里，求可能的数量。 思路 暴力 最朴素，也是简单的方法，就是通过暴力组合进行配对。 #incl ......

[HD2016.X1] 价钱统计 题目描述 夏天到了，超市里摆满了各种各样的应季水果。现在知道：西瓜的价钱是每斤 1.2 元；桃子的价钱是每斤 3.5 元；葡萄的价钱是每斤 4.5 元；苹果的价钱是每斤 5 元。 现在分别给出上述四种所购买的斤数（均不超过 20），请你编写程序帮助售货员阿姨计算并依 ......

Preface 来场我最爱的SUA的题，而且恰逢南京站因此袋鼠题懂得都懂 然而好家伙点开题目一看怎么全是OP题，我们队没一个玩原的这下大输特输了 因此这场前中期可以说是崩完了，一个签到因为没判\(n=1\)从20min挂到150min，除此之外其它题目基本上都要挂上三四发 不过好在最后20min连着 ......

第一次 Noip。前一天秋游可还行玩嗨了 快进到开题。 去晚了 8:20 才进考场。密码晚发两分钟然后延了五分钟 开T1。都错题好耶。以为一个串只能换一次。于是9点写完了，发现读错了。赶紧写了个 \(nm^2\) 的扔了。其实是没发现复杂度不对 开T2。不会。但是感觉切分好写。于是快11点的时候把6 ......

Link CF1898 E Sofia and Strings Question 给出两个由小写字母组成的序列 \(t\) ，\(s\) 我们有两种操作， 删去 \(t\) 中的任意一个字母 \(t_i\) 把 \(t\) 的任意一个区间 \(t_l\sim t_r\) 按从小到大排序 可以操作任意 ......

一、题目 现有 \(2^n\times2^n\ (n≤10)\) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小 ......

明明看着不难的题目，却意外的卡人。 思路 考虑两头奶牛可以成为朋友条件是什么。 存在一条路径连接这两头奶牛。 且除去端点外的路径上的所有点的编号小于两端点的较小值。 充分必要性都比较显然。 如何维护。 我们可以从小到大加入点，维护这些路径。 对于每个点维护一个 \(\text{set}\)。 表示这 ......

\(Meaning\) \(Solution\) 这道题我来讲一个不一样的解法：\(dp\) 在写 \(dp\) 之前，我们需要明确以下几个东西：状态的表示，状态转移方程，边界条件和答案的表示。 状态的表示 \(dp[i]\) 表示到达第 \(i\) 个站点所需要的最少钱数， \(w[i]\) 表示 ......

妙妙题。 不难发现，我们对于每个 \(k\) 取出的人都是满足 \(a_i \leq k \leq b_i\) 的。 经典的，我们直接将 \((a_i, b_i)\) 转化到二维平面上，将它转化成一个二维数点问题。 我们对于每一个询问，都使 \(k\) 有序，从小到大贪心的选择，也就相当于 \(x\ ......

其他的题解感觉都好高级，分享一种好想且好实现的方法。 我们可以先把点 \(s\) 和与其相连的边都删除，我们发现剩下的部分变成了一些连通块。 我们不难发现，当要求与 \(s\) 点相连的边的个数为 \(k\) 时，我们的连通块个数显然是 \(k\) 的。 接下来这个问题就转化成了：\(n - 1\) ......

blog。NOIP2023 T3，特殊性质题。 什么是特殊性质题？就是题目给出了你极其神秘的性质，从而引导你想出正解。 本篇题解将从部分分的角度，一步步讲述部分分与正解的关系。这样看的话，本题会变得十分简单。 \(\text{Task }1\sim7\)，\(O(Tnm)\) 首先转换题意。\(\f ......

blog。NOIP2023 T1。 可以对字符串随意交换，即可以重排每个单词。对于询问 \(i\)，最优方案显然是将 \(\forall j\ne i\) 的 \(w_j\) 重排至字典序最大，将 \(w_i\) 重排至字典序最小。 这件事情本质是将 \(w_i\) 与 \(\min\limits_ ......

原题链接 题解已经讲的足够好了，我想来补充一点我在思考过程中遇到的“小石子”（此处dalao可以跳过） 1.逆序对和线性代数里的逆序数有点不一样，逆序数 是指一段排列中所有逆序对的数量（蒟蒻当时卡在这里好久） 2.每进行一次交换，最多 能消除一个逆序对 所以为了消除所有的逆序对，最少交换次数就等于逆 ......

Link UVA1396 Most Distant Point from the Sea Question 在大海的中央，有一个凸 \(n\) 边形的小岛，求出岛上离海边最远的一个点到海边的距离 Solution 二分答案，然后去验证是否有一个点，距离海的距离大于 \(mid\) 如何验证？ 把每条 ......

Day -inf 打模拟赛。别的忘了。 Day 0 抽一个早上。因为没有在 5s 内算出 16^3 被 AzusidNya 嘲讽一整天。 中午走之前去剪刀顺了两瓶牢大，一点半坐车去中山。手机被少强收了，看 Cust10 抽一个钟 1.6，然后靠在 qyzyq 肩上睡了一个钟。三点半左右到希尔顿，四点 ......

NOIP2023 游寄 Day -2 遗憾生病离场回家。 Day -1 速度赶往杭州，稍作复习。 Day 1 正式开寄。 开题后，发现把所有题看了一遍，一如既往的又臭又长。 T3 和 T4 感觉很不可做。 T1 光速秒了，T2 有些思路。 发现能根据操作建图后乱判一通，先写了40部分分。 发现乱判少 ......

Link CF1894 A Secret Sport Question 其实这个翻译有一点点小问题，正确的翻译应该是这样 \(A,B\) 两人玩游戏，游戏规则如下： 整场游戏有多轮，每轮游戏先胜 ，\(X\) 局的人获胜，每场游戏先胜 ，\(Y\) 轮的人获胜。 Solution 引用 haohao ......

day -2 刚考完期中，停课了（怎么有人考前2天才停啊 看了看板子，下午跟 @carp_oier 一起vp了一场abc233 20min写完A-E然后F在赛后3min调完，我是小丑，傻呗构造。 去看了看g，发现g比f简单多了，场上应该先开这个的。 补完了g。 day -1 班上另一个同学也停了一上 ......

Link T401305 平面划分(easy) Solution 平面上 \(n\) 条直线所划分处的区域最大个数 \(L_n\) 是多少 我们考虑假设已经有\(n-1\) 条直线，我们需要画一条直线，这条直线最多和 \(n-1\) 条直线相交产生 \(n\) 个新的区域 所以我们得到了 \[\be ......