超人基因
题目大意
给定一个正整数，规定一次操作为选定 l,rl,rl,r，删去所有从后往前数第 l∼rl\sim rl∼r 位的数字，且不能把所有的数位全都删完，剩下的数字组成一个新的正整数。
有 TTT 组询问，每次询问给定一个正整数 nnn，你需要判断这个正整数能否通过最多一次操作（不操作也算）将其变为 444 的倍数。
题意分析
给出整数 nnn 求其删掉连续的一段，剩下的数可不可以是 444 的倍数。
解题思路1
首先用 a1∼na_{1 \sim n}a1∼n 表示输入正整数的每一位数字，即 aia_iai 表示输入正整数从左往右数第 iii 位数字。
由于 444 的倍数的特征是末尾两位为 444 的倍数。
末尾的情况可以根据删除的起点可以分成三大类。
* 从 ana_nan 开始往左删除，末尾两位是任意连续的两位；
* 从 an−1a_{n-1}an−1 开始往左删除，末尾两位是 a1∼an−1a_1 \sim a_{n-1}a1 ∼an−1 的中某一个数字跟 ana_nan 组合在一起的数；
* 从其他位置开始往左删除，末尾两位一定是 an−1a_{n-1}an−1 和 ana_nan
如果删除到只剩 111 位数，那么只可能是 a1a_1a1 或者 ana_nan 。
时间复杂度解析
solve 函数的时间复杂度为 O(N)O(N)O(N) ，NNN 表示输入的正整数位数。
代码演示
解题思路2
根据题目意思，我们可以用字符串存储 nnn ，枚举所有 (l,r)(l, r)(l,r) 的删除方案，再将每次删除后剩下的数字对 444 进行求模操作判断即可。
时间复杂度解析
solve 函数的时间复杂度为 O(N3)O(N^3)O(N3) ，NNN 表示输入的正整数位数。
代码演示
