专栏： 蓝桥杯——每日四道编程题（两道真题+两道模拟）
“蓝桥杯就要开始了，这些题刷到就是赚到”
₍ᐢ..ᐢ₎♡
另一个专栏： 蓝桥杯——每日四道填空题（两道真题+两道模拟题）

专题前瞻：复习并查集、Tire字符串、双指针、二分

目录

第一道真题（日志统计）

输出描述

输入输出样例

第二道真题（合根植物）

输出描述

输入输出样例

第三道模拟题（acwing）：Trie字符串统计

第四道真题（扫地机器人）

题目描述

---

第一道真题（日志统计）

 

输出描述

按从小到大的顺序输出热帖 id。每个 id 一行。

输入输出样例

输入：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出;

1
3

运行限制
最大运行时间：1s
最大运行内存: 256M

双指针思想！(滑动窗口类型)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
pair<int,int> pll[N]; //存时间和id 
int cnt[N]; //存id对应的点赞数；
int n , d, k ;
bool rit[N]; //存满足条件的“热帖”id
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>d>>k;
  for (int i = 0 ; i < n ; ++i)
  {
     cin>>pll[i].first>>pll[i].second;
  }
  sort(pll , pll + n); //默认是按first进行排序，这里把时间就行排序，方便双指针维护满足要求的时间区间。
  for (int i = 0 , j = 0 ; i < n ; ++i ) //滑动窗口的类型，i在前， j在后
  {
    int t = pll[i].second;//把每个获赞的帖子id存下来
    cnt[t]++; //出现一次，就给该帖子记录一个赞。
    while (pll[i].first - pll[j].first >= d) //注意时间是从0开始的，并且是前闭后开！！
    {
       cnt[pll[j].second]--;//不满足时间区间了，就可以把它的赞取消啦，它不可能成为热帖了。
       j++; //j指针记得往前走，保证区间是满足时间要求的。
    }
    if (cnt[t] >= k)  rit[t] = true; //记录下满足热帖编号，方便输出哦。

  }
  for (int i = 0 ; i < N ; ++i)  //输出满足条件的id
  {
    if (rit[i]) cout<<i<<endl;
  }
  return 0;
}

总结：

双指针的三个关键点

• 指针的起始位置的选取
• 指针的移动方向
• 指针的移动速度

双指针一般有如如下几种类型;

快慢指针: 两个指针，一个步长大，一个步长小，

 对撞指针：两个指针分别指向数组的开头和结尾，通过循环来完成题目。例如求回文串。

 滑动窗口：两个指针分别代表窗口的左边界和右边界，然后根据条件移动两个指针来维护这段区间，就比如上面那道例题。

 总之，这个双指针非常灵活，你不必局限于上述三个大方向。可以相互结合，互相穿插。

就比如 【蓝桥杯】每日四道编程题（两道真题+两道模拟）| 第一天 里面那道统计子矩阵。通过上下边界指针的移动，来搜索每个子矩阵。

所以我认为双指针一般都是将这种形式(O())

for ( int i = 0 ; i < n ; ++i)
{
   for (int j = 0 ; j < n ; ++j)
   {
      ................
   }
}

