这道题用暴力水过了,蒟蒻是这么想的:枚举两个端点,找最小值,因为shift只能用一次,但是这样10^9*2.5要t,所以减掉只有一个黑点的情况,然后复杂度变为10^9*0.6

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
int n,ll=-(<<),rr=-(<<),ans;
vector<int>left1;
vector<int>right1;
char c;
char s[];
int sum[];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n;
int pos=;
cin.ignore();
for(int i=;i<=n;i++)
{
c=getchar();
s[i]=c;
sum[i]=sum[i-]+(c=='*');
}
s[]='.';
s[++n]='.';
for(int i=;i<=n;i++)
{
int l,r;
if(s[i]=='*'&&s[i-]=='.'){l=i;left1.push_back(i);}
if(s[i]=='*'&&s[i+]=='.')
{
r=i;
if(r-l+<)
{
left1.pop_back();
continue;
}
right1.push_back(i); }
}
int l=,r=;
int MAX=-(<<);
for(int i=;i<left1.size();i++)
{
for(int j=i;j<right1.size();j++)
{
int a=right1[j]-left1[i]+;
// cout<<"left:"<<left1[i]<<endl;
// cout<<"right:"<<right1[j]<<endl;
int b=sum[right1[j]]-sum[left1[i]-];//操作数a-b+2和b比较
// cout<<"MAX="<<MAX<<" "<<a<<" "<<b<<endl;
if(a-b+<b&&MAX<*b-a-)
{
MAX=*b-a-;
ll=left1[i];rr=right1[j];
}
}
}
// cout<<"ll="<<ll<<" "<<"rr="<<rr<<endl;
if(MAX!=-(<<))
{
ans+=(+rr-ll-*(sum[rr]-sum[ll-]));
}
ans+=sum[n-];
// cout<<sum[n]<<endl;
cout<<ans<<endl;
if(MAX!=-(<<))
{
cout<<ll<<endl;
cout<<"Shift+"<<rr<<endl;
for(int i=ll;i<=rr;i++)
if(s[i]=='.')
{
cout<<"Ctrl+"<<i<<endl;
}
}
if(ll==-(<<)&&rr==-(<<))
{
ll=;rr=;
}
for(int i=;i<ll;i++)
if(s[i]=='*')cout<<"Ctrl+"<<i<<endl;
for(int i=rr+;i<=n;i++)
if(s[i]=='*')cout<<"Ctrl+"<<i<<endl;
fclose(stdin);
fclose(stdout);
return ;
}

最新文章

  1. js 碎片整理(变量声明,函数作用域)
  2. web 乱码摘抄
  3. hdoj 2022 海选女主角
  4. activeMq笔记
  5. 用c#实现$.now()(1437813924915)的时间效果
  6. 关于网站高性能中磁盘cpu以及内存对网站性能的影响
  7. 20145211《Java程序设计》第5周学习总结——独上高楼,望尽天涯路
  8. 【转载】UML用例图
  9. C# 多线程操作样例
  10. 微信之Android各版本列表
  11. android:configChanges 屏幕横竖屏切换
  12. Jquery显示和隐藏元素或设为只读(含Ligerui的控件禁用,实例说明)
  13. rs.Open sql,conn,0,2,1
  14. 云计算基础 (redhat7介绍及相关配置)
  15. Javascript Date类型
  16. Linux命令:内建命令
  17. #006 C语言大作业学生管理系统第三天
  18. Struts2对值的推断
  19. Elasticsearch 原理
  20. php array_map array_filter sort

热门文章

  1. AC日记——字符串P型编码 openjudge 1.7 31
  2. OAuth2学习及DotNetOpenAuth部分源码研究
  3. java 22 - 12 多线程之解决线程安全问题的实现方式1
  4. 用nodejs搭建一个简单的服务器
  5. 通俗理解T检验和F检验
  6. JQuery阻止事件冒泡---阻止后续代码执行
  7. IE下默认TD colspan rowspan值为1
  8. 写Java也得了解CPU--CPU缓存
  9. C# WebApi Xml序列化问题解决方法:“ObjectContent`1”类型未能序列化内容类型“application/xml;charset=utf-8&quot;的响应正文。...
  10. 不得不玩玩NHibernate