21华为云挑战赛部分题解

1001.对象存储调度问题

题解

经典的贪心问题，直接上代码。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>

int t;
int n, m;
std:: priority_queue<int> Q;
struct A
{
    int a, num;

    bool operator < (A c) const
    {
        if(a < c.a)
            return true;
        else if(a > c.a)
            return false;
        else
            return num < c.num;
    }
};
std:: set<A> S;

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        while(! Q.empty()) Q.pop();
        S.clear();

        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i ++)
        {
            int a;
            scanf("%d", &a);

            S.insert((A) {a, i});
        }
        for(int i = 1; i <= m; i ++)
        {
            int b;
            scanf("%d", &b);

            Q.push(b);
        }

        while(! Q.empty())
        {
            if(S.empty())
            {
                printf("Yes\n");

                break;
            }

            int b = Q.top();
            Q.pop();

            while(b)
            {
                auto it = S.upper_bound((A) {b, n + 1});

                if(it == S.begin())
                    break;
                else
                    it --, b -= it->a, S.erase(it);
            }

            if(S.empty())
            {
                printf("Yes\n");

                break;
            }
        }

        if(! S.empty()) printf("No\n");
    }

    return 0;
}

1002.卷业务模型分析

题目链接

题目大意

给定两个卷的业务模型特征，其中特征可以用一个长度为 m 的序列表示，记作 A1,A2。再给定一个卷的任务模型特征序列 B，保证这个序列是由两个给定的特征序列中的一个通过线性变换加上一定的随机抖动得来的。形式化地说，设 B 是由第 x 序列变换得来，则存在一组整数 k,b，使得对于 1∼m 中所有的 i, $| B[i] - (k \times A_{x}[i] + b)| \leq 10$，问这个 B 序列是由哪个已知的特征序列变换得来。T 组数据。

输入输出和数据范围

第一行一个正整数 T(1≤T≤1000)，表示数据组数。

对于每组数据：

第一行一个正整数 m(10≤m≤ $10^5$ )，表示卷业务模型序列的长度。

接下来两行，每行 m 个正整数 $A_{i, j}$ (i∈{1,2},j∈{1,2,⋯,m},1≤ $A_{i, j}$ ≤$10^6$)，表示给定的卷业务模型所对应的序列。

接下来一行 m 个正整数 B1,B2,⋯,$B_m$(1≤$B_i$≤106)，表示询问的卷任务序列。

保证所有数据的 ∑m≤5×$10^5$，除样例的其他数据保证所有的 $A_{i, j}$ 接近 [1,$10^6$] 内的均匀分布。

题解

一开始想的是用最小二乘法来直接求k，没过，然后又尝试让k上下波动10，还是没过，不知道为什么。

正解是我们枚举特征序列中B1, B2和由A1， A2变换后的$B_1^{‘}, B_2^{‘}$之间的差值，就可以确定出唯一的k和b（这里的A指的都是A1）

$A_1 \times k + b + y_1 = B_1$

$A_2 \times k + b + y_2 = B_2$

其中$y_1, y_2$就是我们枚举的差值范围是$(-10, 10)$，这样根据这条直线过$(A_1, B_1 - y_1), (A_2, B_2 - y_2)$就可以确定所有可能的k, b。再逐一检查其是否对$B_3, B_4, …, B_m$适用，如能找到任意一组k，b满足条件，则答案为1，否则为2

不过其实这样可能会有问题，就是如果$A_1 = A_2$，那么求k的时候就会出现分母为0的情况，但是题目好像没有卡这个。

代码如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

int t;
int m;
int a[100005], a1[100005], b[100005];

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        bool p = false;

        scanf("%d", &m);
        for(int i = 1; i <= m; i ++) scanf("%d", &a[i]);
        for(int i = 1; i <= m; i ++) scanf("%d", &a1[i]);
        for(int i = 1; i <= m; i ++) scanf("%d", &b[i]);

        for(int y1 = -10; y1 <= 10; y1 ++)
            for(int y2 = -10; y2 <= 10; y2 ++)
            {
                if(p) break;

                bool judge = true;

                int k = (b[1] + y1 - b[2] - y2) / (a[1] - a[2]);

                if(k * (a[1] - a[2]) != b[1] + y1 - b[2] - y2) continue;

                int d = b[1] + y1 - k * a[1];

                for(int i = 3; i <= m; i ++)
                    if(abs(k * a[i] + d - b[i]) > 10)
                    {
                        judge = false;

                        break;
                    }

                if(judge)
                {
                    printf("1\n");
                    p = true;

                    break;
                }
            }

        if(! p) printf("2\n");
    }

    return 0;
}

1003.CDN流量调度问题

题面

数据范围及输入输出

题解

看到题我有一个很显然的dp思路：设dp[i][j]表示前i - 1条线路已经处理完，现在处理第i条线路，总共用了j个额外的节点的最小代价，转移为

for(int i = 1; i <= n; i ++)
  for(int j = 0; j <= m; j ++)
    f[i][j] = 1e9;

for(int i = 1; i <= n; i ++)
  for(int j = 0; j <= m; j ++)
    for(int k = 0; k <= std:: min(j, t[i] - 1); k ++)
      f[i][j] = std:: min(f[i][j], f[i - 1][j - k] + a[i] / (k + 1) + bool(a[i] % (k + 1)));

但是这样写的话时间复杂度是$O(nm^2)$的，会t，所以考虑优化

从状态设计上来看，已经没有优化空间了，所以只能从转移上优化

由整除分块的知识可知， $\lceil \frac{a_i}{k_i} \rceil$最多只有$O(\sqrt{a_i})$种取值，取值相同的我们当然是选用$k_i$最小的

这样我们就可以在状态转移的k那一维进行优化，优化后时间复杂度为$O(nm\sqrt{a_i})$，可以通过

其实这个优化挺简单的，但是当时做的时候没有想到

整除分块的blog已经赶出来了，在数论tag

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>

int T;
int n, m;
int a[102], t[102];
int f[102][10004];

int main()
{
    scanf("%d", &T);
    while(T --)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
        for(int i = 1; i <= n; i ++) scanf("%d", &t[i]);

        for(int i = 1; i <= n; i ++)
            for(int j = 0; j <= m; j ++)
                f[i][j] = 1e9;

        for(int i = 1; i <= n; i ++)
        {
            int l = 1;

            while(l <= t[i])
            {
                int res = a[i] / l + bool(a[i] % l), r = t[i];
                if(res != 1) r = a[i] / (res - 1) + bool(a[i] % (res - 1)) - 1;

                //printf("%d - %d %d %d\n", i, l, r, res);

                int used = l - 1;
                for(int j = used; j <= m; j ++) f[i][j] = std:: min(f[i][j], f[i - 1][j - used] + res);

                l = r + 1;
            }
        }

        printf("%d\n", f[n][m]);
    }

    return 0;
}

1006.仓颉造数

题目链接

题目大意

给你两个正整数a, b. 初始你拥有两个有理数$\frac{a}{b}, \frac{b}{a}$, 之后你可以从你拥有的数中挑选出两个x, y，把它俩合成为 $\frac{x + y}{2}$ 或 $\frac{2}{x + y}$ ，问能不能在999999999999次操作之内合成1

数据范围

T组数据$1 \leq T \leq 400, 1 \leq a, b \leq10^9$

题解

读完题之后，可以判断这肯定是一道数学题，看一眼数据范围，应该是$O(1)$的算法， ~~然后就不会了~~

反正不看题解的话我是想不到的，那就直接放题解吧

代码

不上了

剩下的题

有空再说吧