- 2024-10-11LOJ 数列分块入门2
算法考虑求小于给定值的数的个数,可以给每个块再维护一个已经排好序的数组,整块加法对于这个块排好序的数组没有影响,零散块加法直接在原序列上加,再将零散块所处的整块从新排序。查询时零散块暴力查找,整块二分查找代码#include<bits/stdc++.h>#defineintlonglongconstintM
- 2024-10-07LOJ 6041 事情的相似度 题解
Statement先把串reverse,多次给\(l,r\),求\[\max_{l\lei<j\ler}\{\text{LCP}(i,j)\}\]Solution\(\text{sqrtlog}\sim\text{sqrt}\):莫队+线段树/树状数组/set,用SA做\(nm/\omega\):bitset乱搞\(\log^2\):SAM+LCT+BIT在parent树上,LCP等于LCA的
- 2024-09-26LOJ 6241. 性能优化 I 题解
题给代码意为\[\begin{align*}&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\sum\limits_{k=1}^j[\gcd(j,k)=1]\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\fracni\rfloor}\varphi(j)\\
- 2024-09-22BZOJ 4932 = BZOJ 9434 = LOJ 6070 基因
Statement问区间本质不同回文串数,强制在线,\(n\le10^5\).其实还有个四倍经验:BZOJ5384.Solution1考虑一个结论:\(s\)的所有回文后缀按长度排序后,可以划分为\(O(\log|s|)\)段等差数列。考虑离线怎么做:移动右端点\(i\),新增一个串\(s\),设其上一次出现的起点为\(q\),则\([q+
- 2024-09-18LOJ #3490. 「JOISC 2021 Day2」逃跑路线
Description在IOI王国,人们使用Byou作为时间单位。IOI王国中的一天被分为了\(S\)个时间单位。每天从最开始经过\(x\(0\lex<S)\)Byou后的时间称为时刻\(x\)。IOI王国由\(N\)个城市组成,以\(0\)到\(N-1\)编号。其中有\(M\)条双向道路连接某些城市,以\(0\)
- 2024-09-15LOJ#2885. 「SDOI2010」猪国杀
对拍器在此。https://www.luogu.com/discuss/81283献忠!AC代码modoiread{usestd::{io::{stdin,Read},ops::{Add,Mul,Neg},};pubfnnext()->u8{letmuta=stdin().lock();letmutc=[0u8];matcha
- 2024-08-31LOJ #6089. 小 Y 的背包计数问题 题解
Description小Y有一个大小为\(n\)的背包,并且小Y有\(n\)种物品。对于第\(i\)种物品,共有\(i\)个可以使用,并且对于每一个\(i\)物品,体积均为\(i\)。求小Y把该背包装满的方案数为多少,答案对于\(23333333\)取模。定义两种不同的方案为:当且仅当至少存在一种物品的
- 2024-08-27LOJ #160. 树形背包 题解
Description有\(N\)个物品,编号分别为\(1\ldotsN\)。物品\(i\)的重量为\(w_i\),价值为\(v_i\)。给出每个物品依赖于哪个物品。我们用\(d_i=j\(i>j>0)\)表示:如果要选取物品\(i\),就必须先选取物品\(j\)。另外,我们用\(d_i=0(i>0)\)表示:该物品不依赖于任何物品。
- 2024-08-10树链剖分
前置知识时间戳在树的\(DFS\)中,以每个节点第一次被访问的顺序,依次给予\(N\)个点\(1-n\)的标记,通常用\(dfn[x]\)表示\(x\)号节点的时间戳。\(DFS\)序进行\(DFS\)时,对每个节点进入递归后以及回溯前各记录一次该点编号,最后产生\(2-n\)的序列即是\(DFS\)序,可设\(L[X]\)和\(R[X]\)
- 2024-08-07数据结构——线段树优化 学习笔记
数据结构——线段树优化学习笔记比较基础,因此讲的很快。我们主要关注单点修改、区间查询的线段树,这是应用最广泛的。线段树问题我们以LOJ的这道题为例,例题:LOJ#130.树状数组1:单点修改,区间查询。洛谷上面也有类似的题:P3374【模板】树状数组1。因为洛谷的题的数据范
- 2024-07-21Loj P10064 黑暗城堡 题解 最短路径树记数
这道题是一道最短路径树问题。首先,什么是最短路径树呢?定义一个图的最短路径树表示一个图上的生成树,且根节点到图上任一点的距离等于原图上两者之间的距离。而不难发现,题目其实是在求图上最短路径树记数。首先,建出最短路径树。枚举每条边,判断边两个端点到根的距离之差是否为
- 2024-06-30loj#2880. JOISC 2014 稻草人
搞了很久,题解区有线段树爆改pushup高妙做法说下cdq分治先将点都按横坐标从小到大排序,cdq分治,那我们现在只需要考虑分治过程中\([l,mid]\)和\([mid+1,r]\)互相形成的合法点对,显然左边的横坐标都小于右边的横坐标。能够发现,如果右边有一个点插在一对本来合法的点之间,那么那对合法
- 2024-05-30创新实训 (一)
为了提高在线评测系统的功能性,需要选择和集成一个强大的代码纠错大模型,用于自动分析和纠正用户提交的代码中的错误。这里的大模型我们选择使用清华大学开源的ChatGLM-CodeGeeX2。在该模型的基础上,选用程序设计试题的专门数据,进行Fine-turning的训练(即微调)。为了令CodeGeeX在
- 2024-05-28BalticOI 2022
有一道题LOJ没有,就没做了。LOJ#3774.「BalticOI2022Day1」ArtCollections注意到询问次数为$n$,我们希望每次确定一个数的位置。考虑增量法,前$i-1$次操作构建出$[1,i-1]$的排列,在第$i$次操作的时候插入$i$。首先询问$p={1,2,3,\dots,n-1,n}$,设返回值为$B_1$。
- 2024-05-26LOJ#4149. 「JOISC 2024 Day1」滑雪 2
首先,不存在\(H_i<H_j\)时增高\(H_i\)至\(H_j+1\)后连\(i\toj\)更优,因为增高后原来能连\(i\)的点现在不一定能连\(i\)了,原来能连\(j\)的点还是能连\(j\),此时的方案集必然是原方案集的子集,答案一定不会更优,又因为你付出了增高的费用,所以这样一定劣。那么我们
- 2024-05-22loj#575. 「LibreOJ NOI Round #2」不等关系
记事件\(A\)为「当\(s_i=\texttt<\)时\(p_i<p_{i+1}\)」,事件\(B\)为「当\(s_i=\texttt<\)时\(p_i<p_{i+1}\),且存在\(s_j=\texttt>\),满足\(p_i<p_{i+1}\)。所求即\(n(A)-n(B)\)。\(n(A)\)是好求的,相当于部分定序排列,记每个递增段的长度为\(a_1
- 2024-05-17loj#566. 「LibreOJ Round #10」yanQval 的生成树
\(\mu\)取值即所选边权的中位数。把每条边拆成两条(黑边和白边),边权分别为\(\mu-w_i\)和\(w_i-\mu\),要求黑边和白边各选\(\left\lfloor\dfrac{n-1}2\right\rfloor\)条,求最大生成树。可以直接wqs二分,时间复杂度\(\mathcalO(nm\logw~\alpha(n))\)。把所有边的边权
- 2024-05-16loj#546. 「LibreOJ β Round #7」网格图
裸的01BFS,时间复杂度\(\mathcalO(nm)\)。相邻的无障碍行可以缩成一行,列同理,所以全图的规模可以缩成\((k+1)\times(k+1)\),再01BFS,时间复杂度\(\mathcalO(k^2)\)。进一步地,所有\(1\timest\)或\(t\times1\)大小的无障碍连通块均可缩成一个点,两个连通块相交,则
- 2024-05-15loj#523. 「LibreOJ β Round #3」绯色 IOI(悬念)
由题述,\(X\)满匹配,根据Hall定理,有对于任意一个有\(k\)个妹子的集合,她们能配对的男生的人数\(\gek\)。把每个妹子看作她所连接的两个(可能是同一个)男生间的无向边,则每个连通块必然是树或基环树。问题转化为给每条无向边定向,满足每个点的入度不超过\(1\),求最大边权和。对
- 2024-04-10LOJ#6020. 「from CommonAnts」寻找 LCT
linkofproblem。依旧是非常精妙的做法呢!问了神仙lca才知道怎么做了,目前网上是没有题解的,有的只是一份带注释的代码的英文题解。我的细节实现也是看了这份代码得以补足的。我们定义一些量:原树重心为rt,rt的某个儿子叫做son,son子树内的某个节点为x。首先考虑哪些连通块
- 2024-03-22loj#533. 「LibreOJ Round #6」花煎
非常巧妙的转化。考虑仅计算半边的序列,那么这样的话\(len\)削了一半,要达成的色彩值也开平方了。问题就转化为,将\(l\)拆分为序列\(a\),使得\(\sum_{i=1}^{n}(a_i+1)=l\),且使得\(\prod_{i=1}^{n}a_i\geqk\)的最小\(l\)。经过一些计算,可以发现2的段不超过一个,3的段不
- 2024-03-12树链剖分【loj模板】(〃>目<)
小声吐槽:如果不是拍了200000组没问题后瞪眼瞪出来了,我才不写呢Decribe:给定一棵\(n\)个节点的树,初始时该树的根为\(1\)号节点,每个节点有一个给定的权值。下面依次进行\(m\)个操作,操作分为如下五种类型:换根:将一个指定的节点设置为树的新根。修改路径权值:给定两个节点
- 2024-02-20有源汇有上下界最大流 【loj】
Describe:\(n\)个点,\(m\)条边,每条边\(e\)有一个流量下界\(\text{lower}(e)\)和流量上界\(\text{upper}(e)\),给定源点\(s\)与汇点\(t\),求源点到汇点的最小流。Solution:首先因为仍然有流量的限制,第一步就是要找可行流。想到上题无源汇做法,尝试转换。上题中可行流实际
- 2024-02-17聊聊 fft 的单位根
与ntt不同,处理fft的单位根要更加复杂,主要原因是考虑精度的问题.我们可以认为直接从三角函数计算出的单位根精度是最高的.当然由于\(\sin(x)\)和\(\cos(x)\)的渐进估计涉及到高次项,因此使用longdouble计算单位根再转成double是一点点意义的(如果longdouble精
- 2024-02-16【loj】维护全序集
平衡树的题能不打平衡树尽量别打,除非你闭着眼都能打对。Describe:维护一个多重集S,初始为空,有以下几种操作:把\(x\)加入\(S\)删除\(S\)中的一个\(x\),保证删除的\(x\)一定存在求\(S\)中第\(k\)小求\(S\)中有多少个元素小于\(x\)求\(S\)中小于\(x\)的最