方差 题解noip 2021

自己的套路还是见少了。 思路 考虑扫描线。 每一个颜色的 \(\min\) 具有单调性，这个很好看出来。 可以使用一个单调栈来维护。 这里都是朴素的。 考虑如何维护。 我们发现在通过单调栈维护的时候。 需要支持撤销上一个元素对区间的影响。 我就在这里卡了很久。 我们有一个很暴力的想法。 我们每一次区 ......

Day -INF 在考前几天补了往年NOIP的题，信心++。 下午到了开发区，由于雪太大，晚上就没去酒店找其他队友，摆了一会然后稍微看了一眼题就睡了。 Day 1 进入考场。 听CCF的广播说禁止在考前写代码，啊？ 开始后经典的只有压缩包密码没有PDF密码，mnt += 2。 看了一眼四道题，T1感 ......

支配点对实在是太有意思了。 本质上就是一个合法的减枝。 思路 考虑维护树上路径问题。 容易想到点分治。 考虑在当前的分治中心 \(\text{rt}\)，每个点到当前分治中心的距离为 \(dp_x\)。 求出每一组点对的贡献。 假设每个点对在距离长的那部分贡献，即 \(dp_i>dp_j\)，求出所 ......

之前忘写了 现在忘了（雾） Day 0 在七高考。 欣赏了一会走廊边上的展示柜。 进考场。印象里是圆桌，结果还是常规的几排。（好像各个考场不一样……？） 开考之后因为键盘的奇怪手感而奇怪了很久。一行头文件打了半天，，。 P.S.之前同学说过七高键盘难用，然而没当回事TAT。 T1有点水……但是还是写 ......

思路 设 \(dp_{i,j}\) 表示第 \(i\) 行 \(j\) 列卒走到这里有多少种方式。 卒是可以向右和下走，所以到这个点只能从左或上来，不难得出转移公式：\(dp_{i,j} = dp_{i-1,j}+dp_{i,j-1}\)。 如果马在这个点上或者说马能到这个点上，那么卒不能到这个点， ......

简单模拟题。 思路 枚举每一个地毯，因为后面的会覆盖前面的，所以从正序枚举。如果要求的点的坐标在当前地毯上，则将答案赋值为当前地毯编号。 最后输出答案。 那如果这个点没有地毯呢？答案初始设为 \(-1\)，这样没有地毯覆盖的话，答案不会改变，这样输出答案就会是 \(-1\)。 注意： 记得赋初始值。 ......

