密码锁

密码锁

混氏新子 蒟蒻
  2023-04-15 18:29:18 2023-04-15 18:29:18 创建   2023-09-24 19:14:02 2023-09-24 19:14:02 更新    3.3k 字  15 分钟  

前情提要

这道题我看了很多题解，当的时候一直也写不会。后来自己摸索出来一个方法，代码量也比较小，但是貌似常熟比较大，能卡过，而且有些地方可以再优化一下，就留给读者了。

题目描述

就是每一列都有几种置换，求这些置换中每一行最大最小值差的最大值的最小值。

思路

当时在考场上我是这样想的()，每一个拨圈可以看成是一个向量，可以转下，所以每一个圈圈对应个维向量，所以把这几个圈圈放到一起，找一个维正方体（超立方体）然后覆盖所有列的向量。但是当时到这里我不知道怎么做了，就开始暴力去找正方体，然后就没过多少分（悲。

现在看感觉思路已经快接近正解了，现在来讲一下标准思路。

这还要说吗，C++刚入门都能做。

这个是普及组难度，用贪心解决。每一列最小值的结果和最大值的结果的最大值。为什么这样是对的呢？我们这样想。先按照这样排好序（假设第一行是最小，第二行最大），如果任意一列进行上下颠倒，我们会发现如果交换的不是最大最小值的列第一行的最小值不会增加，最大值也不可能减少。如果是的话也是显然结果更大，所以这样是对的。

相对好写一些。我们可以想到用二分查找。我们先固定所有的数中最小值在第一排（毕竟是相对的），然后依次枚举最大值在哪一排的情况（也就两种）。每一列有三种变换方式，每一种变换方式只要满足且(是最大值在的那一行)就可以保证最大值和最小值那两行肯定是满足条件的。然后剩下的一个我们把它的数值加到一个 vector 中并记录下它的颜色（也就是第几个圈圈）。

记录完后我们要怎么办呢？我们现在要找一个长度小于的区间包含所有的颜色，那么就很简单了，先按照大小排序，然后使用双指针，并且开一个数组记录当前每种颜色出现的次数就行了。

这个时候有人问，如果最大值最小值都在一个圈圈里面呢？这样其实是没有影响的，因为遍历最大值在哪一行必定会遍历到最大值所在的哪一行（好绕口啊），而且在其它行时也只会使要求更严，不会出现错误的情况，也不会漏掉最小的情况。

至于如果有人说最大值和最小值在同一行……我懒得理你。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int vis[50010];
bool check3(int mid) {
	vector<pair<int, int> >v; //记录第三行数组
	for (int i = 1; i < 3; ++i) { //枚举最大值所在行
		v.clear();
		for (int j = 0; j < n; ++j) {
			for (int l = 0; l < 3; ++l) {
				if (a[j].v[l] - minn <= mid && maxn - a[j].v[(l + i) % 3] <= mid) {
					v.emplace_back(make_pair(a[j].v[(3 - i + l) % 3], j));
				}
			}
		}
		sort(v.begin(), v.end());
		memset(vis, 0, sizeof(vis));
		int tot = 0;
		for (int l = 0, r = 0; r < v.size();) {
			if (!vis[v[r].second]) ++tot;
			vis[v[r++].second]++;
			while (l < r && vis[v[l].second] > 1) --vis[v[l++].second];
			if (tot == n && v[r - 1].first - v[l].first <= mid) return true;
		}
	}
	return false;
}

二分：

