P4620 [SDOI2018]荣誉称号

    • 152通过
    • 368提交
  • 题目提供者 da32s1da
  • 评测方式 云端评测
  • 标签 概率论,统计 各省省选 2018 山东 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 10000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    • Input file: title.in
    • Output file: title.out
    • Time limit: 10 seconds
    • Memory limit: 512 megabytes

    题目描述

    休闲游戏玩家小 $Q$ 不仅在算法竞赛方面取得了优异的成绩,还在一款收集钻石的游戏中排名很高。

    这款游戏一共有 $n$ 种不同类别的钻石,编号依次为 $1$ 到 $n$。小 $Q$ 已经玩了这款游戏很久了,对于第 $i$ 种钻石,他已经收集到了 $a_i$ 个。这款游戏最大的亮点就是,钻石只有一种获得途径,那就是从商城中购买。具体来说,第 $i$ 种钻石的单价为 $b_i$ 点券。为了鼓励玩家充值,每种钻石都没有数量上限,只要肯充钱,就可以拥有任意多的钻石。但是这款游戏并没有开发 “丢弃道具” 功能,因此小 $Q$ 不能通过丢弃钻石去完成任务。

    最近这款游戏推出了一个限时成就任务,完成任务的玩家可以获得荣誉称号,而完成任务条件则是: 给定正整数 $k$ 和 $m$,对于任意一个整数 $x(2^k ≤ x ≤ n)$,$a_x + a_{\lfloor{\frac{x}{2}}\rfloor} + a_{\lfloor{\frac{x}{4}}\rfloor} + _{\lfloor{\frac{x}{8}}\rfloor} + ... + _{\lfloor{\frac{x}{2^k}}\rfloor}$ 都要是 $m$的倍数。

    高玩小 $Q$ 当然想完成这个限时成就任务,但是在充钱之前他想知道他究竟需要多少点券才能完成这个任务。请写一个程序帮助小 $Q$ 计算最少需要的点券数量。

    输入输出格式

    输入格式:

    第一行包含一个正整数 $T$,表示测试数据的组数。

    每组数据第一行包含 $9$ 个正整数 $n, k, m, p, SA, SB, SC, A, B$,其中 $n$ 表示钻石种类数,$k, m$ 表示任 务条件。

    为了在某种程度上减少输入量,$a[]$ 和 $b[]$ 由以下代码生成:

    unsigned int SA, SB, SC;int p, A, B;
    unsigned int rng61(){
        SA ^= SA << 16;
        SA ^= SA >> 5;
        SA ^= SA << 1;
        unsigned int t = SA;
        SA = SB;
        SB = SC;
        SC ^= t ^ SA;
        return SC;
    }
    void gen(){
        scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);
        for(int i = 1; i <= p; i++)scanf("%d%d", &a[i], &b[i]);
        for(int i = p + 1; i <= n; i++){
            a[i] = rng61() % A + 1;
            b[i] = rng61() % B + 1;
        }
    }

    输出格式:

    对于每组数据,输出一行一个整数,即最少需要的点券数量。

    输入输出样例

    输入样例#1: 复制
    2
    3 1 2 3 11111 22222 33333 1 1
    1 5
    2 3
    3 6
    7 2 3 7 11111 22222 33333 1 1
    6 9
    4 5
    3 7
    5 2
    2 4
    1 7
    9 6
    输出样例#1: 复制
    3
    14

    说明

    • $1 ≤ T ≤ 10$,
    • $1 ≤ k ≤ 10$ 且 $2^k ≤ n$, -$ 1 ≤ p ≤ min(n, 100000)$,$10000 ≤ SA, SB, SC ≤ 1000000$, -$ 1 ≤ A, B, ai, bi ≤ 10^7$。

    子任务 $1$($30$ 分):满足 $1 ≤ n ≤ 1000$ 且 $m = 2$。

    子任务 $2$($40$ 分):满足 $1 ≤ n ≤ 10^5$ 且 $m ≤ 200$。

    子任务 $3$($30$ 分):满足 $1 ≤ n ≤ 10^7$ 且 $m ≤ 200$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。