Skip to content

14301: 【原4301】奶牛区间

题目

题目描述

author: TJH 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4301

Description

助教养的N (1<=N<=100000)头奶牛有很多相同之处,并且他己经将每头奶牛的不同之处归纳成为K (1<=K<=30)种特性。比如说,1号特性可以代表奶牛身上有斑点,2号特性代表奶牛身上有条纹等等。

我们使用“特性标识符”来描述奶牛的各种特性:一个特性标识符是一个二进制下有K位的整数,每位比特可以标识一头奶牛的一个特性。比如一头奶牛的特性标识符是13,将13写成二进制:1101,从右向左看,就表示这头奶牛具有1、3、4号特性,但没有2号特性。

如果把N头奶牛排成了一排,发现在有些连续区间里的奶牛,每种特性出现的次数是一样的,我们把这样的连续区间称为“平衡的”。助教希望你能帮忙找出最大的平衡区间的长度。

Input Format

第一行包括N和K。

第2~N+1行:第i+1行是一个十进制整数,表示第i头奶牛的特性标识符。

Output Format

输出最大的平衡区间的长度。

Sample Input

7 3
7
6
7
2
1
4
2

Sample Output

4

Hint

在区间[3, 6](从第3头奶牛到第6头奶牛,长度为4)中,每种特性出现的次数恰好都为2。

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4301.md
*/
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, K, a[100005], sm[100005][33] = {0};
struct CC{
    int a[33];
    bool operator < (CC& c){
        for (int i = 0; i < K; ++i) {
            if (a[i] < c.a[i])
                return true;
            else if (a[i] > c.a[i])
                return false;
        }
        return false;
    }
};
bool check(CC& c1, CC& c2){
    for (int i = 0; i < K - 1; ++i)
        if (c1.a[i] != c2.a[i])
            return false;
    return true;
}
int check2(CC& c1, CC& c2){
    for (int i = 0; i < K - 1; ++i){
        if (c1.a[i] < c2.a[i])
            return -1;
        else if (c1.a[i] > c2.a[i])
            return 1;
    }
    return 0;
}
struct Tr {
    int siz, prio, lch, rch;
    CC v;
};
Tr tr[100005];
int S = 0, root = 0;
void maintain(int x){
    tr[x].siz = 1 + tr[tr[x].lch].siz + tr[tr[x].rch].siz;
}
int tree_new(CC& c, int pp){
    ++S;
    tr[S].siz = 1, tr[S].prio = rand();
    for (int i = 0; i < K - 1; ++i)
        tr[S].v.a[i] = c.a[i];
    tr[S].v.a[K - 1] = pp;
    tr[S].lch = tr[S].rch = 0;
    return S;
}
void Split(int now, CC& kk, int &x, int &y){
    if (!now) x = y = 0;
    else {
        if (tr[now].v < kk){
            x = now, Split(tr[now].rch, kk, tr[now].rch, y);
        }else {
            y = now, Split(tr[now].lch, kk, x, tr[now].lch);
        }
        maintain(now);
    }
}
int Merge(int x, int y){
    if (!x || !y) return x + y;
    if (tr[x].prio < tr[y].prio){
        tr[x].rch = Merge(tr[x].rch, y);
        maintain(x);
        return x;
    }else{
        tr[y].lch = Merge(x, tr[y].lch);
        maintain(y);
        return y;
    }
} 
void Insert(CC& c, int pp){
    int x, y, z = tree_new(c, pp);
    Split(root, c, x, y);
    root = Merge(Merge(x, z), y);
}
int Lookup(CC& kk){
    int t = root;
    while (t){
        int rres = check2(tr[t].v, kk);
        if (rres < 0) t = tr[t].rch;
        else if (rres > 0) t = tr[t].lch;
        else {
            int res = tr[t].v.a[K - 1];
            t = tr[t].lch;
            while (t){
                if (!check(kk, tr[t].v))
                    break;
                if (tr[t].v.a[K - 1] < res)
                    res = tr[t].v.a[K - 1];
                t = tr[t].lch;
            }
            return res;
        }
    }
    return -1;
}
void init(){
    srand(time(NULL));
    n = read(), K = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j < K; ++j)
            sm[i][j] = sm[i - 1][j];
        for (int j = 0; j < K; ++j){
            if (a[i] & (1 << j))
                sm[i][j] += 1;
        }
    }
}
void solve(){
    CC ccc;
    for (int i = 0; i < K - 1; ++i)
        ccc.a[i] = 0;
    Insert(ccc, 0);
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j < K; ++j)
            ccc.a[j - 1] = sm[i][j] - sm[i][j - 1];
        int res = Lookup(ccc);
        if (res >= 0) {
            int d = i - res;
            if (d > ans) ans = d;
        }
        Insert(ccc, i);
    }
    printf("%d\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}

Zsi-r's solution

#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n, m;
const int maxnumber = 1e5 + 5;
const int primenumber = 2333;
typedef long long ll;
vector<ll>htemp[primenumber];
ll sum[maxnumber][35], c[maxnumber][35];
int compare(int x, int y) {

    for(int i = 1; i <= m; i++) {
        if(c[x][i] != c[y][i]) return 0;
    }
    return 1;
}
int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        for(int j = m; j >= 1; j--) {
            sum[i][j] = sum[i - 1][j] + x % 2;
            x /= 2;
        }
    }
    int temp = 0; 
    for(int i = 1; i <= n; i++) {
        int ans = 0;
        int ttt = 0;
        for(int j = 1; j <= m; j++) {
            c[i][j] = sum[i][j] - sum[i][1];
            if(c[i][j] == 0) ans++;
            ttt = (ttt + c[i][j]) % primenumber;
        }
        ttt = abs(ttt);
        if(ans == m) temp = i;
        htemp[ttt].push_back(i);
    }
    for(int i = 1; i < primenumber; i++) {
        int sum = htemp[i].size();
        if(sum > 1) {
            for(int j = 0; j < sum - 1; j++) {
                for(int k = 1; k < sum; k++) {
                    if(compare(htemp[i][j], htemp[i][k]) && htemp[i][k] - htemp[i][j]  > temp) {
                        temp = htemp[i][k] - htemp[i][j];
                    }
                }
            }
        }
    }
    cout << temp <<endl;
    return 0;
}