1, Enumeration: 1753, 2965
2, Greedy: 2109, 2586
3, Minimum spanning tree: 2485, 1258
4, Sort: 2388
5, Deep optimization search: 1321, 2251
6, Breadth optimization search: 3278, 1426
7, Simple search techniques and pruning: 2676
8, Backpack problem: 1837
9, Topology sorting: 1094
10, Shortest path algorithm: 1062, 1125, 2240
11, Huffman tree: 3253
12, Efficient search methods such as hash table and binary search: 2151, 2503
Continue to practice enumeration this week.
Peking University POJ2956: repetition numbers
subject
analysis
Input: the input test file will contain multiple test cases, and each test case is composed of a single line containing the integer ﹐ n ﹐ where 1 ≤ n ≤ 1000000. The end of the file is marked by a test case with n = 0 and should not be processed.
Output: for each input case, the program shall print the # nth # non repeating number on one line.
Sample input:
25
10000
0
Sample output:
27
26057
My idea:
It is a violent solution. Enumeration + classification judge whether the conditions are met.
Advanced
1. Use BFS:
I didn't expect to use BFS at all.
——The initial state is 1 ~ 9. The state of the next layer can be obtained by continuously adding 0 ~ 9 after the initial state. The state of the second layer is continuously expanded until it is extended to the 1000000 state. Each state contains two attributes value and digit. Value is the value of the state. If it is 134, then digit is 11010, and d[i]=1 means I in value. When adding numbers from 0 to 9 after number 134 (assuming the added number is 1), how to judge whether 1 has appeared in 134? If value=1, then digit = 10, and operate 11010 and 10, i.e. 11010 & 10. If the result is not equal to 0, This indicates that 1 exists in 134, otherwise it does not exist.
2. Consider some situations Reduce enumeration:
Create an array, save each bit, and judge whether there are duplicate numbers (it feels a bit like bit storage in the first chapter). For example, for a number 128267, its second bit (from right to left) and the fourth bit are the same, so the numbers like 1282 * * do not need to be enumerated, but can be enumerated directly from 128300, which can speed up the enumeration time.
Code
1. BFS:
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 using namespace std;
5
6 const int N = 1000000;
7 struct Number
8 {
9 int value; //Decimal representation of numbers
10 int digit; //Binary sequence, number digit[i]==1 from right to left, indicating that there is I in value
11
12 Number(){}
13 Number(int v, int d):value(v), digit(d){}
14 }ans[N+10];
15
16 int main()
17 {
18 for(int i=1; i<10; i++)
19 ans[i] = Number(i, 1<<i);
20
21 int k = 1;
22 for(int cur=10; cur<=N; k++)
23 {
24 int v = ans[k].value;
25 int d = ans[k].digit;
26
27 for(int i=0; i<10; i++)
28 {
29 if( !(d & (1<<i)))
30 ans[cur++] = Number(v*10+i, d|1<<i);
31 }
32 }
33
34 int n;
35 while(scanf("%d", &n)==1 && n)
36 printf("%d\n", ans[n].value);
37 return 0;
38 }2. Reduce enumeration:
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 using namespace std;
5
6 const int N = 1000000;
7 int ans[N+1] = {0};
8 int power[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
9
10 void init()
11 {
12 int d[10]; //Store number x
13 int v[10]; //v[i] indicates whether the number I has appeared in x
14 int cur = 1;
15 int x, y=1;
16 while(cur<=N)
17 {
18 x = y;
19 memset(v, -1, sizeof(v));
20 memset(d, 0, sizeof(d));
21
22 int i, j;
23 for(i=0; x!=0; i++)
24 {
25 d[i] = x % 10;
26 if(v[d[i]]!=-1)
27 break;
28 v[d[i]] = i;
29 x /= 10;
30 }
31 if(!x)
32 {
33 ans[cur++] = y;
34 y++;
35 }
36 else
37 {
38 j = v[d[i]];
39 for(i--; i>=j; i--)
40 x = x*10+d[i];
41 x++;
42 y = x*power[j];
43 }
44 }
45 }
46
47 int main()
48 {
49 init();
50 int n;
51 while(cin>>n && n)
52 cout<<ans[n]<<endl;
53 return 0;
54 }