超人基因

题目大意

给定一个正整数，规定一次操作为选定 $l,r$，删去所有从后往前数第 $l\sim r$ 位的数字，且不能把所有的数位全都删完，剩下的数字组成一个新的正整数。

有 $T$ 组询问，每次询问给定一个正整数 $n$，你需要判断这个正整数能否通过最多一次操作（不操作也算）将其变为 $4$ 的倍数。

题意分析

给出整数 $n$ 求其删掉连续的一段，剩下的数可不可以是 $4$​​ 的倍数。

解题思路1

首先用 $a_{1 \sim n}$ 表示输入正整数的每一位数字，即 $a_i$ 表示输入正整数从左往右数第 $i$ 位数字。

由于 $4$ 的倍数的特征是末尾两位为 $4$​ 的倍数。

末尾的情况可以根据删除的起点可以分成三大类。

• 从 $a_n$ 开始往左删除，末尾两位是任意连续的两位；
• 从 $a_{n-1}$ 开始往左删除，末尾两位是 $a_1 \sim a_{n-1}$ 的中某一个数字跟 $a_n$ 组合在一起的数；
• 从其他位置开始往左删除，末尾两位一定是 $a_{n-1}$ 和 $a_n$​

如果删除到只剩 $1$ 位数，那么只可能是 $a_1$ 或者 $a_n$ 。

时间复杂度解析

solve 函数的时间复杂度为 $O(N)$ ，$N$​ 表示输入的正整数位数。

代码演示

#include<iostream>
using namespace std;

typedef long long LL;

bool check(LL n){
	LL k = n;
	while(k){
		if(k % 4 == 0) return true;
		k /= 10;
	}
	k = n / 10;
	LL g = n % 10;
	if(g % 4 == 0) return true;
	while(k){
		LL t = k % 10 * 10 + g;
		if(t % 4 == 0) return true;
		k /= 10;
	}
	return false;
}

void solve(){
	LL n;
	cin >> n;
	cout << (check(n) ? "Yes" : "No") << endl;
}

int main() {
	LL t;
	cin >> t;
	while(t -- ) solve();
	return 0;
}

解题思路2

根据题目意思，我们可以用字符串存储 $n$ ，枚举所有 $(l, r)$ 的删除方案，再将每次删除后剩下的数字对 $4$ 进行求模操作判断即可。

时间复杂度解析

solve 函数的时间复杂度为 $O(N^3)$ ，$N$ 表示输入的正整数位数。

代码演示

#include<iostream>
using namespace std;

typedef long long LL;

LL change(string s){
    LL num = 0;
    int len = s.size();
    for(int i = 0; i < len; ++ i )
      num = num * 10 + (s[i] - '0');
    return num;
}

void solve(){
    string s;
    cin >> s;
    int len = s.size(), flag = 0;
    for(int i = 0; i < len; ++ i ){
        if(flag) break;
        for(int j = i; j < len; ++ j ){
            string k = s;
            auto it_start = k.begin() + i;
            auto it_end = k.begin() + j + 1;
            if(!(i == 0 && j + 1 == len)) k.erase(it_start, it_end);
            LL num = change(k);
            if(num % 4 == 0){
                flag = 1;
                break;
            }
        }
    }
    if(flag) cout << "Superman" << endl;
    else cout << "Human" << endl;
}

int main(){
	int t;
    cin >> t;
    while(t -- ) solve();
	return 0;
}