星际网络

星际网络( 数学\(\star\star \))

• 时限：\(1s\) 内存：\(256M\)

Descrption

• \(LY\) 星系有很多个星球。它们之间通过一个巨大的互联网进行通讯。随着信息时代的发展，旧的网络已经不能满足需求，于是 \(LY\) 星系决定建设一个新的网络。
• \(LY\) 星系有很多个星球，有些星球一天有几十个小时，有些星球一天只有几个小时。但每个星球的一个小时都是一样长的。因此每个星球一天的长短都不一样，这就导致了一个问题：星球上的生物都是在白天工作夜晚 休息，因此每个星球每天都有上网高峰期和低峰期，当很多星球同时达到高峰期时，网络便会变得异常拥堵，进而带来延迟。所以 \(LY\) 星系需要建设一个有足够大带宽的网络来避免这一问题。现在他们想知道，网络在一个小时内的最大流量是多少。

Input

• 输入数据的第一行为一个正整数 \(N\)，表示 \(LY\) 星系共有 \(N\) 个星球。
• 接下来 \(N\) 行，每行描述一个星球。对于每个星球的描述，开头为两个正整数 \(D,T\)，表示这个星球一天有 \(D\) 个小时，当前位于 \(T\) 时刻（即某一天已经过去了 \(T\) 小时）.
• 接下来是 \(D\) 个正整数 \(q_0,q_1……q_{D-1}\)，其中 \(q_i\) 表示第 \(i\) 小时到第 \(i+1\) 小时的流量。

Output

• 输出共一行，为一个整数 \(Ans\)，表示一个小时内的最大流量。

Sample Input

2
4 0 1 2 3 4
2 0 3 1

Sample Output

6

Hint

• 在 \(4n+3\) 时刻，流量\(=3+3=6\) 达到最大。
• 对于 \(10\%\) 的数据，\(N<=10\)；
• 对于 \(20\%\) 的数据，\(N<=100\)；
• 对于 \(40\%\) 的数据，\(N<=10000\)；
• 对于 \(70\%\) 的数据，\(N<=50000\)；
• 对于全部的数据，\(N<=100000,0<=T<D<=24,q_i<=1000000\)；
• 来源：

分析

• 首先观察到算法时间复杂度与 \(n\) 无关，因为一天的长度相同的星球都可以合并，至多 \(24\)个。
• 若 \(A,B\) 星球的小时数互质，则 \(A\) 星球每个时刻与 \(B\) 星球每个时刻均有机会重合。也就是说，若 \(A\) 星球的小时数与 \(1\sim 24\) 其他数都互质，则无论其他数字如何选择，这个星球都可以取到它的最大流量。\(13,17,19,23\) 满足这个条件。其他数字暴力枚举到它们的最小公倍数即可。

Code

#include <bits/stdc++.h>
typedef long long LL;
const int MAX = 55440;//除了13,17,19,23外其他数的最下公倍数
int n,tmp[30];
LL ans,psum,sum[30][30];
void Calc(int D){//计算一天的最大流量
    LL Max = 0;
    for(int i = 1; i <= D; ++i)Max = std::max(Max,sum[D][i]);
    psum += Max;
}
void Solve(){
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i){//n个星球D相同的合并,最多就剩下24个星球
        int D,T;scanf("%d%d",&D,&T);
        for(int j = 1; j <= D; ++j)scanf("%d",&tmp[j]);
        for(int st = T + 1,t = 1; t <= D; ++st,++t){//时刻同步,时刻从1开始
            if(st > D)st -= D;//T+1(平移了一位)都对应t=1时刻，其他依次后倒
            sum[D][t] += tmp[st];//合并到一起
        }
    }
    Calc(13);Calc(17);Calc(19);Calc(23);
    for(int i = 1; i <= MAX; ++i){//大于MAX的就重复的循环了
        LL cursum = 0;
        for(int j = 1; j <= 24; ++j){//枚举24个合并的星球
            if(j == 13 || j == 17 || j == 19 || j == 23)continue;
            int cur = (i - 1) % j + 1;//计算时刻
            cursum += sum[j][cur];
        }
        ans = std::max(ans,cursum);
    }
    printf("%lld\n",ans + psum);
}
int main(){
    Solve();
    return 0;
}