“蔚来杯”2022牛客暑期多校训练营4题解

这把依然和 sigma 姐姐打这场多校。出了4题rank300多也还可以的，该罚坐的题还是罚坐，该做的也都做了。

D. Jobs (Easy Version)

题目描述

题目分析

这题就是说，有 $n$ 家公司，然后主人公有 $q$ 个朋友，每个公司有一定的职位，如果你至少符合一个公司的 $3Q(IQ,EQ,AQ)$ 要求，那么这家公司就会给你发 offer，然后问你这些朋友分别能拿多少 offer。这题防止读入量太大给你一个随机生成器去产生数据，最后还要求强制在线。

因为 3Q 的范围都比较小，然后当然我们就可以存一个最低的要求，因为我只用符合一个职位就可以了，我们最开始的想法是：开个数组：$dp[i][j][k][b]$ 表示第 $i$ 家公司 $IQ=j,EQ=k,AQ=b$ 能拿到多少职位。那么我们读入公司的职位要求然后先给当前点都 $+1$然后前缀以下，查询的时候只需要把相应的公司，3Q 输入下标查询是否为 0 即可，为 0 就说明没有 offer 嘛。

但是一算数据量发现编译器就阻拦住了，因此换一种思路，因为我们不需要知道一个人在一个公司能拿多少 offer 我们只关心拿没拿 offer，因此我们可以降维度去做。 $dp[i][j][k]$ 表示第 $i$ 家公司，$IQ=j,EQ=k$ 的情况下，能至少拿一个职位需要的最低 $AQ$。那么查询的时候我们只需要把 $i\ j\ k$ 给下标取出最低要求判断我的 $AQ$ 是否大于等于即可。然后就是抄随即发生器，在 $seed^{q-i}$ 可以写快速幂去算，最重要的一点：一定不要溢出，可以的话都开 long long 一定没事，或者为了提醒自己，时刻加上 assert(v>=0) 至少提交的时候虽然浪费 20 罚时，但是你看到运行错误你就知道是溢出了，而不是一脸懵逼不知道哪里出错了。

标程

#include<bits/stdc++.h>
#include<random>
#define maxn 200005
#define INF 0x3f3f3f3f
#define MOD 998244353
int seed;
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
int n,m;
int dp[10][401][401];
long long qpow(int base,int exp){
    long long ans=1;
    for(long long k=base;exp;exp>>=1){
        if(exp&1){
            ans=(ans*k)%MOD;
        }
        k=k*k%MOD;
    }
    return ans;
}
void solve(){
    scanf("%d%d",&n,&m);
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<n;i++){
        int num,IQ,EQ,AQ;
        scanf("%d",&num);
        for(int j=1;j<=num;j++){
            scanf("%d%d%d",&IQ,&EQ,&AQ);
            dp[i][IQ][EQ]=min(dp[i][IQ][EQ],AQ);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<=400;j++){
            for(int k=1;k<=400;k++){
                dp[i][j][k]=min(dp[i][j][k],min(dp[i][j][k-1],dp[i][j-1][k]));
            }
        }
    }
    scanf("%d",&seed);
    std::mt19937 rng(seed);
    std::uniform_int_distribution<>u(1,400);
    int lastans=0;
    long long qans=0;
    while(m--){
        int IQ=(u(rng)^lastans)%400+1;
        int EQ=(u(rng)^lastans)%400+1;
        int AQ=(u(rng)^lastans)%400+1;
        //printf("%d %d %d\n",IQ,EQ,AQ);
        int ans=0;
        for(int i=0;i<n;i++){
            if(dp[i][IQ][EQ]<=AQ){
                ans++;
            }
        }
        lastans=ans;
        qans+=lastans*qpow(seed,m);
        assert(qans>=0);
        qans%=MOD;
    }
    
    printf("%lld\n",qans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    //cin>>t;
    while(t--)solve();
    //printf("%d",qpow(2,591));
    
    
    return 0;
}

H. Wall Builder II

题目描述

题目分析

这题的话是赛时我和 sigma 都写出来了的题目。自己还交错几发亏了点罚时，因为没看到说一定要矩形，以为可以任意形状的。就是说给你高度为1的砖头，长度为 1 的有 $n$ 块，长度为 $2$ 的有 $n-1$ 块……长度为 $n$ 的有一块。

容易发现不管怎么放面积十肯定不会变的，那么就变成了我们以前聊到的话题：面积相同的情况下周长怎么最短。那就是长宽接近的时候，因为这题面积不大，所以我们直接 $sqrt$ 往后寻找最大的较小因数作为高度，然后面积/高得到宽度。因为砖头块高为 1，所以我们每一行每一行考虑，不难发现我们先放大的，最后放小的一定能放下。根据这个贪心策略我们就可以很容易写出这题，因为要按顺序输出方案，最后再把方案总结起来然后排个序输出即可。

标程

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int a[maxn];//,b[maxn];
char s[maxn];
int n,m;
int dp[maxn],sum1[maxn],sum2[maxn];
int num[maxn];
queue<int>q[maxn];
void push(int line,int length){
    if(length==0)return ;
    for(int i=min(length,n);i>=1;i--){
        if(num[i]){
            q[line].push(i);
            num[i]--;
            push(line,length-i);
            break;
        }
    }
}
struct pu{
    int x,y,x1,y1;
    bool operator <(const pu&a){
        return (x1-x)<(a.x1-a.x);
    }
}b[200005]; 

