- 2024-11-01『模拟赛』多校A层冲刺NOIP2024模拟赛17
Rank一般A.网络签不上的签到题。首先考虑枚举路径的做法,如果先枚举再计算的话复杂度会是\(\mathcal{O(\binom{n+m-2}{n-1}(n+m))}\)的,稍微优化一点的过程中可以去掉后面的\((n+m)\)。考虑此时我们要记什么,首先遇到加号其前面的值\(z\)就确定了,若上个符号为乘号那么
- 2024-10-29『模拟赛』多校A层冲刺NOIP2024模拟赛15
Rank一般A.追逐游戏(chase)签,但是保龄。上来发现情况好像是有限的,于是直接分讨,不过漏了n种情况,小样例水,大样例vscose自带的compare跑不出来,注销一遍之后甚至进度条都没了导致我以为过了,最后10min才发现(赛后发现二分是可做的,但是倍增的巨大常数加上逆天评测速度
- 2024-10-24线性基相关
[ABC236F]Spices有\(2^N-1\)个数字,分别编号为\(1,2,\dots,2^N-1\),想获得编号为\(i\)的数字需要支付\(c_i\)的代价。现在你可以从这些数字中选出一些数,使得你可以通过你选择的某些数的编号的异或和来表示出\([1,2^N-1]\)中的所有数。请你求出最少需要
- 2024-10-24杂项
树hash#include<cctype>#include<chrono>#include<cstdio>#include<random>#include<set>#include<vector>typedefunsignedlonglongull;constullmask=std::chrono::steady_clock::now().time_since_epoch().coun
- 2024-10-22『模拟赛』多校A层冲刺NOIP2024模拟赛11
Rank考前不挂就是赢A.冒泡排序签,简单的有点格格不入。发现错误代码实质上是将原序列划分成了若干个连通块,并对每个连通块做一遍排序。并查集维护,\(\mathcal{O(n)}\)扫一遍合并连通块,然后按顺序输出即可。复杂度最坏\(\mathcal{O(n\logn)}\)。点击查看代码#include<b
- 2024-10-21线性基相关模板
[ABC236F]Spices有\(2^N-1\)个数字,分别编号为\(1,2,\dots,2^N-1\),想获得编号为\(i\)的数字需要支付\(c_i\)的代价。现在你可以从这些数字中选出一些数,使得你可以通过你选择的某些数的编号的异或和来表示出\([1,2^N-1]\)中的所有数。请你求出最少需要
- 2024-10-21图论模板
最短路(dijkstra)无法处理负边权,时间复杂度O(mlogn)#include<bits/stdc++.h>#definefo(i,a,b)for(ll(i)=(a);(i)<=(b);(i)++)#definefd(i,b,a)for(ll(i)=(b);(i)>=(a);(i)--)#definelc(o<<1)#definerc((o<<1)|1)#definemk(x,y)make_pair((x),(
- 2024-10-18『模拟赛』CSP-S模拟12
Rank有点烂A.小h的几何虽然但是看起来这就是签。赛时看到计算几何直接润了,没看到送的20pts。主要问题在证一个结论:九点圆圆心位于垂心和外心的中点。几何证法见此,用到的全是初中知识,很好懂。证完就很水了,圆心即为\(\frac{A+B+C}{2}\),随便算个选中的方案数再乘上总概率
- 2024-10-14『模拟赛』CSP-S模拟11
Rank地狱场,一般A.玩水(water)签。发现\(n\le1000\),\(T\le10\),\(\mathcal{O(Tn^2)}\)可过,所以简单考虑。我写的好像是dp?为每个点开一个大小为26的状态,表示从哪个字母转移而来的方案数,到该点的全部合法方案数即为\(\max_{i\in\left[0,25\right]}\cnt_i\)。由于是
- 2024-10-14题解:AT_agc027_b [AGC027B] Garbage Collector
ProblemLink[AGC027B]GarbageCollector题意原题翻译已经很不错了,这里不再赘述。思路推论:每次取的垃圾数量应尽可能均分。证明如图,假设有\(4\)个垃圾需要被捡起,有两种取法:取一号垃圾+取二三四号垃圾。取一二号垃圾+取二三号垃圾。前者所需能量为:\(\display
- 2024-10-13『模拟赛』多校A层冲刺NOIP2024模拟赛06
Rank比较还行A.小Z的手套(gloves)签。最大值最小,一眼二分答案。双指针check一下就完了,复杂度\(\mathcal{O(n\logn)}\)。点击查看代码#include<bits/stdc++.h>#definefo(x,y,z)for(registerint(x)=(y);(x)<=(z);(x)++)#definefu(x,y,z)for(regis
- 2024-10-11『模拟赛』多校A层冲刺NOIP2024模拟赛05
Rank烂。A.好数(number)签,唐,没签上。考虑之前几次类似的题方法都是选\(k-1\)的方案存起来以使总复杂度除以一个\(n\),故考虑记共\(n^2\)个两两组合之和,枚举当前点\(i\)前面的点,找是否有值为它们的差的组合,复杂度\(\mathcal{O(n^2)}\),用map记再挂个\(\logn\)。赛
- 2024-10-09『模拟赛』多校A层冲刺NOIP2024模拟赛04
Rank赤石场。A.02表示法签。若干天前在洛谷随到过,不过当时只看了眼讨论区就走了www还好本来不是很难。发现大体上是一个拆分二的幂的问题,从大到小枚举2的幂,判断有没有这个幂只用比较大小关系,然后再对指数做一个同样的操作,递归至不大于2为止,注意\(2^1\)不用输出(1
- 2024-10-08『模拟赛』CSP-S模拟10
Rank没学线性基输麻了,A.欧几里得的噩梦线性基,输麻了。B.清扫思维题,差点签了。(感觉其实不是很难啊,没有紫的水平)一个叶子结点和另一个叶子结点的最短路径一定经过它的父节点。根据这一性质可以让整棵树的合法性拆分成每个节点的合法性。考虑如何判断每个节点的合法性。
- 2024-10-07『模拟赛』多校A层冲刺NOIP2024模拟赛03
Rank炸了,触底反弹A.五彩斑斓(colorful)签,又没签上。考虑如何一步步优化暴力。最暴力的思想\(\mathcal{O(n^4)}\)枚举每个矩形,判断四个顶点颜色。稍微优化些,两次\(\mathcal{O(n^2)}\)跑出对于行/列每个点下一个与之颜色相同的坐标,利用容斥全部减去不合法的方案数,然后再枚
- 2024-09-30『模拟赛』CSP-S模拟5
Rank烂A.median签。你说得对,但是赛时嗯打150行5k代码超级分讨过了。因为容斥做的不好,求总的然后减总会差点东西,所以直接分着加。发现如果中位数在这五个数中不止出现一次那么就会算重,所以分三种大情况考虑。一,中位数只有一个。那么此时我们需要找到另外两个小于它的
- 2024-09-28『模拟赛』CSP-S模拟6
Rank一般恼了怎么又狠狠挂分啊啊啊啊A.一般图最小匹配签。(这么多天终于签上了是吧)结论是,跟图完全没关系。题意转换完就是从\(n\)个数中选出\(m\)对差的绝对值之和最小的数。显然我们选的每一对数都应该是这\(n\)个数中相邻的一组,sort一下,设\(f_{i,j,k}\)表示到
- 2024-08-29luoguP5369 [PKUSC2018] 最大前缀和
题目n<=20题解想了半天3位状态的折半,然后发现空间开不下(时间也不太行)所以放弃思考,直接枚举答案答案是a中的一个集合,设为S;记集合S的和为sum[S]考虑当S确定时,有多少种方案能使答案恰好为sum[S]。为了处理多种sum相同的情况,记S为从前往后考虑,第一次出现最大ans的集合;记剩余部
- 2024-08-22『模拟赛』暑假集训CSP提高模拟27 || The End
《$Never\;Over$》好久没推歌了。Idon'tknowwhattosayIdon'tknowwhattodoIjustwannagorightbacktoyouLikeacloudintheskyMytearsfallforyouIwouldpaintmylifeWhitejusttomakeyoublueCausebabyyouknowweshouldbetogethe
- 2024-08-21『模拟赛』暑假集训CSP提高模拟26
Rank打得一般,倒数第二场了。。A.博弈直接搬了牛客的一套题。一眼没思路,模了一会放弃直接去打T2了,后来把\(\mathcal{O(n^2)}\)暴力打了拿30pts。正解用到了异或哈希。首先确定合法的数量即为总对数\(\frac{n(n-1)}{2}\)减去不合法的数量,而比较显然的,不合法的判断
- 2024-08-19P6222 「P6156 简单题」加强版
P6222「P6156简单题」加强版\(T\)组询问。一开始给定一个常数\(m\)。每次询问单独给定\(n\)。请你求出:\(\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^m\gcd(i,j)\mu^2(\gcd(i,j))\pmod{2^{32}}\)枚举k=(i,j)\(\displaystyle\sum_{k}k\mu^{2}(k)\sum_{i=1}^{n/k}\sum_{j=1}^
- 2024-08-10『模拟赛』暑假集训CSP提高模拟17
RankA.符号化方法初探原[ABC081D]Non-decreasing挺水的,不过赛时想了错解。赛时做法是都塞到一个set里一遍推过去,如果比上一个小就lower_bound找一个最接近差的数加上,不过它存在比较大的问题。首先全是负判不了,会进入死循环;其次用map存下标也会出现存在两个相同的
- 2024-08-01线段树分治小结
一般来说,这种题目是给定一些信息,比如说边,然后这些信息会在一个时间段内出现。一般来说需要离线,然后建立一棵以维护每个时刻信息的线段树,具体来说就是在每个节点维护一个vector。#121.「离线可过」动态图连通性以经典例题来说,我们根据每条边出现的时刻将它插入到线段树上对应时
- 2024-07-31『模拟赛』暑假集训CSP提高模拟12
Rank正常偏下发挥吧。A.黑客签到题。题目中的关键点是只有\(x\)和\(y\)的和在区间\(\left[0,999\right]\)内才合法,因此我们只枚举和在这个范围内的两个值,寻找约分前的值即可,复杂度为\(\mathcal{O(999^2)}\)。点击查看代码#include<bits/stdc++.h>#definefo(x,
- 2024-07-30求助帖,有关玄武密码,同步流
不关同步流tg上面会TLE,关了之后小点会WA,你们有什么头猪吗?原TLE代码#include<bits/stdc++.h>#definefo(x,y,z)for(registerint(x)=(y);(x)<=(z);(x)++)#definefu(x,y,z)for(registerint(x)=(y);(x)>=(z);(x)--)usingnamespacestd;typedeflonglongll;#de