1:哈希
建立：拉链法：
a:数组
#include <bits/stdc++.h> using namespace std;
const int md = 1e9;
int h[1000],idx,ne[1000],e[1000];
void add(int x)
{
int y = (x % md + md) % md;
e[idx] = x;
ne[idx] = h[y];
h[y] = idx ++;
}
int main()
{
memset(h,-1,sizeof h);
int n;
scanf("%d",&n);
add(n);
}
b:二维vector
2：字符串哈希
哈希函数 hash(s) = ((c1*pow(base,0)+c2*pow(base,1)+....+cn*pow(base,n-1))%p;
base 一般是大于ci的最大值，p和base都为质数且大于其给的范围，
同时可以用前缀和得到任意一段s的子串的哈希值
那么子串哈希hash(l,r) = (a[r] - a[l - 1] * base ^(r - l + 1) ) % p;
注意：为了防止偶然性可以用双哈希
3：对顶堆
所谓对顶堆，有点像双栈对顶那样，一个是小根堆，另一个是大根堆。假设 g 是大根堆，l是小根堆，两堆中间的元素，左边都是小于它的，且 g.top() 是小于它的最大值，右边都是大于它的，且 l.top() 是大于它的最小值
那么对顶堆是干嘛用的呢？
举一个例题：
给定N个数字，求其前ii个元素中第K小的那个元素。
我们很容易想到用堆来维护这个单调递增的序列，如果使用数组实现的话，我们直接输入数组下标为K的元素即可。但我们使用的是堆，它的实现方式——优先队列是不支持任意点访问的，那么我们就无法进行单点查询。引申对顶堆的概念，我们可以这样解决问题：
优先队列虽然不支持任意点访问，但可以用O(1)的时间查询出堆顶元素，也就是说，我们只能通过维护对顶堆中两个堆的堆顶元素来进行单调性的维护。怎么办呢？
原理很简单：根据数学中不等式的传递原理，假如一个集合A中的最小元素比另一个集合B中的最大元素还要大，那么就可以断定：A中的所有元素都比B中元素大。所以，我们把小根堆“放在”大根堆“上面”，如果小根堆的堆顶元素比大根堆的堆顶元素大，那么小根堆的所有元素要比大根堆的所有元素大。
回到这个问题：我们要求第K小的元素，那么我们把大根堆的元素个数限制成K个，前K个元素入队之后，每个元素在入队之前先与堆顶元素比较，如果比堆顶元素大，就加入小根堆，如果没有的话，把大根堆的堆顶弹出，将新元素加入大根堆。这样就维护出一个对顶堆。它的作用在于找出第K小的元素。
同理，对顶堆还可以用于解决其他“第K小”的变形问题：比如求前i个元素的中位数等。
1:背包
Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi
然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大
Applese觉得这个题依然太菜，于是他把这个问题丢给了你
当物品数量为偶数时，中位数即中间两个物品的价值的平均值
输入描述:
第一行三个数v, n, m，分别代表背包容量，物品数量以及需要取出的物品数量
接下来n行，每行两个数ai，bi，分别代表物品价值以及大小
n ≤ 1e5, 1 ≤ m ≤ n, ai ≤ 1e9, v ≤ 1e9, bi ≤ v
输出描述:
仅一行，代表最大的中位数
题解：
关于这道题，我们先来看看m是奇数怎么做。
很明显，我们可以考虑枚举中位数，然后判断其是否可行即可。这样，我们先对所有物品按价值从小到大排序。
那么，如果一个物品可以作为中位数，当前仅当存在一种方案，从这个物品的左边选m/2个物品，再从它右边选个物品，他们的容积和加上该物品的容积小于等于背包容积v。那么，我们明显只需要贪心去取，每次取最小的几个即可。
我们从i号点左/右取个物品的最小容积和。
对于这个，我们直接开个优先队列，使得优先队列的元素是当前最小的个元素即可。
那么，枚举i时，我们只需要判断下加上左右是否小于等于v，即可。
偶数
我们发现，其实，我们可以把它看做我们从左边的中位数的左边拿m/2--1个物品，再从右边的中位数的右边拿m/2个物品二分不断往右靠
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
struct Now{
ll vaule;
ll weight;
}a[100001];
bool cmp(Now a,Now b)
{
return a.vaule < b.vaule;
}
int s1[100001],s2[100001];
bool check(int res,int i,int v)
{
return s1[i - 1] + s2[res] + a[i].vaule <= v;
}
int main()
{
int v,n,m;
scanf("%d %d %d",&v,&n,&m);
for(int i = 1;i <= n; i ++)
{
scanf("%lld %lld",&a[i].vaule,&a[i].weight);
}
priority_queue<ll> q;
int x = m & 1;
m >>= 1;
sort(a + 1,a + n + 1,cmp);
for(int i = 1;i <= n; i ++)
{
q.push(a[i].weight);
s1[i] = s1[i - 1] + a[i].weight;
if(q.size() > m - 1 + x)
{
s1[i] -= q.top();
q.pop();
}
}
while(q.size())
q.pop();
for(int i =n; i >= 1;i --)
{
q.push(a[i].weight);
s2[i] = s2[i + 1] + a[i].weight;
if(q.size() > m)
{
s2[i] -= q.top();
q.pop();
}
}
if(x)
{
ll ans = 0;
for(int i = m + 1;i <= n - m;i ++)
{
if(s1[i-1] + s2[i + 1] + a[i].weight <= v)
ans = a[i].vaule;
}
printf("%lld\n",ans);
}
else{
ll ans = 0;
for(int i = m; i <= n- m; i ++)
{
ll l = i + 1,r = n-m + 1;
//int l=i+1,r=n-m+1;
while(l<=r){
int mid=l+r>>1;
if(s1[i-1]+s2[mid]+a[i].weight<=v)l=mid+1;
else r=mid-1;
}
if(r > i)
ans = max(ans,a[i].vaule + a[r].vaule);
}
printf("%lld\n",ans/2);
}
}
注意二分的边界，一个向上去取整一个向下取整。
2.小蜗的疑问
现在给你两个字符串a和b，a和b都由小写字母构成。
小蜗想知道字符串b在a中出现了几次(出现位置可以重叠)。
输入格式
第一行两个整数n,m，分别表示a和b的长度。
接下来两行，给出字符串a和b。
输出格式
输出一个数，表示答案
#include <bits/stdc++.h> using namespace std;
const int base1 = 101,p = 9999971,base2 = 131,p1 = 9999973 ;
char a[200011],b[200011];
int ha[200011],hb[200011],c[200011],c1[200011],ha1[200001],hb1[200001];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
scanf("%s %s",a + 1,b + 1);
c[0] = 1;
c1[0] = 1;
for(int i = 1;i <= 200000; i ++)
{
c[i] = c[i - 1] * base1 %p;
c1[i] = c1[i - 1] * base2 % p1;
}
int res = 0;
for(int i = 1;i <= n;i ++)
{
ha[i] = (ha[i - 1] * base1 + a[i] - 'a' ) % p;
ha1[i] = (ha1[i - 1] * base2 + a[i] - 'a') % p1;
}
for(int i = 1;i <= m; i ++)
{
hb[i] = (hb[i - 1] * base1 + b[i] - 'a' ) % p;
hb1[i] = (hb1[i - 1] * base2 + b[i] - 'a') % p1;
} int ans = 0;
for(int i = 1;i + m - 1 <= n; i ++)
if((ha[i + m - 1]- 1LL * ha[i - 1] * c[m] % p + p ) % p == hb[m]
&& (ha1[i + m - 1] - 1LL * ha1[i - 1] * c1[m] % p1 + p1) % p1 == hb1[m])
{
ans ++;
}
printf("%d\n",ans);
}
3.动态中位数
中位数是按顺序排列的一组数据中居于中间位置的数。
现在依次给你nn个数a1,a2,…,an(保证n为奇数)，你需要给出读入到第1,3,5,…,n 个数时，当前的中位数是多少。
输入格式
第一行一个整数n。
接下来一行共n个数。
输出格式
输出(n+1)/2个数，表示答案。
#include <bits/stdc++.h> using namespace std;
int n;
priority_queue<int> q;
priority_queue<int ,vector<int> ,greater<int> > p;
int a[100010],b[100010],idx = 1;
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++)
{
scanf("%d",&a[i]);
}
q.push(a[1]);
for(int i = 2;i <= n;i ++)
{
if(a[i] <= q.top())
q.push(a[i]);
else
p.push(a[i]);
if(q.size() - p.size() == 3)
p.push(q.top()),q.pop();
if(p.size() - q.size() == 1)
q.push(p.top()),p.pop();
if(i % 2 == 0)
printf("%d ",q.top());
}
printf("%d\n",q.top());
}
