# [[十二省联考2019]异或粽子](<https://www.luogu.org/problemnew/show/P5283>)  先吐槽一下,在考场上完全没有将这道题和超级钢琴联系起来,然后$GG$,喜提$60$走人  赛后听说直接上可持久化$Trie$用堆维护就好了  然后自己回来又打开了超级钢琴.  这道题就有思路了  ------  很明显,这道题我们可以利用前缀和优化到最大的$k$对数的异或和  我们想对于每一个$i$，我们在$0—i-1$去查阅它的异或最大值,用可持久化$Trie$可以办到,统计完答案及答案所在位置(设为$ans_{pos}$)后将该区间分...

# [LuoguP5464 缩小社交圈](P54)64 缩小社交圈  背景:洛谷七月月赛T4  题目大意给定$n$个点,每个点的权值对应着一个区间$[l_i,r_i]$,两个点$i,j$有边当且仅当他们权值的并集不为空集,问有多少个点集$S$满足其连边后是一棵树  $n <= 2*10^3,l_i<=r_i<=2*10^3$  首先,这道题不能转换成一道图论问题去考虑,为什么?  因为这道题区间的性质非常特殊,是解题关键,如果转化成图,就没有了这个性质.  首先,如果不能转化成图论,此类区间的问题还是应该先进行排序.  我们按照$r_i$进行排序之后考虑$DP$  我们发现如...

# 莫队阶段小结  首先,为什么要叫小结呢,因为我只学了一点点,后续可能更多  ## 莫队  莫队是一种离线处理区间问题的神器.答题思路就是你将原数列分成$\sqrt{n}$块,将所有查询左端点定位,并按照左端点所在的块进行排序,相同则按照右端点排序  大体就是这个样子  ```cpp inline bool cmp(Q x,Q y){ return belong[x.li] == belong[y.li] ? x.ri < y.ri : x.li < y.li; } ```  这样的话我们每个快内都暴力求  时间复杂度为$O(m\sqrt{n})$  但是还有一种玄学加速方式,十...

7.17 F 认真读题吧 A 算法一: \(c = ab,x = a + b + c\) 所以 \(x = a + b + ab\) \(=(b + 1)a + b\) 所以我们枚举\(b\) \(O(1)\)check了 但是这样是\(O(x)\)的 之后我们由 \(x = a + b + ab\)可得 \(ab<=x\) 由于\(a，b\)本质相同 所以\(min(a,b)<=\sqrt{x}\) 所以我们枚举到\(\sqrt{x}\)就好了 算法二: 我们由\(x = a + b + ab\)可得 \(x + 1 = (a + 1) (b + 1)\) C 我们发现我们直接括...

