D. Problem with Random Tests(暴力贪心)
创始人
2024-01-25 08:38:17
0次
D. Problem with Random Tests(暴力&贪心)
s1=ss_1=ss1=s，显然是最优的，因为答案不会更坏。
s2s_2s2 取前缀答案不会更劣。
不如s∣(1101),s∣(0101)s|(1101),s|(0101)s∣(1101),s∣(0101) 比s∣(101)s|(101)s∣(101)好。
因此枚举前缀。
因此我们只需找到第一个0的位置即可。
注意到数据随机，所以前303030位都为111的概率为1230\dfrac{1}{2^{30}}2301很小。所以枚举前30位即可。
时间复杂度：O(30n)O(30n)O(30n)
#include
using namespace std;
int n;
string s;
int main() {cin >> n >> s;string an = s;for(int i = 1; i < 30; i++) {string t = s;for(int j = i; j < n; j++) t[j] |= s[j - i];if(an < t) an = t;}int st = 0;while(st < n - 1 && s[st] == '0') st++;cout << an.substr(st) << '\n';return 0;
}
相关内容
热门资讯
首批基金半年报出炉 A股中长期...
对于下半年市场行情，基金预期，指数将窄幅震荡，但仍有望延续结构性行情。就经济基本面而言，富安达健康人...
重磅！证监会正式发布重组新规 ...
（原标题：重磅！证监会正式发布重组新规，允许创业板借壳上市，恢复配套融资，简化认定标准，上市公司重组...
2018年东莞市创新创新兴行业...
5月7日下午，2018年“创客广东”东莞市创新创业大赛推介会在松山湖融易大厦召开。这意味着由东莞市经...
成人在线教育 提升学历的好处有...
中国日报网3月28日电（记者贺炜）28岁的陈华（音）是上海的一名汽车工程师。自从他在一款手机应用软件...
新移民邂逅新经济 中国关注新经...
中国侨网1月1日电据美国《侨报》报道，华人在美国经营中餐馆已有超过百年历史，以前来美新移民多是在中餐...
英文新书《海南 英文新书《海南...
英文新书《海南——中国新兴瑰宝》海口首发南海网12月20日消息(南海网记者赵仕芳)12月19日，...
2019中国美妆行业研究 进入...
作者：孙继文赵悦彤张喻璠指导：潘航自过去一个多世纪以来，国内美妆行业在走到现在的繁盛状态之前，经历了...
1000元创业项目 千元创业 ...
1000元创业项目？对于很多人来说，创业是需要大量的资金的，但是倘若有1000元就能创业的项目，那么...
76小时众筹1000万元 腾讯...
76小时众筹1000万元区块链创业不差钱缺好项目证券时报网证券时报网（）07月13日讯证券时报记者江...
2020春招季 春招进展怎么样...
北京4月10日电（记者陈听雨）2020年高校应届毕业生数量达到874万，创下新高。受新冠肺炎疫情影响...