牛客多校第四场签到题题解

A Task Computing

题意：给定长度为 $nn$ 的序列 $\{(w_i,p_i)\}\backslash \{(w\_i,p\_i)\backslash \}$，从中选出 $mm$ 项并重新排列得到子序列 $\{a_1,a_2,\cdots ,a_m\}\backslash \{a\_1,a\_2,\backslash cdots,a\_m\backslash \}$，最大化 ${\displaystyle \sum _{i=1}^m{w}_{a_i}\prod _{j=1}^i{p}_{a_j}}\backslash displaystyle\; \backslash sum\_\{i=1\}^m\; w\_\{a\_i\}\; \backslash prod\_\{j=1\}^i\; p\_\{a\_j\}$。$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$，$m\le 20m\; \backslash leq\; 20$，$p_i\in [0.8,1.2]p\_i\; \backslash in\; [0.8,1.2]$。

解法：如果选出的元素给定为子序列 $\{(w_i,p_i)\}\backslash \{(w\_i,p\_i)\backslash \}$，考虑如何贪心。使用常见的相邻局部调整法证明贪心：交换相邻两个元素 $(w_i,p_i)(w\_i,p\_i)$ 与 $(w_{i+1},p_{i+1})(w\_\{i+1\},p\_\{i+1\})$，对最终答案的影响只会与 $w_{i}w\_\{i\}$ 与 $w_{i+1}w\_\{i+1\}$ 的系数有关。原始系数为 $a={\displaystyle w_i\prod _{j=1}^i{p}_j+w_{i+1}\prod _{j=1}^{i+1}{p}_j}a=\backslash displaystyle\; w\_i\backslash prod\_\{j=1\}^\{i\}\; p\_j+w\_\{i+1\}\backslash prod\_\{j=1\}^\{i+1\}p\_j$，改变后系数为 $b={\displaystyle \frac{w_{i+1}}{p_i}\prod _{j=1}^{i+1}{p}_j+w_i\prod _{j=1}^{i+1}{p}_j}b=\backslash displaystyle\; \backslash dfrac\{w\_\{i+1\}\}\{p\_i\}\backslash prod\_\{j=1\}^\{i+1\}\; p\_j+w\_\{i\}\backslash prod\_\{j=1\}^\{i+1\}p\_j$。令 ${\displaystyle a-b=\left(\prod _{j=1}^{i-1}{p}_j\right)(w_i{p}_i+w_{i+1}{p}_i{p}_{i+1}-w_{i+1}{p}_{i+1}-w_i{p}_i{p}_{i+1})>0}\backslash displaystyle\; a-b=\backslash left(\backslash prod\_\{j=1\}^\{i-1\}p\_j\backslash right)(w\_ip\_i+w\_\{i+1\}p\_ip\_\{i+1\}-w\_\{i+1\}p\_\{i+1\}-w\_ip\_ip\_\{i+1\})>0$，则 。因而贪心规则为 $w_i(p_{i+1}-1)w\_i(p\_\{i+1\}-1)$。

按照这一贪心排序，那么选择的元素必然按此顺序。为了便于计算，可以用秦九韶算法对上式进行倒序计算。设 $f_{i,j}f\_\{i,j\}$ 为倒序遍历到第 $ii$ 个元素，已经选择了 $jj$ 个元素的最大值，则有 $f_{i,j}\leftarrow \max (f_{i+1,j},f_{i+1,j-1}{p}_i+w_i)f\_\{i,j\}\; \backslash leftarrow\; \backslash max(f\_\{i+1,j\},f\_\{i+1,j-1\}p\_i+w\_i)$。总时间复杂度 $\mathcal{O}(n\log n+nm)\backslash mathcal\; O(n\; \backslash log\; n+nm)$。

