BzhH

问题引入 在这个二维空间中存在两类点，现在需要画一条直线，将这两类点区分开来，并且当有新数据加入时，能根据这条线判断它属于哪一类，应该如何画这条线。 这个问题可以进一步推演到三维空间中，如何用一个二维平面区分两类数据，也可以更进一步推演至高维空间。 那么，以上问题可以被归纳为，为了区分两类数据，NNN 为数据的样本数，MMM 为维度数，如何设计一个维度为 M−1M-1M−1 的超平面，将两类数据区分开来。 SVM算法 支持向量机（Support Vector Machine，SVM）是一种经典的监督学习算法，用于解决二分类和多分类问题。其核心思想是通过在特征空间中找到一个最优的超平面来进行分类，并且间隔最大。 间隔 上面是两种不同的分类画法，左边的存在数据点与决策边界线相当接近，若有一个新的数据点同样接近该边界线，这样错误的概率就会很大。 而第二种画法，两类数据中所有的点都与边界线有着一定的距离，我们把这个距离称为间隔，这个间隔起着缓冲的作用，把两类数据分隔开来。 间隔距离可以体现出两类数据的差异大小，间隔越大，意味着两类数据差异越大，区分就越容易，因此求解最佳决策边界线的问题就 ...

GJK(Gilbert-Johnson-Keerthi)算法 背景知识 凸多边形 定义：对于平面上的一个多边形，如果延长它的任意一条边，使整个多边形都位于延长线的同侧，这样的多边形为凸多边形 显然，人可以直观的判断一个多边形是否为凸多边形，那么在程序中，应该如何判断一个多边形是否为凸多边形 利用向量的叉乘，根据多边形顶点坐标，依次求出每条边的向量axb,bxc,cxd…的结果应同号，否则就为凹多边形 闵可夫斯基和 闵可夫斯基和是两个欧几里得空间点集的和。点集A与B的闵可夫斯基和用公式表示就是 A+B={a+b∣a∈A,b∈B}A+B=\{a+b|a\in A,b\in B\}A+B={a+b∣a∈A,b∈B} 对于减法，闵可夫斯基和的概念也成立，即为闵可夫斯基差，举个例子 下面这两个图形的闵可夫斯基差即为 A−B={(3−5,4−6),(3−6,4−1),(3−10,4−2),(3−9,4−7)(1−5,1−6),(1−6,1−1),(1−10,1−2),(1−9,1−7)(4−5,0−6),(4−6,0−1),(4−10,0−2),(4−9,0−7)}A-B=\\\{(3-5, ...

用于解决一类题目给出多个询问,每次询问只涉及一部分点的树上DP。 很明显如果直接DP那么每次询问都要做一遍DP,复杂度是不能接受的。 虚树 顾名思义就是一棵虚拟创建的树,这棵树上只会保留与答案有关的关键点以及关键点的 LCA, 这样整棵树的规模不会超过原树的两倍。 虚树的建立 预处理出建立虚树所需要的东西，LCA以及一个栈（栈里维护的是根节点到栈顶节点的一条链） 对于每个关键点,按照 dfs 序从小到大排序。 同 a 表示当前需要加入的点，p 表示当前栈顶维护的点，这时会有两种情况： 1.a 与 p 在同一条链中,直接入栈即可 2.a 与 p 在不同子树中,这时就说明 p 所在这棵子树已经遍历完毕了,对它构建虚树 设栈顶元素为 x, 栈顶下一个元素为 y 1.若 dfn[y] > dfn[lca],将 y -> x 连边,x出栈。 2.若 dfn[y] <= dfn[lca],即 y = lca 或 lca 在 x，y之间,将 lca -> x 连边 lca,a 入栈,结束。 不断重复上述过程，就可以构建出一个虚树了。 例题 P2495 [SDOI2011]消耗 ...

题目描述 给出一个 N 个整数构成的序列，有 M 次操作，每次操作有一下三种： ①Insert Y X，在序列的第 Y 个数之前插入一个数 X； ②Add L R X，对序列中第 L 个数到第 R 个数，每个数都加上 X； ③Query L R，询问序列中第 L 个数到第 R 个数的平方和。 输入格式 第一行一个正整数 N，表示初始序列长度。 第二行 N 个整数 Ai，表示初始序列中的数。 第三行一个正整数 M，表示操作数。 接下来 M 行，每行一种操作。 输出格式 对于每一个 Query 操作输出答案。由于答案可能很大，请 mod 7459 后输出。 数据范围 100%的数据满足 N≤105，M≤105N≤10^5，M≤10^5N≤105，M≤105，且 Add 和 Insert 操作中∣X∣≤1000，∣Ai∣≤1000|X|≤1000，|A_i|≤1000∣X∣≤1000，∣Ai​∣≤1000。 解题思路 考场第一题就是这道数据结构，写了160+行代码喜提0分，然后改错从160行->270行，这不写篇题解庆祝一下。 显然，如果没有操作一，就是一道线段树水题，但是这个操作一就 ...

哈希表 头文件 #include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>using namespace __gnu_pbds 两种定义方式 cc_hash_table<string,int>mp1;//拉链法gp_hash_table<string,int>mp2;//查探法(快一些) 用法和map一样,但效率要比map快 这里给出一张进行 10710^7107 次插入查询不同 map 的运行效率 可以看到 pb_ds的哈希还是要快很多的 堆 头文件 #include<ext/pb_ds/priority_queue.hpp> 定义方式 __gnu_pbds::priority_queue<int>q;//因为放置和std重复，故需要带上命名空间__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> pq;//最快__gnu_pbd ...

这题暴力建图再加个最短路就可以过。 对于一个点 xxx，我们给它和它相邻的点之间连一条有向边，若相邻的点为石头，则边权为 111，反之，则为 000。 然后大力枚举每一个点 xxx，对于每一个点都跑一遍 Dijskra 算法，这时候，我们就已经求出了点 xxx 到其他所有点需要经过的石头的数量的最小值，然后再枚举终点更新答案即可，时间复杂度 Θ(n4)\Theta(n^4)Θ(n4) 代码 #include<iostream>#include<cstdio>#include<queue>#include<cmath>#include<cstring>#define get(x, y) ((x - 1) * n + y)using namespace std;const int N = 1e6 + 5;typedef pair<int, int> PII;char sq[35][35];int dis[905];int head[N], ver[N], net[N], edge[N], idx;bool vis[90 ...

又是一道构造题，题目所求的是一个单调不降序列，并且要用不超过 2n2n2n 的操作， 咋一眼看上去似乎没什么思路，但我们可以尝试一种构造方案，那就是令 ai=i−1a_i=i-1ai​=i−1，这样的话这个序列就是一个单调上升的序列，满足题目要求，那么接下来的问题就是如何在 2n2n2n 次操作内转化成这个序列，对于一个序列若他不满足 [0,n−1][0,n-1][0,n−1] 的数都只出现了一次，那么它的mex必然在 [0,n−1][0,n-1][0,n−1] 内，那么我们可以直接枚举 nnn 次mex，每次对mex+1的位置的数使用操作，这样就能在 nnn 次内得到一个 [0,n−1][0,n-1][0,n−1]，都只出现了一次的序列，但它不一定满足上面的那个性质，所以对于每一个 ai=k≠i−1a_i=k\ne i-1ai​=k=i−1，对它使用一次操作 ai=na_i=nai​=n，然后再对 k−1k-1k−1 使用使用一次操作 ak−1=ka_{k-1}=kak−1​=k，如此循环，那么这个序列就能满足上面的条件了,并且操作数不会多于 2n2n2n。 代码 #include ...

P5008 [yLOI2018] 锦鲤抄 为啥感觉这道题作为紫题有点水 给你一张有向图，每个点有一个点权。任意时刻你可以任意选择一个有入度的点，获得它的点权并把它和它的出边从图上删去。最多能选择 kkk 个点，求最多能获得多少点权。 首先考虑DAG的情况,不难发现,对于DAG上的每一个点,如果它有入度,那么就一定能被选上,自己想一想就能明白. 然后考虑任意情况,直接跑一遍tarjan,转化为一个DAG.对于DAG上的每一个强连通分量,和上面一样.直接考虑每一个强连通分量内部 若一个强连通分量没有入度,那么无论怎么选,都会有一个点选不到,所以直接去掉最小的点就行 若一个强连通分量有入度,那么总有一个方案可以使所有点都被选上. 直接记录下所有可以被选的点,取前 kkk 大就行 时间复杂度可以做到 O(n+m)O(n+m)O(n+m),用nth_element,不过似乎比sort快不了多少 代码 #include<iostream>#include<cstdio>#include<vector>#include<functional>#incl ...

「SWTR-6」Snow Mountain 假设我们已经构造出一种方案摧毁了所有的水晶，要求最小的花费，显然是一个经典的贪心问题，直接从大到小选即可。 那么问题就在与我们要如何构造出一个满足条件的方案并让它的花费最小，题目中保证了 nnn 为偶数，并且 axi>aia_{x_i}>a_iaxi​​>ai​，不妨将这个数列升序排列，令前半段为 [a1,...,amid][a_1,...,a_{mid}][a1​,...,amid​]，后半段为 [amid+1,...,an][a_{mid+1},...,a_n][amid+1​,...,an​] （这里的 aia_iai​ 表示水晶的编号），显然，如果能够让前半段的所有数与后半段匹配，那么花费一定能够最小，并且在排完序过后，我们不用考虑后半段是否会与前半段共振，只需要考虑前半段即可。 这里给出一种配对的方法，用一个双端队列将后半段存下来，每一次匹配都与队头或队尾中不与 aia_iai​ 号水晶共振的匹配,能够证明，这种方法至少能够匹配 n2−1\frac{n}{2}-12n​−1 对水晶，并且剩下的一定是 amida_{ ...

主要是解决几个数能否拼凑成其他数的问题 例题P3403 跳楼机 给定三个数 x,y,zx,y,zx,y,z,问有多少 w=ax+by+cz≤h−1w=ax+by+cz\le h-1w=ax+by+cz≤h−1 定义 disidis_idisi​ 表示x,y,zx,y,zx,y,z 能够组成 wmod  x=iw\mod x=iwmodx=i 的最小的数 可以这样建图 i⟶yi+ymod  x,i⟶zi+zmod  xi\stackrel{y}{\longrightarrow}i+y\mod x,i\stackrel{z}{\longrightarrow}i+z\mod xi⟶y​i+ymodx,i⟶z​i+zmodx 这样就只需要跑一遍最短路就可以求出 disdisdis 了,统计答案时若 disi≤h−1dis_i\le h-1disi​≤h−1,就加上 ⌊h−1−disix⌋+1\lfloor\frac{h-1-dis_i}{x}\rfloor +1⌊xh−1−disi​​⌋+1 代码 #include<iostream>#include<cstring># ...