2017 国庆清北刷题冲刺班 《角谷猜想》

七月 04, 2018 4029

不错的字符串模拟

题目描述

某个名字末尾是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

1
2
3
4
5
6
5
13713
141713
1333333372589
1411733
2147483647

Sample Output1

1
2
3
4
5
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 )」

显而易见的高精

进而联想到字符串模拟

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

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

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

代码实现

评测记录 AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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;
}