#include <bits/stdc++.h>
using namespace std;
const long double inf = 1e12;
struct node
{
    long long w;
    long double p;
    bool operator<(const node &b)const
    {
        return w * (b.p - 1) < b.w * (p - 1);
    }
};
const int N = 100000;
node que[N + 5];
long double f[N + 5][25];
int main()
{
    int n, m, p;
    long long w;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n;i++)
        scanf("%lld", &que[i].w);
    for (int i = 1; i <= n;i++)
    {
        scanf("%d", &p);
        que[i].p = 1.0 * p / 10000;
    }
    sort(que + 1, que + n + 1);
    f[n + 1][0] = 0;
    for (int i = 1; i <= m; i++)
        f[n + 1][i] = -inf;
    for (int i = n; i >= 0; i--)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i + 1][j];
            if (j)
                f[i][j] = max(f[i][j], que[i].w + que[i].p * f[i + 1][j - 1]);
        }
    printf("%.12Lf\n", f[1][m]);
    return 0;
}

H Wall Builder II

题意：给定 $nn$，长度为 $1\times i1\backslash times\; i$ 的砖块有 $n-i+1n-i+1$ 个。现将这些砖拿来砌墙，不允许旋转（只能 $1\times i1\backslash times\; i$ 的放置）且要密铺，且要求砌成的墙为矩形，问这个大矩形的最小周长。$n\le 100n\; \backslash leq\; 100$。

解法：面积 ${\displaystyle S=\sum _{i=1}^{n}i(n-i+1)}\backslash displaystyle\; S=\backslash sum\_\{i=1\}^n\; i(n-i+1)$。因而枚举长宽 $h,wh,w$，贪心的从大到小的将 $1\times w1\backslash times\; w$ 的区域填砖块，填满 $hh$ 次即可。可以证明这样贪心对 $n\le 100n\; \backslash leq\; 100$ 成立。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        int s = 0;
        for (int i = 1; i <= n;i++)
            s += i * (n - i + 1);
        vector<pair<pair<int, int>, pair<int, int>>> put;
        function<bool(int, int)> check = [&](int w, int h)
        {
            put.clear();
            vector<int> cnt(n + 1);
            for (int i = 1; i <= n;i++)
                cnt[i] = n - i + 1;
            for (int times = 0; times < h; times++)
            {
                int last = w;
                while(last)
                {
                    bool flag = 0;
                    for (int j = min(n, last); j >= 1;j--)
                        if(cnt[j])
                        {
                            put.emplace_back(make_pair(times, w - last), make_pair(times + 1, w - last + j));
                            flag = 1;
                            last -= j;
                            cnt[j]--;
                            break;
                        }
                    if (!flag)
                        return false;
                }
            }
            return true;
        };
        int ans = 0;
        for (int i = sqrt(s); i >= 1;i--)
            if (s % i == 0 && (check(i, s / i) || check(s / i, i)))
            {
                ans = 2 * (i + s / i);
                break;
            }
        printf("%d\n", ans);
        for (auto i : put)
            printf("%d %d %d %d\n", i.first.second, i.first.first, i.second.second, i.second.first);
    }
    return 0;
}

K NIO's Sword

题意：初始 $x=0x=0$，给定 $nn$，每次执行操作 $x\leftarrow 10x+Ax\; \backslash leftarrow\; 10x+A$，$A\in [0,9]A\; \backslash in\; [0,9]$，问使 $x\mathrm{m}\mathrm{o}\mathrm{d}nx\; \backslash bmod\; n$ 从 $11$ 依次变化到 $nn$ 需要最少执行几次操作。$n\le 1\times 10^{6}n\; \backslash leq\; 1\backslash times\; 10^6$。

解法：从 $ii$ 到 $i+1i+1$ 有 $10^{k}i+y\equiv i+1(\mathrm{m}\mathrm{o}\mathrm{d}n)10^ki+y\; \backslash equiv\; i+1\; \backslash pmod\; n$，其中 ，$kk$ 为操作次数。因而 $y\equiv i(1-10^k)+1(\mathrm{m}\mathrm{o}\mathrm{d}n)y\; \backslash equiv\; i(1-10^k)+1\; \backslash pmod\; n$。因而枚举 $kk$ 即可。注意 $n=1n=1$ 时答案为 $00$。

