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;
}