蔚来杯2022牛客暑期多校训练营4

比赛链接

A

题解

知识点：贪心，背包dp。

注意到交换邻项不影响其他的结果，可以通过邻项交换证明选择顺序，假设a在b前更优：

Σ+waΠ+wbpaΠ+Σ′≥Σ+wbΠ+wapbΠ+Σ′wa+wbpa≥wb+wapbwa1−pa≥wb1−pb

发现排序性质只和自己有关，显然具有传递性，因此以此排序。

但这只是确定了选择的顺序，即一个序列中元素应当出现的顺序，并不是指前 m 个是最优的序列，因此需要通过背包dp，f[i][j] 表示考虑到第 i 个服务器，已经选了 j 个。

题目虽然要求我们必须选 m 个，但由于收益全是正的，所以不需要初始化负无穷。

因为在背包收益计算中如果正着选则需要记录前面选择的所有 p 值累乘，很不方便。而倒着选，可以通过整体乘法给选好的都乘上这次选的 p ，非常方便。

时间复杂度 O(n(m+logn))

空间复杂度 O(n+m)

代码

#include 
#define ll long long
 
using namespace std;
 
struct node {
    ll w, p;
}a[100007];
 
double f[27];
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i].w;
    for (int i = 1;i <= n;i++) cin >> a[i].p;
    sort(a + 1, a + 1 + n, [&](node a, node b) {
        return a.w * 10000 + b.w * a.p > b.w * 10000 + a.w * b.p;
    });///排的是选择的相对顺序，即如果选了a和b，则a在前比b在前更优的条件，而非前m个一定最优，最优子序列需要dp
 
    //for (int i = 1;i <= n;i++) cout << a[i].w << ' ' << a[i].p << '\n';
    for (int i = n;i >= 1;i--) {///倒着选，因为要累乘
        for (int j = m;j >= 1;j--) {
            f[j] = max(f[j], f[j - 1] * a[i].p / 10000.0 + a[i].w);
        }
    }
    cout << fixed << setprecision(7) << f[m] << '\n';
    return 0;
}
折叠 

D

题解

方法一

知识点：枚举，前缀和。

题目强制在线，卡掉了一些离线算法，此时还有一些如树套树，K-D树等结构可用（但我不会wwwwww。本题我用了较简单的方法。

dp[i][j] 代表IQ为 i ，EQ为 j 时需要满足的最小AQ。对于一个公司，把每个工作记录，通过 min(dp[a][b],c) 更新给出IQ,EQ的最低AQ。再通过递推式：min(dp[i-1][j],dp[i][j]) ，min(dp[i][j-1],dp[i][j]) 遍历状态空间，更新所有IQ,EQ的最低AQ。

时间复杂度 O(Σm+n⋅4002+nq)

空间复杂度 O(n⋅4002)

方法二

知识点：枚举，前缀和。

bs[i][j][k] 表示IQ,EQ,AQ时可以。因此有递推式： bs[id][i][j][k] = bs[id][i][j][k] | bs[id][i - 1][j][k] | bs[id][i][j - 1][k] | bs[id][i][j][k - 1] 。

注意常数。

时间复杂度 O(Σm+n⋅4003+nq)

空间复杂度 O(n⋅4003)

代码

方法一

#include 
#include 
 
using namespace std;
 
const int mod = 998244353;
int dp[17][407][407];///第id家公司，当IQ为i，EQ为j的能入职的最小AQ
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    memset(dp, 0x3f, sizeof(dp));
    int n, q;
    cin >> n >> q;
    for (int id = 1;id <= n;id++) {
        int m;
        cin >> m;
        for (int i = 1;i <= m;i++) {///表示IQ>=a,EQ>=b的最小AQ
            int a, b, c;
            cin >> a >> b >> c;
            dp[id][a][b] = min(dp[id][a][b], c);
        }
        for (int i = 1;i <= 400;i++) {
            for (int j = 1;j <= 400;j++) {///发现有效区是一个向i,j,k方向展开的正方体，因此从坐标最小递推，取第三维能满足的最小值
                dp[id][i][j] = min(dp[id][i - 1][j], dp[id][i][j]);
                dp[id][i][j] = min(dp[id][i][j - 1], dp[id][i][j]);
            }
        }
    }
    int seed;
    cin >> seed;
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1, 400);
 
    int lastans = 0, ans = 0;
    for (int i = 1;i <= q;i++) {
        int IQ = (u(rng) ^ lastans) % 400 + 1;  // The IQ of the i-th friend
        int EQ = (u(rng) ^ lastans) % 400 + 1;  // The EQ of the i-th friend
        int AQ = (u(rng) ^ lastans) % 400 + 1;  // The AQ of the i-th friend
        lastans = 0;
        for (int i = 1;i <= n;i++)
            lastans += dp[i][IQ][EQ] <= AQ;  // The answer to the i-th friend
        ans = (1LL * ans * seed + lastans) % mod;
    }
    cout << ans << '\n';
    return 0;
}
折叠 

方法二

#include 
 
using namespace std;
 
