小衣同学的博客

这题有O(nlognlogX)的做法，但是比较复杂难写，不如这个好理解，就先只补这个了。这是一个O(n^2)的做法，比较巧妙，每次O(n)找到一组点，然后递归左右。求p和q的一组完美匹配，使得将两两匹配的点连成线段后，任意两条线段不交。2n(n<=1e4)个二维点，其中n个构成p数组，n个构成q数组，并且由于已按从小到大排序，则这两个点一定会在这些点构成的凸包上，由于每次操作是O(n)的，所以复杂度是O(n^2)的。前缀内满足p和q的个数相同，后缀也满足，O(n)求出这些点的凸包，不妨是下凸壳，

202303-1 田地丈量（矩阵面积交）202303-2垦田计划（二分）202303-3LDAP（模拟+栈+bitset）202303-4星际网络II（线段树）202303-5 施肥（分治+线段树+树状数组）60分题解（O(n^2+nm)暴力）75分题解（特殊性质）100分题解（分治+线段树+树状数组）

AtCoder Beginner Contest 281 F. Xor Minimization(递归/按位分治)

牛客挑战赛65 D.233求min(思维/二分 二维偏序 树状数组/cdq分治)

力扣天池赛-221021天池-04. 意外惊喜(分治优化dp)

题目二维平面，读入若干行，每一行对应一次操作，操作分4种：0：清掉平面内所有点1 x y c(1<=x<=1e6,1<=y<=1e6,0<=c<=50)：在(x,y)加入一个颜色为c的点，点重合时同时存在2 x y1 y2(1<=x<=1e6,1<=y1<=y2<=1e6)：统计以(1,y1)左下角以(x,y2)右上角这个矩形内点的颜色数3：退出程序数据保证只有最后一行是3操作，连续的1或2操作只有最多15W个（即每逢

题目给出一个长为n(n<=1e6)的排列p[]，规定一个区间 [l,r](l<=r) 是 fair 的，当且仅当区间中最小值等于 l 且最大值等于 r求 fair 区间的个数。思路来源https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44985124题解考虑[4,1,2,3]，区间重排之后最小值是1，最大值是4，所以(1,4)这个值对答案有贡献，换言之，[1,4]中1是最小值，[1,.

题目n(n<=2e5)个数的数组a[]，ai在[1,1e9]间，数组内的数是非严格单增的，现在需要猜出这个数组，每次询问输入，? l r，代表询问[l,r]的众数，系统会返回这个区间内众数x及其次数f，如存在多个众数，则会返回最小的那个，保证数组内的不同元素数量为k(k<=min(n,25000))，但k未知，你需要不超过4*k次询问，询问出这个数组，最后输出不算次数交互题日常，输出完之后fflush(stdout)思路来源https://blog.csdn.

题目给定m(1<=m<=20)，代表m叉树，和两个长度为1-26的字母串，分别代表树的前序和后序序列，求这两个序列能确定多少种不同的树思路来源https://www.cnblogs.com/BobHuang/p/8227875.html题解本质区别是，对于一个根固定的区间，第一棵子树对应一段前序和后序区间，第二棵对应一段……，假设有x棵子树，则对应了C(m,x)种选法，找到固定根时，根的每棵子树的前序后序区间，不断递归下去这个题有一个弱化版51n.

题目给你一个数n(n<=500)，代表你需要构造一个n*n的矩阵，该矩阵中，每个格子放上[1,n²]中的一个数，且每个数只能出现一次把国际象棋中的车和皇后初始放在数字1所在的格子，对于车(可横竖走)和皇后(可横竖斜走)来说，它们会按照以下的方案走：①如果在车/皇后一步可达的范围内，存在没有走过的格子，就去这些格子中数值最小的那个格子②如果不存在，就传送到数值最小的格子，并产生1 vun的费用然后继续①操作，直至走完所有格子你需要构造一个n*n的矩阵，使得..

题目给N(0<N<=1e4)个点，坐标范围[0,4e4]，求N个点之间的最近点对的距离，如果该距离大于1e4，输出INFINITY，否则输出距离思路来源《挑战程序设计竞赛》第二版题解先按x轴排增序，分治，考虑跨轴的贡献，设当前左右两边已经递归出最小距离为d，枚举中点的x值为当前中轴时，只考虑距中轴距离d以内的点，视为合法点对于[l,r)区间，归并...

题目T组数据，每次给出n(n<=1e7)个正整数，输出从大到小第k大的数，时限1s，空间131072KB题解现在想想找第k大就是快排划个轴递归嘛，像线段树上二分一样nth_element一下就好，nth_element会取出中间那个参数rank的值放在那个位置，并使左侧的比它小，右侧的比它大在学弟的敦促下，写了一发快排的写法，只是这题由于输入数据1e7，太毒瘤了卡...

题目样例数T<=1e3，需取模的p<=1e7思路来源https://blog.csdn.net/tianyizhicheng/article/details/81698600题解很巧妙，记原式结果为g，由于2的个数是无限的，所以开一个函数f(d)来实现求g mod(d)功能，那么要求g mod(d)就得求g mod(phi[d])，递归求f(phi[...

题目题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays给定两个大小为 m 和 n 的有序数组nums1 和nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为O(log(m + n))。你可以假设nums1和nums2不会同时为空。思路来源https://www....

B. 解密信件Time limit per test:1.0 secondsMemory limit:512 megabytesoxx 总是喜欢给 ultmaster 写信，由于某些原因，这些信的内容又不能被人看见。但传信的过程中，信中信息的泄露又不可避免，于是 oxx 发明了一种信内容信息的加密方式。ultmaster 拿到了 oxx 的加密程序：char letter[]...

题目n<=1e3，要求输出一个n*n的矩阵，每行每列都是一个1-n的排列，且关于主对角线对称的元素不同，即A[i][j]≠A[j][i](i≠j)思路来源https://www.cnblogs.com/vocaloid01/p/9514018.html题解n=1为1，n=2无解，考虑n>=3的情形n为奇数的时候，可以通过循环移位，直接求得答案n=4的时候...