高效算法设计(七)

本节内容
对一些序列的问题进行归纳总结

中途相遇法

这种方法有点类似数学中的夹逼准则

LA3232
LA3232

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
typedef vector<int>::iterator vii;
const int maxn = 5000 + 10;

vector<int> H[maxn], L[maxn];
int N[maxn];
int n;

void init() {
_for(i, 0, maxn) {
H[i].clear();
L[i].clear();
}
Set(N, 0);
}

bool find1(int p) {
_for(i, 0, H[p].size()) {
int q = H[p][i];

vii rit = upper_bound(L[p].begin(), L[p].end(), q);
if(rit == L[p].end()) continue;

int r = *rit;

vii sit = upper_bound(H[p].begin(), H[p].end(), r);
while (sit != H[p].end()) {
int s = *sit;

if(binary_search(L[q].begin(), L[q].end(), s)) return true;

sit++;
}
}
return false;
}

bool find2(int p) {
_for(i, 0, L[p].size()) {
int q = L[p][i];

vii rit = upper_bound(H[p].begin(), H[p].end(), q);
if(rit == H[p].end()) continue;

int r = *rit;

vii sit = upper_bound(L[p].begin(), L[p].end(), r);
while (sit != L[p].end()) {
int s = *sit;

if(binary_search(H[q].begin(), H[q].end(), s)) return true;

sit++;
}
}
return false;
}

bool solve() {
_for(i, 0, n) if(find1(i) || find2(i)) return true;
return false;
}

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

while (T--) {
init();
scanf("%d", &n);
_for(i, 0, n) scanf("%d", &N[i]);

_for(i, 0, n) _for(j, i + 1, n) {
if(N[j] > N[i]) H[i].push_back(j);
else if(N[j] < N[i]) L[i].push_back(j);
}

if(solve()) printf("YES\n");
else printf("NO\n");
}
}

连续的几个数, 连续的子区间最小

这一系列的问题, 可以用滑动窗口解决
UVA11536

UVA11536

滑动窗口中可能会出现: 滑动窗口的长度不固定的情况,这时候注意
1/ win在[L, …]中向右滑动
win不一定会真正删除A[L]处的元素

2/ 只有A[L]中的数在win中出现的次数为1的时候
窗口从L中滑走,win才算是彻底删除了A[L]

3/ 我们需要用map记录每个值在窗口中出现的次数

4/ 滑动窗口和区间扩张相结合的模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(int L = 0, R = 0; L < N; L++) {
if(R >= N) break;
while (win中没有选够点) {
ins(R, win);
R++;
if(R >= N) break;
}

[L, R]构成了新的滑动窗口
滑动窗口是我们需要的值


if(win选够点了)
滑动窗口能否优化呢?
滑动窗口最左边的A[L]元素有没有冗余?A[L]出现次数可能大于1
或者是, 滑动窗口并不包含A[L], A[L]我们不需要

ans = min(ans, R - L + 1);

slide L, del(L, win)
R = max(L, R);
}
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
const int maxn = 1000000 + 10;
int n, m, k;
int x[maxn];

void cal() {
_for(i, 0, n) {
if(i < 3) x[i] = i + 1;
else x[i] = (x[i - 3] + x[i - 2] + x[i - 1]) % m + 1;
}
}

bool valid(int x) {
return 1 <= x && x <= k;
}

void ins(int x, map<int, int>& win) {
if(valid(x)) win[x] = win[x] + 1;
}

void del(int x, map<int, int>& win) {
if(!win.count(x)) return;
win[x] = win[x] - 1;
if(win[x] < 1) win.erase(x);
}

int solve() {
map<int, int> win;
win.clear();

int ans = 0;

for(int L = 0, R = 0; L < n; L++) {
while (win.size() < k) {
ins(x[R], win);
R++;
if(R >= n) break;
}

if(R >= n) break;

if(win.size() == k) {
// enough points

while (win[x[L]] > 1 || !win.count(x[L])) {
del(x[L], win);
L++;
}

if(!ans) ans = R - L + 1;
else ans = min(ans, R - L + 1);
}

del(x[L], win);
}

return ans;
}

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