void solve(){
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=(n+1-i)*i;
        num[i]=n+1-i;
    }
    int k=(int)sqrt(ans);
    
    int width=0,height=0;
    for(int i=k;i>=1;i--){
        if(ans%i==0){
            printf("%d %d\n",i,ans/i);
            height=i;
            width=ans/i;
            break;
        }
    } 
    
    printf("%d\n",width*2+height*2);
    
    for(int i=1;i<=height;i++){
        //printf("%d %d\n",i,height);
        push(i,width);
    }
    
    int cnt=0;
    for(int i=1;i<=height;i++){
        int start=0;
        while(q[i].size()){
            int len=q[i].front();
            q[i].pop();
        //    printf("%d %d %d %d\n",);
            b[++cnt]={start,i-1,start+len,i};
            start+=len;
        }
    }
    sort(b+1,b+1+cnt);
    for(int i=1;i<=cnt;i++){
        printf("%d %d %d %d\n",b[i].x,b[i].y,b[i].x1,b[i].y1);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
    #endif
    int t=1;
    cin>>t;
    while(t--)solve();
    
    
    
    return 0;
}

sigma的题目分析

利用公式 $\frac{n * (n + 1) * (n + 2)}{6} $得到面积，当面积确定时，最接近 $sqrt(s)$ 的长宽为让周长最小的方案。将较长的边作为底边，按照长度从大到小枚举所有砖头的插入方案，倒序输出即可。

也贴一下sigma姐姐的博客链接

sigma的标程

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int len[N];

struct node {
    int x1, y1, x2, y2;
};

vector<node> ans;

void solve() {
    int n;
    cin >> n;
    int s = n * (n + 1) * (n + 2) / 6;
    ans.clear();
    if (n == 1) {
        cout << "4" << endl << "0 0 1 1" << endl;
        return;
    }

    int a = 0, b = 0;
    for (b = sqrt(s); b <= s; b++) {
        a = s / b;
        if (s % b == 0)
            break;
    }

    cout << 2 * (a + b) << endl;
    for (int i = 0; i <= b; i++) {
        len[i] = 0;
    }
    if (a > b)
        swap(a, b);

    for (int i = n; i >= 1; i--) {                //当前块的长度
        for (int j = 1; j <= n - i + 1; j++) {    //块数
            for (int lie = 1; lie <= a; lie++) {  //枚举每列
                if (b - len[lie] >= i) {
                    ans.push_back({len[lie], lie - 1, len[lie] + i, lie});
                    len[lie] += i;
                    break;
                }
            }
        }
    }

    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i].x1 << " " << ans[i].y1 << " " << ans[i].x2 << " "
             << ans[i].y2 << endl;
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

K. NIO’s Sword

sigma姐姐做出来的！

题目描述

题目分析

初始时攻击力为 $0$，每次可以任意在攻击力之后添加一个数字，仅有在攻击力模 $n$ 与 $i$ 同余时才能够击杀第 $i$ 个敌人，问需要的最少升级次数。

暴力跑结论公式即可，注意特判 $n=1$ 时的情况。

警惕开场 $10$ 分钟暴力猜结论输入什么输出什么，喜提罚时。

标程

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int now = 1;
        for (int j = 0; j <= N; j++) {
            if (((i - (i - 1) * (now % n) % n) % n + n) % n < now) {
                ans += j;
                break;
            }
            now = now * 10;
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
//     cin >> T;
    while (T--)
        solve();
    return 0;
}

N. Particle Arts

sigma姐姐做出来的！

题目描述

题目分析

给定一个数组 $n$，数组中的任意两个元素 $a,b$ 都可能产生碰撞，并形成两个新的元素 $a&b$ 和 $a|b$ ，而原先的元素 $a,b$ 将消失。求若干次后该数组趋近的稳定方差是多少。

容易得到样例中最后得到的数组应为： $0\ 0\ 1\ 7\ 7$ ，即对于原数组中所有元素各位上的 $1$，都优先全部分配给稳定数组中的同一位。

采用方差公式：$\frac{n\times psum-sum\times sum}{n\times n}$

其中 $n$ 为样本数，$sum=\sum_{i=1}^{n}{x_i}$ ， $psum=\sum_{i=1}^{n}{x_i^2}$ 。

标程

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 1e5 + 10;

int a[N], b[N], cnt[N];

void solve() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        for (int j = 0; j < 15; j++) {
            if ((a[i] >> j) & 1) {
                cnt[j]++;
            }
        }
    }

    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < 15; j++) {
            if (cnt[j]) {
                b[i] += (1 << j);
                cnt[j]--;
            }
        }
    }
    int ans = 0;
    int psum = 0;
    for (int i = 1; i <= n; i++) {
        psum += b[i] * b[i];
    }
    ans = n * psum - sum * sum;
    int ans2 = n * n;
    if (ans == 0) {
        cout << "0/1" << endl;
        return;
    }
    int gg = __gcd(ans, ans2);
    ans /= gg, ans2 /= gg;
    cout << ans << "/" << ans2 << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

小结

冲冲冲吧，今天还算不错的！