Codeforces Round #455 (Div. 2) D题(花了一个早自习补了昨晚的一道模拟QAQ)
D. Colorful Points
You are given a set of points on a straight line. Each point has a color assigned to it. For point a, its neighbors are the points which don't have any other points between them and a. Each point has at most two neighbors - one from the left and one from the right.
You perform a sequence of operations on this set of points. In one operation, you delete all points which have a neighbor point of a different color than the point itself. Points are deleted simultaneously, i.e. first you decide which points have to be deleted and then delete them. After that you can perform the next operation etc. If an operation would not delete any points, you can't perform it.
How many operations will you need to perform until the next operation does not have any points to delete?
Input
Input contains a single string of lowercase English letters 'a'-'z'. The letters give the points' colors in the order in which they are arranged on the line: the first letter gives the color of the leftmost point, the second gives the color of the second point from the left etc.
The number of the points is between 1 and 106.
Output
Output one line containing an integer - the number of operations which can be performed on the given set of points until there are no more points to delete.
Input
aabb
Output
Input
aabcaa
Output
思路：模拟一下
AC代码：
#include<bits/stdc++.h> using namespace std;
vector< pair<int,int> > v;
int main(){
string str;
cin>>str;
int num=;
int flag=;
for(int i=;i<=str.size();i++){
if(str[i]!=str[i+]&&(i+)<str.size()){
flag=;
}
if(str[i]!=str[i+]){
v.push_back(make_pair(str[i]-'a',num));
num=;
}else{
num++;
}
}
if(flag){
printf("");
return ;
}
/*vector<pair<int,int> > ::iterator it;
for(it=v.begin();it!=v.end();it++){
cout<<(*it).first<<" "<<(*it).second<<endl;
}
*/
int ans=;//aabcaa while(){
vector<pair<int,int> > ::iterator it;
for(it=v.begin();it!=v.end();it++){
if(it==v.begin()||it==(v.end()-)){
(*it).second--;
continue;
}else{
(*it).second-=;
}
}
vector<pair<int,int> > ::iterator xit;
/*for(xit=v.begin();xit!=v.end();xit++){
cout<<(*xit).first<<" "<<(*xit).second<<endl;
}
*/
vector< pair<int,int> > temp;
vector<pair<int,int> > ::iterator itt;
for(itt=v.begin();itt!=(v.end());itt++){
if((*itt).second>){
if(temp.size()==){
temp.push_back(make_pair((*itt).first,(*itt).second));
}else{
vector<pair<int,int> > ::iterator t=temp.end()-;
if((*itt).first==(*t).first){
(*t).second+=(*itt).second;
}else{
temp.push_back(make_pair((*itt).first,(*itt).second));
}
}
}
}
/*vector<pair<int,int> > ::iterator flag=temp.begin(); cout<<temp.size()<<endl;
for(;flag!=temp.end();flag++){
cout<<(*flag).first<<" "<<(*flag).second<<endl;
}
*/
ans++;
if(temp.size()<=){
break;
}else{
v=temp;
} }
cout<<ans<<endl;
return ;
} /* aabbaaa */
最新文章
- SQL Queries from Transactional Plugin Pipeline
- WPF自定义控件与样式(9)-树控件TreeView与菜单Menu-ContextMenu
- C#异常类相关总结
- Web 在线文件管理器学习笔记与总结（2）显示文件列表（名称，类型，大小，可读，可写，可执行，创建时间，修改时间，访问时间）
- AFN网络状态的时时监控以及网络的判断、
- 离线安装PM2
- IOS之表视图添加索引
- linux内核打印"BUG: scheduling while atomic
- Spring中自己主动装配
- 在Eclipse中使用Maven构建SpringMVC项目
- 【ASP.NET Web API教程】2.3.7 创建首页
- JS中判定问题
- python小趣味_520绘制一个心形.
- epoch、 iteration和batchsize区别
- vim编辑
- LVS、Nginx 及 HAProxy 工作原理
- 节点的启动与关闭 ros::init()解析（c++）
- Linux 配置文件管理
- sdk接入
- URL编码分析与乱码解决方案