ztr loves lucky numbers 傻逼的我来了个大模拟

http://acm.hdu.edu.cn/showproblem.php?pid=5676

这题的正解因该是dfs的，但是有18个位，然后我一算，全排列的话，有18!个啊，那不是很大？但是有很多是相同的，因为4477和第一个和第二个数字调转的结果是一样的。

先说说我模拟的方法。

真的很麻烦，不想看的，给几组数据就跑

7
0
8
4500
47
55
44447778
78
47777445

我是贪心模拟前n位，模拟的时候，如果这一位是3，如果我还有4，那么证明比后面的大了，然后后面的直接按4优先输出即可。

还有可能要加位的，就是78这样，要加位。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn = 1e2 + ;

char str[maxn];

char ans[maxn];

int findnotseven(int begin, int end) {

    for (int i = end; i >= begin; --i) {

        if (ans[i] != '') return i;

    }

    return inf;

}

void work() {

    for (int i = ; i <= ; ++i) str[i] = '';

    scanf("%s", str + );

    int lenstr = strlen(str + );

    bool big = false;

    int lenans = lenstr;

    int four;

    int seven;

    if (lenstr & ) {

        big = true;

        four = lenstr /  + ;

        seven = lenstr /  + ;

        lenstr++;

    } else {

        four = lenstr / ;

        seven = lenstr / ;

    }

    int tnow = ;

    int add = ;

    int pos = false;

    char what;

    for (int i = ; i <= lenstr; ++i) {

        if (big) {

            if (four) {

                ans[++tnow] = '';

                four--;

            } else if (seven) {

                ans[++tnow] = '';

                seven--;

            } else while();

        } else {

            if (str[i] > '') {

                if (pos) {

                    ans[pos] = what;

                    four = ;

                    seven = ;

                    for (int k = ; k <= pos; ++k) {

                        four += ans[k] == '';

                        seven += ans[k] == '';

                    }

                    four = lenstr /  - four;

                    seven = lenstr /  - seven;

                    big = true;

                    i = pos;

                    tnow = pos;

                } else {

                    add = ;

                    big = true;

                    four = (lenstr + ) /  - ;

                    seven = (lenstr + ) / ;

                    i = ;

                    tnow = ;

                }

            } else {

                if (str[i] >= '' && str[i] <= '') {

                    if (seven) {

                        ans[++tnow] = '';

                        seven--;

                        if (str[i] != '') {

                            big = true;

                            four = ;

                            seven = ;

                            for (int k = ; k <= i; ++k) {

                                four += ans[k] == '';

                                seven += ans[k] == '';

                            }

                            four = lenstr /  - four;

                            seven = lenstr /  - seven;

                            //************//

                            pos = i;

                            what = '';

                        }

                    } else { //也要改

                        if (pos) {

                            ans[pos] = what;

                            four = ;

                            seven = ;

                            for (int k = ; k <= pos; ++k) {

                                four += ans[k] == '';

                                seven += ans[k] == '';

                            }

                            four = lenstr /  - four;

                            seven = lenstr /  - seven;

                            big = true;

                            i = pos;

                            tnow = pos;

                        } else {

                            add = ;

                            big = true;

                            four = (lenstr + ) /  - ;

                            seven = (lenstr + ) / ;

                            i = ;

                            tnow = ;

                        }

                    }

                } else {

                    if (four) {

                        ans[++tnow] = '';

                        four--;

                        if (str[i] != '') {

                            big = true;

                            four = ;

                            seven = ;

                            for (int k = ; k <= i; ++k) {

                                four += ans[k] == '';

                                seven += ans[k] == '';

                            }

                            four = lenstr /  - four;

                            seven = lenstr /  - seven;

                            pos = i;

                            what = '';

                        } else {

                            if (seven) {

                                pos = i;

                                what = '';

                            }

                        }

                    } else if (seven) {

                        ans[++tnow] = '';

                        seven--;

                        big = true;

                        four = ;

                        seven = ;

                        for (int k = ; k <= i; ++k) {

                            four += ans[k] == '';

                            seven += ans[k] == '';

                        }

                        four = lenstr /  - four;

                        seven = lenstr /  - seven;

                        pos = i;

                        what = '';

                        pos = i;

                        what = '';

                    }

                }

            }

        }

    }

    while (add--) {

        printf("");

    }

    for (int i = ; i <= tnow; ++i) {

        printf("%c", ans[i]);

    }

    printf("\n");

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

说一下按位DFS的做法

预处理出所有结果，首先要知道有多少种结果

当数字有18位的时候，9位4,9位7，那么C(18, 9)的意思就是选9个位置来放四，其他的放7，那么结果就是C（18,9）

所以总答案数只有66196种。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn = 1e6 + ;

LL ans[maxn];

int lenans;

void dfs(LL now, int num_four, int num_seven) {

    if (num_four ==  && num_seven == ) {

        ans[++lenans] = now;

        return;

    }

    if (num_four == ) {

        dfs(now *  + , num_four, num_seven - );

    } else if (num_seven == ) {

        dfs(now *  + , num_four - , num_seven);

    } else {

        dfs(now *  + , num_four - , num_seven);

        dfs(now *  + , num_four, num_seven - );

    }

}

void init() {

    for (int i = ; i <= ; i += ) {

        dfs(, i / , i / );

    }

    cout << lenans << endl;

}

void work() {

    LL n;

    scanf("%I64d", &n);

    if (n > ans[lenans]) { //最大值777777777444444444。1e17内的最大值

        printf("44444444447777777777\n");

    } else {

//        LL tans = lower_bound(ans + 1, ans + 1 + lenans);

//        printf("%I64d\n", tans);

        int begin = , end = lenans;

        while (begin <= end) {

            int mid = (begin + end) >> ;

            if (ans[mid] >= n) {

                end = mid - ;

            } else begin = mid + ;

        }

        printf("%I64d\n", ans[begin]);

    }

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    init();

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

可以学习下DFS的做法

巴特西

ztr loves lucky numbers 傻逼的我来了个大模拟

最新文章

热门文章