#include <bits/stdc++.h>
using namespace std;
long long th[20];
int main()
{
    th[0] = 1;
    for (int i = 1; i < 20;i++)
        th[i] = th[i - 1] * 10;
    int n;
    scanf("%d", &n);
    long long ans = 0;
    for (int i = 0; i < n;i++)
        for (int j = 0;;j++)
        {
            long long x = (1 - (th[j] - 1) * i % n + n) % n;
            if (x < th[j])
            {
                ans += j;
                break;
            }
        }
    printf("%lld", ans);
    return 0;
}

L Black Hole

题意：给定初始正 $nn$ 面体和棱长，每次将其面心相连构成新正多面体，进行 $kk$ 次，问最终是几面体、棱长多少。$n\le 200n\; \backslash leq\; 200$，$k\le 20k\; \backslash leq\; 20$，$a\le 1000a\; \backslash leq\; 1000$。

解法：只有五种正多面体：正四、六、八、十二、二十面体。这种变化规律下，四面体还是四面体，正六、八面体互换，正十二、二十面体互换。这是因为正六面体有 $88$ 个顶点，正八面体有 $66$ 个顶点，正十二面体有 $2020$ 个顶点，正二十面体有 $1212$ 个顶点。

正四面体内缩之后边长变为 ${\displaystyle \frac{a}{3}}\backslash dfrac\{a\}\{3\}$，正六面体内缩后边长变为 ${\displaystyle \frac{a}{\sqrt{2}}}\backslash dfrac\{a\}\{\backslash sqrt\; 2\}$，正八面体内缩后边长变为 ${\displaystyle \frac{\sqrt{2}a}{3}}\backslash dfrac\{\backslash sqrt\; 2a\}\{3\}$。

对于正十二面体，每个面为正五边形。考虑面心到棱的距离为 $h={\displaystyle \frac{a}{2}}\tan 54^{\circ }h=\backslash dfrac\{a\}\{2\}\; \backslash tan\; 54^\backslash circ$，两个面的二面角为 $\theta =2\arctan (\varphi +1)=2\arcsin \sqrt{{\displaystyle \frac{2}{5-\sqrt{5}}}}\backslash theta=2\backslash arctan(\backslash phi+1)=2\backslash arcsin\; \backslash sqrt\{\backslash dfrac\{2\}\{5-\backslash sqrt\; 5\}\}$，其中 $\varphi ={\displaystyle \frac{\sqrt{5}-1}{2}}\backslash phi=\backslash dfrac\{\backslash sqrt\; 5-1\}\{2\}$，则面心距离为新的棱长，为 $2h\sin {\displaystyle \frac{\theta }{2}}=a\tan 54^{\circ }\sqrt{{\displaystyle \frac{2}{5-\sqrt{5}}}}2h\; \backslash sin\; \backslash dfrac\{\backslash theta\}\{2\}=a\; \backslash tan\; 54^\backslash circ\; \backslash sqrt\{\backslash dfrac\{2\}\{5-\backslash sqrt\; 5\}\}$。

对于正二十面体，每个面为等边三角形。面心到棱长距离 $h={\displaystyle \frac{a}{2\sqrt{3}}}h=\backslash dfrac\{a\}\{2\backslash sqrt\; 3\}$，两个面二面角为 $\theta =2\arctan (\varphi +2)=2\arcsin {\displaystyle \frac{1+\sqrt{5}}{2\sqrt{3}}}\backslash theta=2\backslash arctan(\backslash phi+2)=2\backslash arcsin\; \backslash dfrac\{1+\backslash sqrt\; 5\}\{2\backslash sqrt\; 3\}$，因而面心距 $2h\sin {\displaystyle \frac{\theta }{2}}={\displaystyle \frac{a(1+\sqrt{5})}{6}}2h\backslash sin\; \backslash dfrac\{\backslash theta\}\{2\}=\backslash dfrac\{a(1+\backslash sqrt\; 5)\}\{6\}$。