思路 我写的好像是动规的做法。 设 \(f_{i,j}\) 表示第 \(i\) 步 \(j\) 个点是否可以走到，值要么为 \(1\)，要么为 \(0\)。最多走 \(n\) 步，因为总共只有 \(n\) 个点，每一步都肯定会多延伸出一个点，要不然就重复计算。 不难得出转移公式： \(f_{i+1, ......

考察了小学奥数知识，不会的请先去学习一下相遇与追及。 思路 两个人相遇的点一定是有周期性的，我们可以先算出一个周期会走多远，而这个距离是两人速度的最小公倍数。 接着需分情况讨论。 如果两人是同向，则为追及，需用距离除以一人的速度减去距离除以另一人的速度。需要取绝对值。 如果两人是反向，则为相遇，需用 ......

省流：爆单了。 \(\rm Day\ 0\) 中午感觉身体发冷，有一种不详的预感。 下午润去看病，好像寄了。 做了甲流的检测，不过好像要考 \(\rm NOIP\) 时才能出结果。 吃了退烧药，但还是 \(\rm 38\) 度多。 没有胃口吃晚饭。 晚上到了杭州稍微好了一点，喝了一点粥。 \(\rm ......

本文同时发表在个人洛谷博客。 CSP Day -1 上午打德文布置的毒瘤信心赛，据说请了一个D类金验题，没有成功ak。 打完没信心了。 下午去下沙。有点像小县城。 晚饭在下沙天街，好评。 颓废。 Day 0 上午打J。 开场3分钟没过T1，然后发现次数是 \(\log\) 级别的，无脑暴力。菜死了。 ......

哈哈哈，我是文化课强神，我太牛了？ day-1 话说既然第一天叫 day1 那么为什么前一天不叫 day0 而是 day1 呢。我感觉要解决这个问题就必须解决为什么电梯没有 0 楼这个问题。 考前做模拟赛，t2 是反人类的 dp，状态定义莫名其妙，但是好多人都切了。太恐怖了吧！我是团队垫底人，有了这 ......

省流：某个网站测的 100 + 20 + 5 + 56 = 181 OI 到底是一门什么样的学科？ 所谓的思维题到底是什么？ 这些已经随着我的 OI 生涯结束而消逝了。 OI 似乎拼的是积累 + 运气，就像 2022 一直考 tarjan 一样。我不相信运气，但是这个真的是没有办法避免的，回想起 n ......

Before 晚上的 fan 给予了二连击 jio冷爆了，ice-cream assassin 终究活成了 fan assassin 的模样 珊姐早餐的混沌的麻油很香，像出前一丁，但是 xc 的生煎包也很好吃，吃了一袋 感觉可能会寄，csp-s 的 T3 用掉了挺多 rp 的 Duration 忘记 ......

来一发分治题解吧。 感觉和单纯的整体二分还是有一点区别。 虽然整体二分也能看作分治就是了。 思路 首先时光倒流。 删边改为加边。 这没有什么好说的，比较基础。 我们考虑在不断加边时，每两个点是在什么时候变成一个强连通分量里面的。 考虑分治。 首先在 \([l,r]\) 内选取中点 \(\text{m ......

[NOIP2002 普及组] 过河卒 题目描述 棋盘上 \(A\) 点有一个过河卒，需要走到目标 \(B\) 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 \(C\) 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，\(A\) ......

[CSP-J 2021] 插入排序 - 洛谷 昨天下午爆肝一下午都没整出来（悲 是我太菜了 思路 第一种想法，暴力 即，每次修改操作后重新维护整个数组，时间复杂度\(O(Qn^2)\)，能拿52pts 但是，想要拿满分，很简单，只需要把排序的双层循环\(n^2\)变为\(n\)即可 因为冒泡是对每个 ......

[CSP-J 2021] 网络连接 - 洛谷 距离CSP2023还有 \(**3**\) 天 题意及思路 恶臭大模拟，按照题意模拟即可。有几个代码上的难点： 当定义了一个scanf或者sscanf并且有一定的输入规则，那么如果读取到的字符串不符合定义的规则，那读入了几个变量就返回几个变量 例如，如下 ......

2023 10 03 CSP-J 模拟赛 复盘 这次模拟赛考的特别差，只有160。 T1：一上来，虽然不那么打卡，但也挺简单，然后五分钟写完，对了对样例，对了，走人。 T2：需要在\(O(n logn)\)或者\(O(n)\)的时间复杂度求出每一个区间被覆盖的区间，这要怎么求啊？我想了半天也只知道\ ......

我看看有多少人吊打我 Day -1： 复习了ST表，线段树，KMP，LCA，结果，一个都没考！！ Day 0： 再次复习，好像都会了，又好像都不会，思考了考场策略，然后就躺倒床上了。 Day 1： 六点半才起来，再复习了一下。 吃完早餐直奔yh。 7：30 来到了yh，一个人也没有，过了一会，z老师 ......

给一个长度为 \(n\) 的字符串 \(s\)，\(q\) 次询问，每一次 \(l\) 和 \(r\) 区间内有多少个 \(s_i\) 等于 \(s_{i-1}\)。 \(10^5\) 的数据 \(O(N^2)\) 暴力肯定行不通。于是我们考虑预处理前缀和，处理到 \(i\) 下标以及之前有多少个 ......

插曲 因为本人看错了题面，买看到一个子串只包含一种字母，所以切完 D 和 E 才回来发现很简单。 问题翻译 给你一个长度为 \(N\) 的字符串 \(S\)，由小写英文字母组成。 求 \(S\) 的非空子串中有多少个是一个字符的重复。在这里，作为字符串的两个子串是相等的，即使它们是以不同的方式得到的 ......

题目翻译 有一场选举，要从 \(N\) 名候选人中选出一名获胜者，候选人编号为 \(1, 2, \ldots, N\)，共有 \(M\) 张选票。 每张选票正好投给一位候选人，其中 \(i\) 票投给了候选人 \(A_i\)。 选票将按照从第一张到最后一张的顺序进行统计，每张选票统计完毕后，将更新并 ......

题目翻译 给你两个字符串：\(S\) 由大写英文字母组成，长度为 \(N\)；\(T\) 也由大写英文字母组成，长度为 \(M\)，小于 \(N\)。有一个长度为 \(N\) 的字符串 \(X\)，它只由 # 字符组成。请判断是否有可能通过执行以下任意次数的操作使 \(X\) 与 \(S\) 匹配： ......

题目大意： 给你一个字符串 \(s\)。你要在其中找到多少个 ABC 的子串，例如 AABCBC 算两个，删掉中间的 ABC 后，前面的和后面的加起来也是一个 ABC，所以就算两个。 思路分析： 首先很容易写出暴力，把一个 ABC 提取出来后把后面的元素往前移，然后再重复操作，但是我们发现时间复杂度 ......

分析： 这一道题很容易发现可以用并查集来维护 （不知道为什么其他人都用了图论），\(a_i\) 与其对应的 \(b_i\) 代表着 \(a_i\) 这个集合里不能存在着 \(b_i\)。 根据只有存在两个集合，所以我们会发现，若 \(x\) 与 \(y\) 不在一个集合且 \(x\) 与 \(z\) ......

题目大意 给你 \(n\) 个字符串 \(s\)，和一个字符串 \(t\)。 问你，有多少组是 \(s_j\) 拼在 \(s_i\) 后面所组成的新字符串中，\(t\) 是其子序列。 思路 分析：\(5 \times 10^5\) 的数据肯定需要 \(O(n)\) 或 \(O(n \log n)\) ......

前言 一个下午，一个晚上，一个早上，可以算是一天了吧，终于调出了这道题，纪念一下吧！！！ 食用更佳。 这道题其实就是一道简简单单的 BFS 模（du）板（liu）题。 说难不难，简单不简单，虽然没有难的算法，但是就是码量一百多行，比较难调。 题目难度绿，思维难度橙，代码难度蓝。真是个绝世好题。 题目 ......

P6239 [JXOI2012] 奇怪的道路 首先，拿到题面，\(n \le 30\)，\(k \le 8\)，这不就暴搜吗。再想想，紫题会给你暴搜的机会吗？所以进一步思考，发现这其实是一道 DP，而且数据这么小，肯定是给状压 DP 的样子。 经过一定思考，发现我们可以直接线性枚举 \([1,n]\ ......

P3161[CQOI2012]模拟工厂题解。题目 其实发现这是一道状压，发现这道题是一道数学题，其实就很简单了。对于每一次的订单我们可以设： \(time\) 为距离下一个订单的时间。 \(num\) 为这个订单要生产的数量。 \(x\) 为生产能力。 \(y\) 的时间可以用来提高工厂的生产力。那 ......

题解 前言 个人认为官方题解写得最为详细、干净、清楚，如果有意向阅读外文版的题解的话，还是推荐去读一读： Editorial - AtCoder Regular Contest 117 本文属于转载（？），有一些自己的思考过程，希望有帮助。 题意 有多少个长度为 \(2N\) 的序列 \(A\) 满 ......