贴一波谷歌翻译~

图片说明

注意，这题中每个方便面的分发是唯一的

由于本人英语和语文辣鸡，所以完美将此题看错。。。

出题人告诉我们：每次我们将一个大小为N的方便面分块时，我们要尽量使得所有的块小，而不是任意分成等差数列。

由于我看错了题，所以我们先来讲讲分成任意等差数列怎么做。（大雾）

我们设dp[i]表示大小为i的面最多可以分多少次。

那么，如果我们要求dp[i]的值，就需要枚举所有等差数列了。因为T很小只要判断够快，就貌似可行的（没试过）

但是，这样明显不够优秀，我们考虑直接预处理枚举等差数列。

我们先枚举首项，然后依次算当前等差数列的和，若大于n，就break掉就行了。

但是，这么做的复杂度是多少呢？不会爆吗？

答案是不会的。

因为，每次我们的等差数列的和，都会加上一个大于首项的数，而且加的数也在不断增大。。。

那么我们参考下埃式筛，埃式筛其实和这个是类似的，而且埃式筛是每次加上的是"首项"，所以，这个预处理的复杂度是小于埃式筛的！也就是说，我们可以在的时间内处理好我们需要的。

那么，对于一个数x，我们找到了一个满足和为x的等差数列，然后怎么办储存呢？

vector?亲测超时。

直接上向前星啊！

我们用向前星储存每个点的满足和为这个点的等差数列的首项和末项即可。

那么怎么计算呢？

我们知道，

那么，我们直接枚举肯定是不优的，我们观察可以发现，这玩意儿，明显可以弄个前缀和优化，即设

那么,对于每个符合的等差数列，我们都可以进行O(1)转移了。

最后询问时，就可以直接回答了

复杂度:

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1,M=1e7;
struct node{
    int v,w,nex;
}t[M];
int las[N],len,n=1e6;
unsigned long long s[N];//注意，和会爆long long
int g[N];bool vis[N];
inline int max(int x,int y){
    return x>y?x:y;
}
inline void add(int u,int v,int w){
    t[++len]=(node){v,w,las[u]},las[u]=len;
}
inline void f(int x){
    for(int i=las[x];i;i=t[i].nex){
        int v=t[i].v,w=t[i].w;//首项
        g[x]=max(g[x],s[w]-s[v-1]+1);
    }
    return;
}
int main(){
    for(int i=1;i<=n;++i){//生成首项
        if(i+i+1>n)break;
        int tot=i;
        for(int j=i+1;;++j){//复杂度小于埃式筛，不怂
            tot+=j;
            if(tot>n)break;
            add(tot,i,j);
        }
    }
    for(int i=1;i<=n;++i){
        f(i);s[i]=s[i-1]+g[i];
    }
    int T;
    scanf("%d",&T);
    while(T--){
        int x;
        scanf("%d",&x);
        printf("%d\n",g[x]);
    }
    return 0;
}

那么，再考虑这个题怎么做。

其实，你会了上面那个，这个题就简单了。

不难发现，只要首先越小那么，最终分成的每个等比数列的项就越小。

那么，我们只需要将上面的代码改成从大到小枚举首项，然后，把向前星改成直接赋值，就可以算出答案了。

复杂度同上（由于算dp[i]的时候，每个点只有了一次转移，所以会比上面的快一点）:

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1,M=1e7;
int L[N],R[N];
long long s[N];
int g[N];bool vis[N];
inline void f(int x){
    if(!L[x])return;
    g[x]=(s[R[x]]-s[L[x]-1]+1);
    return;
}
int main(){
    int n=1000000;
    for(int i=n;i;--i){//生成首项
        int tot=i;
        for(int j=i+1;;++j){//复杂度小于埃式筛，不怂
            tot+=j;
            if(tot>n)break;
            L[tot]=i,R[tot]=j;
        }
    }
    for(int i=1;i<=n;++i){
        f(i);s[i]=s[i-1]+g[i];
    }
    int T;
    scanf("%d",&T);
    while(T--){
        int x;
        scanf("%d",&x);
        printf("%d\n",g[x]);
    }
    return 0;
}

所以这个代码可以做到更多组的回答