P4829 kry loves 2048

    • 277通过
    • 2.1K提交
  • 题目提供者 liuyisong1999
  • 评测方式 云端评测
  • 标签 排序 桶排 队列
  • 难度 提高+/省选-
  • 时空限制 2000ms / 256MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    kls是一个人赢。

    题目描述

    kls最近在玩一款类似2048的游戏,规则是这样的:

    一开始,有$n$个方块,每个方块上有一个$1$到$m$的整数。

    kls可以进行两种操作:

    1. 选择两个数字相同的方块(不一定要相邻),将它们合并成一个数字为原来的两倍的方块;

    2. 减小一个方块上的数字。

    操作的次数没有限制,最终的得分为所有方块上的最大的数字。

    因为kls要去陪妹子了,没有时间继续玩,他想让你帮忙计算一下,最多能得到多少分。

    输入输出格式

    输入格式:

    因为数据可能很大,读入容易超时,所以kls给你们提供了一个c++的随机数生成器。

    void generate_array(int a[], int n, int m, int seed) {
        unsigned x = seed;
        for (int i = 0; i < n; ++i) {
            x ^= x << 13;
            x ^= x >> 17;
            x ^= x << 5;
            a[i] = x % m + 1;
        }
    }

    把这个函数复制到你的程序里。用一个足够大的数组,以及输入数据给出的$n$,$m$和$seed$作为参数,调用这个函数。然后这个数组里就是一开始的方块上的数字(下标从0开始)。

    输入一行三个数$n,m,seed$,含义如上。

    输出格式:

    一行一个数,表示最大得分。

    输入输出样例

    输入样例#1: 复制
    5 10 233
    输出样例#1: 复制
    24
    输入样例#2: 复制
    5 50 3
    输出样例#2: 复制
    48
    输入样例#3: 复制
    1000 1000 666
    输出样例#3: 复制
    374784

    说明

    样例解释

    样例1生成出来的数是 6 10 7 5 4。

    样例2生成出来的数是 8 12 48 4 4。

    数据范围

    对于30%的数据,$n, m \le 10$;

    对于60%的数据,$n, m \le 10^5$;

    对于100%的数据,$n, m \le 10^7$,$1 \le seed \le 10^9$。

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