#include <bits/stdc++.h>

using namespace std;
const int N = 205;
using db = double;
const db phi = (sqrt(5) - 1) / 2, pi = acos(-1);
int n, k, T[N];
db calc(db a, int t) {
    switch (t) {
    case 4: return a / 3;
    case 6: return a / sqrt(2);
    case 8: return a * sqrt(2) / 3;
    case 12: return a * tan(54 * pi / 180) * sin(atan(phi + 1));
    case 20: return a / sqrt(3) * sin(atan(phi + 2));
    }
    return -1;
}
void Solve() {
    db a;
    scanf("%d%lf%d", &n, &a, &k);
    if (!T[n]) return puts("impossible"), void();
    while (k--) a = calc(a, n), n = T[n];
    printf("possible %d %.12lf\n", n, a);
}
int main() {
    int t = 1;
    T[4] = 4, T[6] = 8, T[8] = 6, T[12] = 20, T[20] = 12;
    scanf("%d", &t);
    while (t--) Solve();
    return 0;
}

N Particle Arts

题意：给定序列 $\{a_n\}\backslash \{a\_n\backslash \}$，可以执行无穷多次操作：选定两个数字 $a_i,a_{j}a\_i,a\_j$，然后 ，$a_j\leftarrow a_i\mathrm{\mid }{a}_{j}a\_j\; \backslash leftarrow\; a\_i\; |\; a\_j$，问最大方差。$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$，$a_i\le 2^{15}a\_i\; \backslash leq\; 2^\{15\}$。

解法：，因而 $\sigma \backslash sigma$ 不变。当 $\mu \backslash mu$ 最大时一定是数字差距最大的。因而对于每一位分开考虑，若第 $ii$ 位上有 $kk$ 个 $11$ 则把最大的 $kk$ 个数字加上 $2^{i}2^i$，这样得到新序列 $\{b_n\}\backslash \{b\_n\backslash \}$。然后根据公式计算 ${\displaystyle \mu =\frac{1}{n^3}\sum _{i=1}^n{(n{b}_i-\sum _{j=1}^n{b}_j)}^2}\backslash displaystyle\; \backslash mu=\backslash dfrac\{1\}\{n^3\}\backslash sum\_\{i=1\}^n\; \backslash left(nb\_i-\backslash sum\_\{j=1\}^n\; b\_j\backslash right)^2$ 即可。注意计算过程中会爆 long long，需要使用 int_128。

#include <bits/stdc++.h>
using namespace std;
void print(__int128_t x)
{
    string s;
    while(x)
    {
        s += x % 10 + 48;
        x /= 10;
    }
    if(s.empty())
        s += "0";
    reverse(s.begin(), s.end());
    cout << s;
}
int main()
{
    int n;
    scanf("%d", &n);
    vector<long long> a(n);
    long long sum = 0;
    for (int i = 0; i < n;i++)
    {
        scanf("%lld", &a[i]);
        sum += a[i];
    }
    vector<int> times(21, 0);
    for (auto i : a)
        for (int j = 0; j <= 20;j++)
            if (i & (1 << j))
                times[j]++;
    for (auto &i : a)
        i = 0;
    for (int i = 0; i <= 20;i++)
        for (int j = 0; j < times[i];j++)
            a[j] |= 1ll << i;
    __int128_t ans = 0;
    for (int i = 0; i < n;i++)
    {
        __int128_t now = a[i] * n - sum;
        ans += now * now;
    }
    __int128_t x = ans, y = (__int128_t)n * n * n;
    __int128_t g = __gcd(x, y);
    print(x / g);
    printf("/");
    print(y / g);
    return 0;
}