2022牛客多校第四场

2022/7/31 23:38:48

本文主要是介绍2022牛客多校第四场,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

2022牛客多校第四场

过程

开局顺利签到K,N,队友也做出A题,开场顺利。然后我看D,队友看C,D一开始陷入了三维树状数组的陷阱,耽误了时间,但之后立刻想到了正解,码完之后发现自己生成的数据和题目给的不一样,然后就开始坐牢了,队友在想题不想段思维,只剩我百思不得其解还冒险交了两发,实在是难蚌,最后一个半小时队友,心态崩了开看其他题,而队友在想C无果后将H过了后30min把D题A了,我一看代码,跟我一摸一样,这是为什么呢,哦,原来是我把随机数种子放到头文件了,把种子发到输入seed后就过了,蚌,第一见到这种写法的人确实不知道怎么使用,最后时间不够了,没有时间推L了,5题惨淡收场。

只能说我D确实是没绷住,确实是没想到能在这里出错,在牛客群里也有跟我同样问题的人,只能说这下稀奇古怪的题都见识过了,新奇的WA的手法也经历了,下次是不会再犯了。同时也觉得出题人好怪,这种随机种子只有C++能用,同时确实也没标清楚放哪里,不知道跟我遇到同样问题的队伍多不多,同时L也基本是道搜索引擎题,关于正多面体我想真正了解的人并不多。

最后总结是又把队友演了,演的角度越来越新奇,赛后看H也是个签到,L通过搜索引擎有时间也能推出来,只能说D又做了很多无意义的牢,下次应在前半场就把所有签到搞定,不能在签到上坐无意义的牢,同时应该加强队友间的沟通,有时第一次见还真不知道是哪里有问题。

题解

A

这种题有类似的套路,在m个选出的任务中,看看如果将两个相邻的位置互换,比较权值的变化,就可以知道这m个任务应该按什么顺序排序。然后对于从n个中选m个,可以用dp来解决,并且我们可以首先将n排好序,那m个即为从这n个中选出一个子序列。\(dp[i]\)表示已选择i个任务时可获得最大效率,转移方程\(dp[i]=max(dp[i],dp[i-1]*a[j].p+a[j].w)\),此时运用了类似秦九韶算法的思想,可减少时间复杂度,不过此时排序顺序应反向,因为第一个选的会乘最多的\(a[j].p\)

int n,m;
struct node{
    ll w;double p;
}a[maxn];
double ans[maxn];
bool cmp(node a,node b){return a.w+a.p*b.w<b.w+b.p*a.w;}
void solve(){
    cin>>n>>m;
    rep(i,1,n) cin>>a[i].w;
    rep(i,1,n) {
        double tmp;cin>>tmp;
        a[i].p=tmp/10000.0;
    }
    sort(a+1,a+1+n,cmp);
    rep(i,1,n){
        rpe(j,m,1){
            ans[j]=max(ans[j],ans[j-1]*a[i].p+a[i].w);
        }
    }
    printf("%.12lf\n",ans[m]);
}  

D

观察到职场要求\(a_i,b_i,c_i\)只有400,因此可将其看作立体坐标,对于人员能力\(x,y,z\),只要在\(x,y,z\)内这个小立体坐标内有职场可行即可,那么只需要知道\(x,y\)二位平面内最小的\(c_i\)即可,令\(dp[i][a][b]\)表示在第i家公司在IQ,EQ要求小于a,b时最小的AQ要求,预处理即可,然后每次询问O(n)枚举查询。
本题注意种子的使用方法,我看题目中在头文件下,我也粘到了头文件底下,然后就百思不得其解,坐大牢。

int n,q;
int seed;
int dp[11][402][402];
ll qpow(ll a,ll b){
    ll s=1;
    while(b){
        if(b&1) s=s*a%mod;
        b>>=1;a=a*a%mod;
    }
    return s;
}
void solve(){
    cin>>n>>q;
    rep(i,1,n){
        int m;cin>>m;
        rep(j,0,400) rep(l,0,400) dp[i][j][l]=inf;
        rep(j,1,m){
            int x,y,z;scanf("%d %d %d",&x,&y,&z);
            dp[i][x][y]=min(dp[i][x][y],z);
        }
        rep(j,1,400) 
            rep(l,1,400) 
                dp[i][j][l]=min(dp[i][j][l],min(dp[i][j-1][l],dp[i][j][l-1]));
    }
    cin>>seed;
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1,400);
    int lastans=0;
    ll ans=0;
    for (int i=1;i<=q;i++){
        int x=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
        int y=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
        int z=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
        int num=0;
        rep(j,1,n){
            if(dp[j][x][y]<=z) num++;
        }
        lastans=num;
        ans=(ans+1LL*num*qpow(seed,q-i)%mod)%mod;
    }
    printf("%lld\n",ans);
}

