题意:给定n*m的格子,每个格子有不同的种类,q次操作,每次操作使[x1,y1]到[x2,y2]的格子除了k类型的以外都删除,最后单次询问所有格子被删了几个 官方题解提到了两种有意思的做法,随机和二进制分组 目前我写了随机的做法,简单粗暴好懂 (upd.劳资总算把二进制分组的给做出来了! 给每种类型打个随机权值,操作覆盖到的区间都加上这个权值 最后查询的时候只需这道这个点的值是不是该类型的权值的倍数就行了 就这么简单 实现上只需套路作差取前缀和就能得到单点的值,总复杂度\(O(n)\) (WA了几发忘记递推前缀了…) 另外提一下二进制分组的思路 对于每个操作的整体而...

题意：给出一个带权树，多次询问路径\((u,v)\)的第k小权值 这是主席树往区间扩展到树上的套路题 由于是按路径查询，我们无法使用dfs序，但可利用主席树对父亲扩展的方法构造出链 因此要用dfs构造才能保证正确性 查询就xjb差分一下 \(u+v-lca-p_{lca}\) 注意p的父亲是自身的情况的特判 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<c...

题意:动态第k大,可单点更新,操作+原数组范围6e4 年轻人的第一道纯手工树套树 静态第k大可以很轻易的用权值主席树作差而得 而动态第k大由于修改第i个数会影响[i…n]棵树,因此我们不能在原主席树T上扩展, 而是另开一个表示影响的主席树dT并由树状数组来控制更新和查询前缀线段树和 注意更新时dT的下标要遵循树状数组的子集表示方法 查询时留意整个dT下移到儿子的操作 最后祝ZOJ全家Segmentation Fault #include<iostream> #include<algorithm> #include<cstdio> #i...

题意:在x轴\([1,X]\)内的上空分布有n个占据空间\([L_i,R_i]\),高度\(D_i\)的线段,射中线段的得分为其高度,每次询问从x轴的\(x\)往上空射的最近k个线段的总得分,具体得分制看题 按高度对线段进行排序,那么如果我们能\(O(logn)\)内查询到某一时间段的占据\(x\)的线段个数,那么由占据\(x\)的个数的单调性就能在\(O(log^2n)\)内找到符合的最近k个线段 而某一时间段占据某位置的线段个数那就对应于主席树,二分对应于某一历史版本的根 注意由于查询必然经过叶子,那么我们就可以实现lazy不下传,只要打到它最后要覆盖的节点即可 还有空间要...

题意:给定\(n\)个定长为\(m\)的字符串,询问有多少对字符串是相似的(仅1个字符不同) 哈希处理所有字符串,枚举\(m\)个断点,拼接字符串后排序,如果相等那肯定是接连出现的 此处的\(haxi\)数组是按照多项式形式存储的,而不是递推形式,所以没有完整意义下的哈希 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k) for(register int i=j;i>=k;i--) #define erep(i,u) f...

题意：给定\(a[1...n]\)，\(m\)次操作，0表示使\([L,R]\)中的值\(a[i]=min(a[i],x)\),其余的1是查最值2是查区间和 本题是jls的2016论文题，1 2套路不说 对于操作0，维护当前最值和严格次大最值，更新过程分三种情况 1.当前的最大值本来就比\(x\)小或相等，直接剪枝（全局剪枝更优，道理不必多说） 2.当前最大值大于\(x\),次大值小于等于\(x\)，那么影响到的值只有最大值，打个tag维护 3.其它情况，暴力dfs 具体地，\(max\)值的改变影响了\(sum\)值，那我们需要维护的tag需要值为\(max\)的个数，此...

题意:给定一个矩形\(W*H\),一共\(n\)次切割操作(水平/垂直),求每次操作后得出的最大面积 随机按tag扫CF题目找到的题,可以分别用平衡树维护割边的位置和长度(\(x/y\)各两个) 具体操作看代码 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k) for(register int i=j;i>=k;i--) #define erep(i,u) for(register int i=head[u];~i;i=...