优化成这样的形式（O(n））的。(当然i 和 j 指针不一定都从0起点开始，根据具体体条件而定，反正代码基本都是这种形式的)

for (int i = 0 , j = 0 ; j < n ; ++j)
{
  while (j < i && check(i ,j))
    ...................
}

第二道真题（合根植物）

 比如：5×4 的小格子，编号：

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

输出描述

输出植物数量。

输入输出样例

输入样例：

5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

输出样例：

5

样例说明，其合根情况参考下图：

 运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

复习并查集（O()）：是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查） ，一般有find()函数（找父节点）、merge()函数（合并集合）、pre[ ]数组（记录每个集合，并且指明其前驱节点是谁？）

#include <iostream>
using namespace std;
 
int n,m,k;
int p[1000010];//要1e6  1000*1000
 
int find(int x)
{
  return x==p[x]?x:p[x]=find(p[x]);
}
 
int main()
{
  cin>>n>>m>>k;
  int  root=n*m;
  for(int i=1;i<=root;i++) p[i]=i;
  while(k--)
  {
  	int a,b;
  	cin>>a>>b;
  	if(find(a)!=find(b))
  	{
  		p[find(a)]=find(b);
  		root--;
	}
  }
  cout<<root;
  return 0;
}

想再检测一下自己，就再做一道2019省赛的真题吧。【蓝桥杯】​蓝桥杯——每日四道编程题（两道真题+两道模拟）​| 第 二 天里面那道修改数组吧

第三道模拟题（acwing）：Trie字符串统计

输入样例：

 

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

时/空限制：1s / 64MB

复习Tire 字符串的使用：（快速高效查找字符串集合的数据结构）

Tire树又称字典树或前缀树，是一种能够快速查找一组字符串含有一个字符串的类似哈希表的树结构，是以空间换时间，利用字符串的前缀来降低查询时间。

与二叉树不同，Tire树26子节点对应26个字母，根节点不包含字符串，从根节点到某个节点，经过的字符连起来的字符串就是对应的字符串。当储存结束一个字符串后，尾节点会用cnt[ ]数组来说明该字符串的次数。

当然你可以根据这个思想，运用在其他方面，例如存二进位，快速查找其最大异或对

//开始先定义 ： int son[N][26], cnt[N], idx;

//son[N][26]:储存子节点的位置，分支最多26条

//cnt[N]：存储以节点结尾的字符串个数

//idx：表示当前要插入的节点（新建节点）
#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N][26],b[N],n,idx;
char c[N];
void insert(char c[]){
    int p=0;
    for(int i=0;c[i];++i){
        int u=c[i]-'a';
        if(!a[p][u]) a[p][u]=++idx;
        p=a[p][u];
    }
    b[p]++;
}
int query(char c[])
{
    int p=0;
    for(int i=0;c[i];++i)
    {
        int u=c[i]-'a';
        if(!a[p][u]) return 0;
        p=a[p][u];
    }
    return b[p];
}
int main()
{
    cin>>n;
    while(n--)
    {
        char t;
        cin>>t;
        if(t=='I'){
            cin>>c;
            insert(c);
        }else{
            cin>>c;
            printf("%d\n",query(c));
        }
    }
    return 0;
}

第四道真题（扫地机器人）

题目描述

小明公司的办公区有一条长长的走廊，由 NN 个方格区域组成，如下图所示。

走廊内部署了 KK 台扫地机器人，其中第 ii 台在第 A_iAi​ 个方格区域中。已知扫地机器人每分钟可以移动到左右相邻的方格中，并将该区域清扫干净。

请你编写一个程序，计算每台机器人的清扫路线，使得

1. 它们最终都返回出发方格，

2. 每个方格区域都至少被清扫一遍，

3. 从机器人开始行动到最后一台机器人归位花费的时间最少。

注意多台机器人可以同时清扫同一方块区域，它们不会互相影响。

输出最少花费的时间。 在上图所示的例子中，最少花费时间是 6。第一台路线：2-1-2-3-4-3-2，清 扫了 1、2、3、4 号区域。第二台路线 5-6-7-6-5，清扫了 5、6、7。第三台路线 10-9-8-9-10，清扫了 8、9 和 10。

 

 输入样例:

10 3
5
2
10

输出样例：

6

• 最大运行时间：1s
• 最大运行内存: 256M

复习二分（题解来自蓝桥杯）

/*
解题思路：
本题为一道比较明显的二分题目。

题目要求最少花费时间。由于每个机器人的工作时间可能不同，那么这些机器人各自的花费时间中的最大值（设为 t ）的就是本题要求的答案,
需要做的是使得 t 最小。将最大花费时间（t）最小化，显然需要使用二分求解。

假设某个机器人需要清扫 a,b,c,d 四个格子，因为这个机器人清扫完还需要回到最初始的位置，所以无论这个机器人初始位置在什么地方，
其清扫路径的本质都是重复两次 a 到 b，b 到 c，c 到 d 的过程，花费时间为 6，由此，假设某个机器人清扫的格子范围为 l, 
那么这个机器人花费的时间为 (l-1)\times*2。所以只需要对机器人清扫的范围（l）进行二分即可，最后的答案为 t=(l-1)\times*2。

显然当每个机器人清扫的范围大小相同时，花费时间最小。
可以对清扫范围进行二分，然后验证其答案的正确性即可，判断条件是清扫范围可以使得每个格子都能够扫到

可以明显的知道，最左边的格子由左边第一台机器人清扫，花费时间是最少的，在此可以采用贪心的思想，
让每台机器人都要优先清扫其左边还未扫的到格子，然后再往右扫，在二分得到的范围下往右扫得越多越好，
这样可以减少右边下一个机器人需要往左扫的范围，增加其往右扫的范围，以此类推，可减少清扫时间。

综上，本题采用二分加贪心的思想解答。 
*/
#include<bits/stdc++.h>
using namespace std;

int robot[1000005];//机器人位置
int n, k;

bool check(int len)
{
    int sweep = 0;//sweep代表清扫到了哪个位置
    for(int i = 1; i <= k; i++)
    {
        if(robot[i] - len <= sweep)//如果当前机器人只扫左侧，能够覆盖左侧未清扫的位置，则可进行当前机器人的清扫
        {
            if(robot[i] <= sweep)//如果当前机器人已经处于清扫过的位置，则当前机器人只扫右侧区域
                sweep = robot[i] + len - 1;
            else//否则从上一个清扫到的位置继续
                sweep += len;
        }
        else//当前机器人只扫左侧，不能覆盖左侧未清扫的位置，当前方案不可行，返回
            return 0;
        //cout<<sweep<<endl;
    }
    return sweep>=n; //表示当前方案可行
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= k; i++)
    {
        cin >> robot[i];
    }
    sort(robot + 1, robot + k + 1);//首先对机器人的位置进行排序
    int L=0, R=n, M, ans;
    while(L <= R)//二分清扫范围
    {
        M = (L + R) / 2;
        if(check(M))//如果当前方案可行，则缩小清扫范围，试图寻找更小的方案
        {
            R = M - 1;
            ans = M;
        }
        else//如果方案不可行，则扩大清扫范围，寻找可行方案
            L = M + 1;
    }
    cout << (ans - 1) * 2 << endl;//计算并输出答案
    return 0;
}