2021 百度之星大赛初赛第二场题解

• Marvolo • 0条评论 •

比赛信息

比赛地址

Solved 4/8

Rank 237/6190

[A] 签到

题意

给出a,b,每次a,b会变为a+b,a-b,问k次后变成什么。结果对998244353取模。

题解

真·签到题，不是题目名诈骗。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 998244353
using namespace std;

int T;
LL a,b,k,x,y,z;

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

inline LL Mi(LL x,LL y){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
    return Res;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        scanf("%lld%lld%lld",&a,&b,&k);
        x=Mi(2,k/2);
        a=(a*x)%MOD;    b=(b*x)%MOD;
        if (k&1){
            printf("%lld %lld\n",(a+b)%MOD,(a-b+MOD)%MOD);
        }
        else printf("%lld %lld\n",a,b);
    }
    return 0;
}

[B] 随机题意

题意

给出一个长度为n​的整数数列a​,构造另一个整数数列b​，使得满足|a_{i}-b_{i}| \leq k的i最多。

题解

首先对a​​排序，从前往后依次构造b_{i}​​。令b_{1}=a_{1}-k​​，之后按照b_{i}=min(a_{i}+k,max(b_{i-1}+1,a_{i}-k))​​构造即可。

不难证明这种贪心依次构造的方式可以使满足条件的i最多。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;

int T,n,k,i,Ans;
int a[N],b[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();   k=read();
        for (i=1;i<=n;i++)  a[i]=read();
        sort(a+1,a+1+n);
        Ans=1;
        b[1]=a[1]-k;
        for (i=2;i<=n;i++){
            b[i]=Max(a[i]-k,b[i-1]+1);
            if (b[i]>a[i]+k)    b[i]=a[i]+k;
            else Ans++;
        }
        printf("%d\n",Ans);
    }
    return 0;
}

[D] 净化

题意

给出一个数列a_{n}​​和m​​。一开始有一个数x​​，初始值是0。称一轮操作为，让x​​依次加上a_{i}​​。如果在某个时刻x<0​​，则将其立刻修改为0。如果某个时刻x\leq m​​，则结束该轮操作，输出到目前为止进行的操作轮数。如果永远无法满足条件，输出-1。

题解

有个结论，是否无解只需要模拟两轮操作就可以知道。如果模拟完第一轮操作后，x还是0，则无解；如果在第二轮操作中，x被减为了负数，则还是无解。

否则，记录一轮操作中x的最大值以及一轮操作过后x的增量。根据这两个数以及m就可以算出对应的轮数。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;

int T,n,i,flag;
int a[N];
LL m,x,Ans,up,y;

IL LL Max(LL a,LL b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL LL Work(LL p){
    reg int i=0;
    LL x=p;
    for (i=1;i<=n;i++){
        x+=a[i];
        if (x<0)    x=0,flag=1;
        up=Max(up,x);
    }
    return x;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();   scanf("%lld",&m);
        for (i=1;i<=n;i++)  a[i]=read();

        up=0;   flag=0; x=Work(0);
        if (up>=m){
            puts("1");  continue;
        }
        if (x==0){
            puts("-1"); continue;
        }
        if (!flag){
            printf("%lld\n",(m-up+x-1)/x+1);    continue;
        }
        // 1 Round

        flag=0; up=0;   y=Work(x);
        if (up>=m){
            puts("2");  continue;
        }
        if (y==0 || y==x || flag){
            puts("-1"); continue;
        }
        printf("%lld\n",(m-up+y-x-1)/(y-x)+2);
    }
    return 0;
}

[E] 水题

题意

给出一个1-n​的排列，一开始是有序的。接下来可能会等概率挑选出两个位置，并将这两个位置的数交换。交换可能进行3n次也可能进行7n次。

现在给出操作后的排列，问具体进行了几次。

题解

本场比赛最大的玄学题。

一开始的思路是先模拟计算出逆序对数的均值，然后看给出数列和哪个较为接近。

实际上从期望的角度出发，3n次操作后还位于原来位置的数的个数是超过\frac{n}{1000}的，直接根据这个判断就行。

代码

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<ctime>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 100000);

int n,i,j,T;
int a[N],b[N];
LL Ans,p,q;
unsigned long long x,y;

IL LL Abs(LL x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void Merge(int low,int high){
/*  reg int q=low,mid=(low+high)>>1,w=0,e=low,i=0;
    if (low>=high)  return;
    Merge(low,mid); Merge(mid+1,high);
    w=mid+1;
    while (q<=mid && w<=high){
        if (a[q]<=a[w]) b[e++]=a[q++];
        else {
            Ans+=mid-q+1;
            b[e++]=a[w++];
        }
    }
    while (q<=mid)  b[e++]=a[q++];
    while (w<=high) b[e++]=a[w++];
    for (i=low;i<=high;i++) a[i]=b[i];*/

    reg int i=0;
    for (i=1;i<=n;i++)  Ans+=Abs(a[i]-i);
}

IL int Rand(){
    return dis(gen);
}

IL void Ready(){
    reg int i=0,j=0;
    Ans=0;
    for (i=1;i<=n;i++)  a[i]=i;
    for (i=1;i<=3*n;i++){
        x = Rand(); x%=n; x+=1;
        y = Rand(); y%=n; y+=1;
        Swap(a[x],a[y]);
    }
    Merge(1,n); p+=Ans;

    Ans=0;
    for (i=1;i<=n;i++)  a[i]=i;
    for (i=1;i<=7*n;i++){
        x = Rand(); x%=n; x+=1;
        y = Rand(); y%=n; y+=1;
        Swap(a[x],a[y]);
    }
    Merge(1,n); q+=Ans;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    srand(time(NULL));

    T=read();
    while (T--){
        Ans=p=q=0;
        n=read(); //    Ready();
        for (i=1;i<=n;i++)  a[i]=read();

        Ans=0;
        for (i=1;i<=n;i++)  if (a[i]==i)    Ans++;
        if (Ans>n/1000) puts("First");
        else puts("Second");
    }
    return 0;
}

总结

这次比赛的参赛人数暴增，直接达到了快7000人，进而导致复赛门槛有所提高，需要 AC 两道题同时罚时要较少才能晋级复赛。题目难度相比昨天也有所提升。

可能是因为已经晋级的缘故，这一场打的很欢乐，中间一直认为是随机数没有造好才过不了E，一直在尝试不同的写法，于是就吃了8个罚时。还有一道人均会做的C题没有特别好的思路，感觉是欧拉回路加奇奇怪怪的连通性判断？

有个小插曲是，后面的垃圾时间看了一眼比赛官方群，居然还没有禁言，很多人贴脸讨论题解，有人提议禁言管理员还说需要反馈一下...这管理水平和组织比赛的经验真是不敢恭维，活久见了。

声明: 本文采用 BY-NC-SA 协议进行授权，如无注明均为原创，转载请注明转自 Marvolo
本文地址: 2021 百度之星大赛初赛第二场题解
数学 贪心
说点什么
登录
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...