题意:求\(u\)到\(v\)的最短路径的不同权值种类个数 树上莫队试水题 设\(S(u,v)\):\(u-v\)最短路径所覆盖的点集 [S(u,v)=S(root,u)⊕S(root,v)⊕lca(u,v)] 记\(T(u,v)=S(root,u)⊕S(root,v)\) 每次转移我们只考虑\(T\)的部分,\(lca\)单独处理 对于某一次距离为1的转移,如\(u→u'\) [T(u,u’)=S(root,u)⊕S(root,u’)] [T(u’,v)=S(root,u’)⊕S(root,v)] [T(u’,v)=S(root,u)⊕S(root,v)⊕S(roo...

题意:给定一个二元组\((x,v)\)数列,求数列中每一对\(max(v_1,v_2)*|x_1-x_2|\)的累和 树状数组的简单应用,我觉得这道题对贡献处理的手段不错,DSA不是重点 对数列按关键字\(v\)排序,消除\(v\)的影响,逐步计算\(max(v_1,v_2)=v\)时对答案的贡献 计算过程满足\(max(v_i,v_j)=v_i\)的情况必然是\(j<i\),那我们边统计边更新,既分别维护当前\(x\)的个数/值的表 具体操作看代码 #include<iostream> #include<cstdio> #include<...

题意:已知平面内 N 个点的坐标,求欧氏距离下的第 K 远点对 维护大小为2k最小堆 PS.网上有人估价是使用边界四个点的最值来独立枚举,然而这样写似乎过不了 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k) for(register int i=j;i>=k;i--) #define erep(i,u) for(register int i=head[u];~i;i=nxt[i]) #define print(a) p...

