34.笔记1

今天，我们回顾回顾曾经的知识。

1.二分

还记得当初的二分吗？

1.一开始的二分

就像下面这个故事：

有一只老鼠，躲在10个大瓷瓶后面。你的任务就是抓住这只老鼠，但在抓的过程会导致你选择的大瓷瓶成为分子碎片。

如果挨个攻击，最坏的情况是大瓷瓶全部打碎，那样你的妈妈会很生气的。（洛西：真可怕。）

所以，你可以每次把正中间的大瓷瓶打碎，若没打到，老鼠发出的“吱吱”声会提醒你老鼠在哪里。

2.现在的二分的特点

1.单调性

想必你知道一点吧！假如我们有变量mid，l，r，k，d。每一行的第k大的最大值不超过d等价于每一行都至少有m-k+1个<=d的数字。

单调性如下：

若mid可以，[mid,r]显然是可以的，[l,mid]却不一定，因为所有行的第k大的最大值<=100，所有行的第k大的最大值也一定可以<=101

 2.双指针

双指针，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相同移动来维护、统计信息。

3.前缀和差分

1.差分思想

其实，差分是把“区间操作”转化为“两点操作”，大大加快了速度。这也就是一些复杂的题要用适合的算法。

2.举例

假设有一个序列a,它的差分数组b定义为：

b[1]=a[1]

b[i]=a[i]-a[l-1](2<=l<=n)

4.代码题

题目描述

灵梦有 n 个单词想要背，但她想通过一篇文章中的一段来记住这些单词。

文章由 m 个单词构成，她想在文章中找出连续的一段，其中包含最多的她想要背的单词（重复的只算一个）。并且在背诵的单词量尽量多的情况下，还要使选出的文章段落尽量短，这样她就可以用尽量短的时间学习尽可能多的单词了。

输入格式

第 1 行一个数 n，接下来 n 行每行是一个长度不超过 10 的字符串，表示一个要背的单词。

接着是一个数 m，然后是 m 行长度不超过 10 的字符串，每个表示文章中的一个单词。

输出格式

输出文件共 2 行。第 1 行为文章中最多包含的要背的单词数，第 2 行表示在文章中包含最多要背单词的最短的连续段的长度。

#include<bits/stdc++.h>
using namespace std;
map<string,bool> tar;
map<string,int> cnt;
string s[100005];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){string str;cin>>str;tar[str]=1;}int ans=0,len,m;cin>>m;for(int i=1,j=1;i<=m;i++){cin>>s[i];if(tar[s[i]]){cnt[s[i]]++;}if(cnt[s[i]]==1){ans++;len=i-j+1;}while(j<=i){if(cnt[s[j]]==1){break;}if(cnt[s[j]]>=2){cnt[s[j]]--;j++;}if(!tar[s[j]]){j++;}}len=min(len,i-j+1);}cout<<ans<<endl<<len;return 0;
}