2020牛客多校第十场AE题解

A. Permutation

题意

输出序列1~p-1，使其满足

解题

类似搜索，能乘2就乘2，否则乘3，总数量不足则无解。

int t;
int n,m;
int a[maxn];
bool vis[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
         m = 0;
         a[++m] = 1;  vis[1] = 1;
         bool flg = 1;
        for(int i=2;i<n;++i)
        {
            int p = 2*a[i-1]%n;
            if(!vis[p])
            {
                vis[p] = 1;
                a[++m] = p; continue;
            }
            p = 3*a[i-1]%n;
            if(!vis[p])
            {
                vis[p] = 1;
                a[++m] = p; continue;
            }
            flg = 0; break;
        }
        if(!flg) puts("-1");
        else {for(int i=1;i<n;++i) printf("%d ",a[i]); printf("\n");}
        for(int i=1;i<n;++i) vis[i] = 0;
    }
    return 0;
}

E. Game

题意

每次操作可以把右边的一行格子向左移动，由于重力格子下落，可以操作任意次，求最小的最高高度。

解题

直觉是总数除以列数再向上取整，但是考虑一组样例1 20 1 1，自然可以想到求一下前缀平均值，取最大值就是答案。

int t;
int n,m;
ll a[maxn];
ll f[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&a[i]);
        }
        f[0] = 0;
        for(int i=1;i<=n;++i)
        {
            f[i] = f[i-1] + a[i];
        }
        ll ans = 0;
        for(int i=1;i<=n;++i)
        {
            f[i] = (f[i]+i-1)/i; ans = max(ans,f[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}