「LibreOJ β Round

发表于 更新于 分类于

「LibreOJ β Round #2」DP 一般看规律

感觉题目不是很难，不过代码技巧学习了。

把所有数按颜色插入到\(\text{set}\)里面，每次合并的时候对于每个数只有前驱或者后缀会产生答案。

所以合并的时候更新下答案就可以了。

这个\(\text{map<int,set<int>>}\)学到了啊，相当于每个下标都对应了一个\(\text{set}\)，也就是开了多个\(\text{set}\)，并且是动态申请的。

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
#include <bits/stdc++.h>
using namespace std;

map<int, set<int> > m;
int n, q, ans = 2147483647;

void find(int s, int x) {
    auto it = m[s].lower-bound(x);
    if (it != m[s].end()) ans = min(ans, *it - x);
    if (it != m[s].begin()) ans = min(ans, x - *--it);
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1, x; i <= n; i++) {
    	scanf("%d", &x);
    	m[x].insert(i);
    }
    for (; q--; ) {
    	int x, y;
    	scanf("%d %d", &x, &y);
    	if (x == y) printf("%d\n", ans);
    	else {
            for (auto it = m[x].begin(); it != m[x].end(); ++it) {
            	find(y, *it);
            	m[y].insert(*it);
            }
            m[x].clear();
            printf("%d\n", ans);
    	}
    }
    return 0;
}