牛客网暑期ACM多校训练营(第三场)C(Shuffle Cards)

2024-01-14 21:58

本文主要是介绍牛客网暑期ACM多校训练营(第三场)C(Shuffle Cards),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述 
Eddy likes to play cards game since there are always lots of randomness in the game. For most of the cards game, the very first step in the game is shuffling the cards. And, mostly the randomness in the game is from this step. However, Eddy doubts that if the shuffling is not done well, the order of the cards is predictable! 

To prove that, Eddy wants to shuffle cards and tries to predict the final order of the cards. Actually, Eddy knows only one way to shuffle cards that is taking some middle consecutive cards and put them on the top of rest. When shuffling cards, Eddy just keeps repeating this procedure. After several rounds, Eddy has lost the track of the order of cards and believes that the assumption he made is wrong. As Eddy's friend, you are watching him doing such foolish thing and easily memorizes all the moves he done. Now, you are going to tell Eddy the final order of cards as a magic to surprise him.

Eddy has showed you at first that the cards are number from 1 to N from top to bottom.

For example, there are 5 cards and Eddy has done 1 shuffling. He takes out 2-nd card from top to 4-th card from top(indexed from 1) and put them on the top of rest cards. Then, the final order of cards from top will be [2,3,4,1,5].
输入描述:
The first line contains two space-separated integer N, M indicating the number of cards and the number of shuffling Eddy has done.
Each of following M lines contains two space-separated integer pi, si indicating that Eddy takes pi-th card from top to (pi+si-1)-th card from top(indexed from 1) and put them on the top of rest cards.


1 ≤ N, M ≤ 105
1 ≤ pi ≤ N
1 ≤ si ≤ N-pi+1
输出描述:
Output one line contains N space-separated integers indicating the final order of the cards from top to bottom.

输入

5 1
2 3
输出

2 3 4 1 5

输入

5 2
2 3
2 3
输出

3 4 1 2 5

输入

5 3
2 3
1 4
2 4
输出

3 4 1 5 2

题意:给出n,m表示1到n的按顺序排列的数和m次操作。然后每次操作给出l和len,将从l及其后面len长度的数转移到开头组成新序列。多次操作问最终弄结果。

思路两种解法

1,(编译器版本要高)

来自:https://blog.csdn.net/b_r_e_a_d/article/details/81235449

#include <ext/rope>
using namespace __gnu_cxx;
int a[1000];
rope<int> x;
rope<int> x(a,a + n);
rope<int> a(x);

x->at(10);
x[10];
x->push_back(x)     // 在末尾添加x
x->insert(pos,x)    // 在pos插入x
x->erase(pos,x)     // 从pos开始删除x个
x->replace(pos,x)   // 从pos开始换成x
x->substr(pos,x)    // 提取pos开始往后x个

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define LL long long int
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
int n,m;
int l,r;
rope<int>rop;
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        rop.clear();
        for(int i=1;i<=n;i++)
            rop.push_back(i);
        while(m--)
        {
            scanf("%d%d",&l,&r);
            rop.insert(0,rop.substr(l-1,r));
            rop.erase(l+r-1,r);
        }
        for(int i=0;i<n;i++)
        {
            if(!0) printf(" ");
            printf("%d",rop[i]);
        }
        printf("\n");
    }
    return 0;
}

2,(splay树)

