当前位置：网站首页>“蔚来杯“2022牛客暑期多校训练营4 ADHK题解

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

2022-08-10 23:46:00 【Shanhj】

A-Task Computing

题目大意：
给定一系列任务，需要选定n个任务并进行排序，每个任务的效率等于当前任务的w值乘上之前所有任务的p值，也就是每个任务的效率都会受到之前所选任务的影响。求出最大的效率和。

思路：
比较简单的动态规划题，但是需要用贪心思想对数据进行排序。

贪心的策略是： 对于任意两个相邻的任务x和y（假设x在y之前），如果交换二者的位置可以使得效率和变大，那就交换。
比较交换后的效率是比较容易的，因为交换xy之后，在二者之前任务的p值乘积是不变的，而二者之后的p值又不会对其产生影响，所以在计算过程中可以相消，最后就可以化简为比较序列xy和yx的效率和。

动态规划转移方式：
因为当前任务的效率会受到之前任务的影响，如果将每种情况的p值记录下来又不太可能，那么我们不妨将每次新的任务插入到开头，这样就不用考虑之前任务的影响了。只要将原来的效率乘上当前任务的p值后再加上当前任务的w值即可。

dp[i][j]表示从任务[i, n]中选取了j个任务的最大效率和。
转移方程：dp[i][j] = max(dp[i][j], dp[i+1][j-1]*p[i] + w[i])

AC代码：

#include <bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;

struct task
{
    
    double w, q;
} t[N];

int n, m;
double dp[N][21];
bool cmp(task a, task b) {
     return (a.w + a.q * b.w - b.w - b.q * a.w) > 0; }

signed main()
{
    
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> t[i].w;
    for (int i = 1; i <= n; i++)
    {
    
        cin >> t[i].q;
        t[i].q /= 10000.0;
    }
    sort(t, t + n, cmp);
    dp[n][0] = 0;
    dp[n][1] = t[n].w;
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= min(m, n - i); j++)
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - 1] * t[i].q + t[i].w);
    printf("%.8lf", dp[1][m]);
    return 0;
}

D-Jobs (Easy Version)

题目大意： n家公司的m个职位对应聘者有IQ、EQ、AQ三个指标的要求，只有三者都不低于要求者才可以入岗。一个人只要符合一个职位的要求即可被这家公司录取，给出一个人的IQ、EQ、AQ，求出这个人能被多少家公司录取。1<=IQ、EQ、AQ<=400，n<=10

思路：
一种做法是kd树，另一种针对该简单版本的做法是三维前缀和
三维前缀和：

用cpm[i][j][k]表示是否有IQ、EQ、AQ同时不高于i，j，k的岗位
一个公司对应二进制中的一位，1表示有，0表示没有
那么当输入公司的IQ、EQ、AQ标准时，便将cpm[IQ][EQ][AQ]的对应位置1
然后用一个三层循环从小往大递推
for (int i = 1; i <= 400; i++)
{
    for (int j = 1; j <= 400; j++)
    {
        for (int k = 1; k <= 400; k++)
        {
            cpn[i][j][k] |= (cpn[i][j][k - 1]);
            cpn[i][j][k] |= (cpn[i][j - 1][k]);
            cpn[i][j][k] |= (cpn[i - 1][j][k]);
        }
    }
}
对于每位应聘者的IQ、EQ、AQ，查询cpm[IQ][EQ][AQ]中1的位数即可。

AC代码：

#include <bits/stdc++.h>
#define int long long
const long long mod = 998244353;
const int N = 1e5 + 5;
using namespace std;
inline int read()
{
    
    char c = getchar();
    int x = 0, s = 1;
    while (c < '0' || c > '9')
    {
    
        if (c == '-') s = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
    
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * s;
}
int n, q, m[11];
int I, E, A;
int lastans = 0;

long long ans = 0;
long long f[2000005];
unsigned short cpn[401][401][401];

void solve()
{
    
    lastans = 0;
    for (int i = 0; i < n; i++)
        if (cpn[I][E][A] & (1 << i)) lastans++;
}
signed main()
{
    
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    memset(cpn, 0, sizeof(cpn));
    int seed, iq, eq, aq;
    n = read();
    q = read();
    for (int i = 0; i < n; i++)
    {
    
        m[i] = read();
        for (int j = 0; j < m[i]; j++)
        {
    
            iq = read();
            eq = read();
            aq = read();
            cpn[iq][eq][aq] |= (1 << i); //将公司对应的位置1
        }
    }
    for (int i = 1; i <= 400; i++)
    {
    
        for (int j = 1; j <= 400; j++)
        {
    
            for (int k = 1; k <= 400; k++)
            {
    
                cpn[i][j][k] |= (cpn[i][j][k - 1]);
                cpn[i][j][k] |= (cpn[i][j - 1][k]);
                cpn[i][j][k] |= (cpn[i - 1][j][k]);
            }
        }
    }
    seed = read();
    f[0] = 1;
    for (int i = 1; i <= q; i++)
        f[i] = (f[i - 1] * seed) % mod;
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1, 400);
    for (int i = 1; i <= q; i++)
    {
    
        I = (u(rng) ^ lastans) % 400 + 1; // The IQ of the i-th friend
        E = (u(rng) ^ lastans) % 400 + 1; // The EQ of the i-th friend
        A = (u(rng) ^ lastans) % 400 + 1; // The AQ of the i-th friend
        solve();
        ans = (ans + lastans * f[q - i]) % mod;
    }
    cout << ans;
    return 0;
}