H

要周长最小,即长宽尽可能接近,那么直接从sqrt(面积)从大到小枚举,如果长款合法即输出,随后贪心的对于每一行进行填充,先用大的再用小的,输出坐标即可。同时注意输出坐标是严格按照直角坐标系的。

int n;
int cnt[maxn];
void solve(){
    cin>>n;
    ll sum=0;
    rep(i,1,n){
        sum+=i*(n-i+1);
        cnt[i]=(n-i+1);
    }
    int k,c;
    rpe(s,sqrt(sum),1){
        if(sum%s==0){
            k=s;c=sum/s;
            break;
        } 
    }
    printf("%d\n",(k+c)<<1);
    rep(i,1,k){
        int now=c,x=0;
        rpe(j,n,1){
            while(cnt[j]&&now>=j){
                now-=j;cnt[j]--;
                printf("%d %d %d %d\n",x,i-1,x+j,i);
                x+=j;
            }
        }
    }
}

K

题目等价于\((i-1)*10^k + x \equiv i\pmod{n},0\leq x<10^k\),那么从小到大枚举k,找到合适x即可,然后特判1时答案为0.

int n;
void solve(){
    cin>>n;
    ll sum=0;
    rep(i,1,n){
        ll tmp=10,num=0;
        while(1){
            num++;
            ll y=tmp*(i-1)%n;
            y=i-y;if(y<0) y+=n;
            if(y>=n) y=0;
            if(y>=0&&y<=tmp-1) break;
            tmp*=10;
        }
        sum+=num;
    }
    if(n!=1) cout<<sum<<endl;
    else puts("0");
}

L

给定正多面体的面数和边长,问该多面体是否存在,若存在则k次面心连线构成新的立方体后,求出新的立方体边长是多少。直接搜索引擎之只有5种正多面体,且正四面体与自己对偶,即面心相连构成新的立方体为正四面体,正六面体和正八面体互为对偶,正十二面体和正二十面体互为对偶,通过一些数学知识我们可以得知对偶后边长的对应关系,直接变化即可。

int n;
double a;
int k;
const double a6=1/sqrt(2);
const double a8=sqrt(2)/3;
const double a12=cos(PI/5)/(sin(PI/5)*sin(PI/5)*2.0);
const double a20=2*cos(PI/5)/3;
void solve(){
    cin>>n;
    cin>>a;
    cin>>k;
    
    if(n==4||n==6||n==8||n==20||n==12){
        if(n==4) {
            while(k--) a/=3.0;
            printf("possible %d %.12lf\n",n,a);
        }
        else if(n==6||n==8){
            while(k--){
                if(n==6) a*=a6,n=8;
                else a*=a8,n=6;
            }
            printf("possible %d %.12lf\n",n,a);
        }
        else if(n==12||n==20){
            while(k--){
                if(n==12) a*=a12,n=20;
                else a*=a20,n=12;
            }
            printf("possible %d %.12lf\n",n,a);
        }
    }
    else puts("impossible");
}

N

注意到1的总数不会减少,且当\(a\&b,a|b\)结果相同时a,b满足包含关系,即\(a\&b=b,a|b=a\)或者\(a\&b=a,a|b=b\),那么此时1富集起来,依次将所有1分配出去即可,随后统计方差,这里可能需要__int128,用快输输出。

int n;
int cnt[16];
ll sum=0;
vector<int>g;
void print(__int128 x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
__int128 gcd(__int128 a,__int128 b){
    if(!b) return a;
    return gcd(b,a%b);
}
void solve(){
    cin>>n;
    int tmp=0;
    rpe(i,15,0) cnt[i]=0;
    sum=0;g.clear();
    rep(i,1,n){
        cin>>tmp;sum+=tmp;
        rpe(j,15,0){
            if(tmp&(1<<j)) cnt[j]++;
        }
    }
    rep(i,1,n){
        int tmp=0;
        rpe(j,15,0){
            if(cnt[j]) tmp+=(1<<j),cnt[j]--;
        }
        g.pb(tmp);
    }
    __int128 num=0;
    for(auto x:g){
        __int128 tmp = 1LL*n*x - sum;
        num=num + tmp*tmp;
    }
    __int128 tep = 1LL*n*n*n;
    __int128 tt = gcd(num,tep);
    num/=tt;tep/=tt;
    if(num==0) tep=1;
    print(num);cout<<"/";print(tep);
}


这篇关于2022牛客多校第四场的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程