LuoguP5464 缩小社交圈 背景:洛谷七月月赛T4 题目大意给定\(n\)个点,每个点的权值对应着一个区间\([l_i,r_i]\),两个点\(i,j\)有边当且仅当他们权值的并集不为空集,问有多少个点集\(S\)满足其连边后是一棵树 \(n <= 2*10^3,l_i<=r_i<=2*10^3\) 首先,这道题不能转换成一道图论问题去考虑,为什么? 因为这道题区间的性质非常特殊,是解题关键,如果转化成图,就没有了这个性质. 首先,如果不能转化成图论,此类区间的问题还是应该先进行排序. 我们按照\(r_i\)进行排序之后考虑\(DP\) 我们发现如果\(i\)与\(j\...

Comet OJ - Contest #5 总有一天,我会拿掉给\(dyj\)的小裙子的. A 显然 \(ans = min(cnt_1/3,cnt_4/2,cnt5)\) B 我们可以感性理解一下,最大的满足条件的\(x\)不会太大 因为当\(x\)越来越大时\(f(x)\)的增长速度比\(x\)的增长速度慢得多 其实可以证明,最大的满足的\(x\)不会超过\(100\) 因为没有任何一个三位数的各位之和大于等于\(50\) 所以我们就直接预处理\(1-99\)所有的合法的 暴力枚举即可 其实赛后题解说满足条件的\(x\)只有\(17\)和\(18\) #include<cstdio&...

Codeforces Round #564(div2) 本来以为是送分场,结果成了送命场. 菜是原罪 A SB题,上来读不懂题就交WA了一发,代码就不粘了 B 简单构造 很明显,\(n*n\)的矩阵可以按照这个顺序排列  然后根据\(n\)的大小搞一搞就好了 #include<cstdio> #include<cctype> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #define LL long long #defi...

莫队阶段小结 首先,为什么要叫小结呢,因为我只学了一点点,后续可能更多 莫队 莫队是一种离线处理区间问题的神器.答题思路就是你将原数列分成\(\sqrt{n}\)块,将所有查询左端点定位,并按照左端点所在的块进行排序,相同则按照右端点排序 大体就是这个样子 inline bool cmp(Q x,Q y){ return belong[x.li] == belong[y.li] ? x.ri < y.ri : x.li < y.li; } 这样的话我们每个快内都暴力求 时间复杂度为\(O(m\sqrt{n})\) 但是还有一种玄学加速方式,十分有用 inline bool cmp(...

CF 453C. Little Pony and Summer Sun Celebration 构造题。 题目大意,给定一个无向图,每个点必须被指定的奇数或者偶数次,求一条满足条件的路径（长度不超\(4n\)）.没有输出-1 首先我们应该判断掉-1的情况 图不连通且所有的奇数点不在同一个联通块内 发现只有上述情况可以 为什么 我们发现图不连通但所有的奇数点在同一个联通块内和图连通在本质上是一种情况. 我们在这里就只考虑图连通该怎么办. 首先,我们对于这张图求出他任意一个生成树 之后我们进行dfs,在dfs再次回到\(x\)点时(即我们已经处理玩了\(x\)的所有子树),我们就要求他合法.但是,...

CF1137 C. Museums Tour 一般来说的正常思路:看到有向图的第一思路都是缩点(但是要分析一波证明强联通分量中的个体可以拼凑成整体,一般都是边和点可以经过无数次然后贡献只算一次这种类型)\(DAG\)上面DP. 这道题第一眼看上去比较麻烦,因为这个时间限制比较恶心的样子. 我们考虑拆点,将一个点拆成\(d\)个,\((i,j)\)表示第\(i\)个点在第\(j\)天的联通情况 这样的话,我们在缩点的时候,就统计一下每一个强联通分量内有多少点在其对应的博物馆的开放时间内(注意去重) 这样的话,我们貌似就得到了每个强联通分量的点权 剩下的貌似就是一个\(DAG\)上的最长链问题了....

Loj3033 JOISC 2019 Day2两个天线 下午唯一听懂的题目但,但还是比较模糊.写一篇题解来加深一下印象. 题目大意:给定\(n\)根天线,第\(i\)跟天线的高度为\(h_i\),切它能和与他距离在\([a_i,b_i]\)内的天线交流. 两根天线互相交流当且仅当他们彼此都在对方的交流范围内.定义两根天线交流的代价为\(|H_i-H_j|\) 有\(Q\)次询问,每次询问区间\([l,r]\)内所有够相互交流的天线的交流代价的最大值(\(n <= 2*10^5\)) 首先看到这种东西,我的第一反应是CDQ分治,但是CDQ分治不好处理这种多组区间询问的问题 所以只能另想办法...

5.29 SD省队培训D1 自闭的一天 T1 梦批糼 先咕一咕(两天之内一定补上) T2 等你哈苏德 继续咕(一星期之内补上) T3喜欢最最痛 四十分做法： 首先，我们发现同一个点加两条额外边是一件非常蠢的事,然后同时,加额外边也同时意味着讲这两个点在树上的路径长度用当前权值代替.那么题目就转化成了对与每个\(k\in[0,m]\)求出树上的边不相交(因为上面说了,相交是一件很蠢的事)的\(k\)条路径的最大和. 我们考虑\(dp\),因为点不相交就贪心,有点类似noip2018D1T3 设\(dp_{i,j0/1}\)表示在以\(i\)为跟的子树中,选了\(k\)条路径,能\((1)\)否\...

CF526F Pudding Monsters 题目大意:给出一个\(n* n\)的棋盘，其中有\(n\)个格子包含棋子。 每行每列恰有一个棋子。 求\(k*k\)的恰好包含\(k\)枚棋子的子矩形个数。 比较有意思的一道分治题目. 首先我们将所有棋子归位 设\(sum_i\)表示第\(i\)行的棋子在第\(sum_i\)列 那么\(sum\)数组就一定是一个排列 而题目就可以转化为 这个排列中有多少个区间的值域是连续的 我们考虑分治解决,每次考虑夸\(mid\)的答案个数 我们提前预处理出\(mid\)为起点的向左后缀最值和向右前缀最值 分四种情况考虑, 1：最大值和最小值都在左边 我们可以...

P4169 [Violet]天使玩偶/SJY摆棋子 CDQ分治的题目. 我们发现题目要我们求的\(|A_x-B_x|+|A_y-B_y|\)的绝对值号比较恶心. 试想一下怎么去掉 如果所有的点都在我们当前求的点的左下方(就是只考虑在他坐下方的点对他的贡献). 我们怎么求? 那么就要我们求\(min{A_x-B_x+A_y-B_y}\)(假设\(A\)为询问的点) 那么其实就是让我们求\(A_x+A_y-max(B_x+B_y)\) 也因为要满足左下角的限制 其实就是满足 \(B_x<=A_x\)同时满足\(B_y<=A_y\)中最大的\(B_x+B_y\) 这个是可以直接CDQ的 ...