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 + 20; char str[maxn]; char ans[maxn]; int findnotseven(int begin, int end) { for (int i = end; i >= begin; --i) { if (ans[i] != '7') return i; } return inf; } void work() { for (int i = 1; i <= 100; ++i) str[i] = '0'; scanf("%s", str + 1); int lenstr = strlen(str + 1); bool big = false; int lenans = lenstr; int four; int seven; if (lenstr & 1) { big = true; four = lenstr / 2 + 1; seven = lenstr / 2 + 1; lenstr++; } else { four = lenstr / 2; seven = lenstr / 2; } int tnow = 0; int add = 0; int pos = false; char what; for (int i = 1; i <= lenstr; ++i) { if (big) { if (four) { ans[++tnow] = '4'; four--; } else if (seven) { ans[++tnow] = '7'; seven--; } else while(1); } else { if (str[i] > '7') { if (pos) { ans[pos] = what; four = 0; seven = 0; for (int k = 1; k <= pos; ++k) { four += ans[k] == '4'; seven += ans[k] == '7'; } four = lenstr / 2 - four; seven = lenstr / 2 - seven; big = true; i = pos; tnow = pos; } else { add = 2; big = true; four = (lenstr + 2) / 2 - 2; seven = (lenstr + 2) / 2; i = 0; tnow = 0; } } else { if (str[i] >= '5' && str[i] <= '7') { if (seven) { ans[++tnow] = '7'; seven--; if (str[i] != '7') { big = true; four = 0; seven = 0; for (int k = 1; k <= i; ++k) { four += ans[k] == '4'; seven += ans[k] == '7'; } four = lenstr / 2 - four; seven = lenstr / 2 - seven; //************// pos = i; what = '7'; } } else { //也要改 if (pos) { ans[pos] = what; four = 0; seven = 0; for (int k = 1; k <= pos; ++k) { four += ans[k] == '4'; seven += ans[k] == '7'; } four = lenstr / 2 - four; seven = lenstr / 2 - seven; big = true; i = pos; tnow = pos; } else { add = 2; big = true; four = (lenstr + 2) / 2 - 2; seven = (lenstr + 2) / 2; i = 0; tnow = 0; } } } else { if (four) { ans[++tnow] = '4'; four--; if (str[i] != '4') { big = true; four = 0; seven = 0; for (int k = 1; k <= i; ++k) { four += ans[k] == '4'; seven += ans[k] == '7'; } four = lenstr / 2 - four; seven = lenstr / 2 - seven; pos = i; what = '4'; } else { if (seven) { pos = i; what = '7'; } } } else if (seven) { ans[++tnow] = '7'; seven--; big = true; four = 0; seven = 0; for (int k = 1; k <= i; ++k) { four += ans[k] == '4'; seven += ans[k] == '7'; } four = lenstr / 2 - four; seven = lenstr / 2 - seven; pos = i; what = '4'; pos = i; what = '7'; } } } } } while (add--) { printf("4"); } for (int i = 1; i <= tnow; ++i) { printf("%c", ans[i]); } printf(" "); } int main() { #ifdef local freopen("data.txt","r",stdin); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
说一下按位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 + 20; LL ans[maxn]; int lenans; void dfs(LL now, int num_four, int num_seven) { if (num_four == 0 && num_seven == 0) { ans[++lenans] = now; return; } if (num_four == 0) { dfs(now * 10 + 7, num_four, num_seven - 1); } else if (num_seven == 0) { dfs(now * 10 + 4, num_four - 1, num_seven); } else { dfs(now * 10 + 4, num_four - 1, num_seven); dfs(now * 10 + 7, num_four, num_seven - 1); } } void init() { for (int i = 2; i <= 18; i += 2) { dfs(0, i / 2, i / 2); } cout << lenans << endl; } void work() { LL n; scanf("%I64d", &n); if (n > ans[lenans]) { //最大值777777777444444444。1e17内的最大值 printf("44444444447777777777 "); } else { // LL tans = lower_bound(ans + 1, ans + 1 + lenans); // printf("%I64d ", tans); int begin = 1, end = lenans; while (begin <= end) { int mid = (begin + end) >> 1; if (ans[mid] >= n) { end = mid - 1; } else begin = mid + 1; } printf("%I64d ", ans[begin]); } } int main() { #ifdef local freopen("data.txt","r",stdin); #endif init(); int t; scanf("%d", &t); while (t--) work(); return 0; }
可以学习下DFS的做法