[BZOJ3535][Usaco2014 Open]Fair Photography

试题描述

FJ's N cows (1 <= N <= 100,000) are standing at various positions along a long one-dimensional fence. The ith cow is standing at position x_i (an integer in the range 0...1,000,000,000) and has breed b_i (an integer in the range 1..8). No two cows occupy the same position. FJ wants to take a photo of a contiguous interval of cows for the county fair, but we wants all of his breeds to be fairly represented in the photo. Therefore, he wants to ensure that, for whatever breeds are present in the photo, there is an equal number of each breed (for example, a photo with 27 each of breeds 1 and 3 is ok, a photo with 27 of breeds 1, 3, and 4 is ok, but 9 of breed 1 and 10 of breed 3 is not ok). Farmer John also wants at least K (K >= 2) breeds (out of the 8 total) to be represented in the photo. Help FJ take his fair photo by finding the maximum size of a photo that satisfies FJ's constraints. The size of a photo is the difference between the maximum and minimum positions of the cows in the photo. If there are no photos satisfying FJ's constraints, output -1 instead.

X的非负轴上有n头奶牛,每个奶牛有一个坐标xi和品种bi.

没有两头奶牛在同一个位置上.

选择一个区间[L,R],使得所有品种的奶牛数量, 在[L,R]中,要么为0,要么相等.且出现的品种数(注意是品种数而不是每个品种的个数丫> <.)至少为K.

区间长度定义为[L,R]中最右和最左的奶牛的差的绝对值.

求最长满足上述条件的区间长度.

输入

* Line 1: N and K separated by a space
* Lines 2..N+1: Each line contains a description of a cow as two integers separated by a space; x(i) and its breed id.

输出

* Line 1: A single integer indicating the maximum size of a fair photo. If no such photo exists, output -1.

输入示例

输出示例

数据规模及约定

见“试题描述”

题解

其实这题唯一用到的数据结构就是哈希表（数组啥的就暂且不算数据结构了）。

我们发现颜色种类很少，那么突破口一定在这里。

考虑一种更简单的情况：颜色只有两种的时候怎么做。不难联想到类似“括号序列”的做法，左括号 +1，右括号 -1；在这里就是颜色 1 的位置上 +1，颜色 2 的位置上 -1。

好了，有了上面做法的启发，我们可以拓展到颜色不多的做法了。深度理解一下一堆 +1、-1 的意义是什么：每个位置上的数其实就是颜色 1 比颜色 2 多了多少个。

那么最多 8 种颜色，我们 2⁸ 枚举一下选且只选的颜色集合 S。那么对于不在集合 S 的颜色的位置就把它删掉，这样会把整个序列分成若干个连续的区间，区间总长度不超过 O(n)。对于每一段区间我们这样处理：在每个位置上记录“考虑以这个位置为结尾的前缀中集合 S 中所有颜色的个数比集合 S 中第一个颜色的个数多多少”，然后如果有两个位置上的这样的信息完全相同则表明所有出现的颜色数目相等。于是我们每个位置上的信息哈希一下，并存储信息最早出现的位置，然后随便统计一下答案就好了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 100010
#define oo 2147483647

struct Cow {
	int x, b;
	Cow() {}
	Cow(int _, int __): x(_), b(__) {}
	bool operator < (const Cow& t) const { return x < t.x; }
} cs[maxn];
int n, K;

#define MOD 2097151
bool Equal(int a[8], int b[8]) {
	for(int i = 0; i < 8; i++) if(a[i] != b[i]) return 0;
	return 1;
}
int CNT;
struct Hash {
	int ToT, head[MOD+1], nxt[maxn], more[maxn][8], val[maxn];
	
	void init() {
		for(int t = 1; t <= ToT; t++) {
			int u = 0;
			for(int i = 0; i < 8; i++) CNT++, u = u ^ more[t][i] & MOD;
			head[u] = 0;
		}
		ToT = 0;
		return ;
	}
	
	int Find(int tmp[8]) {
		int u = 0;
		for(int i = 0; i < 8; i++) u = u ^ tmp[i] & MOD;
		for(int e = head[u]; e; e = nxt[e]) if(Equal(more[e], tmp)) return val[e];
		return oo;
	}
	void Insert(int tmp[8], int v) {
		int u = 0;
		for(int i = 0; i < 8; i++) u = u ^ tmp[i] & MOD;
		val[++ToT] = v; for(int i = 0; i < 8; i++) more[ToT][i] = tmp[i]; nxt[ToT] = head[u]; head[u] = ToT;
		return ;
	}
} hh;

int lstb[maxn][8], more[maxn][8], ans = -1;
void work(int S) {
	int lCNT = CNT;
	memset(more, 0, sizeof(more));
	int cnt[8], mb;
	for(int i = 0; i < 8; i++) if(S >> i & 1){ mb = i; break; }
	bool has = 0;
	for(int i = 1; i <= n;) {
		while(i <= n && !(S >> cs[i].b & 1)) i++;
		if(i > n) break;
		
		memset(cnt, 0, sizeof(cnt));
		hh.init(); hh.Insert(cnt, i - 1);
		int l = i, r = i;
		while(r <= n && (S >> cs[r].b & 1)) {
			cnt[cs[r].b]++;
			for(int j = 0; j < 8; j++) {
				if(S >> j & 1) more[r][j] = cnt[j] - cnt[mb];
				CNT++;
			}
			if(hh.Find(more[r]) == oo) hh.Insert(more[r], r);
			r++;
		}
		r--;
		for(int p = l; p <= r; p++) {
			int pre = hh.Find(more[p]) + 1; bool ok = 1;
			for(int j = 0; j < 8; j++) {
				CNT++;
				if((S >> j & 1) && lstb[p][j] < pre){ ok = 0; break; }
			}
			if(ok) has = 1, ans = max(ans, cs[p].x - cs[pre].x);
		}
		i = r + 1;
	}
//	printf("work(%d) %d %d
", S, CNT, CNT - lCNT);
	return ;
}

int main() {
	n = read(); K = read();
	for(int i = 1; i <= n; i++) {
		int x = read(), b = read() - 1;
		cs[i] = Cow(x, b);
	}
	
	sort(cs + 1, cs + n + 1);
	int lst[8]; memset(lst, 0, sizeof(lst));
	for(int i = 1; i <= n; i++) {
		lst[cs[i].b] = i;
		for(int j = 0; j < 8; j++) lstb[i][j] = lst[j];
	}
	int all = (1 << 8) - 1;
	for(int S = 0; S <= all; S++) {
		int cnt = 0;
		for(int i = 0; i < 8; i++) cnt += S >> i & 1;
		if(cnt >= K) work(S);
	}
	
	printf("%d
", ans);
	
	return 0;
}