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

icpc多校牛客

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

D. Jobs (Easy Version)

题目描述

1

题目分析

这题就是说，有 $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 罚时，但是你看到运行错误你就知道是溢出了，而不是一脸懵逼不知道哪里出错了。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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

题目描述

2

题目分析

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

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

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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的标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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姐姐做出来的！

题目描述

3

题目分析

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

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

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

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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姐姐做出来的！

题目描述

4

题目分析

给定一个数组 $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}$ 。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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;
}

小结

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

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

文章作者:xia0ji233

发布时间:2022-07-30, 18:00:00

最后更新:2023-05-14, 21:56:08

原始链接:http://example.com/2022/07/30/WeilaiCup2022-4/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. D. Jobs (Easy Version)
    1. 1.1. 题目描述
    2. 1.2. 题目分析
    3. 1.3. 标程
  2. 2. H. Wall Builder II
    1. 2.1. 题目描述
    2. 2.2. 题目分析
    3. 2.3. 标程
    4. 2.4. sigma的题目分析
    5. 2.5. sigma的标程
  3. 3. K. NIO’s Sword
    1. 3.1. 题目描述
    2. 3.2. 题目分析
    3. 3.3. 标程
  4. 4. N. Particle Arts
    1. 4.1. 题目描述
    2. 4.2. 题目分析
    3. 4.3. 标程
  5. 5. 小结
|