题意:给定数列\(a[1...n]\),\(Q\)次查询\([L,R]\)中只出现一次的最大值 对每个元素构造三维空间的点\((i,pre[i],next[i])\),查询\([L,R]\)可以转换为查询\((L≤x≤R,y<L,z>R)\)的区间的最大值 就是说前一个和后一个都不在这个范围内的值 除此以外要注意剪枝!直接按照上面的思路码是会T的 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k) for(regi...

题意:给定一颗树,每个叶子节点\(u\)都有权值\(val[u]\),求每个非叶子节点子树的最小叶子距离,若该子树只有一个叶子节点,输出INF 貌似本来是一道树分治(并不会)的题目,然而可以利用平衡树进行离线合并,边统计边更新 一开始没有想到这种方法,看了别人家的代码后觉得真是清晰明了 set交换后无需额外在dfs维护和叶节点更新后置为INF满足题意的单一叶子情况确实是不错的trick,值得学习 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define r...

题意:求每一个子树存在最多颜色的颜色代号和(可重复) 本题是离线统计操作,因此可以直接合并重儿子已达到\(O(nlogn)\)的复杂度 PS.不知道什么是启发式合并的可以这样感受一下:进行树链剖分,分出重儿子和轻儿子,每次离线dfs时保留重儿子得出的贡献,清除轻儿子的贡献并重新遍历 (反正是一种取代树上莫队的简单粗暴玩意,但是效率贼tm好) #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k) for(register int i=...

题意:给定一棵树,树上每个节点有对应的字符,多次询问在\(u\)子树的深度为\(d\)的所有节点上的字符任意组合能否凑成一个回文串 把dfs序存储在一个二维线性表中,一个维度记录字符另一个维度记录深度 因为dfs序是单调递增的,所以每个二维表的值也是单调递增的 那么只需用两次二分把合法的儿子搞出来就行 感觉是个比较奇怪的姿势,总之学习了 //时间空间都这么暴力真的大丈夫? #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k)...

题意:给定\(a[1...n]\)和\(Q\)次询问,每次统计\([L,R]\)范围内出现频率最高的数的次数 想法没啥好说的,分别统计该数出现的次数和次数出现的次数,然后莫队暴力 注意本题时间卡的很紧,map无法通过 还有一个小细节是莫队时必须把add操作全部放在前面,保证操作不会数据越界,否则会RTE(你想想为什么?) 细节太重要了 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> ...

题意：给一个1-base数组{a}，有N次操作，每次操作会使一个位置无效。一个区间的权值定义为这个区间里选出一些数的异或和的最大值。求在每次操作前，所有不包含无效位置的区间的权值的最大值。 线性基删除不知道怎么维护,不妨逆向添加 然后区间连通性的维护自然要应用到并查集,每次操作mark一下当前位置,如果在操作时左边的区间已经mark过就搞它,右边同理 注意find时谁的基被插入 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #i...

题意:给定一个图集\((V,E)\),求路径\(1...n\)的最大异或和,其中重复经过的部分也会重复异或 所求既任意一条\(1...n\)的路径的异或和,再异或上任意独立回路的组合的异或和(仔细想想,异或的过程是不是不断抵消并选取更优异或路径的过程?) 因此dfs返向边把环的异或值弄出来丢入线性基中贪心选取即可 顺便转载一下菊苣的独立回路小姿势(电路课似乎讲过但我摸鱼了XD) 首先有个结论：一个无向连通图G中有且仅有M-N+1个独立回路。 独立回路是指任意一个都不能由其他回路构成。 引用一段数学归纳法证明： “M=N-1时，树，结论成立 设M=K时结论成立，当M=K+1...

题意:有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。求能够获得的最高奖励。 从没想过并查集可以这么用 这道题很显然需要做的是贪心把大的先占用掉,然后往小的尽可能塞 那么该怎么塞也应该是贪心的从结束的点开始塞,不行就往前推,这个链式反应的过程如果用并查集来实现,就可以达到接近O(1)的速度 诀窍就是x和p[x]相同时,返回x-1,表示x可以占用,并维护关系 #include<iostream> ...

题意：给定\(n\)门课和\(m\)个学期，每门课在每个学期有不同的得分，需要选定一个学期去完成，但存在约束条件，共有\(k\)对课程需要\(a\)在\(b\)开始学前学会，求最大得分（原问题是求最高平均得分） 把问题转换为最小损失得分，那么可以用最小割来求解 \(Y[i][j]\)为第\(i\)门课在\(j\)学期损失的学分，若不存在则设为正无穷 那么每一门课\(i\)都要拆\(m\)个点，表示为\((i,j)\)，源\(S\)和\((i,1)\)的容量为\(Y[i][1]\)，其他学期相互连边，容量为\(Y[i][j]\)， 注意到汇点\(T\)时是\((i,m)\)到\(...

题意：给定n*m的图，每个士兵可以占领当前行和列，第i行至少要R[i]个士兵占领，第j列至少要C[j]个士兵占领，部分网格无法占领，求占领所用最少士兵数，若无解则输出orz 士兵的贡献情况有1(只有效占领行/列)，2（既占领行又占领列） 用最大流跑出贡献为2的士兵的个数，然后把所有要求相减处理就得出贡献为1的士兵个数 非法方案用极端情况和要求行列士兵数去考虑 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<c...

题意:求最小割集\(C\),使得\(\frac{\sum_{i∈C} cost_i}{|C|}\)最小 模型就是01分数规划\(\frac{\sum_{i=1}^{m}cost_i\cdot x}{\sum_{i=1}^{m}c_i\cdot x}\),其中\(c_i\)恒为1,\(x\)为\(0\)或\(1\) 令上式为\(λ\),简单变换后有\(\sum_{i=1}^{m}(cost_i-1\cdot λ)x_i\),利用单调性进行二分,迭代时边的代价为\(cost_i-λ\) 整型模板改了下发现跑不动图,随便网上捡了个模板(｀･ω･) #include<bits/s...

题意:给你一个串,支持两种操作,1修改某个点的字符,2询问\([l,r]\)内模式串P与原串的匹配个数 bitset的写法是真的6啊,简直是优雅暴力的典范 \(bs[i]\)表示\(T_i\)与\(P\)匹配与否, 具体地,每次错位按位与依次表示\(T_i,T_{i+1} \cdots T_{i+len2-1}\)与\(P_1,P_2 \cdots P_{len2}\)匹配与否 注意的是最后去除重复部分的起始下标应该是\((r-len2+1)+1\),而不是\(r+1\) #include<iostream> #include<algorithm> #...

题意:小马哥有 \(n\) 杯盐水，第 \(i\) 杯有 \(a_i\)单位的盐和 \(b_i\)单位的水。小马哥很无聊，于是他想知道有多少种这 \(n\) 杯盐水的非空子集，倒在一起之后盐和水的比是 \(\frac{x}{y}\)，范围\(2<n<35\) 这道题比赛没A出来，要是A了就能两个人分900块辣 //隔了一天才突然想到,我太菜了 折半枚举过程如下 分两个桶A,B,分别装前一半杯子的子集和后一半杯子的子集 先暴力枚举A桶所有组合，装入一个排好序的vec，这部分时间复杂度是\(O(2^{n/2}log_22^{n/2})\) 再暴力枚举B桶的方案，二分...

题意：白书P209 本题用普通字典树会更快，为了练习还是尝试再敲一遍左儿子-右兄弟字典树（其实就是字典树上开前向星） dp[i]为满足[i…len)的分配方案数，转移方程为dp[i]=sum{dp[i+slen(j)]，如果后缀j存在符合前缀的方案，slen(j)为该后缀完全匹配前缀的长度} 这种利用前缀进行dp从后往前推的方法我并没有用过，学习了 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string...

题意：大白P95 本题比较特别的是状压两个集合并且进行转移，因此要分别处理当前集合只有1个老师/2个老师的记录（然后可O(1)得出0个老师的集合） 记忆化过了但是迭代式不能记忆超过2的之前的状态是怎样的，除非多记录一个超过2的集合，因此无法实现（是我太菜了） #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<sstrea...

先来看看比较显然的几个局面 (a,0) 先手必败 (a,a) 先手必胜 (a,ak) 先手必胜 (a,ak+r),k>1 先手必胜，因为先手有主动权把(a,r)让给后手或留给自己 对于开局(a,r),r<a&&a/r<2,比较难分析，我们用暴力直接跑出结果 挑战程序设计竞赛把这种主动权成为自由度，名字真高端 这次的代码写的不怎么简练，不过能AC #include<iostream> #include<algorithm> #include<cstdio> #include<cstring>...

题意：买瓜，每天的瓜有不同的价格和xu命时间，要求能苟到第n天的最小代价 定义DP方程\(dp[i]\)，指苟到第\(i\)天的最小代价，所求即为\(dp[n]\) 那么怎么转移就是问题，这里的状态表示显然不能转移，因为哪一天买的瓜苟到哪一刻都不知道，空间太大不足以维护 再定义一个st表\(st[i]\)，表示【能够】苟到第\(i\)天的最小代价，那么转移就是dp[i]=min(dp[i-1]+瓜,st[i…n])，后者表示不买瓜直接xu命 st表肯定是一个每一位都单调非增序列，应该可以用单调队列优化（然而不会），所以还是放到线段树上更新了.. #include<ios...

题意：给定一个图，节点可以放灯，要求用最少的灯覆盖所有的边（每盏灯能覆盖该节点邻接的边），满足条件的同时求该前提下尽量多的被两盏灯照亮的边数 条件二转化为求尽量少的被一盏灯照亮的边数，两个条件都是求min，我们需要构造一个条件一取决定性作用的式子， 令\(f(a,b)=Ma+b\),其中\(a\)为条件一的最优解，\(M\)为一个足够大的数，以至于\(b\)的最大值都小于\(M\)（更精确的应该是\(M>b_{max}-a_{min}\)），那么\(b\)为满足\(a\)前提下的最优解，所以我们就是在图上DP求解这条式子的min，两个系数分别对应不同的解 有一些实现上的细节...

安装尼尔等了老半天,翻硬盘找到一本极其古老的数论基础(苏联译本),写一下笔记学习学习(才看到15页就差不多安装完了,LOL) Note: 博客迁移导致乱码，懒得fix了 如果\(\sum a_i=\sum b_i\),除掉删除的一项,所有的项都是\(c\)的倍数,那么删除的一项也是\(c\)的倍数 移项后提取\(c\)得证 \(a=bq+r,(0≤r<b)\)是唯一确定的 证明: 如果存在另一个\(a=bq_1+r_1,(0≤r_1<b)\) 与原式作差后得到\(0=b(q-q_1)+(r-r_1)\) ,观察到\(r-r_1\)是\(b\)的倍数,而由...

题意:给出\(n\)个节点的树,每个节点有一种颜色,统计每棵子树的不同颜色的数目 直接对每个树\(dfs\)并回溯可以得出\(O(n^2)\)的算法,并不是十分OK 如果顏色種類少可以用尺取法開\(C\)個數組離線處理或者線段樹在線處理 多了的話聽說能用主席樹？（學的太水不會用） 看了下Codeforces里的Tutorial,暂时感受了一种叫做dsu on tree的暴力黑科技 核心就是进行树链剖分,分出重儿子和轻儿子,每次离线\(dfs\)时保留重儿子得出的贡献,清除轻儿子的贡献并重新遍历 可以证明是\(O(nlogn)\),证明方法没看,应该是树链剖分的同款证明? ...

题意:求重复次数最多的重复子串(并非长度最长) 枚举循环子串长度\(L\),求最多能连续出现多少次,相邻的节点往后的判断可以使用\(LCP\)得到值为\(K\),那么得到一个可能的解就是\(K/L+1\) 这个不是最优解,还需要往前判断,往前的判断必须是两个后缀依然等间距的,而且首个后缀必须在此前已经枚举过的后缀之后(否则无意义),并且最优情况只会比上述\(K/L+1\)大1 翻别人题解找到一个很简洁的式子,可以很轻易的凑出\(L\)的整数倍的判断点(就是个补全),感觉有点像KMP啊 #include<iostream> #include<algorithm&...

题意:求最长回文子串 这种有专门的O(n)套板子算法,但作为练习还是用后缀数组来解吧 只需把相同的另一个串反接(中间用一个足够小且未出现的字符衔接),然后枚举回文串的中点,不断求解该点往前和往后计算的\(LCP\)即可 发现模板有个BUG改好了 有个值得注意的地方是回文长度奇偶枚举时的端点选择问题,具体直接看栗子 abcccd 奇数枚举时应该是abcccd#dcccba 偶数枚举时应该是abcccd#dcccba 两个子串枚举首端与#的距离相等或相差一,列出式子就是当奇数端枚举\(i\)时,另一子串始端为\(2n+2-i\),偶数端为\(2n+3-i\) #inclu...

题意:求最长不可重叠的相同差值子串的长度 这道题算是拖了好几个月,现在花了点时间应该搞懂了不少,尝试分析一下 我们首先来解决一个退化的版本,求最长不可重叠的相同子串(差值为0) 比如\(aabaabaa\), 那么所求的子串有\(aab,aba,baa\)三个 如何求?不妨枚举.枚举是否有长度为\(k\)的最长不可重叠相同子串 可是后缀数组中并不能直接表示出子串,只能间接地用后缀来表示 长度为\(k\)的相同子串\(=>\)最大公共前缀长度为\(k\)的子串\(=>\)最大公共前缀长度大于等于\(k\)的后缀(注意非充要) 而我们所求的就是一个\(lcp\),...

题意:给定\(a\)和\(n\),输出\(a^n\)的前三位和后三位 后三位快速幂 [log_{10}(a^n)=n\cdot log_{10}(a)=n\cdot log_{10}(x\cdot y),y<10,x mod 10 = 0] \(n\cdot log_{10}(x\cdot y)=p+q,q<1\),\(p\)作为整数只是倍数上的贡献,其中前三位就是\(pow(10,q)\cdot 100\) #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i...

参考官方题解 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define rrep(i,j,k) for(register int i=j;i>=k;i--) using namespace std; string s[100]={"H","He","Li","Be","B", "C","N","O","F","Ne", "Na","Mg","Al","Si","P", "S","Cl","Ar","K","Ca", "Sc","Ti","V","Cr",...

题意:求\(\sum_{i=1}^n\sum_{j=1}^n{|i-j|+k \choose k}\) 知识点: 朱世杰恒等式,\(\sum_{i=r}^n{i \choose r}={n+1 \choose r+1},r<n\) 题解:首先去除式子中的绝对值,考虑对称性还有i=j时的重复,原式可转化为\(2\sum_{i=1}^n\sum_{j=i}^n{j-i+k \choose k}-n\) 对式子内部循环调用一遍朱世杰恒等式\(\sum_{j=i}^n{j-i+k \choose k}=\sum_{j=k}^{k+n-i}{j \choose k}={\ {k+n-...

题意:给你矩阵\(A\),求\(S=\sum_{i=1}^{k}A^i\) 构造矩阵 [\begin{bmatrix} A & E \ 0 & E \ \end{bmatrix}] 很酷炫的矩阵套矩阵,学习了 PS.更通用的解法是二分求等比 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<string...

题意:求\(\sum_{i=0}^{n-1}a_ib_i\) 其中,\(a_i=A_xa_{i-1}+A_y,b_i=B_xb_{i-1}+B_y\) 构造矩阵分别维护\(a_ib_i,a_i,b_i,A_yB_y,A_y,B_y,S_i\) [\begin{bmatrix} a_ib_i \ a_i \ b_i \ A_yB_y \ A_y \ B_y \ S_i \ \end{bmatrix} = \begin{bmatrix} A_xB_x & A_xB_y & A_yB_x & 1 & 0 & 0 & 0 0 & A...

题意:给定\(k,b,n,m\),求\(\sum_{i=0}^{n-1}f(g(i))\) 其中\(f(i)=f(i-1)+f(i-2),f(1)=1,f(0)=0\),\(g(i)=k*i+b\) 令矩阵\(A\)为 [\begin{bmatrix} 1 & 1 1 & 0 \end{bmatrix}] 那么 [\begin{bmatrix} f(n+1) f(n) \end{bmatrix}=A^n \begin{bmatrix} 1 0 \end{bmatrix}] 我们所求的 [S = f(g(1))+f(g(2))+…+...

记dp[i]为长度i且符合题意的方案数,dp[n]就是解 符合方案的是不含fmf和fff子串的字符串 考虑如何从前面几项递推出后面第i项 (★表示存在生成的非法方案)←其实没啥用处 i=1时 m③ f③ i=2时 mm② mf② fm★② ff★② i=3时 mmm mmf mfm★ mff★ fmm ffm★ i=4时 mmmm① mmmf① mmfm★① mmff★① mfmm① mffm★① fmmm① fmmf① ffmm① i=5时 mmmmm① mmmmf② mmmfm① mmmff③ mmfmm① mmffm① mfmmm① mfmmf② ...