题解 联盟noip

「比赛游记」NOIP 2023 游记 点击查看索引 这是 Index . 百度百科扒的，有没有人给我来一张更好的 . 11.14（day 998244350） 模拟赛，稳定打挂 . 高二的明天信息学考，晚上看他们做题感觉很有趣味 . 但是初中有无聊的信息中考 😧 😧 😧，危险的实验中考 😨 ......

《信心赛》 《很简单》 T1 \(O(n\log n)\) 居然卡不过去（愤怒） 所以我们需要研发 \(O(n)\) 的算法：单调队列。 维护两个指针 \(l,r\) 从最左边开始扫，只要极差小于 \(k\) 就把 \(r\) 一直往右边挪，只要极差大于 \(k\) 就把 \(l\) 往右边挪，这样 ......

feecle 的题单 . 后文复杂度分析中默认 \(v\) 是值域 . 目录CF1292B Aroma's Search (*1700)CF1304C Air Conditioner (*1500)CF1313D Happy New Year (*2500)CF1322B Present (*210 ......

目录DescriptionSolutionCode Description 在一个教室里有 \(n\) 排座位，每排有 \(6\) 个，从左至右标号分别为 ABCDEF，其中 C 和 D 中有过道，通往教室前端和后端的两个房间，每个房间最开始没有人,每个座位上开始都有人。 有 \(m\) 个不同的学 ......

Day -3 我朝为什么只剩两天了，我不想学 whk。 下午写建造军营，写挂了。 晚上典中典没部分分全真模拟赛。/jk fls : 怎么弄了个 EC Final 给你们打啊 开 A，写 A，开 B，开 C，写 B，开 D，写 D，写 C，拍 A，拍 C。 预计得分 \(1+1+1+1=4\)，实际得 ......

Day 1 kitty 核心思路：将转移过程中的方案加入转移矩阵，边转移边累加 string dp设计：\(f[i][x][y]\) 表示长度为 \(i\)，第一段以 \(x\) 结尾，且 \(x\leqslant p\)，第二段以 \(p\) 开头，以 \(y\) 结尾的两段完全相同的序列的对数。 ......

2023NOIP A层联测32 T4 红楼 ~ Eastern Dream 根号分治加分块。 Ps：分块后面真的用的多。 思路 考虑根号分治，将 \(x\) 分为 \(x \leq \sqrt n\) 的情况和 \(x>\sqrt n\) 的情况。 \(x \leq \sqrt n\) 由于这一部分 ......

人生第一次 NOIP。 \(\text{Day 1 = 2023.11.18}\). Day -? CSP 考烂了之后心态貌似反而正常了一点，也不知道是好事还是坏事。 比如怎么会有人心安理得地在这写游记不去复习呢？ Day -4 感冒了。 上一次比较严重的感冒还是 NOI 的 Day 1.5，奇奇怪 ......

Day -4 感觉也应该是开始写游记的时间了？ 把之前想做还没做的两道 agc 的题写了写，顺便写写题解，做完这件事感觉 OI 生涯其实也就圆满了。至少我退役以后不会想着我有题没写完了。 Day -3 今天上午又是无所事事的一上午啊，看了看往年的 noip 题，感觉自己啥都不会，咋办呢。 都在写《再 ......

原题链接 \(b\) 的顺序与答案无关，先排序。能与 \(a_i\) 配对的肯定是 \(b\) 的末尾一段，因为 \(a_i+b_j\ge h\)，那么一定有 \(a_i+b_{j+1}\ge h\)。 设 \(c_i\) 为与 \(b_i\) 配对的 \(a\) 的个数，显然 \(c\) 是单调不 ......

上次 CSP 2023 考完，因为考得太烂把写了一半的游记删了，希望这次不会。 考完可能 23 年剩下就没有奥赛了，变成苦逼 whker 了。 Day -3 上午模拟赛 \(70+80+0+40\)。T1 细节没处理到，本来过了，被 UU 卡了。T2 想到了正解，没来得及写完，时间浪费在思考太慢了， ......

CSP模拟47联测9 数据我造的。 CSP模拟48联测10 B. 特 卡掉了一种基于先快速筛查决策点后枚举剩余的决策点进行暴力判定的做法。 list CSP模拟50联测12 C. 路径 卡掉了暴力合并的点分治。 由于没有重测，我代为提交。 CSP模拟51联测13 A. 菜 卡掉了并查集判断的假做法和 ......

