2020牛客多校第十场

A Permutation

链接：https://ac.nowcoder.com/acm/contest/5675/A
题意：
给定一个质数p,问是否存在一个长度为n-1的数列, $图片说明$ =1, $图片说明$ %p或者 $图片说明$ %p，存在输出数列，否则输出-1
题解：
暴力，模拟
注意：
不能出现重复的数字
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int a[maxn];
int vis[maxn];
int main()
{
    int t,p;
    scanf("%d",&t);
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        scanf("%d",&p);
        a[1]=1;vis[1]=1;int a1,a2,flag=0;
        for(int i=2;i<=p-1;i++)
        {
            a1=a[i-1]*2%p;
            a2=a[i-1]*3%p;
            if(!vis[a1])
            {
                vis[a1]=1;
                a[i]=a1;
            }
            else if(!vis[a2]){
                vis[a2]=1;
                a[i]=a2;
            }
            else
            {
                flag=1;
                break;
            }
        }
        if(flag){
            printf("-1\n");
            continue;
        }
        for(int i=1;i<=p-1;i++)
        {
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    return 0;
}

E Game

链接：https://ac.nowcoder.com/acm/contest/5675/E
题意：
一堆摞在一起的砖头，只能从右往左推，问能够推之后得到的最低的高度
题解：
就是从左边开始的i个前缀和除以i的最小值，（比方说第一个，肯定是最高的高度，接下来第二个，可以挪动，挪到最小的高度，...直到最后一个）
注意：
向下取整
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll a[maxn];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int x,ans=0;double sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];
            x=ceil(sum/i);
            ans=max(ans,x);
        }
        printf("%d\n",ans);
    }
    return 0;
}

I Tournament

链接：https://ac.nowcoder.com/acm/contest/5675/I
题意：
有n个队伍，现在两两比赛，一共要进行n(n-1)/2场比赛，而每个队伍只需要在他最开始的比赛和最后一场比赛都在场就行，其他的时间可以离开，问所有队伍到场的天数的总和最小是多少
题解：
可以先把队伍分成两部分。前，后
前与前进行比赛
前与后进行比赛（分成两部分，第一部分是前->分散着进行比赛，后->集中。第二部分前->集中（开始渐渐离场），后->分散）
后与后进行比赛
注意：
队伍比赛的顺序尽可能的分散
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll a[maxn];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int x,ans=0;double sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];
            x=ceil(sum/i);
            ans=max(ans,x);
        }
        printf("%d\n",ans);
    }
    return 0;
}

J Identical Trees

链接：https://ac.nowcoder.com/acm/contest/5675/J
题意：
给定两颗n个节点的树，要修改多少次编号，才能使得他们一样
题解：
从他们的根节点开始搜索，搜到叶节点。由叶节点逐个进行比较，叶节点得到的修改个数然后再继续向上，最后弄出来，，，~~（好吧，老实说，我看不懂）~~
注意：
下次再来看看吧，我太low了，只能给代码注释注释了，看懂了的小伙伴可以滴滴我
代码：

2020牛客多校第十场

A Permutation

E Game

I Tournament

J Identical Trees

全站热榜