WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
BZOJ 5440: 老虎机
BZOJ 5440: 老虎机

Description

n台老虎机,第i台老虎机里有L_i个球,其中第j个球的颜色为C_{i,j}
每次可以选择一台还有球的老虎机,投入一个硬币,它会随机掉出一个球。
求出如果采用最优策略,在最坏情况下,需要多少个硬币才能得到两个颜色相同的球。
注意你可以根据之前的结果来决定之后的操作。
有多组数据。

Input

第一行一个整数T表示数据组数。
每组数据第一行一个整数n,接下来n行每行第一个整数表示L_i,接着L_i个整数表示C_{i,j}
T\leq 10,1\leq n,L_i,C_{i,j}\leq 10^5,1\leq L_1+L_2+\cdots+L_n\leq 10^5

Output

每组数据输出一行一个整数表示答案。

Sample Input

1
7
4 1 2 3 4
1 1
1 2
1 3
1 4
7 4 7 4 4 7 7 4
1 5

Sample Output

2

题解

经过简单的推理可以发现,最优策略下,我们应该只会在至多两台老虎机上进行操作:
1. 在一台上持续投币直到颜色重复
2. 在一台老虎机A上先投若干硬币获得一些颜色,然后在另一台老虎机B上持续投币直到颜色与之前获得的重复

操作第三台老虎机C是没有意义的,因为如果第三台C更优,我们完全可以不用操作第二台B,直接去操作第三台C。

第一种情况很好维护,如果当前老虎机A里面存在颜色重复,那么答案等于A的颜色集合的大小,否则不存在。

第二种情况,相当于我们一开始投币在老虎机A里获得了一种颜色c,然后要在其他所有老虎机B上面投币获得这种颜色。显然如果B不存在这种颜色,则GG,如果B存在这种颜色,那么需要的次数为B的颜色集合的大小。
对于每一种颜色,我们都维护一个线段树,第i个位置表示在第i个老虎机上获得颜色的最少次数。在确定了颜色c之后,我们只需要线段树区间查询就可以得到让这种颜色重复的最少投币次数了。
对于原本的老虎机A,我们要求的它所有颜色的最少次数,然后从大到小排序,得到数组Arr_{1\cdots k},最坏情况下,肯定是老虎机从大到小吐出需要颜色重复次数的硬币,我们统计一下答案即可:min(Arr_1+1, Arr_2+2, \cdots ,Arr_k+k)

这道题目的数据保证了持续投币一定可以获得重复颜色。

代码

/**
* Author : WNJXYK
* Date : 20180824
* Problem : 5440
**/

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define FOR(x,y,z) for (y::iterator x=(z).begin(); x!=(z).end(); x++)


const int MOD=998244353;
const int MAXN=1e5+50;
const int INF=2100000000;

LL Abs(LL x) {return x<0?-x:x;}
LL Pow(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL Gcd(LL a, LL b) {return b?Gcd(b,a%b):a;}

int n, ans[MAXN];
VI mac[MAXN], que[MAXN];
struct Tree{ int mi, lx, rx; } tree[MAXN*20];
int root[MAXN], numt;

void modify(int &x, int l, int r, int p, int v){
    if (!x) { x=++numt; tree[x].lx=tree[x].rx=0; tree[x].mi=INF; }
    tree[x].mi=min(tree[x].mi, v);
    if (l!=r){
        int m=(l+r)/2;
        if (p<=m) modify(tree[x].lx, l, m, p, v);
        else{
            modify(tree[x].rx, m+1, r, p, v);
        }
    }
}

int query(int x, int l, int r, int left, int right){
    if (!x || left>right) return INF;
    if (left<=l && r<=right){
        return tree[x].mi;
    }else{
        int m=(l+r)/2, ret=INF;
        if (left<=m) ret=min(ret, query(tree[x].lx, l, m, left, right));
        if (m+1<=right) ret=min(ret, query(tree[x].rx, m+1, r, left, right));
        return ret;
    }
}

inline void solve(int T){
    scanf("%d", &n);
    for (int i=1; i<=n; i++){
        int c=0; scanf("%d", &c);
        mac[i].clear(); que[i].clear(); ans[i]=INF;
        for (int j=1; j<=c; j++){
            int x=0; scanf("%d", &x);
            mac[i].pb(x);
        }
    }

    memset(root, 0, sizeof(root)); numt=0;
    for (int i=1; i<=n; i++){
        sort(all(mac[i]));
        int sz=SZ(mac[i]);
        VI::iterator e_begin=unique(all(mac[i])); mac[i].erase(e_begin, mac[i].end());
        int nsz=SZ(mac[i]);
        if (sz!=nsz) ans[i]=nsz+1, sz=nsz;

        FOR (c, VI, mac[i]) modify(root[*c], 1, n, i, sz);
    }

    int Ans=INF;
    for (int i=1; i<=n; i++){
        FOR (c, VI, mac[i]){
            int now=INF;
            now=min(now, query(root[*c], 1, n, 1, i-1));
            now=min(now, query(root[*c], 1, n, i+1, n));
            que[i].pb(now);
        }
        sort(all(que[i]));
        int sz=SZ(que[i]);
        FOR (x, VI, que[i]) ans[i]=min(ans[i], sz+(*x)), --sz;
        Ans=min(Ans, ans[i]);
    }

    //if (Ans==INF) Ans=-1;
    printf("%d\n", Ans);
}

int main(){
    // freopen("in.txt" ,"r", stdin);
    // freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    // solve(0);
    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

BZOJ 5440: 老虎机
Description 有$n$台老虎机,第i台老虎机里有$L_i$个球,其中第$j$个球的颜色为$C_{i,j}$。 每次可以选择一台还有球的老虎机,投入一个硬币,它会随机掉出一个球。 求出如果采用最优策略…
扫描二维码继续阅读
2018-08-24
<--! http2https -->