T1 基于1的算术 标签 暴力枚举 思路1 赛时想了个假的 DP，只拿了 77 分，，， 小于 \(10^{15}\) 的仅由 \(1\) 组成的数只有 \(15\) 个，直接枚举即可。 想了一个做法，就是直接枚举第 \(i\) 位作为最高位的 \(1\) 串取了几个，分解每位，设从高到低 \(i\ ......

题目链接 依然枚举每个位置作为最小值的情况，记录“值/下标”二元组，按第一维从大到小排序后，每次将第二位的位置在序列中标成 \(1\)，那么选择的一定是序列里一个 \(1\) 的极长段。加入一个位置检查其左右是否加入过，如果加入过就用并查集合并掉，同时维护极长段的和/左右端点是简单的，复杂度 \(\ ......

DAY -3 状态稀烂，NOIP2021T4爆搜打了一天，但是常数还是薄纱echo_long,于是下午开摆，体活课跑路踢球去了，惨遭2班6:1暴打，蒟蒻半空门球都停下来了，竟然抽歪了，过人晃倒自己，晚上7:30跑路，回家开始欢乐pes，打双十一竞技场快被系统气死了，门将场场摄政王，对面每场门将都跟开 ......

[NOIP2022] 建造军营 题解 Part I 观察 注意到如果删掉的边在一个边双连通分量里面，那么无论如何都不会影响 A 国，所以 B 国只会删掉桥，于是把图边双缩点之后，同一个边双里面的点要么都不选，要么随便选至少一个。 Part II DP 再次发现军营一定是一个极大的连通块，所以可以考虑 ......

2023NOIP A层联测32 T3 sakuya 虚伪的期望，彬彬赛时都能 A 的数学题。 思路 考虑算出来总的花费，再除以 \(m!\) 求期望。 对于某个排列的花费为：\(\sum\limits_{i=2}^m dis(a_{i-1},a_i)\)。 但考虑一下，这个式子重要吗？ 我们的目的是 ......

Archaeology 有一颗带权树，有三个操作： 给一个点打上标记。 删除一个点的标记。 查询有标记的点的导出子树的边权和。 \(n, q \le 10^5\)。 求的实际上就是虚树的大小，求这个有一个常用的方法就是把点按 dfn 排序后相邻点对（首尾也算相邻）之间的距离和除以 2。 所以我们可以 ......

这道题的思路非常简单，经过对样例的分析，我们发现，所有区间的总和为： $\sum_{i = 1}^{n} a_i \times d_i $（其中 $a_i$ 为原数组的第 $i$ 项，$d_i$ 为第 $i$ 个元素被区间覆盖的次数） 这里有一个小细节：对于某一个元素被覆盖的次数我们可用差分进行优化 ......

题意 给出一串数，请问，通过将 \(a_i\) 和 \(a_{i+1}\) 同时加 \(1\) 或减 \(1\)若干次，能否使它单调不减？ 思路 我们发现，如果要让 \(a_i\) 和 \(a_{i - 1}\) 满足单调不减，可以通过修改 \(a_i\) 和 \(a_{i+1}\) 让 \(a_i ......

这个小丑看了好久题目才发现保证 \(t\) 不降。 好像与其他题解做法稍有不同。 思路 其他题解的标记做法非常复杂，怎么办。 我们可以使用适用性可加强大的矩阵乘法。 我们考虑维护： \[\begin{bmatrix} \sum v&\sum a\times b&\sum a&\sum b&len\\ ......

### 题意 给出一串数，请尝试在这串数中找到三段**连续**的子段，使得这三个子段的和分别为 $P$、$Q$ 和 $R$。问：是否可行？ ### 思路 通过观察，观察我们可以发现，其实我们可以根据题目的要求写出一段关系式： $A+P+Q+R+B$（其中 $A$ 表示被选子段前面没被选的子段和，其中 ......

2023NOIP A层联测32 目录2023NOIP A层联测32A flandreB.meirinC.sakuyaD. 红楼 ~ Eastern Dream总结 A flandre 有 \(n\) 种烟花，每种烟花有两个参数 \(a ， b\)，你要构造一种燃放顺序，使得 \(b\) 的和最大， ......

题意 给你一个数组 \(a1,a2…an\) 请计算有多少个四元组 \((i,j,k,l)\) 符合以下条件: \(1 <= i < j < k < l <= n\) \(a_i=a_k \ \&\&\ a_j=a_l\) \(4<=n<=3000,1<=a_i<=n\) \(input\) 2 5 ......

Day -3 Day -3 写了好多啊 怎么就剩三天了啊。 考前的状态似乎不怎么样，于是天天颓。模拟赛也没有认真打，骗分都不会了。NOIP 难度不到的模拟赛也只有 210pts。 梦熊的题似乎和我相性不是很好啊，怎么总是 200-，写四题挂四题。但是前几天 InfOJ 那场似乎相性挺好的，骗到了 r ......

[SDOI2017] 遗忘的集合 题解 【多项式】 CF387D George and Interesting Graph 【网络流】网络流题，枚举中心点，贡献拆成 “连向中心点”+“连向其他点”，前半部分统计度数直接算，后边部分二分图匹配即可。 P4705 玩游戏 【多项式】列出贡献式子，难算的是 ......

题目链接 题意简述 给定一个正整数 \(N\)，将它的因数分解式按规定输出。 题目分析 模拟题意即可。 具体地，我们可以枚举 \(2\) 到 \(\lfloor \sqrt N \rfloor\) 中所有数 \(i\)，如果 \(i\) 能整除 \(N\)，则不断地从 \(N\) 中除掉 \(i\) ......

洛谷 AT 完全图的最小生成树是不好求的，但是发现 \(\mathcal{O}(n^2)\) 级别的边中显然有很多都是没有用的，这种时候可以考虑分治。 显然如果对 \(E'(E'\in E)\) 求 MST，没有选择的边一定也不在最后的 MST 的边集中。于是就让选出的边集的并等于原图，然后再求一遍 ......

CF1436E Complicated Computations mex的定义是：一个区间中没有出现过的数中最小的整数。 对于一个区间，当正整数x在区间中没有出现过、[1, x - 1]（整数）在区间中全部出现过，那么正整数x就是该区间的mex 正整数x在区间中没有出现过 我们一共有n个数字，所有的 ......

[APIO2012] 派遣 题目背景 在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。 题目描述 在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给 ......