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了，只能给代码注释注释了，看懂了的小伙伴可以滴滴我
代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
struct rec{
    int r1,r2,c;
    bool operator <(const rec&n)const {return c>n.c;}
};//自定义排序
int t1[maxn][maxn],t2[maxn][maxn];bool v1[maxn],v2[maxn];
int dfs(int r1,int r2)//表示两方的根节点
{
    priority_queue<rec>q;//优先队列
    int s1=t1[r1][0],s2=t2[r2][0];//s1,s2表示r1,r2的子节点个数
    if(s1!=s2)return -1;//节点个数就不一样，崩
    for(int i=1;i<=s1;i++)v1[t1[r1][i]]=false;//让所有的子节点都清空，进行下面的循环操作
    for(int i=1;i<=s2;i++)v2[t2[r2][i]]=false;
    for(int i=1;i<=s1;i++)
    {
        for(int j=1;j<=s2;j++)
        {
            int cc=dfs(t1[r1][i],t2[r2][j]);//去访问r1r2的子节点,得到子节点需要更换的次数
            if(cc!=-1)
                q.push({t1[r1][i],t2[r2][j],cc});//先从子节点开始访问得到个数，然后慢慢迭代
        }
    }
    int ans=0;
    if(r1!=r2)ans++;//表示这两个对应的编号不同，需要变换
    int c1=0;
    while(!q.empty())
    {
        rec now=q.top();//先给ans大的子节点标记
        q.pop();
        if(v1[now.r1]||v2[now.r2])continue;
        ans+=now.c;
        v1[now.r1]=true;
        v2[now.r2]=true;
        c1++;
    }
    if(c1!=s1)return -1;//表示访问的节点少于已知的节点，出现问题
    return ans;
}
int main()
{
    int n,x;
    scanf("%d",&n);
    int r1,r2;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        t1[x][++t1[x][0]]=i;
        r1=(x==0?i:r1);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        t2[x][++t2[x][0]]=i;
        r2=(x==0?i:r2);//得到的是根节点的编号
    }
    printf("%d",dfs(r1,r2));
    return 0;
}