CodeforcesRound#312(Div.2)E.ASimpleTask

作者：GRIROR格雷尔 | 来源：互联网 | 2023-05-19 04:56

题目大意就是给一个字符串，然后多个操作，每次操作可以把每一段区间的字符进行升序或者降序排序，问最终的字符串是多少。一开始只考虑字符串中字符a的情况，假设操作区间[L,R]中有x个a

　　题目大意就是给一个字符串，然后多个操作，每次操作可以把每一段区间的字符进行升序或者降序排序，问最终的字符串是多少。

　　一开始只考虑字符串中字符'a'的情况，假设操作区间[L,R]中有x个'a',那么一次操作后，这x个'a'要么去最左(升序)，要么去最右(降序),我们可以建立一颗线段树来维护这样的操作，字符'a'出现的位置值为1，否则为0，那么q次操作后，最后值为1的地方填的就是'a'了。

　　在考虑字符'a'和'b'的情况，操作的情况和上面类似，字符'a'和'b'出现的位置值为1，否则为0，q次操作后，如果一个位置的值为1，并且该位置没有填写'a'，那么这个位置就填写'b'。接下来的情况以此类推，一直做到z，复杂度O(26*qlogn)。

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include
  8 #include<string>
  9 #define N 1000010
 10 #define M 1010
 11 #define P 1000000007
 12 using namespace std;
 13 int v[N],s[N],l[N],r[N],tt;
 14 int L[N],R[N],typ[N],n,q,i,j,tmp,ans[N];
 15 string str;
 16 void build(int x,int a,int b)
 17 {
 18     int m;
 19     l[x]=a;r[x]=b;
 20     if (x>tt) tt=x;
 21     if (b-a>1)
 22     {
 23         m=(a+b)>>1;
 24         build(2*x,a,m);
 25         build(2*x+1,m,b);   
 26     }
 27     v[x]=-1;
 28 }
 29 void clean(int x)
 30 {
 31     if (v[x]!=-1)
 32     {
 33         s[x]=(r[x]-l[x])*v[x];
 34         if (2*x<=tt) v[2*x]=v[x];
 35         if (2*x+1<=tt) v[2*x+1]=v[x];
 36         v[x]=-1;
 37     }
 38 }
 39 void change(int x,int a,int b,int c)
 40 {
 41     int m;
 42     clean(x);
 43     if ((a<=l[x])&&(r[x]<=b))
 44     {
 45         v[x]=c;
 46         return;
 47     }
 48     m=(l[x]+r[x])>>1;
 49     if (a2*x,a,b,c);
 50     if (m2*x+1,a,b,c);
 51     clean(2*x);clean(2*x+1);
 52     s[x]=s[2*x]+s[2*x+1];
 53 }
 54 int query(int x,int a,int b)
 55 {
 56     int m,ans=0;
 57     clean(x);
 58     if ((a<=l[x])&&(r[x]<=b))
 59         return s[x];
 60     m=(l[x]+r[x])>>1;
 61     if (a2*x,a,b);
 62     if (m2*x+1,a,b);
 63     return ans;
 64 }
 65 int main()
 66 {
 67     cin>>n>>q;
 68     cin>>str;
 69     build(1,0,n);
 70     for (i=1;i<=q;i++)
 71     cin>>L[i]>>R[i]>>typ[i];
 72     
 73     for (j=1;j<=26;j++)
 74     {
 75         change(1,0,n,0);
 76         for (i=0;i)
 77         if (str[i]-96<=j)
 78         change(1,i,i+1,1);
 79         for (i=1;i<=q;i++)
 80         {
 81             tmp=query(1,L[i]-1,R[i]);
 82             change(1,L[i]-1,R[i],0);
 83             if (tmp)
 84             {
 85             if (typ[i]==0)
 86             change(1,R[i]-tmp,R[i],1);
 87             else
 88             change(1,L[i]-1,L[i]-1+tmp,1);
 89             }
 90         }
 91         
 92         for (i=1;i<=n;i++)
 93         if ((query(1,i-1,i)==1)&&(ans[i]==0))
 94         ans[i]=96+j;
 95     }
 96     
 97     for (i=1;i<=n;i++)
 98     {
 99         char ch=ans[i];
100         cout<<ch;
101     }
102 }

推荐阅读

io
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
io
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
io
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
io
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
python
Python正则表达式学习记录及常用方法

本文记录了学习Python正则表达式的过程，介绍了re模块的常用方法re.search，并解释了rawstring的作用。正则表达式是一种方便检查字符串匹配模式的工具，通过本文的学习可以掌握Python中使用正则表达式的基本方法。 ... [详细]

蜡笔小新 2023-12-13 16:37:19
io
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
io
伊振华作品 | 沈阳市智慧城市运行管理中心的设计与建设

本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计，并以数字赋能和创新驱动高质量发展的理念，建设了集成、智慧、高效的一体化城市综合管理平台，促进了城市的数字化转型。该中心被称为当代城市的智能心脏，为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]

蜡笔小新 2023-12-14 16:35:39
python
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
io
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
io
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
io
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
io
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
import
Netty拆包粘包问题解决 —— 特殊结束符

本文介绍了解决Netty拆包粘包问题的一种方法——使用特殊结束符。在通讯过程中，客户端和服务器协商定义一个特殊的分隔符号，只要没有发送分隔符号，就代表一条数据没有结束。文章还提供了服务端的示例代码。 ... [详细]

蜡笔小新 2023-12-14 18:02:45
io
【机器学习】生成式对抗网络模型综述

生成式对抗网络模型综述摘要生成式对抗网络模型(GAN)是基于深度学习的一种强大的生成模型，可以应用于计算机视觉、自然语言处理、半监督学习等重要领域。生成式对抗网络 ... [详细]

蜡笔小新 2023-12-14 17:51:18
import
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00

GRIROR格雷尔

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章