ACGO欢乐赛#19题解 T1 、人工AI T2、判闰年 T3、一天中的某个时刻 T4、二进制下1的个数 T5、修正字符 T6、恰排骨 T7、买零食 T8、真-签到题

本次比赛为鲁迅专辑哦，IOI赛制 欢迎参加~ 一共4道关于鲁迅的简单到爆炸的题目~ 满分选手可以加入“中国”团队当师长哦 传送门 邀请码：psYt 中国

一下写了两篇题解

奶牛贝西从她的牲口棚可以看到美丽的景色，她隔着马路看到两个广告牌，上面画着看起来很美味的牛饲料。不幸的是，其中一个广告牌最近被更换了，所以现在它的广告是“农夫拉里的割草机”。贝西不喜欢割草机，因为据她所知，割草机的唯一目的就是割掉她认为很好吃的草(如果你没有注意到，贝西的大部分思维过程都是围绕着食物的)。 幸运的是，剩余的奶牛饲料广告牌位于割草机广告牌的前面，可能挡住了一部分。 贝茜决心把那块令人讨厌的割草机广告牌完全从她的视线中移开，于是想出了一个危险的计划。她打算从谷仓里偷一块长方形的防水布，然后在深夜偷偷溜出去，盖住割草机广告牌的剩余部分，这样她就看不到任何部分了。 根据两个广告牌的位置，请帮助贝西计算出她需要的防水布的最小面积。由于谷仓里唯一可用的防水布是长方形的，贝西发现她需要的防水布的面积可能比割草机广告牌的暴露面积要略大一些，如下面的例子所示。防水布只能放置在与其他广告牌平行(即，则不能“倾斜”)。 第一行输入包含四个空格分隔的整数:x1x_1x1 y1y_1y1 x2x_2x2 y2y_2y2 ，其中 (x1,y1)(x_1,y_1)(x1 ,y1 ) 和 (x2,y2)(x_2,y_2)(x2 ,y2 ) 是贝西视野中割草机广告牌左下角和右上角的坐标。下一行包含另外四个整数，类似地指定奶牛饲料广告牌的左下角和右上角。奶牛饲料的广告牌可能会掩盖割草机广告牌的全部或者部分，也可能完全没有遮住。所有坐标都在 −1000-1000−1000 到 +1000+1000+1000 之间。 请输出贝西需要用到的防水布的最小面积，能够把割草机广告牌的露出部分完全盖住。 在这里，奶牛饲料的广告牌遮住了割草机广告牌的右下角，但这并没有真正的帮助，因为贝西仍然需要使用一块防水布，其大小与整个割草机广告牌一样大。

114514

广搜 模板： regenfallen 6

最近准备接着在这写题解，大家有什么建议吗 题解后续将同步:CSDN账号&微博账号 以下内容持续更新: 完成内容: * 高精度算法I(加法,减法) * 高精度算法II(乘法) * 高精度算法III(除法)(因ACGO上已有该算法讲解,故不发ACGO,望谅解) * 排序算法I(冒泡排序) * 排序算法II(选择排序) * 二叉树Binary Tree * C++ 深度探索：从基础到高级实战（ACGO端口即将上线） 确定内容: * 排序算法III(插入排序) * 排序算法IV(桶排序) * STL库-stack(栈)-详解 * 指针-详解 * ACGO排位赛#10详解(同步ACGO看情况) 待官宣内容: * 排序算法V(归并排序) * 排序算法VI(快速排序) * 排序算法VII(sort)

