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);
}