A Tricky Template
题目描述
给一个数字
n和三个长度为n的字符串a,b,c。找一个模板使得字符串a,b匹配，而c不匹配,是否存在这样一个模板.
匹配的定义是:当模板字母为小写时,两个字符串字符相同,为大写时,两个字符不同,这样的两个字符串则匹配
解题思路
我们可以直接得出当
a字符串和b字符串都不等于c字符串时,就存在这样一个模板使得满足题意
参考代码
B Forming Triangles
题目描述
给定一个长度为
n的一个数组a,对于a[i]来说,就是一个长度为2^a[i]的木棒,现在问:用这些木棒能组成多少个三角形.
解题思路
对于一个三角形来说,两边之和大于第三边,两边之差小于第三边,不可能存在两边之和等于第三边,那么我们就可以得到要组成一个三角形就至少需要两条边相等,第三边小于等于这两个边,那么这个问题就成了一个组合数问题
组合数用
C(cnt, m)来表示,其中cnt为这个数的总数,m为我们需要选的个数;
cnt可以用map来写,对数组去重,遍历一次数组,s表示比遍历到当前数字小的个数
即写成ans += C(mp[a[i]], 3) + C(mp[a[i]], 2) * s
参考代码
C Closest Cities
题目描述
在
x轴上有n个城市,其位置为a[i],并且序列a按升序排列,保证每个城市只有一个最近的城市
若i的最近城市是i+1则花费1,否则花费|a[i]-a[i+1]|,现在有q次询问
问:每次询问城市x到城市y的最小花费.
解题思路
先分析一下
x<y,我们只有一直向右走才会有最小花费,那就需要判断当前城市的最近城市是否为下一个城市.
由于是一直向右走,我么就可以用前缀和求解这个问题.
同理,x>y时,我们是从右向左走,可以用后缀和求解.
