1、目前为止见过的最长的第一道题目了，直接计数就OK了
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cmath> 6 #include <map> 7 #include <stack> 8 #include <algorithm> 9 #include <list> 10 #include <ctime> 11 #include <set> 12 #include <queue> 13 typedef long long ll; 14 using namespace std; 15 int a[30]; 16 class CityMap { 17 public: 18 string getLegend(vector<string> cityMap, vector<int> POIs) { 19 int r = cityMap.size(); 20 int c = cityMap[0].size(); 21 int sz = POIs.size(); 22 string res; 23 for (int i = 0; i < r; i++) { 24 for (int j = 0; j < c; j++) { 25 int t = cityMap[i][j] - 'A'; 26 if (cityMap[i][j] != '.') { 27 a[t]++; 28 } 29 } 30 } 31 for (int i = 0; i < sz; i++) { 32 for (int j = 0; j < 30; j++) { 33 if (a[j] == POIs[i]) { 34 char t = 'A' + j; 35 res += t; 36 break; 37 } 38 39 } 40 41 } 42 return res; 43 44 } 45 };
2、当时脑子秀逗了，写了一百多行，只需要对当前情况和翻转以后判断一些就ok了，B出现在A的最左边时需要注意一下，我就这么cha掉一个
#include <iostream> #include <string> #include <vector> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <algorithm> #include <list> #include <ctime> #include <set> #include <queue> #include <sstream> typedef long long ll; using namespace std; int exist[20]; class TheNumberGameDiv2 { public: int minimumMoves(int A, int B) { stringstream a, b; a << A; b << B; string va, vb; a >> va; b >> vb; int sza = va.size(); int szb = vb.size(); int pos = va.find(vb); int res=100; if (pos == 0) { res=min(res, (sza - szb)); } else if (pos > 0) { res=min(res, (sza - szb) + 2); } reverse(va.begin(), va.end()); pos = va.find(vb); if (pos >= 0) { res=min(res, (sza - szb) + 1); } if(res==100) return -1; return res; } };
3、递归算法就ok了，第二道题耽误太多时间，没时间写了
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cmath> 6 #include <map> 7 #include <stack> 8 #include <algorithm> 9 #include <list> 10 #include <ctime> 11 #include <set> 12 #include <queue> 13 typedef long long ll; 14 using namespace std; 15 16 int exist[20]; 17 18 class PolygonTraversal2 { 19 public: 20 21 int bfs(int cur, int n,int s) { 22 int over = 1; 23 int res = 0; 24 for (int i = 0; i < n; i++) { 25 if (exist[i] == 0) { 26 over = 0; 27 break; 28 } 29 } 30 if (1 == over) { 31 if (cur == ((s+n-1)%n) || cur == ((s+1)%n)) { 32 return 0; 33 } else { 34 return 1; 35 } 36 } 37 for (int i = 0; i < n; i++) { 38 if (exist[i] == 0) { 39 int start = min(i, cur); 40 int end = max(i, cur); 41 int num = 0; 42 for (int j = start + 1; j < end; j++) { 43 if (exist[j] == 1) { 44 num++; 45 break; 46 } 47 } 48 49 if (1 == num) { 50 for (int j = (end + 1); j < n; j++) { 51 if (exist[j] == 1) { 52 num = 2; 53 break; 54 } 55 } 56 for (int j = 0; j < start; j++) { 57 if (exist[j] == 1) { 58 num = 2; 59 break; 60 } 61 } 62 } 63 64 if (2 == num) { 65 exist[i] = 1; 66 int t = bfs(i, n,s); 67 res = res + t; 68 exist[i] = 0; 69 } 70 } 71 } 72 73 return res; 74 } 75 int count(int N, vector<int> points) { 76 int sz = points.size(); 77 int t = 100; 78 for (int i = 0; i < sz; i++) { 79 t = min(points[i], t); 80 } 81 for (int i = 0; i < sz; i++) { 82 points[i] = points[i] - t; 83 } 84 for (int i = 0; i < sz; i++) { 85 exist[points[i]] = 1; 86 } 87 int cur = points[sz - 1]; 88 int res = bfs(cur, N,points[0]); 89 return res; 90 91 } 92 };
DIV1-2、状态压缩，用DIV2-2做成dp应该也可以，peter的代码改的~~
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cmath> 6 #include <map> 7 #include <stack> 8 #include <algorithm> 9 #include <list> 10 #include <ctime> 11 #include <set> 12 #include <queue> 13 typedef long long ll; 14 using namespace std; 15 16 class PolygonTraversal { 17 public: 18 ll count(int N, vector<int> points) { 19 int all = (1 << N); 20 vector<vector<ll> > ways(all, vector<ll>(N, 0)); 21 int start = 0; 22 int sz = points.size(); 23 for (int i = 0; i < sz; i++) { 24 start = start | (1 << (points[i] - 1)); 25 } 26 ways[start][points[sz - 1] - 1] = 1; 27 for (int set = 0; set < all; ++set) 28 for (int cur = 0; cur < N; ++cur) 29 if (ways[set][cur] > 0) { 30 for (int next = 0; next < N; ++next) 31 if ((set & (1 << next)) == 0) { 32 int a = min(cur, next); 33 int b = max(cur, next); 34 int m1 = (set & ((1 << a) - 1)) 35 | ((set >> (b + 1)) << (b + 1)); 36 int m2 = ((set & ((1 << b) - 1)) >> (a + 1)) 37 << (a + 1); 38 if (m1 == 0 || m2 == 0) 39 continue; 40 ways[set | (1 << next)][next] += ways[set][cur]; 41 } 42 } 43 ll res = 0; 44 for (int cur = 0; cur < N; ++cur) 45 if (ways[all - 1][cur] > 0) { 46 int set = all - 1; 47 int next = points[0] - 1; 48 int a = min(cur, next); 49 int b = max(cur, next); 50 int m1 = (set & ((1 << a) - 1)) | ((set >> (b + 1)) << (b + 1)); 51 int m2 = ((set & ((1 << b) - 1)) >> (a + 1)) << (a + 1); 52 if (m1 == 0 || m2 == 0) 53 continue; 54 res += ways[set][cur]; 55 } 56 return res; 57 } 58 };