听说发笔记能精华，所以我来了。 写的不好，内容少，请见谅。 由于图挂了，所以在 这里看 吧。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 分块是一种思想，并不是一种数据结构。 分块的思想，就是把数列适当的分成很多块，分别维护每个块内的信息。这虽然是一种很暴力的思想，但是比暴力快特别多。 对于查询，就是处理整块中的信息，然后再暴力枚举处理处理散块中的信息。 对于修改，和查询一样，先修改整块的信息，再暴力枚举修改散块中的信息。 下面是图： 对于整块就是红色，对于散块就是绿色： 分块的时间复杂度取决于块长，就比如我分的块长是 n\sqrt{n}n ，那么对于修改就是 n\sqrt{n}n ，对于查询也是 n\sqrt{n}n 。 块长我一般用 n\sqrt{n}n ，但是根据 OI-wiki 上说的，应该用均值不等式求，但是我不会qwq。 分块的好处是他有时候短，并且比线段树和树状数组能支持的东西强（除了线段树的特色懒标记）。但是就是时间复杂度太高了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 比如线段树模板题，要求支持区间加与区间和查询，就可以用分块做了。 我们维护这个块内已经堆积的整体加，这个块内所有数的加和，然后再维护每个地方上的数（没有处理块内堆积的加和）。 对于查询，整块的话查红色块内的加和就可以了，散块的话查绿色块内的现在真实的数（数加上块堆积的整体加）。 对于修改，整块直接改标记，让标记加上修改的数，对于散块枚举所有数，让这个数单独加上修改。 我们就愉快的用分块水过线段树啦！ 时间复杂度 O(nn)O(n \sqrt{n})O(nn )，明显劣于线段树的 O(nlog⁡n)O(n \log n)O(nlogn)，但是他码量小。 P3372 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 其实分块还可以是静态的，解决的东西也多了。 如区间众数，可以 这样 处理。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 如简介所说的，分块是个 思想，别把它看作数据结构来搞。 弹飞绵羊，正解 LCT，分块是歪解（？） 首先暴力肯定是模拟每个地方往后弹到了哪里然后继续往后弹。 可以先把他分成 n\sqrt{n}n 块，维护每个数弹几次能弹出该块，和弹出该块后会跑到哪里。 先说查询，其实查询就是模拟一下每次跳到哪里了，答案加上跳了几次。 再说修改。显然修改是不会影响到其他块的，所以我们再把块内的东西重搞一遍。 对于构造这两个数组，“弹出该块后会跑到哪里”数组直接算可以吧，“弹几次能弹出该块”这个是可以递推出来的。所以构造这两个数组的时间复杂度是 O(n)O(n)O(n)。 所以总时间复杂度 O(nn)O(n \sqrt{n})O(nn )。 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 练习： P1975 [国家集训队] 排队。 给你一个数列，要求支持区间加法，区间内小于 xxx 数的个数。 给你一个数列，要求支持单点修改，求区间内第 kkk 大的数是什么。 对于最后一个问题，目前处于口胡状态。现在思路是对于每个块维护一个排好序的数列。对于修改，修改块内哪个数列（插入排序 O(n)O(\sqrt{n})O(n ) 实现）。对于查询，二分答案（区间是值域）然后 check，check 中二分每个块内有多少个小于 mid 的数，然后最后和 kkk 比较（类似 P10417），时间复杂度 O(nlog⁡nlog⁡V)O(\sqrt{n} \log n \log V)O(n lognlogV)。如果不可做就别做了。

众所周知,在第九次排位赛时官方加入了Python提交的功能,ACGO的人数也随之上升,那么接下来我们就来讨论下社区到底有多少人 这是官方发表的帖子,阅读量超过了14w,根据官方设置的,一个人最多给阅读量增加五次这一设定,用144138去 ÷\div ÷ 5 可以得到结果为28827.6,四舍五入保留整数就是28828,所以个人认为社区共有28828人 请各位发表自己的看法,谢谢

链接 都是个人观点，欢迎补充：）

带SPJ的 官方的那个没有多个答案 checker代码展示 我都写了官方还不改？？？？？？？

老师，我那个代码是对的，可是他输出的和你给我们的那个输出的不一样。

就是一个测试点有多种答案的 玩一下（

(⊙﹏⊙)