牛客练习赛【65】非官方题解

前面的碎碎念：
这次比赛事故有点大啊，D和E题都是在最后关头才进行了rejugde。牛客的题目老实说还是挺不错的，就是题面或者数据老出问题，给人的体验就不太好...

题解部分：

A-最值序列
很显然，我们把数字从小到大排序后，取前n/2个数字相加，再不断乘以后n/2个数字，通过这样的贪心策略即可最大化答案。
时间复杂度：O(n $图片说明$ log(n))。
代码部分：

#include<bits/stdc++.h>
using namespace std;

int i,j,n,ans=0,a[500005];
const int mod=998244353;
int main()
{
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    for(i=0;i<n;i++)
    {
        if(i<n/2)ans=(ans+a[i])%mod;
        else ans=(long long)ans*a[i]%mod;
    }
    printf("%d\n",ans);
    return 0;
}

B-多重序列
注意到每个数字都是k的非负整数次幂，根据乘法原理，有：k^p1 $图片说明$ k^p2=k^(p1+p2)，即两数相乘时，若底数相同，则指数相加。因此我们只需要用ans保存每组数字指数相加后的最大值，最后的答案就是k^ans。
时间复杂度：O(n $图片说明$ m $图片说明$ log(max(aij)))。
代码部分：

#include<bits/stdc++.h>
using namespace std;

long long t,mod;
long long fastpow(long long a,int b)
{
    long long s=1;
    for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
    return s;
}
int main()
{
    int i,j,n,m,k,ans=0,a;
    scanf("%d%d%d%lld",&n,&m,&k,&mod);
    while(n--)
    {
        for(a=0,i=1;i<=m;i++)
        {
            scanf("%lld",&t);
            for(j=0;t!=1;t/=k)j++;
            a+=j;
        }
        ans=max(ans,a);
    }
    printf("%lld\n",fastpow(k,ans));
    return 0;
}

C-二维动点
这是一道结论题，通过画图可以得出(猜出)结论，我们在这设定每个给出的点与(0,0)点相连，其直线方程都有一个自己的斜率。于是我们先把所有给出点的不同斜率存起来，同时记录不同斜率个数有多少，这里可以通过map+gcd存储二元组实现，注意特判给出点是(0,0)点的情况。
接下来对于每次询问：
①若询问点为(0,0)，直接输出0。
②若不同斜率个数为1，则检查询问点与(0,0)点相连的直线方程斜率是否在map中存在，若存在输出1，否则输出-1。
③若不同斜率个数为2，则检查询问点与(0,0)点相连的直线方程斜率是否在map中存在，若存在输出1。若不存在，将询问点与不同斜率代表的两个点相连，再将不同斜率代表的两个点与(0,0)点相连，若其能形成一个平行四边形，则输出3，否则输出2。
④若不同斜率个数大于等于3，则检查询问点与(0,0)点相连的直线方程斜率是否在map中存在，若存在输出1，否则输出2。
时间复杂度：O(n $图片说明$ log(n)+q $图片说明$ log(n))。
代码部分：

#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
map<int,map<int,int>>V;
int main()
{
    int i,n,q,x,y,L=0;
    long long X[2],Y[2];
    scanf("%d%d",&n,&q);
    while(n--)
    {
        scanf("%d%d",&x,&y),i=gcd(x,y);
        if((!x&&!y)||V[x/i][y/i])continue;
        V[x/i][y/i]=1;
        if(L<2)X[L]=x,Y[L++]=y;
    }
    while(q--)
    {
        scanf("%d%d",&x,&y);
        if(!x&&!y){printf("0\n");continue;}
        i=gcd(x,y);
        if(V[x/i][y/i]){printf("1\n");continue;}
        if(L==1){printf("-1\n");continue;}
        if(L>2){printf("2\n");continue;}
        if(X[1]*(y-Y[0])==Y[1]*(x-X[0])&&X[0]*(y-Y[1])==Y[0]*(x-X[1]))printf("3\n");
        else printf("2\n");
    }
}

D-最小公倍数
数论题，不会...

E-游走配对
网络流，不会...

F-操作树
不会...

完结撒花，若有疏漏之处，还望大佬轻喷。