首页 > 其他分享 >Shuffle Cards (牛客多校) (rope 块状链表 用作可持续优化平衡树, 用于区间的整体移动操作(可以类比于字符串))

Shuffle Cards (牛客多校) (rope 块状链表 用作可持续优化平衡树, 用于区间的整体移动操作(可以类比于字符串))

时间:2023-06-28 12:34:11浏览次数:44  
标签:rope Shuffle string int 多校 pos 链表 字符串 下标

rope:

#include<ext/rope>

using namespace __gnu_cxx; 

定义方法:rope<变量类型>变量名称;

人话解释:超级string

算法解释:块状链表(即讲链表与数组的优势结合,形成分块思想)

用途解释:这本来是一个用于快速操作string的工具,却一般被定义成int,然后用作可持久化线段树!

insert(int pos, string &s, int n) 将字符串s的前n位插入rope的下标pos处,如没有参数n则将字符串s的所有位都插入rope的下标pos处 (补充地址知识:如果你不想从字符串下标为0(即第一个字符)的地址开始取n位,就将你想开始取的地址代入。如s+1表示从字符串下标为1(即第二个字符)的地址开始取n位。int、char等变量类型的数组都适用这种方法来更改数组操作的起始位置。)

substr(int pos, int len) 提取rope的从下标pos开始的len个字符

at(int x) 访问rope的下标为x的元素

erase(int pos, int num) 从rope的下标pos开始删除num个字符

copy(int pos, int len, string &s) 从rope的下标pos开始的len个字符用字符串s代替,如果pos后的位数不够就补足

replace(int pos, string &x);//从rope的下标pos开始替换成字符串x,x的长度为从pos开始替换的位数,如果pos后的位数不够就补足

 

一般用 substr 即可 

 

题目大意:

  • 给一个牌堆,  然后m次操作,
  • 每次操作可以选择 l-r的牌 放到牌堆顶部
  • 问最后的牌堆样子

 思路;

  • 利用 C++ 自带的 rope

 

标签:rope,Shuffle,string,int,多校,pos,链表,字符串,下标
From: https://www.cnblogs.com/Lamboofhome/p/17511090.html

相关文章

  • PACM Team (牛客多校) (DP 01背包, 维度较多)
    题目大意:给出n个物品,物品有4个空间值,然后有一个权值问在不超过最大的空间值时,最大的权值  思路:一开始想了很多其他思路没有想出来开始广搜算法,发现dp可以解决(注意看数据范围,是满足的)遇到奇怪的题,就试试dp,特别在数据范围很小的时候 ......
  • #yyds干货盘点# LeetCode程序员面试金典:重排链表
    题目:给定一个单链表L的头节点head,单链表L表示为:L0→L1→…→Ln-1→Ln请将其重新排列后变为:L0→Ln→L1→Ln-1→L2→Ln-2→…不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例1:输入:head=[1,2,3,4]输出:[1,4,2,3]示例2:输入:head......
  • 【考后总结】6 月多校国赛模拟赛 6
    6.27冲刺国赛模拟25T1简单计数不是古典概型所以不能方案数相除。考虑枚举第一个选择的位置\(i\),这样分成两个独立的区间,只关心\(k\)所在的一个,转移方程:\[f_{n,k}=\dfrac{1}{n-1}\left([k<n]+[k>1]+\sum_{i>k}f_{i-1,k}+\sum_{i<k-1}f_{n-(i+1),k-(i+1)}\right)\]前缀和......
  • 【考后总结】6 月西安多校国赛模拟赛 3
    6.17冲刺国赛模拟20T1树染色容易发现每种方案都可以变成没有交边的链剖分,在此基础上的方案数是每个链顶的深度,考虑DP。直接DP大致是维护\(\prod(\proda+\prodb)\timesdep_{top}\),发现这个东西非常不好转移,转移时需要枚举叶子,复杂度不优秀。改为设\(f_{i,0/1}\)表......
  • 【考后总结】6 月西安多校国赛模拟赛 4
    6.21冲刺国赛模拟22T1跳跃不妨看作两只青蛙从相同起点出发且跳跃次数相同,设\(f_{i,j,k}\)为两只青蛙分别在\(i,j\)位置,且相差步数\(k\)。由于需要记录相邻位置对答案贡献,我们在要求必须严格按照升序对处理状态,也就是必须保证当前跳跃的一只青蛙落点在另一只青蛙更前面,且......
  • 【考后总结】6 月西安多校国赛模拟赛 5
    6.24冲刺国赛模拟24T2简单图论题原题:Gym-104053CCustomsControls2构造题。这个限制可以进一步加强到对于每个节点\(u\),\(1\tou\)的路径权值都相等,定义为\(d_u\)。于是对\(u\)连边的两个节点的\(d\)一定相等,进而可以把所有相等的缩到一起,且这些点直接不能连边(点......
  • 【杂题乱写】6 月多校字符串专题训练
    ACodeForces-547EMikeandFriends*2800肯定要建广义SAM。在每个\(cur\)打一个标记,没有区间限制就在对应节点上查一下后缀树子树标记总数,有区间限制线段树合并维护标记。点击查看代码intn,q;chars[maxn];intmark[maxn];structSegmentTree{#definemid((l+r)>......
  • leetcode 21. 合并两个有序链表
    直接合并即可这道题是简单题,直接合并即可/**Definitionforsingly-linkedlist.publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=nex......
  • 【华为机试ACM基础#02】从单向链表中删除指定值的节点(熟悉链表的输入方式,虽然说本题可
    从单向链表中删除指定值的节点输入一个单向链表和一个节点的值,从单向链表中删除等于该值的节点,删除后如果链表中无节点则返回空指针。链表的值不能重复。构造过程,例如输入一行数据为:6212325145722则第一个参数6表示输入总共6个节点,第二个参数2表示头节点值为2,剩......
  • 用指针处理链表
    什么是链表?链表是一种常见的重要的数据结构。它是动态的进行春初分配的一种结构。用数组存放数据时,必须先定义固定的数组长度,显然这会浪费内存。链表则没有这个缺点,他根据需要开辟内存单元。 ......