_rep(t, 1, T) {
scanf("%d%d%d", &n, &m, &k);

// then we init cal() x[] and solve()

cal();

printf("Case %d: ", t);

int ans = solve();
if(!ans) printf("sequence nai\n");
else printf("%d\n", ans - 1);
}
}

连续子序列权值问题

LA3517

LA3517

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
const int maxn = 100000 + 10;
int n;

llong L[maxn], R[maxn], sum[maxn], A[maxn];
stack<int> stk;
// stk used to store index

void init() {
Set(sum, 0);
Set(A, 0);
Set(L, 0);
Set(R, 0);
}

void popGreater(int i) {
while(!stk.empty() && A[stk.top()] >= A[i]) stk.pop();
}

void solve() {
while (!stk.empty()) stk.pop();

_rep(i, 1, n) {
popGreater(i);
L[i] = stk.empty() ? 0 : stk.top();
stk.push(i);
}

while (!stk.empty()) stk.pop();

_forDown(i, n, 1) {
popGreater(i);
R[i] = stk.empty() ? n + 1 : stk.top();
stk.push(i);
}

llong ans = -1, ansl = -1, ansr = -1;
_rep(i, 1, n) {
// if A[i] is min value
llong li = L[i], ri = R[i] - 1, tmp = (sum[ri] - sum[li]) * A[i];
li++;

bool update = false;
if(tmp < ans) continue;
if(tmp > ans) update = true;

if(tmp == ans) {
if(ansr - ansl > ri - li) update = true;
else if(ansr - ansl == ri - li) update = li < ansl;
}

ans = max(tmp, ans);
if(update) {
ansl = li;
ansr = ri;
}
}

printf("%lld\n%lld %lld\n", ans, ansl, ansr);
}


int main() {
freopen("input.txt", "r", stdin);

bool first = true;

while (scanf("%d", &n) == 1) {
init();

if(first) first = false;
else puts("");


bool all0 = true;
_rep(i, 1, n) {
scanf("%lld", &A[i]);
if(A[i]) all0 = false;
sum[i] = A[i] + sum[i - 1];
}


if(all0) {
printf("0\n1 1\n");
continue;
}

// then solve the problem
solve();
}
}

坐标离散化

LA2689
LA2689

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
const int maxn = 100 + 4;

class Point {
public:
int x, y;
bool operator< (const Point& rhs) const {
if(x != rhs.x) return x < rhs.x;
return y < rhs.y;
}
};

Point P[maxn];
int dy[maxn];
int ans, ansX, ansY;

void init() {
Set(dy, 0);
ans = ansX = ansY = 0;
}

int N, W, H;

void solve() {
int n = unique(dy, dy + N + 2) - dy;
_for(i, 0, n) _for(j, i + 1, n) {
int minY = dy[i], maxY = dy[j];
int hh = maxY - minY, last = 0, ww = 0;

_for(k, 0, N) {
Point& cur = P[k];
if(cur.y <= minY || cur.y >= maxY) continue;

ww = cur.x - last;
if(ans < min(ww, hh)) {
ans = min(ww, hh);
ansX = last, ansY = minY;
}
last = cur.x;
}

ww = W - last;
if(ans < min(ww, hh)) {
ans = min(ww, hh);
ansX = last, ansY = minY;
}
}
printf("%d %d %d\n", ansX, ansY, ans);
}

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

while (T--) {
init();
scanf("%d%d%d", &N, &W, &H);

_for(i, 0, N) {
scanf("%d%d", &P[i].x, &P[i].y);
dy[i] = P[i].y;
}
dy[N] = 0, dy[N + 1] = H;

// discrete
sort(dy, dy + N + 2);
sort(P, P + N);

solve();
if(T) printf("\n");
}
}

逆序对(找规律枚举)

LA4000
LA4000

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
const int maxn = 500 + 10;
int n;
int A[maxn];

void init() {
Set(A, 0);
}

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

while (T--) {
init();
scanf("%d", &n);
_for(i, 0, n) scanf("%d", &A[i]);

int cnt = 0;
_for(i, 0, n - 1) _for(j, i + 1, n) {
if(A[i] > A[j]) cnt++;
}

if(n % 2 && cnt % 2) cout << "impossible" << endl;
else cout << "possible" << endl;
}
}