几乎花了一天的时间学习平衡树,对于这道题就是个模版。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <cstring>
#define Stop system("pause")
#define type int
#define MAXN 2000005
#define MAXL 100005
#define INF (1<<30)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
struct Splay_Tree
{
    struct Node//节点
    {
        Node *c[2],*p;
        int value,size,Min,lazy;
        bool rev;
    }*root,*null,*lb,*rb,S[MAXN];
    int scnt;
    //inline int max(int a,int b) {return a>b?a:b;}
    inline Node * NewNode(int value,Node *p)//插入新节点
    {
        Node *e=S+(++scnt);
        e->value=value;
        e->size=1;
        e->p=p;
        e->Min=value;
        e->lazy=0;
        e->rev=false;
        e->c[0]=e->c[1]=null;
        return e;
    }
    inline void Update(Node *p)//更新节点信息
    {
        if (p==null)
            return;
        p->size=p->c[0]->size+p->c[1]->size+1;
        p->Min=min(p->value,min(p->c[0]->Min,p->c[1]->Min));
    }
    inline void PushDown(Node *x)//更新标记
    {
        if(x==null)
            return;
        if(x->rev)
        {
            x->rev=false;
            Node *t=x->c[0];
            x->c[0]=x->c[1];
            x->c[1]=t;
            x->c[0]->rev=!x->c[0]->rev;
            x->c[1]->rev=!x->c[1]->rev;
            //int w=x->ll; x->ll=x->rr; x->rr=w;
        }
        if(x->lazy)
        {
            int w=x->lazy;
            x->value+=w;
            x->Min+=w;
            x->c[0]->lazy+=w;
            x->c[1]->lazy+=w;
            x->lazy=0;
        }
    }
    inline void Rotate(Node *x,int k)//左旋 k=0;右旋 k=1;
    {
        Node *y=x->p;
        PushDown(x->c[0]);
        PushDown(x->c[1]);
        PushDown(y->c[!k]);
        y->c[k]=x->c[!k];
        y->c[k]->p=y;
        x->p=y->p;
        if(y->p->c[0]==y)
            y->p->c[0]=x;
        else
            y->p->c[1]=x;
        y->p=x;
        x->c[!k]=y;
        Update(y);
        Update(x);
        if(root==y)
            root=x;
    }
    inline void Splay(Node *x,Node *y)//伸展
    {
        PushDown(x);
        while(x->p!=y)
        {
            if(x->p->p==y)
            {
                if(x->p->c[0]==x)
                    Rotate(x,0);
                else
                    Rotate(x,1);
            }
            else if(x->p->p->c[0]==x->p)
            {
                if(x->p->c[0]==x)
                    Rotate(x->p,0),Rotate(x,0);
                else
                    Rotate(x,1),Rotate(x,0);
            }
            else
            {
                if(x->p->c[1]==x)
                    Rotate(x->p,1),Rotate(x,1);
                else
                    Rotate(x,0),Rotate(x,1);
            }
        }
        Update(x);
    }
    inline void Select(int k,Node *y)
    {
        Node *x=root;
        PushDown(x);
        while(k!=x->c[0]->size+1)
        {
            if(k<=x->c[0]->size)
                x=x->c[0];
            else
            {
                k-=x->c[0]->size+1;
                x=x->c[1];
            }
            PushDown(x);
        }
        Splay(x,y);
    }
    inline void MakeTree(int l,int r,type C[],Node *p,int side)
    {
        if(l>r)
            return;
        int mid=(l+r)>>1;
        Node *x;
        x=NewNode(C[mid],p);
        p->c[side]=x;
        MakeTree(l,mid-1,C,x,0);
        MakeTree(mid+1,r,C,x,1);
        Update(x);
    }
    inline void Insert(int pos,int cnt,type C[])//在pos后插入长度为cnt的区间
    {
        Select(pos+1,null);
        Select(pos+2,root);
        MakeTree(1,cnt,C,root->c[1],0);
        Splay(root->c[1]->c[0],null);
    }
    inline void Add(int pos,int cnt,type value)//对pos后长度为cnt的区间中的每个值都增加value
    {
        Select(pos,null);
        Select(pos+cnt+1,root);
        root->c[1]->c[0]->lazy+=value;
        Splay(root->c[1]->c[0],null);
    }
    inline void Delete(int pos,int cnt)//删除pos后长度为cnt的区间
    {
        Select(pos,null);
        Select(pos+cnt+1,root);
        root->c[1]->c[0]=null;
        Splay(root->c[1],null);
    }
    inline void Reverse(int pos,int cnt)//旋转pos后长度为cnt的区间
    {
        Select(pos,null);
        Select(pos+cnt+1,root);
        root->c[1]->c[0]->rev=!root->c[1]->c[0]->rev;
        Splay(root->c[1]->c[0],null);
    }
    inline void Revolve(int a,int b)//将[a,b]区间向右旋转k步
    {
        int A=1;
        int B=a-1;
        int C=a+b-1;                  //转化成交换区间[A,B],[B+1,C];
        Node *p1,*p2,*p3,*p4;
 
        Select(A,null);
        p1=root;        //A-1;
        Select(C+2,null);
        p2=root;      //C+1;
        Select(A+1,null);
        p3=root;      //A;
        Select(B+1,null);
        p4=root;      //B;
 
        Select(A,null);                 //将A-1伸展成root
        Select(C+2,p1);                 //将C+1伸展到A-1的右边
        Select(B+1,p2);                 //将B伸展到C+1的左边
        Node *x,*y;
 
        x=p4->c[1];                     //把b的右子树切断,挂在a的左边
        p4->c[1]=null;
 
        p3->c[0]=x;
        Splay(p3,null);                 //把a伸展为root,一路更新即可
    }
    inline type GetMin(int pos,int cnt)//获得pos后长度为cnt的区间的最小值
    {
        Select(pos,null);
        Select(pos+cnt+1,root);
        PushDown(root->c[1]->c[0]);
        return root->c[1]->c[0]->Min;
    }
    void Index(int pos)
    {
        Select(pos+1,null);
        printf("*%d\n",root->value);
    }
    inline void Print()//打印区间
    {
        int i;
        for(i=1; i<scnt-1; i++)
            Index(i);
    }
    inline void Init()
    {
        scnt=-1;
        null=0;
        null=NewNode(INF,0);
        null->size=0;
        lb=root=NewNode(INF,null);
        rb=root->c[1]=NewNode(INF,root);
        Update(root);
    }
} Splay;
int N,M,pos;
type C[MAXL],ans;
char s[20];
int main()
{
    int i,j,a,b,c,k;
    Splay.Init();
    scanf("%d",&N);
    for(i=1; i<=N; i++)
        C[i]=i;
    Splay.Insert(0,N,C);
 
 
    scanf("%d",&M);
    while(M--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if (a!=1) Splay.Revolve(a,b);
    }
    for (i=1; i<N; i++)
        printf("%d ",Splay.GetMin(i,1));
    printf("%d\n",Splay.GetMin(N,1));
    return 0;
}

