本来早就该写的，一直拖到现在。
第一题应该算是很水的题，就是数字的种类乘以某种数字出现的最大次数。
http://community.topcoder.com/stat?c=problem_solution&rm=313611&rd=15170&pm=11985&cr=23038076
第二题比赛期间没有想到，后来看来一下别人的，原来用二分法就可以搞定了
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <map> 6 #include <algorithm> 7 #include <cmath> 8 using namespace std; 9 class KingdomAndTrees{ 10 public: 11 bool valid(vector <int> heights,int l,int n){ 12 heights[0]=max(heights[0]-l,1); 13 for(int i=1;i<n;i++){ 14 if(heights[i]<=heights[i-1]) 15 heights[i]=min(heights[i-1]+1,heights[i]+l); 16 else 17 heights[i]=max(heights[i-1]+1,heights[i]-l); 18 19 if(heights[i]<=heights[i-1]) 20 return false; 21 } 22 return true; 23 24 } 25 int minLevel(vector <int> heights){ 26 int left=0; 27 int right=1000000000; 28 int mid; 29 int n=heights.size(); 30 int exists=0; 31 while(left<right){ 32 mid=(left+right)/2; 33 if(valid(heights,mid,n)){ 34 right=mid; 35 exists=1; 36 }else{ 37 left=mid+1; 38 } 39 } 40 41 return left; 42 } 43 };
第三题则悲催了，用的穷举法加剪枝，明显不行，第五个测试用例就超时了，就没有提交，据说是用的DFS，还没有看大牛的代码。
topcoder wiki 的答案，加上了自己的一点注释，自己真心想不出来啊.....
1 #define FOR(x,a,b) for (int x = a; x <= b; x++) 2 int f[(1 << 17) + 10][18][2]; 3 int n, cs[17], res[17], old[17]; 4 vector<int> rt; 5 6 //s store information about wich digits is used 7 //i is the position that we have to dicide which digits to push in 8 //ok = 1 min the i + 1 digits prefix of the password is strictly less than the 9 //i + 1 digits prefix of oldpassword 10 //f[s][i][ok] = 1 mean we can continue bulding the password that strictly less than oldpassword 11 int lower(int s, int i, int ok) { 12 if (f[s][i][ok] != -1)//假如已经计算出来了 13 return f[s][i][ok]; 14 if (i == n) { 15 f[s][i][ok] = ok;//备忘录 16 return ok; 17 } 18 19 f[s][i][ok] = 0; 20 FORD(j, n - 1, 0)//因为是选取小于原数字的最大值，所以倒着选 21 if ((s & (1 << j)) == 0 //第j位还没有使用 22 && cs[j] != rt[i]//不是限制的数字 23 && (ok == 1 || cs[j] <= old[i]))//已经严格小或者当前位<=原来的 24 if (lower(s | (1 << j),//使用第j位 25 i + 1, //计算后边的 26 ok | (cs[j] < old[i]))) //填加第j位后是否<原来的 27 { 28 f[s][i][ok] = 1; 29 return 1; 30 } 31 32 return 0; 33 } 34 35 //find the maximum password in all passwords that less than oldpassword 36 void find_lower(int s, int i, int ok) { 37 if (i == n) 38 return; 39 40 FORD(j, n - 1, 0) 41 if ((s & (1 << j)) == 0 &&//某一位还没有选 42 cs[j] != rt[i] &&//不是限制条件 43 (ok == 1 || cs[j] <= old[i]))//判断是否可以用这个数字 44 if (lower(s | (1 << j), i + 1, ok | (cs[j] < old[i]))) { 45 res[i] = cs[j]; 46 find_lower(s | (1 << j), i + 1, ok | (cs[j] < old[i])); 47 return; 48 } 49 } 50 51 //funtion upper and find_upper is similar with lower and find_lower 52 int upper(int s, int i, int ok) { 53 if (f[s][i][ok] != -1) 54 return f[s][i][ok]; 55 if (i == n) { 56 f[s][i][ok] = ok; 57 return ok; 58 } 59 60 f[s][i][ok] = 0; 61 FOR (j, 0, n - 1) 62 if ((s & (1 << j)) == 0 && cs[j] != rt[i] 63 && (ok == 1 || cs[j] >= old[i])) 64 if (upper(s | (1 << j), i + 1, ok | (cs[j] > old[i]))) { 65 f[s][i][ok] = 1; 66 return 1; 67 } 68 return 0; 69 } 70 71 void find_upper(int s, int i, int ok) { 72 if (i == n) 73 return; 74 75 FOR (j, 0, n - 1) 76 if ((s & (1 << j)) == 0 && cs[j] != rt[i] 77 && (ok == 1 || cs[j] >= old[i])) 78 if (upper(s | (1 << j), i + 1, ok | (cs[j] > old[i]))) { 79 res[i] = cs[j]; 80 find_upper(s | (1 << j), i + 1, ok | (cs[j] > old[i])); 81 return; 82 } 83 } 84 85 long long newPassword(long long oldPassword, vector<int> restrictedDigits) { 86 n = 0; 87 LL tg = oldPassword; 88 while (tg) { 89 cs[n++] = tg % 10; 90 tg /= 10; 91 } 92 93 //old store digits of oldPassword from left to right 94 //cs store digits of oldPassword in non-decrease order 95 FOR (i, 0, n - 1) 96 old[i] = cs[n - 1 - i]; 97 sort(cs, cs + n); 98 99 rt = restrictedDigits; 100 //FOR (i, 0, n - 1) cout << old[i] << " " << cs[i] << " " << rt[i] << endl; 101 102 //if the new password can be same as the old one, return it 103 int ok = 1; 104 FOR (i, 0, n - 1) 105 if (old[i] == rt[i]) 106 ok = 0; 107 if (ok) 108 return oldPassword; 109 110 LL a, b; 111 a = b = -1; 112 113 //find a is the maximum password that less than the oldPassword 114 SET(f, -1); 115 if (lower(0, 0, 0)) { 116 find_lower(0, 0, 0); 117 a = 0; 118 FOR (i, 0, n - 1) 119 a = a * 10 + res[i]; 120 } 121 122 //find b is the minimum password that greater than the oldPassword 123 SET(f, -1); 124 if (upper(0, 0, 0)) { 125 find_upper(0, 0, 0); 126 b = 0; 127 FOR (i, 0, n - 1) 128 b = b * 10 + res[i]; 129 } 130 131 //decide a or b is the result 132 if (a == -1) 133 return b; 134 if (b == -1) 135 return a; 136 137 if (abs(a - oldPassword) > abs(b - oldPassword)) 138 return b; 139 if (abs(a - oldPassword) < abs(b - oldPassword)) 140 return a; 141 142 return a; 143 144 }