「BZOJ3535」[Usaco2014 Open] Fair Photography
Description
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.
Input
* 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.
Output
* Line 1: A single integer indicating the maximum size of a fair photo. If no such photo exists, output -1.
Sample Input
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3
INPUT DETAILS: Breed ids: 1 2 3 – 1 1 2 3 1 – … – 1 Locations: 1 2 3 4 5 6 7 8 9 10 … 99 100
Sample Output
OUTPUT DETAILS: The range from x = 2 to x = 8 has 2 each of breeds 1, 2, and 3. The range from x = 9 to x = 100 has 2 of breed 1, but this is invalid because K = 2 and so we must have at least 2 distinct breeds.
题解
「FJ集训2015」大水题
枚举左端点暴力拿了50分QAQ
lazycal：
首先考虑区间[I,j]合法的条件。假设所有种类都出现了，对于每头牛，我们记录前面所有种类出现次数，再记录出现次数与种类1出现次数之差。那么区间[I,j]合法当且仅当各个种类出现次数之差相等。
于是一种显然的做法是枚举出现的种类，然后只考虑枚举到的种类，将次数之差的信息放进hash表，枚举右端点，通过hash表得出左端点。复杂度为O(2^8*N)，无法通过所有数据。
改进的方法是：对于确定的右端点，随着左端点的移动，所包含的种类数只会改变8次，即只有8种状态。于是我们对8种状态求hash即可。右端点每左移一次，就把这个种类之前出现位置到当前位置之间的奶牛都删掉，然后再重新插入。假设hash复杂度为O(1)，则总复杂度为O(8*N)。
N^2暴力
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define p(x) p[(x+n)%n] using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K,ans; struct data{ int x,b; friend bool operator<(data a,data b){ return a.x<b.x; } }a[100005]; void cal(int t) { int num[15]={},mx=0,k=0,tot=0; for(int i=t;i<=n;i++) { num[a[i].b]++; if(num[a[i].b]==1)tot++; if(num[a[i].b]>mx) { mx=num[a[i].b],k=0; if(tot*mx+t-1>n)return; } if(num[a[i].b]==mx)k++; if(tot==k&&tot>=K) ans=max(ans,a[i].x-a[t].x); } } int main() { // freopen("fairphoto.in","r",stdin); // freopen("fairphoto.out","w",stdout); n=read();K=read(); for(int i=1;i<=n;i++) a[i].x=read(),a[i].b=read(); sort(a+1,a+n+1); for(int i=1;i<=n;i++)cal(i); if(!ans)puts("-1"); else printf("%d\n",ans); fclose(stdin); fclose(stdout); return 0; } |
2^8*N暴力卡过bzoj，不管了QAQ
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll unsigned long long #define inf 1000000000 #define P 999983 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K,ans,mx; int top,q[100005],nxt[100005]; bool mark[15]; struct H{ int cnt; int nxt[100005],last[1000005],val[100005]; ll Hash[100005]; void insert(ll H,int t){ int x=H%P; q[++top]=x; nxt[++cnt]=last[x];val[cnt]=t;Hash[cnt]=H; last[x]=cnt; } int find(ll H){ int x=H%P; for(int i=last[x];i;i=nxt[i]) if(Hash[i]==H)return val[i]; return -1; } void clear(){ while(top)last[q[top--]]=0; cnt=0; } }mp; struct data{ int x,b; friend bool operator<(data a,data b){ return a.x<b.x; } }a[100005]; ll geth(int *num) { ll t=0; for(int i=1;i<=mx;i++)t=t*1000000007+num[i]*13; return t; } void cal() { int p=1;while(!mark[p])p++; int num[10]={}; mp.clear(); for(int i=1;i<=n;i++) if(!mark[a[i].b]) { mp.clear();mp.insert(0,i); memset(num,0,sizeof(num)); } else { if(a[i].b==p) { for(int j=p+1;j<=mx;j++) if(mark[j])num[j]--; } else num[a[i].b]++; ll t=geth(num); int p=mp.find(t); if(p!=-1) ans=max(ans,a[i].x-nxt[p]); else mp.insert(t,i); } } void dfs(int x,int k) { if(x==mx+1) { if(k>=K)cal(); return; } dfs(x+1,k); mark[x]=1; dfs(x+1,k+1); mark[x]=0; } int main() { n=read();K=read(); for(int i=1;i<=n;i++) { a[i].x=read(),a[i].b=read(); mx=max(a[i].b,mx); } sort(a+1,a+n+1); for(int i=0;i<n;i++)nxt[i]=a[i+1].x; dfs(1,0); if(!ans)puts("-1"); else printf("%d\n",ans); return 0; } |
OI 课件=>
18 1040247 wjy1998 59244 KB 4432 MS C++ 3916 B 2015-07-10 18:01:38
19 1042564 hzwer 8308 KB 6028 MS C++ 2115 B 2015-07-12 17:06:54
黄学长你这姿势不对啊= =我复杂度是O(NlogN*8*2^8)……