"NIO Cup" 2022 Nioke Summer Multi-School Training Camp 4 ADHK Problem Solving

A-Task Computing

题目大意：
Given a sequence of tasks,需要选定ntasks and sort them,The efficiency of each task is equal to that of the current taskwThe value is multiplied by all previous tasksp值,That is, the efficiency of each task will be affected by the previously selected task.Find the maximum efficiency sum.

思路：
Simple dynamic programming problem,But the data needs to be sorted with greedy thinking.

贪心的策略是： for any two adjacent tasksx和y（假设x在y之前）,If the positions of the two are exchanged, the efficiency and the size can be increased,那就交换.
It is easier to compare the efficiency after the exchange,因为交换xy之后,task before the twopThe value product is constant,And after the twopvalue does not affect it,So it can be cancelled during the calculation,Finally, it can be simplified to compare sequencesxy和yx的效率和.

Dynamic programming transfer method：
Because the efficiency of the current task will be affected by the previous task,If will each casepIt is unlikely that the value will be recorded,Then we might as well insert each new task at the beginning,This way you don't have to consider the effects of previous tasks.Just multiply the original efficiency by the current taskpThe value is then added to the current taskw值即可.

dp[i][j]表示从任务[i, n]中选取了jmaximum efficiency of a task.
转移方程：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家公司的mThere are jobs available for candidatesIQ、EQ、AQrequirements of the three indicators,Only those who are not lower than the requirements of the three can enter the post.A person can be admitted to the company as long as they meet the requirements of a position,given to a personIQ、EQ、AQ,Find out how many companies this person can get hired by.1<=IQ、EQ、AQ<=400,n<=10

思路：
一种做法是kd树,Another approach to this simple version is a three-dimensional prefix sum
三维前缀和：

用cpm[i][j][k]表示是否有IQ、EQ、AQAt the same time not higher thani,j,k的岗位
A company corresponds to one bit in binary,1表示有,0表示没有
Then when entering the company'sIQ、EQ、AQ标准时,便将cpm[IQ][EQ][AQ]的对应位置1
Then use a three-layer loop to recurse from small to large
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]);
        }
    }
}
for each candidateIQ、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); //Place the company in the corresponding location1
        }
    }
    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

题目大意：
Given a number of bricks,The height of each brick is 1,长度在1~n之间,Make sure the bricks fit into a rectangular wall,Find the smallest wall perimeter.

思路：
Enumerates the height or length of the wall,Then judge whether the bricks can be placed just right.
The height and length should ensure that the total area of ​​the bricks can be divided and the length should be able to put down the longest turn,This can reduce a lot of unnecessary enumeration.

验证的方式： Each layer height records the length and sum of the currently placed bricks,Start with the longest brick,Every time you look for the height you can put down from the bottom up.

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

题目大意：
NIOinitial attack power(A)为0,要通过n层副本,第 i Layer copy requires attack power to meet A%n == i 才能通过,NIOYou can turn your attack power into A*10 + x (0<= x <=9),Ask for clearancenThe minimum number of times a tier copy needs to change the attack power.

思路：
对于第 i Close copy,The initial attack power can be regarded as i-1,Each change of attack power is equivalent to a commandA变成(A*10 + x)%n,那么对于每个 i ,枚举k,使得kIt suffices to satisfy the following formula

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

Explain why it is less than10^k 而不是10,Because this formula is a direct multiplication10的幂次,把每次乘10added from time to timex省略了（x₁*10^k-1、x₂*10^k-2 …x_k）,So as long as less than10^k ,to omitxAdd it back to meet the requirements.
要注意的是,当n==0时,直接输出1即可,for any non-negative integer modulo1都是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;
}