转载自（图片没有放）原文链接：http://blog.csdn.net/bone_ace/article/details/46239187） 凸包问题的五种解法[转] 前言： 首先，什么是凸包？ 假设平面上有p0~p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候，我们就叫它“凸包”。如下图： 然后，什么是凸包问题？ 我们把这些点放在二维坐标系里面，那么每个点都能用 (x,y) 来表示。 现给出点的数目13，和各个点的坐标。求构成凸包的点？ 解一：穷举法（蛮力法） 时间复杂度：O(n³）。 思路：两点确定一条直线，如果剩余的其它点都在...

转载自https://blog.csdn.net/liangzhaoyang1/article/details/52819835 Fast Walsh-Hadamard Transform 就是用于解决一类卷积问题的方法。大概如下： 其中指任一二元逻辑位运算。 一些基础的想法： 为了加速这个运算，我们还是需要用一些类似FFT的东西。 注意到位运算都是有位独立性的，那么每次我们只考虑某一位？ 不妨假设： 那么，我们的目标就是求出： 假如构造了一个变换 ，满足： 且可以在较短时间内进行变换及其逆变换，那么我们的目标就可以实现了。 似乎便不能继续往下走了，那我们具体情况具体分析。 XO...

https://blog.csdn.net/GGN_2015/article/details/69518685

我们知道能用单调队列优化的DP问题需要满足： dp[i] = max / min （f[k]）+ g[i] （k < i && g[i]是与k无关的变量） 多重背包问题多用二进制优化，优化后的复杂度为O（NVΣlogni）。多重背包问题的状态转移也能转化成此状态转移方程，从而利用单调队列优化，优化后的复杂度为O（NV）。 具体思路： 对于第i件物品： 已知体积为we，价值为val，数量为num，可以按照we的余数，将当前的体积分成we组（0，1，…we - 1）。对于任意一组，可以得到转移方程：f[i * we + c] = max（f[k * we + c] ...

struct data{ int l,r,v,size,rnd,w; }tr[100005]; rnd//堆的随机权值 int n,size,root,ans; void update(int k){ tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w; } void insert(int x){ if (k==0) { size++;k=size; tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].rnd=rand(); return; } tr[k].size+...

搬运自https://www.bilibili.com/video/av6445624?from=search&seid=16371895668105873445 using namespace std; const int maxn=1e5+7; int belong[maxn],num,l[maxn],r[maxn],n,q,block; long long a[maxn],Max[maxn]; void build(){ block=sqrt(n); num=n/block;if (n%block==0) num++; for (int i=1;i<=num;...

已经团报，三缺一

p=0 extend(c) { new np; np.max=++L; for (i=p;trans[i][c]==null&&i!=null;i=parent[i]) trans[i][c]=np; if (i==null) trans[np]=root else q=i.trans[c] if (q.max==i.max+1) np.parent=q; else new nq nq.trans[]=q.trans[] nq.parent=q.parent ...

vector<pair<int,int>>imp; vector<int>G[MAX]; int s[MAX],s_top; void build() { sort(imp.begin(),imp.end()); //为了方便处理，为我们把树根固定当做关键点 s[s_top=1]=1; //按照dfs序遍历每个点 for (int i=0;i<imp.size();i++){ int v=imp[i].second; int t=lca(v,s[s_top]); //t的dfs序肯定小于栈顶元素(因为他是v和栈顶元素...

给定两个字符串S和T 你每次可以在S的某个字符c后面添加一个字符d，要保证c!=d 问有没有可能把S变成T 1<=|S|<=|T|<=1e5 首先S必须要是T的子序列，且S1=T1 因为字符不同的限制，所以S开头连续相同的字符数要不小于T开头的连续相同的字符数 如果满足以上条件，那么一定可以得到T 时间复杂度O（n） #include<iostream> #include<cstdio> #include<cstring> int solve() { int i,j; int l1=strlen(s); int l2...

转载自https://www.cnblogs.com/xiaoxubi/p/6185733.html #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int Mx=100010; int n,m,rank[Mx],mn[Mx][50],h[Mx],sa[Mx],rank1[Mx],tmp[Mx],temp=1,Ton[26],ton1[Mx],nu...

为了搞网络编程大作业，本来想在网上抄个爬图片作业二应付过去的，后来觉得爬虫挺重要的，于是一无所知的我去b站学了快一个星期，https://www.bilibili.com/video/av50730537/?p=84&t=277，只看到82章，scrapy配了一天失败了，接下来还要去搞编译原理大作业。 这是一些脚本的记录，就都扔这里了。 json #encoding:utf-8 import json # json_str='[{"username": "张三", "age": 18, "country&quot...

Print Article Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 20528 Accepted Submission(s): 6240 Problem Description Zero has an old printer that doesn’t work well sometimes. As it is antique, he still like to use it to print articles. But it ...