• 2024-11-13NOIP 模拟赛:2024-11-11
    T1:法一:\(O(n^2)\)的DP。\(dp[i][j][0/1]\)表示在\(i\)的子树内染色,\(i\)是红/黑,使得每个要求的结点的黑点个数都等于\(j\)。法二:\(O(n)\)的神秘做法。取出最浅的被要求结点,把深度\(\le\)它的都染成黑色,其余点都染成红色。T2:对于一个元素属于\([0,2^m)\),且互不相
  • 2024-09-28SMOI-R1 赛后若干个月的总结
    打得非常好的一场比赛,所以才来写总结。T1「SMOI-R1」Queue打表找规律题,太签到了,不讲。T2「SMOI-R1」Company首先,如果要使得\(x,y\)的距离最后是尽可能远的,我们就要考虑一些满足最优解的性质。不难想到一个结论:如果将初始时每一棵树缩成一个节点,那么最优解形成的新的树必
  • 2024-07-10cdq分治
    cdq分治其大致形式为递归左右半边考虑左半边对右半边的影响二维偏序(归并排序):计算数对\((i,j)\)满足\(a_i<a_j\)并且\(b_i<b_j\)的数对数量先以\(a_i\)排序,这样条件被转换为\(i<j\)且\(b_i<b_j\)考虑cdq分治先递归左右半边对左右两边各开一个指针,若\(b_i<b_
  • 2024-06-20不知道记哪的小tips
    Tips对于\(a_i\len\),可以连边\((i,a_i)\),然后就变成一棵内向基环树森林一种图论题目可以把边挂在点上(可以挂一半,也可以挂全部),当然也可以把点权挂在边上要求图的度都为奇数,等价于要求图的连通块大小都为偶数证明:必要性:反证,考虑若有一个连通块大小奇数,那么图的总度数为
  • 2024-02-15其他题目合集
    袭击给出\(2n\)个点,求在前\(n\)个和后\(n\)个点中各选一个点的距离的最小值是多少。分治出处:《算法竞赛进阶指南》题解:先考虑只有一种点,怎么求两两距离的最小值。分治,整体的最小距离\(ans=\min(\)左半边的最小值,右半边的最小值,左右之间的最小值\().\)只需考虑左右之
  • 2024-01-28CodeForces 1924D Balanced Subsequences
    洛谷传送门CF传送门发现去掉匹配的\(2k\)个括号后,剩下的串一定形如\())\ldots)((\ldots(\),其中右括号数量为\(a=m-k\),左括号数量为\(b=n-k\)。考虑把剩下的串像\())\ldots)\mid((\ldots(\)一样分成两半。枚举左半边加入了\(\frac{i}{2}\)对匹配,则
  • 2023-09-06二分的边界问题
    二分法的适用场景1.有单调性的题目一定可以二分2.没有单调性也有可能二分由此可见,二分的核心并不是单调性。核心是:定义了某种性质,使得可以将整个数据集一分为二,左半边满足一种性质,右半边不满足;右半边满足另一种性质,左半边不满足。则二分可以寻找左区间的边界,也可以寻找右区
  • 2023-05-16luogu P8340 [AHOI2022] 山河重整
    题面传送门牛逼题。solution首先来推一推性质。假设我们现在有一个合法的集合,覆盖了\([1,S]\),显然新加进去的数\(i\)不能\(\geqS+2\),而如果\(\leqS+1\)那么\([1,i+S]\)显然可以被覆盖到。因此有一个\(O(n^2)\)的dp:设选到了第\(i\)个数,总和为\(j\),要求\(j\geq
  • 2023-04-072023.4.7【模板】快速沃尔什变换FWT
    2023.4.7【模板】快速沃尔什变换FWT题目概述给定长度为\(2^n\)两个序列\(A,B\),设\(C_i=\sum_{j\oplusk=i}A_j\timesB_k\)分别当\(\oplus\)是or,and,xor时求出\(C\)我们通常将这个操作,叫做“位运算卷积”,因为它的卷积是按照位运算法则“卷”起来的。算法流程或
  • 2023-03-19初识OpenMesh
    本文是笔者修读《计算机图形学》时,课程作业的副产物。本文的大部分内容是官方文档的“UsingandunderstandingOpenMesh”一章的翻译。简介OpenMesh是一个通用且高效的
  • 2023-01-0101排序
    快速排序问题将序列q的l~r区间排序voidquick_sort(intq[],intl,intr)基本思想——分治找一个参考值x通过双指针算法交换使得左半边全部是<=x,
  • 2022-12-28AcWing245. 你能回答这些问题吗
    题目描述给定长度为\(N\)的数列\(A\),以及\(M\)条指令,每条指令可能是以下两种之一:1xy,查询区间\([x,y]\)中的最大连续子段和2xy,把\(A[x]\)改成\(y\)。对
  • 2022-11-04半边数据结构与OpenMesh中的处理
    参考:https://blog.csdn.net/jialong_chen/article/details/118497495《Springer.3DMeshProcessingandCharacterAnimation.WithExamplesUsingOpenGL,OpenMeshand
  • 2022-09-04Leetcode — 34. 查找有序数组中元素的第一个和最后一个位置
    Leetcode—34.查找有序数组中元素的第一个和最后一个位置题目:查找排序数组中元素的第一个和最后一个位置难度:medium语言:Python中文题意:给一串以递增排序的整数