hihocoder
1151:提补交卡
提取主要信息:得到最长连续天数
在一张补交卡提交之后,总能得到比之前所有连续天数更长的数据。
简单来说,我们需要明白,这里的连续天数是如何求到的。显然,两个连续出现的未签到日期的序号之差即为连续天数,而求其中最大,则是找到其中具有最大差值的两个序号。
一言以蔽之:只有连续使用补交卡才能获得最大值——即贪心算法+枚举。
伪代码如下:
if N > M then : return 100;
days[0] = {0};
days[1...M] = { 未签到日期 };
max = 0;
for i = 0 to days.length then:
max = days[N]-days[0] > max ? (days[N]-days[0]) : max;
这个问题只要明白连续天数所具有的含义,就已经做完了。
1135:Magic Box
这是一道枚举题,非常简单,甚至不需要提取有效信息,阅读完之后立刻能想到枚举。
直接伪代码:
input = 输入的子串;
x[3] = 爆炸时气球个数差;
ryd[3] = 各种颜色的统计;
for i = 1 to input.length then :
统计各种颜色的总数;
if 两两颜色差值是否与爆炸时气球个数差相同 then :
max = 当前箱中气球总数 > max ? 总数 : max;
清空ryd;
1120:小Hi和小Ho的惊天大作战:扫雷 三
int check(k) // k传入的是一个可能的地雷分布,判断该分布是否符合要求
// 我们知道,这个传入的k其实是0~2^num的一个序列,那问题来了,为什么可以这样去传入序列呢?
// 将这个范围转换成二进制,我们就不难发现,其实1~2^num是:00000000~11111111
// 可以想象到,这个范围是对分布的一个直接枚举,(我们手动枚举当然是可以的,但,我们需要枚举多少个呢?答案是2^num+1个)
if(k & (1<<i))
// 这一句其实就是在遍历传入的分布,也是通过二进制的性质实现的。
这里借鉴的是@小拳头的代码,原文章。
文章最后发布于: 2018-03-31 20:21:10
相关阅读
hihoCoder - 1633(2017北京icpc现场赛-G题)
题意:给你一个三角形的三个坐标,还有一张图,让你从图中的左下角走到右上角,左下角坐标是(0,0),每两点之间的长度是1,'.'代表能走,'#'代表不
#1538 : 大礼堂地毯 时间限制:10000ms 单点时限:1000ms 内存限制:2