洛谷P4829题解

传送锚点

摸鱼环节

kry loves 2048

题目背景

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

样例输入 #1

5 10 233

样例输出 #1

24

样例 #2

样例输入 #2

5 50 3

样例输出 #2

48

样例 #3

样例输入 #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\)。

众所周知，oier们喜欢处理一些奇奇怪怪非常有意思的问题。同时，oier们都乐于助人，每天都在帮不同的人处理不同的问题（我cow，今天这个人怎么还有妹子可以陪），面对kls的困难之处，咱们oier酸了当然得帮他解决。所以，正解是帮他陪妹子。

正片开始

1.草率代码

类似于合并果子，每次应该选取小于数\(a\)
中的最大值进行合并，考虑用优先队列维护。

code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e7+5;
ll n,m,seed,ans;
ll a[N];
priority_queue<ll,vector<ll>,greater<ll> > q;//小数在前
void cao(ll n, ll m, ll seed) //n个数，m域 
{
    unsigned x=seed;
    for(ll i=0;i<n;++i) 
	{
        x^=x<<13;
        x^=x>>17;
        x^=x<<5;
        a[i]=x%m+1;
    }
}
int main()
{
    cin>>n>>m>>seed;
    cao(n,m,seed);
    for(int i=0;i<=n;i++) q.push(a[i]);
    while(q.size()>1)
    {
    	ll x=q.top(),y,z;
    	q.pop();
    	y=q.top();
    	q.pop();
    	z=2*x;
    	ans=max(ans,max(x,y));//更新当前答案
    	q.push(max(z,y));//比较是选择较小数*2更优，还是较大数更优。
	}
	ans=max(ans,q.top());
	cout<<ans;
    return 0;
}

然后突然发现，代码TLE，还T了4个点，看着黄色的60，内心万分不甘，于是打开题解区认真分析下复杂度。发现代码的复杂度为\(nlogn\)，\(n=1e7\)显然是祭得很惨。

2.优化环节

很明显这个\(logn\)肯定是得去掉的，由于在排序上的复杂度不够优，所以选择用计数排序预处理解决问题，这样复杂度就降到了\(o(n)\)，于是快乐AC了。

code：

for(int i=mina;i<=maxa;i++)
    for(int j=1;j<=t[i];j++)
        a[++len]=i;

完整代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+5;
int n,m,seed,b[N],a[N],t[N];
ll maxa=0,mina=0x3f;
ll len=0,cnt=1;
queue<ll>q;
void cao(int n, int m, int seed) 
{
    unsigned x=seed;
    for(int i=1;i<=n;++i) 
	{
        x^=x<<13;
        x^=x>>17;
        x^=x<<5;
        b[i]=x%m+1;
    }
}
ll get()
{
    if(q.empty()) return a[cnt++];
    ll x=q.front();
    if(cnt==n+1||a[cnt]>x)
    {
        q.pop();
        return x;
    }
    return a[cnt++];
    
}
int main()
{
    cin>>n>>m>>seed;
    cao(n,m,seed);
    for(int i=1;i<=n;i++)
    {
        t[b[i]]++;
        maxa=max(maxa,1ll*b[i]);
        mina=min(mina,1ll*b[i]);
    }
    for(int i=mina;i<=maxa;i++)
        for(int j=1;j<=t[i];j++)
            a[++len]=i;//计数排序
    for(int i=1;i<n;i++)
    {
        ll x=get(),y=get();
        q.push(max(x*2,y));
    }
    cout<<q.front()<<endl;
    return 0;
}

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)