Fo
  • 2024-11-21『模拟赛』多校A层冲刺NOIP2024模拟赛25
    Rank极限了,感觉还行感觉T3不是一般人可做的,遂先来写赛记。A.图签。本来不是很一眼的,但看到给了这个和这个然后就很一眼了。用longlong状压每个点所有操作下是否属于S/T集合的状态,那么发现对于一条边\((i,j)\),只有某一次操作满足\(i\inS\)且\(j\inT\)
  • 2024-11-18『模拟赛』NOIP2024加赛6
    Rank大奋场,T3没切有点菜A.草莓和前天多校T3很像,所以一眼鉴定为贪心,从大到小选比从小到大选一眼优,代价一样时横竖无所谓先后,然后sort一遍就做完了,复杂度\((n+m)\log(n+m)\)。10min切的。点击查看代码#include<bits/stdc++.h>#definefo(x,y,z)for(registerint
  • 2024-11-11『模拟赛』NOIP2024加赛4
    Rank给我唐完了,又名,【MX-S5】梦熊NOIP2024模拟赛1。A.王国边缘好像简单倍增就做完了。由于昨天T5在我脑海中留下了挥之不去的印象,今天一上来看到这题就发现是一个内向基环树森林。然后被硬控硬控硬控,最后一个小点加一点优化就能过没调出来,挂30pts,菜菜菜菜菜。注
  • 2024-11-10『模拟赛』NOIP2024(欢乐)加赛3
    Rank真欢乐吗,不过missionaccomplished.A.SakurakoandWaterCF2033B*900byd还懂难易搭配,不过这个b翻译甚至不着重以下主对角线差评,被硬控半个小时,直到手模样例才发觉不对。读懂题就很简单了,最优一定是找最长的对角线每次加,一共只有\(2n-1\)条线,枚举一下求出每条
  • 2024-11-0822
    #include<bits/stdc++.h>#definefo(x,y,z)for(int(x)=(y);(x)<=(z);(x)++)#definefu(x,y,z)for(int(x)=(y);(x)>=(z);(x)--)usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;#definelxllinlinelxqr()
  • 2024-11-06『模拟赛』NOIP2024加赛2
    Rank一直烂,什么时候触底反弹(A.新的阶乘赛时觉得线筛一遍同时统计每个质数的指数就做完了,然后本机怎么跑不进1s,卡常卡了半个小时,最后没T,但是vector炸了,70pts。可以换思路考虑,赛时一直没转换过来。对于每个质数枚举其倍数统计贡献。复杂度不知道多少,跑得中等速度。点
  • 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