星际网络（数学）

题目大意

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

输入格式

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

输出格式

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

样例

样例输入

2
4 0 1 2 3 4
2 0 3 1

样例输出

6

算法分析

• 正解思路有点像暴力 但是比暴力多了一个合并星球的操作
• 这个题思路很容易看出来的 通过枚举每一个时刻（枚举到最小公倍数） 然后求出当前时刻所有星球的流量
• 但是星球有100000个，时刻有55440（前24个数最小公倍数）个，枚举显然会炸
• 我们可以把星球合并 虽然每个星球当前所处的时刻不同 但是通过合并操作之后可以让所有星球合并为24个（表示每天多少个时刻的星球）
• 然后就可以枚举了
• 关于24以内数字 显然如果成倍数关系就会掉进循环，而如果互质那么可以到达任意时刻 通俗解释就是如果这个数与其他数都互质 那么这个数可以直接加上他的最大值（肯定可以加上）

代码展示

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int GBS = 55440;
long long d[maxn];
long long q[maxn][25];

long long modify(int x){
    long long ans = 0;
    for(int i = 1;i <= x;++i)ans = max(ans,q[x][i]);
    return ans;
}

int main(){
    int n;scanf("%d",&n);
    for(int i = 1; i <= n; ++i){
        int D,T;scanf("%d%d",&D,&T);
        for(int j = 1; j <= D; ++j)scanf("%lld",&d[j]);
        for(int st = T + 1,t = 1; t <= D; ++st,++t){//将时刻统一
            if(st > D)st -= D;//如果时刻超过D
            q[D][t] += d[st];//D表示每天小时数目 t表示时间
        }
    }
    long long Max = 0;
    for(int i = 1;i <= GBS;++i){
        long long sum = 0;
        for(int j = 1;j <= 24;++j){
            if(j == 13 || j == 17 || j == 19 || j == 23)continue;//如果遇到与其他数都互质的直接跳过
            int now = (i - 1) % j + 1;//处理时刻，这里操作为了防止出现%j之后出现0的情况
            sum += q[j][now];
        }
        Max = max(Max,sum);//Max存最大的流量
    }
    Max += modify(13) + modify(17) + modify(19) + modify(23);//这几个数与24内任何数都互质 特殊处理
    printf("%lld\n",Max);
    return 0;
}