[ABC150-A]500日元硬币

题意

给定$k$枚$500$日元的硬币，判断是否大于等于$x$。

解法

直接定义两个变量$k$和$x$并输入，判断$k \times 500$是否大于等于$x$即可。

---

[ABC112-B]超过时间限制

题意

给定多条路线，每条路线$i$有一个费用$c_i$和时间$t_i$。求出在满足时间限制的情况下最小的回家费用。

解法

遍历所有的路线，如果满足时间限制，则判断费用是否比当前最小的还要小，如果是的话更新最小费用即可。

---

[ABC150-B]ABC计数

题意

判断给定字符串中有多少个子串为"ABC"。

解法

子串/连续子序列：要求连续

子序列：不要求连续

先定义一个ans=0，然后枚举$i$从$2$到$n-1$，如果s[i-1]== 'A' && s[i] == 'B' && s[i+1] == 'C'，则ans加一。最后输出ans即可。

---

[ABC150-C]计数顺序

题意

给定两个$1$到$n$的排列$p$和$q$，判断他们按照字典序全排列后的索引差值的绝对值。

解法

本题数据量较小，因此可以直接暴力枚举。

定义两个string类型变量输入，让$p$是较小的那一个，$q$是较大的那一个，从$p$开始迭代，一直到$q$走了多少步输出就可以。

c++函数：next_permutation( 起始位置，终止位置)，可以让起始位置和终止位置之间的序列得到下一个排列，如果没有下一个序列返回false，否则返回true。

对于一个string类型变量来说，起始位置是s.begin()，结束位置是s.end()。

---

[ABC108-C]三角关系

题意

给定两个整数$n,k$，计算三元组$(a,b,c)$的数量。三元组满足$a,b,c$均小于$n$且，$a+b,a+c,b+c$都是$k$的倍数。

解法

考虑$a,b,c$都是$k$的倍数，一定是满足条件的，一共有$(\frac{n}{k}) ^ 3$种可能。

另外的情况，假设$a,b,c$中有不是$k$的倍数的数字，如果$k$是奇数，可以证明$a,b,c$必定是$k$的倍数。因此只需要考虑$k$为偶数的情况。

剩下的情况里两个数字加起来为$k$，只有一种情况，就是三个数字都是$\frac{k}{2}$的奇数倍的和。

---

[ABC108-C]三角关系

证明：

因为$a+b,a+c$都是$k$的倍数，因此$b\%k == c\%k == temp$。又因为$b+c==k$，因此$temp+temp = 2*temp = k$。即$b$和$c$除以$k$的余数都是$\frac{k}{2}$，即他们都是$\frac{k}{2}$的奇数倍。

如果有一个是偶数倍，则加起来一定会多一个$\frac{k}{2}$，如果两个都是偶数，则包含在第一种情况里。

因此，如有$k$是偶数，答案还需要再加上$[1,n]$中 $\frac{k}{2}$的奇数倍的个数，即$( \frac{n}{ \frac{k}{2} } - \frac{n}{k})$

---

[ABC150-D]半公倍数

题意

给定一个长度为 $n \ (1 \leq n \leq 10^5)$ 的数组$a$，且 $a_i$ 是偶数，求 $[1, M]$ 有多少个 $X$ 满足对任意 $X = a_i \cdot (p + 0.5)$ 成立。

解法

原来的公式可以转换为：$x = \frac{a_i}{2} \cdot (2 \cdot p + 1)$,即 $x$ 一定是所有$\frac{a_i}{2}$的奇数倍。

令$b_i = \frac{a_i}{2}$

我们把这个问题拆解成两部分，首先，$x$必须是所有$b_i$的倍数，也就是$x$是所有$b_i$的最小公倍数$lcm$的倍数。

然后是第二个条件，$x$还得是所有$b_i$的奇数倍才行。这里引入了两个条件，首先$x$必须是$lcm$的奇数被，其次，$lcm$必须是所有$b_i$的奇数倍。

我们可以这样判断：如果$lcm$除以每个$b_i$都是奇数，就说明可行。如果$lcm$除以某一个$b_i$得到了偶数，则直接输出0即可，因为$x$不可能是所有$b_i$的奇数倍。