H-Wall Builder II

题目大意：
给定若干块砖，每块砖的高度为1，长度在1~n之间，要使得这些砖块能正好拼成一面矩形的墙，求出最小的墙周长。

思路：
枚举墙的高度或者长度，然后判断砖块能不能正好放得下即可。
高度和长度要保证能整除砖块的总面积以及长度要能够放下最长的转，这样就可以减少很多不必要的枚举了。

验证的方式： 每层高度都记录当前已放置砖块的长度和，从最长的砖块开始放，每次从下往上找还能放得下的高度。

AC代码：

#include <bits/stdc++.h>
const int inf = 1e9 + 7;
const int N = 2e7 + 5;
using namespace std;
int T, n, sum, ans, h, w, ansh, answ;
int len[N];
vector<int> v1, v2;
bool check()
{
    
    for (int i = 1; i <= h; i++)
        len[i] = 0;
    v1.clear();
    for (int i = 1; i <= n; i++)
    {
    
        int brick = n - i + 1;
        for (int j = 1; j <= i; j++)
        {
    
            bool flag = 0;
            for (int k = 1; k <= h; k++)
            {
    
                if (len[k] + brick <= w)
                {
    
                    flag = 1;
                    v1.push_back(len[k]);
                    v1.push_back(k - 1);
                    len[k] += brick;
                    v1.push_back(len[k]);
                    v1.push_back(k);
                    break;
                }
            }
            if (!flag) return 0;
        }
    }
    return 1;
}

signed main()
{
    
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
    
        cin >> n;
        sum = 0;
        ans = inf;
        for (int i = 1; i <= n; i++)
            sum += i * (n - i + 1);
        for (h = sum / n; h >= 1; h--)
        {
    
            if (sum % h) continue;
            w = sum / h;
            if (check() && h + w < ans)
            {
    
                ans = h + w;
                v2 = v1;
            }
        }
        cout << ans * 2 << "\n";
        for (int i = 0; i < v2.size(); i += 4)
            cout << v2[i] << " " << v2[i + 1] << " " << v2[i + 2] << " " << v2[i + 3] << "\n";
    }
    return 0;
}

K-NIO’s Sword

题目大意：
NIO的初始攻击力(A)为0，要通过n层副本，第 i 层副本需要攻击力满足 A%n == i 才能通过，NIO可以让自己的攻击力变成 A*10 + x (0<= x <=9)，求出要通关n层副本需要改变攻击力的最少次数。

思路：
对于第 i 关副本，可以将初始攻击力视为i-1，每次改变攻击力相当于令A变成(A*10 + x)%n，那么对于每个 i ，枚举k，使得k满足以下式子即可

(i - p[k] * (i - 1) % n + n) % n) < p[k] //p[k]==10^k

解释一下为什么要小于10k 而不是10，因为这个式子里是直接乘10的幂次，把每次乘10时加的x省略了（x1*10k-1、x2*10k-2 …xk），因此只要小于10k ，把省略的x加回去就可以达到要求。
要注意的是，当n==0时，直接输出1即可，因为任何非负整数模1都是0。

AC代码：

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    
    long long n, ans = 0, p[20];
    cin >> n;
    if (n == 1)
        cout << "0";
    else
    {
    
        p[0] = 1;
        for (long long i = 1; i < 20; i++)
            p[i] = p[i - 1] * 10;
        for (long long i = 1; i <= n; i++)
        {
    
            for (long long k = 1;; k++)
            {
    
                if (((i - p[k] * (i - 1) % n + n) % n) < p[k])
                {
    
                    ans += k;
                    break;
                }
            }
        }
        cout << ans;
    }

    return 0;
}
原网站

版权声明
本文为[Shanhj]所创，转载请带上原文链接，感谢
https://blog.csdn.net/Shanhj/article/details/126233457

边栏推荐

猜你喜欢

随机推荐