首页 > 其他分享 >P8475 「GLR-R3」雨水 题解

P8475 「GLR-R3」雨水 题解

时间:2024-09-26 18:16:02浏览次数:7  
标签:nxt int 题解 位置 交换 最小 ull P8475 GLR

关于这道题目卡 \(O(n\log n)\) 但是放 \(O(n^2)\) 我也是很疑惑。

我们发现,题目要求的是字典序最小的序列。但凡涉及了字典序最小,答案或多或少的都会带点贪心思想。

那我们也来贪一贪。考虑当前枚举到第 \(i\) 个点,如果后面有比它更小的数,那显然把它们交换过来是更优的。如果有多个,那显然也是最小的那一个交换过来是最优的。如果最小的还有多个,那肯定把当前这个和最后一次出现的交换是最优的。

同时,由于题目要求 \(P\) 是 \(\lang 1,2,\dots,n\rang\) 的一个子序列,所以假设我们这次将 \(i\) 和 \(j\) 位置上的元素交换了,接下来就不能对下标 \(k\le j\) 的元素动手动脚了,下一个枚举到的点就是 \(j + 1\) 了。

如果这么说还不明白的话,我们模拟一下样例:


样例一:

1 1 3 0 0 1 3
↑       ↑
i       j

起初,i = 1,我们发现 i 以后最小的数是 0,它是小于 a[i] 的,而 j = 5 是 0 最后一次出现的位置,所以将 a[1] 和 a[5] 交换。

0 1 3 0 1 1 3
          ↑
          i

接下来 i 移动到 6 的位置,发现后面没有小于 a[i] 的数了。

0 1 3 0 1 1 3
            ↑
            i

最后,i 移动到 7,程序结束。

样例二:

2 8 0 6 2 2 1 7 8 3
↑   ↑
i   j

起初,i = 1,我们发现 i 以后最小的数是 0,它是小于 a[i] 的,而 j = 3 是 0 最后一次出现的位置,所以将 a[1] 和 a[3] 交换。

0 8 2 6 2 2 1 7 8 3
      ↑     ↑
      i     j

接下来 i 移动到 4 的位置,我们发现 i 以后最小的数是 1,它也是小于 a[i] 的,而 j = 7 是 0 最后一次出现的位置,所以将 a[4] 和 a[7] 交换。

0 8 2 1 2 2 6 7 8 3
              ↑   ↑
              i   j

接下来 i 移动到 8 的位置,我们发现 i 以后最小的数是 3,它同样是小于 a[i] 的,而 j = 10 是 3 最后一次出现的位置,所以将 a[8] 和 a[10] 交换。

0 8 2 1 2 2 6 3 8 7
                    ↑
                    i

最后,i 移动到 11,程序结束。

至于实现,我们可以维护一个后缀最小值最后一次出现的位置 \(p\),而且是最后一次出现的位置,然后将 \(a_i\) 与 \(a_{p_i}\) 交换,再令 \(i = p_i + 1\),然后重复以上步骤直到 \(i \ge n\)。

我的程序中是用 \(nxt\) 来存储后缀最小值最后一次出现的位置的,大家看的时候转换一下就好:

#include<bits/stdc++.h>
#define MAXN 10000010
using namespace std;
typedef unsigned long long ull;
int n, m, k;
int a[MAXN], nxt[MAXN];
namespace Generator{
    ull k1, k2;
    int thres;
    inline ull xorShift128Plus() {
        ull k3 = k1, k4 = k2;
        k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
        return k2 + k4;
    }
    inline void generate() {
        for (int i = 1; i <= n; ++i) {
            a[i] = xorShift128Plus() % thres;
        }
    }
}
int main(){
    scanf("%d%llu%llu%d", &n, &Generator::k1, &Generator::k2, &Generator::thres);
    Generator::generate();
    nxt[n] = n;
    for(int i = n - 1; i >= 1; i--){
        if(a[i] < a[nxt[i + 1]]) nxt[i] = i;
        else nxt[i] = nxt[i + 1];
    }
    for(int i = 1; i < n; i++){
        if(a[nxt[i + 1]] < a[i]){
            swap(a[i], a[nxt[i + 1]]);
            i = nxt[i + 1];
        }
    }
    ull ans = 0;
    for(int i = 1; i <= n; i++) ans += (ull)i * a[i];
    printf("%llu\n",ans);
    return 0;
}

