7.28集训

Posted on Edited on In

#上午

教练让补补坑 先改了改以前的题，然后开始透彻几道题

1.滑稽窗口

以前总是感觉迷迷糊糊不太透彻，今天tmd终于搞明白了

我们维护一个希望维护一个长度为m的队列，对于求最小值的时候，我们维护单增队列，所以队尾一定要保证是最大的

所以对于当前的\(a[i]\)，我们必须保证\(a[i] > a[q[t]]\)才能使其入队，否则就一直让队尾缩短

对于求最大值的时候，我们希望维护一个递减队列，保证队尾最小

所以同理，对于当前的\(a[i]\)，我们保证\(a[i] > a[q[t]]\)才能使其入队，否则一直使得t自减

（最近超喜欢写han yu pin yin 的函数） 

1
return ~~(0^_^0);
其中

1
define _ 0

下面给出漂亮的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define _ 0
using namespace std;

const int N = 1e6+66;

int n, m;
int a[N], q[N];

inline void shuruyijichushihua () {
   cin >> n >> m;
   for (int i = 1; i <= n; ++ i) cin >> a[i];
}

inline void caozuoyifan () {
   int h = 1, t = 0;
   for (int i = 1; i <= n; ++ i) {
      while (h <= t && q[h] + m <= i) ++ h;
      while (h <= t && a[i] < a[q[t]]) -- t;
      q[++ t] = i;
      if (i >= m) cout << a[q[h]] << ' ';
   }
   cout << '\n';
   memset(q, 0, sizeof q);
   for (int i = 1; i <= n; ++ i) {
      while (h <= t && q[h] + m <= i) ++ h;
      while (h <= t && a[i] > a[q[t]]) -- t;
      q[++ t] = i;
      if (i >= m) cout << a[q[h]] << ' ';
   }
}

int main () {
   shuruyijichushihua();
   caozuoyifan();
   return ~~(0^_^0);
}

下午

讲了拓扑排序，寻找入度为零的点，从那些点开始搜索，一般用队列实现 给出常见代码：
Code 
for (int i = 1; i <= n; ++ i) if (!rudu[i]) q.push(i);
while(q.size()) {
   int now = q.front(); q.pop();
   for (int i = head[now]; i; i = e[i].nxt) {
      int y = e[i].to;
      -- rudu[y];
      if (!rudu[y]) q.push(y);
   }
}

典型的tuopupaixu例题：

我去你家

题目：原文叽哩哇啦的看不懂

翻译：balabala的一堆废话，我默然...

说人话：给你个有向图，判断是否存在任意两点\(u,v\)，存在\(u -> v\) \(or\) \(v->u\)

大体思路：扫一遍图，缩点，对于缩点完毕的强连通分量，我们考虑将其tuo pu pai xu，无论哪一阶段只要入度大于1就是false

变态覆盖矩形

开篇得图，给你一个很大大大大大大的字母矩阵，说白了就是几个矩形套在一起，让你求最底下到最底层的顺序（保证字典序）

我们首先得用结构体，其次我们对于每一个矩形，扫描它的上下左右四条边，有不同的，就记录下来，最后向覆盖他的矩形连边

关于输出的时候，我们考虑用dfs版本的tuopupaixu，只要搜到解，立刻输出停止，这样就是字典序最小的了

变态排序

不会，----->题解

下面是ufs的典型例题

###小仙女

不会：

很容易看出这是一道并查集的题，可是与并查集不同的是，这道题不仅要建立联系还要删除联系，如果这样想是很复杂的，但是如果将所有请求保存起来，然后反向请求，离线来做的话，就很简单了，如果遇到query就查询与该星球有联系且power值最大的，如果遇到destory就把两个星球建立联系，最后将答案反向输出。

如果把power值大的作为父亲，则查询起来更加方便了

------>

把destory边，看成合并。初始化的时候，对给定的边进行并集操作（除去将会被destory的边），然后把问题逆向依次考虑，遇到destory的时候就把边加入集合。最后把答案输出即可。

注意：相邻的case之间要输出空行，路径压缩的时候，相同的power值时，编号小的作为祖先。

下面给出别人代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
const int N = 1e4 + 10, M = 2e4 + 10, Q = 5e4 + 10;
int fa[N],power[N],ans[Q];
map<pair<int, int>, int> mp;	//离散存储
int n, m, q;
struct Node {
   int flag;	//0表示query u,1表示destory u-v
   int u, v;
   void setNode(int flag, int u, int v) { this->flag = flag, this->u = u, this->v = v; }
}ques[Q];

