题目

1423 - Olympic Swimming

PDF (English)

Statistics

Forum

'Hurdles' is a common event in athletics where the runners race in running tracks containing hurdles (obstacles). For the race some hurdles are placed evenly spaced along a straight running course. They are positioned so that they will fall
over if bumped into by the runner.

The organizers of 20012 Olympic Games are planning to introduce a hurdles event in swimming. For this purpose, some hurdles will be placed in the swimming pool used in the competition. Let's describe the construction of a swimming pool at first. A pool isL
meters long and is divided into K equal sized lanes across the width. Each participant swims along his own lane. As events of various lengths take place in the same pool, measurement of length is very critical. So, there is a mark after every
meter along the length of the pool starting from 0 in one end. There are some hurdles placed in the pool. A hurdle is placed between two adjacent marks in a lane. Now, the hurdles are not uniformly distributed. For example, in a 5 meter long pool with 2 lanes,
the first lane may have 2 hurdles, one between 1m and 2m while another between 3m and 4m. The second lane may have 1 hurdle, between 0m and 1m. For ensuring a fair race, the course must be defined in a way that all the participants have to face same number
of hurdles. In other words, you are to select two length marks from the pool so that there is exactly same number of hurdles placed in every lane between these two length marks. You can safely assume that, a race will always start or end in a length mark.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing two integers L and
K (1 ≤ L ≤ 50000, 1 ≤ K ≤ 30). Each of the next K lines describes a lane. Each of these lines starts with an integern (1 ≤ n ≤ 5000) denoting the number of hurdles in the lane, followed byn distinct
integers. The i^th integerp_i (0 ≤ p_i < L) denotes that there is a hurdle between length markp_i and
p_i+1.

Output

For each case, print the case number and the length of the longest race that can take place in the pool.

Note

Dataset is huge, use faster I/O methods.

题解

题目的意思是说，有k条长l的泳道，为了增加难度，会在每一条泳道上增加ni个障碍，障碍的坐标分别是p1,p2,...,pni。但是为了比赛的公平，必须保证每个运动员的泳道中障碍物的数量必须相同。同时为了照顾到资源的最大化利用，输出这个比赛场地可以让运动员公平竞赛的最大的泳道长度。

算是一道比较简单的散列表的问题了，用STL来做，具体的请看代码吧，应该没什么大问题的=.=

代码示例

#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

typedef long long int64;
typedef unsigned long long Uint64;

const int MAXN=50050;
map<Uint64,int> g;
int ar[MAXN][30];
int cnt[30];
void solved(int tt) {
    int L,K,Q,p;
    scanf(" %d %d",&L,&K);
    g.clear();
    memset(ar,0,sizeof(ar));
    for (int i=0;i<K;++i) {
        scanf(" %d",&Q);
        while (Q--) {
            scanf(" %d",&p);
            ar[p][i]++;
        }
    }
    int ret=p=0;
    for (int i=0;i<L;++i) {
        int mi=L+1,ma=-1;
        for (int j=0;j<K;++j) {
            if (i) ar[i][j]+=ar[i-1][j];
            mi=min(mi,ar[i][j]);
            ma=max(ma,ar[i][j]);
        }
        if (mi == ma) ret=i+1;
        for (int j=0;j<K;++j) {
            cnt[j]=ar[i][j]-mi;
        }
        Uint64 tmp=0;
        for (int j=0;j<K;++j) {
            tmp *= 16777619;
            tmp ^= cnt[j];
        }
        int t=g[tmp];
        if (t) {
            ret=max(ret,i-t+1);
        }
        else {
            g[tmp]=i+1;
        }
    }
    printf("Case %d: %d meter(s)\n",tt,ret);
}

int main (){
    int T;scanf(" %d",&T);
    int tt=0;
    while (T--){
        solved(++tt);
    }
    return 0;
}