题目描述

某个名字末尾是654321的小A同学是个大家眼中公认的学霸(虽然他永远不承认),他对题目的直觉到了一种可怕的地步,一眼看出题目的算法对他而言只是小 Case,他甚至能在看到一个证明的瞬间敏锐地判断出这个证明的真伪。

现在小A同学机缘巧合地看到了角古猜想(即对于$x$当它为奇数则$x=3x+1$,$x$为偶数,则$x=\frac{x}{2}$,一直重复这个步骤,则最终$x$会变为$1$),在看完这个猜想的一瞬间,他的直觉就来了——他认为角古猜想一定是错的!然后——他立刻就能找出反例!

他立刻在纸上写满了$n$($1<=n<=1000$)个小于$10^L$($0<=L<=10^4$)的正整数,打算放到他的grand super computer 上去跑,可是他突然觉得有些正整数不是很吉利,可能会干扰到他的最终结果,所以他打算把一些正整数加工一下。

小A觉得4、7、13都是不吉利的数字,所以要把所有正整数里的4、7、13都去掉,如果去掉后得到的新数字里依旧有4、7、13,那么就要继续删掉,直到最后的数组不存在4、7、13,它才是一个吉利的数字。例如$1411733=>111733=>11133=>113=>1$
特别规定,如果最后所有数字都被删掉了,就输出$0$
小A觉得这个枯燥的工作不适合他这样的天才,于是就把这个工作交给了你。

当然,只要你能顺利解决,小A承诺会在那篇将会震惊世界的论文的特别感谢栏上署上你的大名。

Input/Output 格式 & 样例

Input

一共$n+1$行。

第一行一个正整数$n$($1<=n<=100$),表示数字个数。

接下来每行一个正整数$x$。

Output

一共$n$行。

每行一个正整数,表示输入每个$x$对应的答案。

Sample Input 1

5
13713
141713
1333333372589
1411733
2147483647

Sample Output1

0
11
3333332589
1
21836

数据范围

对于$10%$的数据,$0<=x<=2147483647$
对于另外的$10%$数据,给定的数字没有数码$3$
对于另外的$10%$数据,$n=1$
对于全部的数据,$n$($1<=n<=1000$),$1<=x<=10^L$($0<=L<=10^4$)

解析

「$1<=x<=10^L$($0<=L<=10^4$)」

显而易见的高精

进而联想到字符串模拟

这道题有两个点需要注意:

  • 顺序不能乱
先执行删除4和7的操作,再执行删除13的操作
  • 在删除13时要检查是否残留
样例里有一个数据1411733
先删除4和7,得到11133
再删除13,得到113

假如只删除一次13,那么就会有残留的13出现
所以要在删除之后进行检查,
否则就需要递归,将13再次删除

代码实现

评测记录 AC

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
using namespace std;

inline string eraseAll4s(string x) {
    string ret = "";
    int len = x.length();
    for (int i = 0; i < len; ++i) if (x[i] == '4') x[i] = '-'; // 删除的'4'用'-'表示
    for (int i = 0; i < len; ++i) if (isdigit(x[i])) ret += x[i]; // 采集存留的数字,组成一个新的字符串
    return ret;
}

inline string eraseAll7s(string x) {
    // 代码思想一样,不再赘述
    string ret = "";
    int len = x.length();
    for (int i = 0; i < len; ++i) if (x[i] == '7') x[i] = '-';
    for (int i = 0; i < len; ++i) if (isdigit(x[i])) ret += x[i];
    return ret;
}

inline string eraseAll13s(string x) {
    string ret = "";
    int len = x.length();
    for (int i = 0; i < len - 1; ++i) {
        if (x[i] == '1' && x[i+1] == '3') x[i] = x[i+1] = '-';
        // 注意这里要同时检测两个字符
    }
    bool b = false;
    for (int i = 0; i < len; ++i) if (isdigit(x[i])) ret += x[i];
    for (int i = 0; i < len - 1; ++i) {
        // 重新进行检查
        if (ret[i] == '1' && ret[i+1] == '3') {
            b = true;
            break;
        }
    }
    if (b) {
        ret = eraseAll13s(ret); // 递归删除
    }
    return ret;
}

string Modify(string x) {
    string ret = "";
    ret = eraseAll4s(x);
    ret = eraseAll7s(ret);
    ret = eraseAll13s(ret);
    // 进行删除
    if (ret == "") ret = "0";
    return ret;
}

int main(int argc, char *const argv[]) {
    ios::sync_with_stdio(false);
    int n;
    string v;
    cin >> n;
    while (n --> 0) {
        /*
           这里是一个比较神奇的 while(),
           效果相当于 for (int i = 0; i < n; ++i),
           但是会对n进行修改,下标也是从n-1到0
        */
        cin >> v;
        cout << Modify(v) << endl;
    }
    return 0;
}
01-31 21:45