“蔚来杯“2022牛客暑期多校训练营4-N、K、D（待补）、H

N-Particle Arts

题面

输入样例

5
1 2 3 4 5
1
2

输出样例

54/5
1

---

题意

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

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

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

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

参考代码

#include 
#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;
}
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

K-NIO’s Sword

题面

输入样例

4
1

输出样例

4
1

样例解释

题意

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

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

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

参考代码

#include 
#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;
}
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

D-Jobs (Easy Version)

本题感恩由 xia0ji 在赛时解决出来的，翻译+思路都很清晰，贴个题解链接推荐移步！

H-Wall Builder II

题面

输入样例

4
1
2
3
4
1
2
3
4
5

输出样例

4
0 0 1 1
8
0 1 1 2
1 1 2 2
0 0 2 1
14
2 1 3 2
3 1 4 2
4 1 5 2
3 0 5 1
0 1 2 2
0 0 3 1
18
4 0 5 1
2 3 3 4
3 3 4 4
4 3 5 4
3 1 5 2
3 2 5 3
0 3 2 4
0 1 3 2
0 2 3 3
0 0 4 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

---

题意

当前拥有 $n$ 块长度为 $1$ ，$n-1$ 块长度为 $2$，$\dots$，$2$ 块长度为 $n-1$ ，$1$ 块长度为 $n$ 的砖头，且所有的砖头高度为 $1$ 。要求利用所有砖头铺成一个矩形（不能够竖放），求该矩形的最小周长及对应的摆放状态。

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

参考代码

#include 
#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;
}
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