Algorithms&Data Structures

智算之道高校组初赛第一场集锦

题目链接:http://oj.csen.org.cn/contest/3

初赛有点水啊,不过第三题还是让我学了一下字符串哈希,所以还是写个题解

A 排队

直接暴力水过

B 开关

从后往前判断一下即可,每个位置根据后面开关灯次数的奇偶来决定是否需要开和关

C 字符串

C题还是有点东西的,一开始用map<string,bool>来映射,无论怎么卡常都是90(也有一些大佬map卡常也能过),然后比赛中学了一下字符串哈希,然后就过了

因为字符串只包含小写字母,开大小为26的数组来记录所要截取的字符串的包含的每种字母的个数,跟S比对,完全一样就hash判断是否出现过,没出现过+1,判断数组置true,最后输出

时间复杂度O(26n)

 

发表评论

邮箱地址不会被公开。 必填项已用*标注