1
2
3
4
5
6
7
8
9
10
11
12
13
case 3: {
	int l = 0, r = 30000, mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (check3(mid)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	printf("%d\n", l);
	break;
}

折腾了我最久的一种情况，在考场上写出来需要很强的代码能力。经过我对众多题解的理解与融合，我最终写出了一个较为好理解的代码（也许要短一点，总共代码只有5.37KB，✌我好牛逼我是蒟蒻）。

还是照搬时的思路，这时候你发现除掉最小值和最大值两行还剩两行，现在就变成两维了！你现在就是要找一个正方形去覆盖，直接硬刚时绝对不行的！

那我们怎么办呢？我们还是先把所有的坐标都放到数组里，如果放在一个里面的话太杂乱了，我们把时的方法精简一下，先定义一个 vector <pair<int, int > > cc[30010] 和 set <int> ls 。这两个数组是干什么用的呢？ cc[i] 表示横坐标为 i 的所有二维点对，里面存颜色和纵坐标，ls 里面存着所有的横坐标（就是点对的第一个数）（其实你也可以不用 set ，用一个数组和记录数组大小的数最后排一次序，去重也可以），然后我们还是按照时的思路先对横坐标进行双指针，然后我们考虑现在的纵坐标。每次加入删除纵坐标。纵坐标肯定不可以再用双指针了，这样会超时，那我们就请出线段树来帮忙。

每一个纵坐标，影响的区间可以看作是，在这个区间内这个都是可行的。至于为什么右端点不加，你画一下图就知道了。比如，如果右端点为的话这两个就是有交集的，但是实际上应该不能有交集，所以就这样了。然后我们在线段树里面对这段区间加然后看有没有一个位置是就行了。

就行了？ 不然你以为为什么这道题这么难做。我们还要考虑两个同色点有交集的情况。这里我们使用 multiset <int> orz[30010] 。为什么要用 multiset 允许重复呢？因为有可能同种颜色有两段是一样的。那么 orz[i] 就表示颜色为 i 的所有加进去的区间的右端点。那么我们每次新加入点找到前趋和后继对其容斥一下就行了（因为所有区间都是等长的，所以前趋和后继就行了），删除同理。但是请记住，加入是先容斥再加入；删除是先从orz中删除再容斥线段树中减去的区间。另外提醒，如果直接使用 orz[i].erase(x) 删去的是所有值等于 x 的节点，只删去一个应使用 orz[i].erase(orz[i].find(x)) 。

另外请注意，线段树清空不能全部清，可能会超时。

线段树节点存储左右子树值得最大值。

代码如下：

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
vector <pair<int, int > > cc[30010]; //见上文
multiset <int> orz[30010];
set <int> ls;
inline int xy(int x, int y) { //找到前趋应为<=的第一项
  if (orz[x].empty()) return 0;
  auto tmp = orz[x].upper_bound(y); // 大于的前一项就是<=
  if(tmp == orz[x].begin()) return 0; //注意处理特殊情况
  --tmp;
  return *tmp + 1;
}
inline int dx(int x, int y, int mid) { //后继，>=的第一项
  if (orz[x].empty()) return 30000;
  auto tmp = orz[x].lower_bound(y);
  if (tmp == orz[x].end()) return 30000; //特殊处理
  return *tmp - mid - 1;
}
bool check4(int mid) {
	pair<int, int> tmp;
	for (int i = 1; i < 4; ++i) { //最大值所在行
		bool ppp = 0;
		ls.clear();
		for (int j = 0; j < n; ++j) { //枚举每一个圈圈
      orz[j].clear(); //初始化
      bool pp = 0;
			for (int l = 0; l < 4; ++l) { //移动多少下
				if (a[j].v[l] - minn <= mid && maxn - a[j].v[(l + i) % 4] <= mid) {
          bool p = 0;
          for (int m = 1; m < 4; ++m) { //找那个二位数对
            if (m == i) continue;
            if(!p) tmp.first = a[j].v[(m + l) % 4], p = 1;
            else tmp.second = a[j].v[(m + l) % 4];
          }
          pp = 1;
          //如果不存在就初始化
          if (ls.find(tmp.first) == ls.end()) cc[tmp.first].clear(), ls.insert(tmp.first);
	        //加入
          cc[tmp.first].emplace_back(make_pair(j, tmp.second));
				}
			}
			if (!pp) {
        ppp = 1;
        break;
			}
		}
		//小优化，如果有个颜色没有加进去的话直接下一种情况
		if (ppp) continue; //以上代码就是获取这种i值的时候的二维数对
		//写得比较复杂，可以精简一下，也可以自己写
		t[1].cl(); //清空线段树
		//双指针横坐标
		for (auto l = ls.begin(), r = ls.begin(); r != ls.end(); ++r) {
      for (auto &j : cc[*r]) { //枚举新加进去一行里所有项
        int tl = max(j.second - mid, xy(j.first, j.second));
        int tr = min(j.second, dx(j.first, j.second, mid)); //容斥要加的区间
        tl = max(tl, minn);
        if (tl <= tr) {
          add(1, 1, 30000, tl, tr, 1); //线段树加1
        }
        orz[j.first].insert(j.second); //orz里面添加
      }
      while (l != r && *r - *l > mid) { //删除已经落后的行
        for (auto &j : cc[*l]) { //同加入
          orz[j.first].erase(orz[j.first].find(j.second)); //记得先删
          int tl = max(j.second - mid, xy(j.first, j.second)); //同加
          int tr = min(j.second, dx(j.first, j.second, mid));
          tl = max(tl, minn);
          if (tl <= tr) {
            add(1, 1, 30000, tl, tr, -1); //这里是减去
          }
        }
        ++l; //记得将最下方一行向上移
      }
      if (t[1].v == n) return true; //如果有就返回真
		}
	}
	return false;
}

代码

真的很少！

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#include<bits/stdc++.h>
using namespace std;
int T, k, n, ans;
int minn, maxn;
struct vec {
	int v[4];
}a[50010];
int vis[50010];
struct tree { //线段树代码
  int v, laz, c; //值，懒标记，是否清空
  int ls, rs;
  tree() {
    v = laz = ls = rs = 0;
  }
  void cl() {
    v = laz = 0;
    c = 1;
  }
}t[240010];
int cnt = 1;
inline void update(int nod) { //上传
  t[nod].v = max(t[t[nod].ls].v, t[t[nod].rs].v);
}
inline void pushdown(int nod) {
  if (t[nod].c) { //向下清空
    t[t[nod].ls].cl();
    t[t[nod].rs].cl();
    t[nod].c = 0;
  }
  if (t[nod].laz) {
    t[t[nod].ls].v += t[nod].laz;
    t[t[nod].ls].laz += t[nod].laz;
    t[t[nod].rs].v += t[nod].laz;
    t[t[nod].rs].laz += t[nod].laz;
    t[nod].laz = 0;
  }
}
void build(int nod, int l, int r) { //建树
  if (l == r) return;
  int mid = (l + r) >> 1;
  t[nod].ls = ++cnt;
  t[nod].rs = ++cnt;
  build(t[nod].ls, l, mid);
  build(t[nod].rs, mid + 1, r);
}
void add(int nod, int l, int r, int pl, int pr, int x) {
  if (l >= pl && r <= pr) {
    t[nod].v += x; //两个子树都加同样的数相对大小肯定不变
    t[nod].laz += x;
    return;
  }
  pushdown(nod);
  int mid = (l + r) >> 1;
  if (mid >= pl) add(t[nod].ls, l, mid, pl, pr, x);
  if (pr > mid) add(t[nod].rs, mid + 1, r, pl, pr, x);
  update(nod);
}
bool check3(int mid) { //注释在上面
	vector<pair<int, int> >v;
	for (int i = 1; i < 3; ++i) {
		v.clear();
		for (int j = 0; j < n; ++j) {
			for (int l = 0; l < 3; ++l) {
				if (a[j].v[l] - minn <= mid && maxn - a[j].v[(l + i) % 3] <= mid) {
					v.emplace_back(make_pair(a[j].v[(3 - i + l) % 3], j));
				}
			}
		}
		sort(v.begin(), v.end());
		memset(vis, 0, sizeof(vis));
		int tot = 0;
		for (int l = 0, r = 0; r < v.size();) {
			if (!vis[v[r].second]) ++tot;
			vis[v[r++].second]++;
			while (l < r && vis[v[l].second] > 1) --vis[v[l++].second];
			if (tot == n && v[r - 1].first - v[l].first <= mid) return true;
		}
	}
	return false;
}
vector <pair<int, int > > cc[30010];
multiset <int> orz[30010];
set <int> ls;
inline int xy(int x, int y) {
  if (orz[x].empty()) return 0;
  auto tmp = orz[x].upper_bound(y);
  if(tmp == orz[x].begin()) return 0;
  --tmp;
  return *tmp + 1;
}
inline int dx(int x, int y, int mid) {
  if (orz[x].empty()) return 30000;
  auto tmp = orz[x].lower_bound(y);
  if (tmp == orz[x].end()) return 30000;
  return *tmp - mid - 1;
}
bool check4(int mid) { //注释请看上面
	pair<int, int> tmp;
	for (int i = 1; i < 4; ++i) {
		bool ppp = 0;
		ls.clear();
		for (int j = 0; j < n; ++j) {
      orz[j].clear();
      bool pp = 0;
			for (int l = 0; l < 4; ++l) {
				if (a[j].v[l] - minn <= mid && maxn - a[j].v[(l + i) % 4] <= mid) {
          bool p = 0;
          for (int m = 1; m < 4; ++m) {
            if (m == i) continue;
            if(!p) tmp.first = a[j].v[(m + l) % 4], p = 1;
            else tmp.second = a[j].v[(m + l) % 4];
          }
          pp = 1;
          if (ls.find(tmp.first) == ls.end()) cc[tmp.first].clear(), ls.insert(tmp.first);
          cc[tmp.first].emplace_back(make_pair(j, tmp.second));
				}
			}
			if (!pp) {
        ppp = 1;
        break;
			}
		}
		if (ppp) continue;
		t[1].cl();
		for (auto l = ls.begin(), r = ls.begin(); r != ls.end(); ++r) {
      for (auto &j : cc[*r]) {
        int tl = max(j.second - mid, xy(j.first, j.second));
        int tr = min(j.second, dx(j.first, j.second, mid));
        tl = max(tl, minn);
        if (tl <= tr) {
          add(1, 1, 30000, tl, tr, 1);
        }
        orz[j.first].insert(j.second);
      }
      while (l != r && *r - *l > mid) {
        for (auto &j : cc[*l]) {
          orz[j.first].erase(orz[j.first].find(j.second));
          int tl = max(j.second - mid, xy(j.first, j.second));
          int tr = min(j.second, dx(j.first, j.second, mid));
          tl = max(tl, minn);
          if (tl <= tr) {
            add(1, 1, 30000, tl, tr, -1);
          }
        }
        ++l;
      }
      if (t[1].v == n) return true;
		}
	}
	return false;
}
int main() {
	scanf("%d%d", &T, &k);
	if (k == 4) build(1, 1, 30000);
	while (T--) {
		ans = 30000;
		minn = 30000;
		maxn = 0;
		scanf("%d", &n);
		for (int i = 0; i < k; ++i) {
			for (int j = 0; j < n; ++j) {
				scanf("%d", &a[j].v[i]);
				maxn = max(maxn, a[j].v[i]);
				minn = min(minn, a[j].v[i]);
			}
		}
		switch(k){
		case 1: {
			printf("%d\n", maxn - minn);
			break;
		}
		case 2: { //这个2的写得很拉，见谅
			int mi = 30000, ma = 0;
			for (int i = 0; i < n; ++i) {
				ma = max(ma, min(a[i].v[0], a[i].v[1]));
				mi = min(mi, min(a[i].v[0], a[i].v[1]));
			}
			ans = ma - mi;
			mi = 30000, ma = 0;
			for (int i = 0; i < n; ++i) {
				ma = max(ma, max(a[i].v[0], a[i].v[1]));
				mi = min(mi, max(a[i].v[0], a[i].v[1]));
			}
			ans = max(ans, ma - mi);
			printf("%d\n", ans);
			break;
		}
		case 3: {
			int l = 0, r = 30000, mid;
			while (l < r) {
				mid = (l + r) >> 1;
				if (check3(mid)) {
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			printf("%d\n", l);
			break;
		}
		case 4: { //这个2分和3没有啥区别
			int l = 0, r = 30000, mid;
			while (l < r) {
				mid = (l + r) >> 1;
				if (check4(mid)) {
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			printf("%d\n", l);
			break;
		}
		}
	}
	return 0;
}

后记

敢于挑战，敢于突破！如果你自己写出来这道题的代码你一定会大有收获的。

  • 标题: 密码锁
  • 作者: 混氏新子
  • 创建于 : 2023-04-15 18:29:18
  • 更新于 : 2023-09-24 19:14:02
  • 链接: https://blog.huasushis.cn/2023/密码锁/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
6.29 测试 6.29 测试 7.3 测试 7.3 测试 2023年10月14日模拟赛 2023年10月14日模拟赛
推荐阅读
6.29 测试 6.29 测试 7.3 测试 7.3 测试
评论
此页目录
密码锁
  1. 前情提要
  2. 题目描述
  3. 思路
  4. 代码
  5. 后记