CF1490A Dense Array

题意

定义一个数组为“稠密的”当且仅当

\forall i

给定一个数组,求最少加几个数可以让其变得“稠密”

题解

注意到我们可以依次考虑相邻的两个元素 ab,假定 a > b。考虑需要加几个元素。首先对于 a \le 2b 是可以直接跳过的。接下来多写几个数字,找一下规律即可发现需要加的元素绝对与 \log_2\dfrac ab 是有关的。

可以开始写程序了,然后我们发现 \log_2\dfrac ab 是不对的,当 ab2^k(k\in\mathbb Z) 倍时答案会多出一个 1。所以考虑直接把 a 减去一个小实数(比如 0.1)就可了。

#include <cstdio>
#include <cctype>
#include <cmath>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}

int main()
{
    int T = read();
    while (T--)
    {
        double a[105];
        int n = read();
        FOR(i, 1, n)
            a[i] = read();
        int ans = 0;
        FOR(i, 1, n - 1)
        {
            int x = max(a[i], a[i + 1]), y = min(a[i], a[i + 1]);
            if (x <= (y << 1)) continue;
            ans += floor(log2((x - 0.1) / y));
        }
        printf("%d\n", ans);
    }
    return 0;
}

CF1490B Balanced Remainders

题意

给定一个序列 \lbrace a\rbrace,每次操作可以给序列中一个数加一,问最少操作多少次可以使 c_0 = c_1 = c_2,其中 c_k 表示序列中满足 a_i\bmod 3 = k 的元素个数。

题解

发现我们要的答案跟 a 没有任何关系,所以直接保存 c_{0,1,2} 就可以了。然后我们发现对于一次操作,如果待操作数 \bmod 3 的结果为 k,操作之后势必会使 c_k – 1c_{(k + 1)\bmod 3} + 1

注意到如上性质之后,会发现这个问题就是个裸的负载平衡问题,费用流即可。就可以愉快的贪心了。有一种贪心方法就是:

  • 找到大于 n/3 的任意一个 c_k
  • c_k 减一,c_{(k + 1)\bmod 3} 加一
  • 一直重复如上操作直到 c_0 = c_1 = c_2 = n / 3

正确性可以这样稍微 yy(我不会证明/kk):既然有大于 n/3c_k 那就必然有小于 n/3c_k,贪心进行的每次调整都会减少 c_k 并增加 c_{(k + 1)\bmod 3} 的值,相当于会让大于 n / 3 的变小,让小于 n / 3 的变大并且不会再让小于 n / 3 的再变小。调整若干次就能得到答案。

当然你要是像我一样在赛时想不到这个贪心,那就一起愉快费用流。建边的方式可以参考 P4016 的各个题解:不拆点,从 s 向每个点连容量为初始的 c_i 费用为 0 的边,对于可以执行操作的连容量无限费用为 1 的边,再从每个点向 t 连容量为 n/3 费用为 0 的边。跑最小费用最大流。最大流可以保证调整结果的正确性,最小费用可以最小化步数。

贪心的代码:

#include <cstdio>
#include <cctype>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int min(int a, int b) {return a < b ? a : b;}

int c[3];

