P4875 [USACO14OPEN]Fair Photography G 题解

· · 题解

模拟赛考到这题了，跟风 yspm 写篇题解

翻译

### sol 奶牛只有 $8$ 个品种，前缀和后可以在 $O(8)$ 的时间内判断出一个区间是否合法。（如果一个区间合法，那么它两个端点处的前缀和数组差分得到的差分表对应相等，注意这里的差分指的是各个品种出现次数之差，并非还原前缀和数组的差分） 考虑移动区间右端点时维护左端点的合法性。一个暴力的想法是对于每个右端点 $2^8$ 枚举出现过的品种，hash 表记录左端点。复杂度 $O(2^88n)$，不太行。 其实没有必要枚举 $2^8$ 枚举出现品种的集合，左端点从当前右端点向左移时只会出现 $8$ 种集合（每个品种出现了就不会消失），因此只需按每个品种最后一次出现的位置倒序加入当前集合并查询。 右端点移动会改变这个品种上一次出现的位置到当前位置的出现品种集合，暴力修改即可。 时间复杂度 $O(8^2n)

code

省略的头文件

const int N = 1e5+5;
int n,m;
PII a[N];

int ans=-1,lst[10],sum[N][10]; // lst记录每个品种上次出现的位置
PII tmp[10];
unordered_map<ULL,int> mp; // hash表

ULL hsh(int s,int i) { // hash函数
    int fi = 7; For(j,0,7) if( s & (1<<j) ) { fi = j; break; }
    ULL res = 0;
    For(j,fi+1,7) if( s & (1<<j) ) res = res * 997 + sum[i][j]-sum[i][fi];
    return res;
}

signed main() {
    read(n,m); --m;
    For(i,1,n) read(a[i].fi,a[i].se), --a[i].se; sort(a+1,a+n+1);
    For(i,1,n) {
        mp[0] = a[i].fi;
        For(j,0,7) sum[i][j] = sum[i-1][j]; ++sum[i][a[i].se];
        For(j,lst[a[i].se]+1,i) { // 暴力修改
            int s = 0; For(k,0,7) if( sum[i-1][k]-sum[j-1][k] ) s |= 1<<k;
            mp.erase(hsh(s,j-1)); // 删去原来状态
            s |= 1<<a[i].se; ULL h = hsh(s,j-1);
            if( !mp.count(h) ) mp[h] = a[j].fi; // 更新当前状态
        }
        lst[a[i].se] = i;
        // s为当前集合，tmp按每个品种最后一次出现的位置排序加入s
        For(j,0,7) tmp[j] = MP(lst[j],j); sort(tmp,tmp+8,greater<PII>());
        int s = 0; For(j,0,m-1) s |= 1 << tmp[j].se;
        for(int j = m; j < 8 && tmp[j].fi; ++j) {
            s |= 1 << tmp[j].se;
            ULL h = hsh(s,i);
            if( mp.count(h) ) ckmax(ans,a[i].fi-mp[h]);
        }
    }
    write(ans);
    return iocl();
}