struct Node2 {
   int flag;
   int u, v;
}edg[M];	//保存两星球中的通道，flag表示存在否

int find(int x)
{
   if (fa[x] == -1) return x;
   return fa[x] = find(fa[x]);
}
void unite(int u, int v)
{
   int fu = find(u);
   int fv = find(v);
   if (fu == fv)return;
   if (power[fu] > power[fv] || power[fu] == power[fv] && fu<fv)
      fa[fv] = fu;
   else fa[fu] = fv;
}
void init()
{
   memset(fa, -1, sizeof(fa));
   for (int i = 0; i < m; i++)
      if (edg[i].flag) unite(edg[i].u, edg[i].v);
}
int main()
{
   int flag = 0;	//控制连续的测试数据间隔空行
   while (~scanf("%d", &n))
   {
      mp.clear();
      for (int i = 0; i < n; i++)scanf("%d", &power[i]);
	 scanf("%d", &m);
      for (int i = 0; i < m; i++)
      {
	 int u, v;
	 scanf("%d%d", &u, &v);
	 if (u > v)swap(u, v);
	 mp[make_pair(u, v)] = i;
	 edg[i].flag = 1;	//存在边
	 edg[i].u = u, edg[i].v = v;
      }
      int q;
      scanf("%d", &q);
      for (int i = 0; i < q; i++)
      {
	 char str[10];
	 scanf("%s", str);
	 if (str[0] == 'q') {
	    int s;
	    scanf("%d", &s);
	    ques[i].setNode(0, s, -1);
	 } else {
	    int u, v;
	    scanf("%d%d", &u, &v);
            if (u > v)swap(u, v);
            ques[i].setNode(1, u, v);
            int tmp = mp[make_pair(ques[i].u, ques[i].v)];
            edg[tmp].flag = 0;	//逆过来看，该边不存在
	 }
      }
      init();	//初始化边集
      for (int i = q-1; i >= 0; i--)
      {
         if (ques[i].flag)	//destory
	    unite(ques[i].u, ques[i].v);
         else {
	   int tmp = find(ques[i].u);
	   if (power[tmp] > power[ques[i].u]) ans[i] = tmp;
           else ans[i] = -1;
	 }
      }
      if (flag) printf("\n");
      else flag = 1;
      for(int i=0;i<q;i++)
         if(ques[i].flag==0)printf("%d\n", ans[i]);
   }
   return 0;
}

晚上

主要讲的单调队列，栈 其实这也仅仅是一种思想，主要是多做题，这种题就是模拟，没多少技术含量，都是在O(n)的时间内，几乎线性的扫上一遍，然后得出答案

还有左偏树

滑稽窗口

再次不多赘述
Code 
h = 1, t = 0;
for (int i = 1; i <= n; ++ i) {
   while (h <= t && h+k <= i) ++ h;
   while (h <= t && a[i] < a[q[t]]) -- t;
   q[++ t] = i;
   if (i >= k) cout << a[q[h]] << ' ';
}
puts("");
h = 1, t = 0;
memset (q, 0, sizeof q);
for (int i = 1; i <= n; ++ i) {
   while (h <= t && h+k <= i) ++ h;
   while (h <= t && a[i] > a[q[t]]) -- t;
   q[++ t] = i;
   if (i >= k) cout << a[q[h]] << ' ';
}

发射站

维护一个单调栈，每次弹出的时候更新答案，并且正反跑一次，可分别求出两边

正方形

二维的滑动窗口

首先我们考虑行，我们对每一行都维护一个hdck，并把维护的最大值或者是最小值记在那个窗口的最右边（开个新数组）

这样每一行就一定会有k个数（k为hdck的长度）

同理我们再对列维护滑动窗口，并且

中位数

考虑用堆来维护，先排序，然后对于前一半的数考虑维护一个大根堆，对后一半的数维护一个小根堆

如果n为偶数，那么答案就为大根堆的堆顶，如果n为奇数，我们还是强制让\(size_{bigdui}\) \(\leq\) \(size_{smalldui}\) \(\leq\) \(size_{bigdui} + 1\)

这样答案还是大根堆的堆顶

每次插入的时候，两个堆来回倒腾，反正你多一个，我就少一个

单调队列优化

dp式子不难看出：..........

不写了，以后补