int main()
{
    int T = read();
    while (T--)
    {
        int n = read();
        c[0] = c[1] = c[2] = 0;
        FOR(i, 1, n)
            ++c[read() % 3];
        int ans = 0;
        while (min(c[0], min(c[1], c[2])) != n / 3)
        {
            FOR(i, 0, 2)
            {
                if (c[i] > n / 3)
                {
                    ++ans;
                    --c[i], ++c[(i + 1) % 3];
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

费用流的由于是赛时写的,太丑了就不放了。

CF1490C Sum of Cubes

题意

T(T\le 100) 次询问一个整数 x(x\le 10^{12}) 是否可以拆分为两个正整数的立方和

题解

注意到 \sqrt[3]{10^{12}} 的值为 10^4,因此我们只需要考虑 10^4 个数的立方和是否能凑出 x。直接将这些数存进一个 std::set<long long> 然后从小到大枚举 a,看 x – a^3 在不在 set 中即可。时间复杂度为 O(Tx\log x),大概估算一下是 10^7 数量级的,能过。

然后其实对于这种时间比较宽裕的题尽量不要用 std::unordered_map,可能会被有心人利用 hash 的性质给 hack 掉,详见 Blowing up unordered_map, and how to stop getting hacked on it

std::set<int> cube;

signed main()
{
    int T = read();
    FOR(i, 1, 10000)
        cube.insert(i * i * i);
    while (T--)
    {
        int x = read();
        bool flag = 0;
        FOR(i, 1, 10000)
            if (cube.count(x - i * i * i))
            {
                flag = 1;
                break;
            }
        if (flag) YES;
        else NO;
    }
    return 0;
}

CF1490D Permutation Transformation

题意

将一个 1 – n 的排列按照如下规则建成一棵二叉树。

  • 找到最大元素,定为树根
  • 递归构建左子树
  • 递归构建右子树

并输出每个节点的深度(根的深度为 0

题解

数据范围 1\le n\le 100,所以根本不虚,直接大力按照题意模拟就可以了,构建 [l,r] 的时候找到最大值所在位置 k,更新 k 的深度,然后继续建 [l, k – 1][k + 1, r],详见代码。

void build(int i, int j, int d)
{
    if (i > j) return;
    int maxa = -1, pos;
    FOR(k, i, j)
        if (a[k] > maxa)
            maxa = a[k], pos = k;
    dep[pos] = d;
    build(i, pos - 1, d + 1);
    build(pos + 1, j, d + 1);
    return;
}

int main()
{
    int T = read();
    while (T--)
    {
        int n = read();
        FOR(i, 1, n)
            a[i] = read(), dep[i] = 0;
        build(1, n, 0);
        FOR(i, 1, n) printf("%d ", dep[i]);
        puts("");
    }
    return 0;
}

CF1490E Accidental Victory

题意

一场锦标赛中有 n 个选手,第 i 个选手一开始有 a_i 个 token。进行 n – 1 场比赛。每场比赛随机抽取两个 token 不为 0 的选手,token 大的一方为胜方,(token 相同则胜方随机选一个),胜方会拿走败方的所有 token。最后会产生一位冠军。

很明显,冠军是谁与每场比赛选取的选手有很大关系。升序输出有可能成为冠军的选手的编号。

题解

我们考虑一个选手如何能成为冠军。容易构造出一种方案:

  • 首先先跟所有 token 小于等于自己的选手打若干场然后作为胜方拿走他们的 token
  • 然后转战 token 大于自己的初始 token 的选手,从小往大打,如果能打得过所有选手他就成冠军

第一步肯定是能够实现的(除非是 token 垫底的那个选手),关键就在于他拿了所有比自己弱的选手的 token 之后能不能打得过那些比自己一开始强的选手。

考虑到这里,我们很自然的会先把所有选手按照 token 从小到大排个序再求一个前缀和。记排序过后的第 i 个选手的 token 为 b_i,前缀和为 s_i。不难发现如果 s_i \ge b_{i + 1} 的话这个选手就有机会打赢第 i + 1 个选手。然后他现在有的 token 即为 s_{i + 1}。看到这里“第 i 个选手能不能赢”的问题就已经被转化成了“第 i+1 个选手能不能赢”的问题了,不难归纳出如下结论:

如果第 i 个选手能成为冠军,并且 b_i \le s_{i – 1},那么第 i -1 个选手也能成为冠军。说明如果第 i 个选手没机会成为冠军,那么初始 token 比他低的也都没有机会了

所以直接建结构体排序就可以了。

如果你 WA on test 3,就像我在比赛过程中一样,大概率你没有long long

int sum[maxn];

struct node
{
    int val, id;
    node(){}
    node(int v, int i) {val = v, id = i;}
} a[maxn];

bool cmp1(node a, node b)
{
    return a.val < b.val;
}

bool cmp2(node a, node b)
{
    return a.id < b.id;
}

signed main()
{
    int T = read();
    while (T--)
    {
        int n = read();
        FOR(i, 1, n) a[i].val = read(), a[i].id = i;
        std::sort(a + 1, a + 1 + n, cmp1);//按照 token 值排序
        FOR(i, 1, n) sum[i] = sum[i - 1] + a[i].val;//前缀和
        int ans = 0, cnt = 0;
        DEC(i, n, 1)//从最大的往最小的考虑
        {
            ++cnt;
            if (a[i].val > sum[i - 1])//遇到后面的都打不赢了的
            {
                ans = a[i].val;
                break;
            }
        }
        std::sort(a + 1, a + n + 1, cmp2);//按照编号重新排序
        printf("%d\n", cnt);
        FOR(i, 1, n)
            if (a[i].val >= ans)
                printf("%d ", i);//升序输出
        puts("");
    }
    return 0;
}

CF1490F Equalize the Array

题意

给定序列 \lbrace a\rbrace,求最少删几个数可以满足每个数都出现刚好要么 0 次要么 c 次。

题解

考虑枚举这个 c。首先处理出每个数的出现次数然后把这些出现次数从小到大排序。

假定我们在考虑第 i 个出现次数 cnt_i,如果所有的数的出现次数都要变为 cnt_i,说明多了的次数要减掉,比 cnt_i 少的出现次数要全部删掉。处理前缀和 s_i。不难发现答案即为

\max_{1\le i\le n}\lbrace s_{i – 1} + (s_n – s_i – (n – i) \times cnt_i)\rbrace

s_{i – 1} 为比 cnt_i 出现少的,要全部删掉,s_n – s_i 表示所有大于 cnt_icnt_k 之和,减掉不需要删除的 (n – i) \times cnt_i 即可。

时间复杂度 O(n\log n)std::map 计数 + 排序)

int a[maxn], cnt[maxn], sum[maxn];
std::map<int, int> m;

int main()
{
    int T = read();
    while (T--)
    {
        int n = read();
        m.clear();
        FOR(i, 1, n)
            ++m[read()];//记录出现次数
        n = m.size();
        int tot = 0;
        for (auto i : m)
            cnt[++tot] = i.second;
        std::sort(cnt + 1, cnt + n + 1);//把所有的出现次数排序
        sum[0] = 0;
        FOR(i, 1, n)
            sum[i] = sum[i - 1] + cnt[i];//前缀和
        int ans = 1e9;
        sum[n + 1] = 0;
        FOR(i, 1, n)
            ans = min(ans, sum[i - 1] + sum[n] - sum[i] - (n - i) * cnt[i]);//统计答案
        printf("%d\n", ans);
    }
    return 0;
}

CF1490G Old Floppy Drive

题意

有一个光盘上面依次记录了一些数,有一个驱动器按照如下算法运行:

  • 接受输入 x 并开一个变量 s
  • 从光盘的第一个数考虑起(此时运行时间为 0),如果这个数小于 x 则把这个数加到 s 中去,如果大于等于 x 就返回运行时间 t。每一秒考虑下一个数,循环。

给定光盘上的数,并给定 mx,对于每个 x 求运行时间 t

题解

光盘上的数有正有负,这是本题的一个重难点。

首先处理一下这些数的前缀和,记为 s_i,不难发现如下性质:如果 x<\max_{1\le i\le n}\lbrace s_i\rbrace,说明光盘要被循环不止一次,如果 s_n \le 0 那么累加的和一辈子都达不到 x,直接输出 -1

对于需要循环多次的,处理出循环的次数,即为

r = \left\lceil\frac{x – \max_{1\le i\le n}\lbrace s_i\rbrace}{s_n}\right\rceil

怎么来的呢?我们必然有 r\times s_n + \max_{1\le i\le n}\lbrace s_i\rbrace \ge x,化简便知要向上取整。代码中即为 r = (x - val[tot] + sum[n] - 1) / sum[n];

把循环的这些次数去掉,即 x:=x – r\times s_n,现在问题就变为找到最小的满足 s_i \ge xi

赛时我就是在这里卡住了。因为 s_i 是不满足单调性的,所以没办法使用二分查找,于是就 GG 了。

怎么办呢?注意到我们要的是最小下标,所以不满足单调性的部分我们可以直接舍弃。即把 s_i 单调递增的部分取出来,就可以使用二分了。

long long

int sum[maxn], val[maxn], id[maxn];

signed main()
{
    int T = read();
    while (T--)
    {
        int n = read(), m = read();
        FOR(i, 1, n) sum[i] = sum[i - 1] + read();
        int tot = 0;
        FOR(i, 1, n)
        {
            if (!tot || sum[i] > val[tot])
                val[++tot] = sum[i], id[tot] = i;//处理出那些单调递增的前缀和以及对应的下标
        }
        while (m--)
        {
            int x = read();
            if (x > val[tot] && sum[n] <= 0)
                printf("-1 ");
            else
            {
                int r = 0;
                if (val[tot] < x)
                    r = (x - val[tot] + sum[n] - 1) / sum[n];//处理出要转多圈的情况
                x -= r * sum[n];
                printf("%lld ", r * n + id[std::lower_bound(val + 1, val + tot +1, x) - val] - 1);
            }
        }
        puts("");
    }
    return 0;
}
最后修改日期:2021年2月19日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。