这篇关于牛客网暑期ACM多校训练营(第三场)C(Shuffle Cards)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/606657

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

暑期学习总结

iOS学习 前言无限轮播图换头像网络请求按钮的configuration属性总结 前言 经过暑期培训,完成了五个项目的仿写,在项目中将零散的内容经过实践学习,有了不少收获,因此来总结一下比较重要的内容。 无限轮播图 这是写项目的第一个难点,在很多项目中都有使用,越写越熟练。 原理为制造两个假页,在首和尾分别制作最后一页和第一页的假页,当移动到假页时,使用取消动画的方式跳到

代码训练营 Day26 | 47.排序II | 51. N-皇后 |

47.排序II 1.跟46题一样只不过加一个树层去重 class Solution(object):def backtracking(self,nums,path,result,used):# recursion stopif len(path) == len(nums):# collect our setresult.append(path[:])return for i in range(

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯(进阶版)

完全背包问题                  和01背包最大区别就是一个物品可以重复放多次,因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt

【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

目录 一、做题心得 二、题目与题解 题目一:卡码网 103. 水流问题 题目链接 题解:DFS 题目二:卡码网 104. 建造最大岛屿 题目链接 题解:DFS  三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节,还是选择使用 DFS 来解决这类搜索问题(单纯因为我更熟悉 DFS 一点),今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