const int mod = 998244353;
bitset<401> bs[11][401][401];///表示id公司，IQ = a,EQ = b,AQ = c时可以
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int id = 1;id <= n;id++) {
        int m;
        cin >> m;
        for (int i = 1;i <= m;i++) {///表示IQ = a,EQ = b,AQ = c时可以
            int a, b, c;
            cin >> a >> b >> c;
            bs[id][a][b][c] = 1;
        }
        for (int i = 1;i <= 400;i++)
            for (int j = 1;j <= 400;j++)
                for (int k = 1;k <= 400;k++)///正方体同上，因此从坐标最小递推，如果坐标小的满足那么这个也能满足
                    bs[id][i][j][k] = bs[id][i][j][k] | bs[id][i - 1][j][k] | bs[id][i][j - 1][k] | bs[id][i][j][k - 1];
    }
    int seed;
    cin >> seed;
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1, 400);
 
    int lastans = 0, ans = 0;
    for (int i = 1;i <= q;i++) {
        int IQ = (u(rng) ^ lastans) % 400 + 1;  // The IQ of the i-th friend
        int EQ = (u(rng) ^ lastans) % 400 + 1;  // The EQ of the i-th friend
        int AQ = (u(rng) ^ lastans) % 400 + 1;  // The AQ of the i-th friend
        lastans = 0;
        for (int i = 1;i <= n;i++)
            lastans += bs[i][IQ][EQ][AQ] == 1;  // The answer to the i-th friend
        ans = (1LL * ans * seed + lastans) % mod;
    }
    cout << ans << '\n';
    return 0;
}
折叠 

H

题解

知识点：枚举，贪心，STL。

先求出面积 S ，只需要枚举可能的长宽，在去检查这个长和宽的答案。对于一行，我们贪心地选择最接近剩余长度的砖块（类似sticks这题，剪枝好恶心qwq），过程中运用到 multiset 查找符合要求的砖块。

时间复杂度 O(n3)

空间复杂度 O(n2)

代码

#include 
#define ll long long
 
using namespace std;
 
int n, ans;
multiset<int> ms;
vector<pair<int, int>> tmp[207], path[207];///长度为i的方块坐标
 
 
void check(int w, int h) {
    ms.clear();
    for (int i = 1;i <= n;i++) tmp[i].clear();
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n - i + 1;j++) ms.insert(i);
    int rem = w;///剩余长度
    int hi = 0;///底部高度
    while (hi < h) {
        auto p = ms.upper_bound(rem);
        if (p == ms.begin()) return;
        int k = *prev(p);
        ms.erase(prev(p));///erase(type)是删掉某个元素全部,删掉一个要用指针
        tmp[k].push_back({ w - rem,hi });///左下角
        rem -= k;
        if (!rem) rem = w, hi++;
    }
    if (2 * (w + h) < ans) {
        ans = 2 * (w + h);
        for (int i = 1;i <= n;i++)
            path[i] = tmp[i];
    }
}
 
bool solve() {
    cin >> n;
    int S = 0;
    for (int i = 1;i <= n;i++) S += (n - i + 1) * i;
    ans = ~(1 << 31);
    for (int w = 1;w * w <= S;w++) {
        if (S % w == 0) {
            int h = S / w;
            check(h, w);
            check(w, h);
        }
    }
    cout << ans << '\n';
    for (int i = 1;i <= n;i++)
        for (auto j : path[i])
            cout << j.first << ' ' << j.second << ' ' << j.first + i << ' ' << j.second + 1 << '\n';
    return true;
}
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}
折叠 

K

题解

知识点：数论，枚举，思维。

首先特判 n=1 时，不需要任何操作。

当 n>1 时，假设有 A≡i−1 (mod n) ，经过 k (1≤k≤6) 次(因为不可能不操作，最多操作6次可以遍历最大的 n )做操作后有如下式：

10kA+x≡i (mod n)x≡i−10kA (mod n)

因此对每个 i 可以求出 x 最小正整数解，若 x<10k 则说明成立。

时间复杂度 O(n)

空间复杂度 O(1)

代码

#include 
#define ll long long
 
using namespace std;
 
int tb[10] = { 1,10,100,1000,10000,100000,1000000 };
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        int k;
        for (k = 1;k <= 6;k++) {
            int x = ((i - 1LL * tb[k] * (i - 1)) % n + n) % n;///可能负数所以先模再加再模
            if (x < tb[k]) break;
        }
        ans += k;
    }
    cout << ans << '\n';
    return 0;
}
/// x = i - 10^k(i-1)  (mod n)
折叠 

N

题解

知识点：位运算，思维，数学。

遍历输入数字的每位，最终得到每位一共有多少二进制 1 存在，随后尽可能组成最大的数（因为根据与和或运算最终一定能将二进制为集中起来），随后计算方差即可 。方差有如下公式：

1nn∑i=1(xi−μ)2=1n(n∑i=1x2i−2μn∑i=1xi+nμ2)=1n2(n∑i=1x2i−(n∑i=1xi)2)

这样分子分母可以分别用整数计算。

时间复杂度 O(n)

空间复杂度 O(n)

代码

#include 
#define ll long long
 
using namespace std;
 
int bit[20], a[100007];
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1, tmp;i <= n;i++) {///拆二进制
        cin >> tmp;
        for (int j = 0;j < 15;j++)
            if ((tmp >> j) & 1) bit[j]++;
    }
    for (int i = 1;i <= n;i++)///重组
        for (int j = 0;j < 15;j++)
            if (bit[j]) a[i] += 1 << j, bit[j]--;
    ll sum = 0, sum2 = 0;
    for (int i = 1;i <= n;i++) {
        sum += a[i];///虽然a&b + a|b = a+b，但为了好看在这里加
        sum2 += a[i] * a[i];
    }
    ///1/n^2 (n*sum2 - sum^2) = 方差
    ll x = n * sum2 - sum * sum;
    ll y = 1LL * n * n;
    ll d = __gcd(x, y);
    cout << x / d << '/' << y / d << '\n';
    return 0;
}
折叠