标签:nxt,int,题解,位置,交换,最小,ull,P8475,GLR
From: https://www.cnblogs.com/NightTide/p/18434018

相关文章

  • P8474 「GLR-R3」立春 题解
    俗话说的好:“打表出奇迹”,所以我们这一题打表计算。其实确实可以打表来找规律。通过打表,我们可以获得如下的结果:1 12 33 214 3155 9765…… ……然后观察可得:\[1\times3=1\times(2^2-1)=3\]\[3\times7=3\times(2^3-1)=21\]\[21\times15=21\t......
  • Codeforces Round 971 (Div. 4)题解记录(G3待补)
    A.Minimize!暴力模拟一遍即可#include<iostream>#include<queue>#include<deque>#include<map>#include<set>#include<stack>#include<vector>#include<bitset>#include<math.h>#include<random>#include&l......
  • P8563 Magenta Potion 题解
    前排警告这是较为通用,不需要脑子,但是代码量巨大的题解,请谨慎食用解题思路不知道大家做没做过带修改的区间最大连续子段和,这一题其实就是带修改的区间最大连续子段积。那么其实做法是类似的。我们用线段树维护五个量:当前区间答案,区间前缀最小值,区间前缀最大值,区间后缀最小值,区......
  • P8564 ρars/ey 题解
    显然树上背包。首先一眼会想到的状态:\(dp_{i,j}\)表示\(i\)的子树最后剩下\(j\)个结点的最小代价。然而开始写会发现这并不好DP。于是我们换一个想法:\(dp_{i,j}\)表示\(i\)的子树删去\(j\)个结点的最小代价。则有转移方程:\[dp_{i,j}=\min_{v\inson(i)}\{dp_{i......
  • 题解:UVA1456 Cellular Network
    UVA1456CellularNetwork题解夭寿了!30行写完紫题了!更新:已联系管理员修改难度,现在是绿题题意很简单,不再赘述。首先一个小贪心,将概率\(u​\)进行从大到小的排序,优先查看概率大的区域,显然这样能够保证访问数量期望最小。接着考虑如何将区域分组。一个显而易见的思路是动态......
  • 题解:CF437B The Child and Set
    CF437BTheChildandSet题解这题目就一个问题。啥是\(\operatorname{lowbit}\)?\(\operatorname{lowbit}(x)\)是指\(x\)的二进制表示中最低位的\(1\)所表示的值。例如\((14)_{10}=(1110)_2\),其中最低位的\(1\)在第二位,表示\((2)_{10}\),即\(\operatorname{lo......
  • 题解:P4288 [SHOI2014] 信号增幅仪
    很好一题目,使我的最小圆覆盖旋转。先假设\(p=1\)。这是最简单的情况。这个时候我们就得到了一个裸的最小圆覆盖。当\(p\not=1\),但是\(a=0\)的时候。圆就变成了对称轴与坐标轴平行的椭圆,运用高中知识仿射一下,又回到了最小圆覆盖。在一般的情况下,我们先通过坐标的旋转......
  • 《超级机器人大战30》缺少roboex32.dll启动遇阻怎么办?轻松应对《超级机器人大战30》ro
    当《超级机器人大战30》因缺少roboex32.dll文件而启动遇阻时,可以尝试以下几种解决方案来轻松应对这一问题:一、下载并替换缺失的DLL文件寻找可靠来源:首先,需要在互联网上找到可靠的roboex32.dll文件下载源。建议访问官方网站、微软官方下载中心或知名的软件下载站点,以确保下载......
  • AT_arc176_e [ARC176E] Max Vector 题解
    发现数据范围很小,考虑最小割。先对题面做一个转化:构造两个序列\(X=(X_1,X_2,\dots,X_N),Y=(Y_1,Y_2,\dots,Y_N)\)最小化\(\sumX_i+Y_i\),有\(M\)个限制,每个限制有一个序列\(A_1,A_2,\dots,A_n\),需要满足\(\foralli,X_i\geA_i\)或者\(\foralli,Y_i\geA_i\)。考虑怎......
  • 1. 两数之和题解
    题目描述[!NOTE]总结:找出整数数组中两数之后等于目标值的两个数,然后返回其下标给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素......