【 2013 Multi-University Training Contest 8 】-白红宇

【 2013 Multi-University Training Contest 8 】

阅读量：5278 次

发布时间：2019-06-14

本文共 8560 字，大约阅读时间需要 28 分钟。

HDU 4678

对于每个空白区域，求SG值。

最后异或起来等于0，先手必败。

1 #pragma comment(linker,"/STACK:102400000,102400000")  2 #include
      
         3 #include
       
          4 #define MAXN 1010  5 #define oo 1234567890  6 int arr[MAXN][MAXN];  7 bool vis[MAXN][MAXN];  8 int n, m;  9 int dg, bk; 10 int sg[MAXN * MAXN][2]; 11 int go[8][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { -1, -1 }, 12         { -1, 1 }, { 1, -1 }, { 1, 1 } }; 13 bool isIn(int x, int y) { 14     return x >= 0 && x < n && y >= 0 && y < m; 15 } 16 int SG(int digit, int blank) { 17     if (sg[digit][blank] == -1) { 18         int x, y; 19         x = y = -1; 20         if (blank) { 21             x = SG(0, 0); 22         } 23         if (digit) { 24             y = SG(digit - 1, blank); 25         } 26         for (int i = 0;; i++) { 27             if (i != x && i != y) { 28                 sg[digit][blank] = i; 29                 break; 30             } 31         } 32     } 33     return sg[digit][blank]; 34 } 35 void dfs(int x, int y) { 36     vis[x][y] = true; 37     if (arr[x][y] > 0) { 38         dg++; 39     } else if (arr[x][y] == 0) { 40         bk = 1; 41         int nx, ny; 42         for (int i = 0; i < 8; i++) { 43             nx = x + go[i][0]; 44             ny = y + go[i][1]; 45             if (isIn(nx, ny) && !vis[nx][ny]) { 46                 dfs(nx, ny); 47             } 48         } 49     } 50 } 51 int main() { 52     int T; 53     int ca = 1; 54     int x, y; 55     int i, j, k; 56     int res; 57     memset(sg, -1, sizeof(sg)); 58     sg[0][0] = 0; 59     scanf("%d", &T); 60     while (T--) { 61         scanf("%d%d%d", &n, &m, &k); 62         memset(arr, 0, sizeof(arr)); 63         while (k--) { 64             scanf("%d%d", &x, &y); 65             arr[x][y] = -oo; 66         } 67         for (i = 0; i < n; i++) { 68             for (j = 0; j < m; j++) { 69                 if (arr[i][j] < 0) { 70                     for (k = 0; k < 8; k++) { 71                         x = i + go[k][0]; 72                         y = j + go[k][1]; 73                         if (isIn(x, y)) { 74                             arr[x][y]++; 75                         } 76                     } 77                 } 78             } 79         } 80         res = 0; 81         memset(vis, false, sizeof(vis)); 82         for (i = 0; i < n; i++) { 83             for (j = 0; j < m; j++) { 84                 if (!vis[i][j] && arr[i][j] == 0) { 85                     dg = bk = 0; 86                     dfs(i, j); 87                     res ^= SG(dg, bk); 88                 } 89             } 90         } 91         for (i = 0; i < n; i++) { 92             for (j = 0; j < m; j++) { 93                 if (!vis[i][j]) { 94                     dg = bk = 0; 95                     dfs(i, j); 96                     res ^= SG(dg, bk); 97                 } 98             } 99         }100         if (res) {101             printf("Case #%d: Xiemao\n", ca++);102         } else {103             printf("Case #%d: Fanglaoshi\n", ca++);104         }105     }106     return 0;107 }

View Code

HDU 4679

dp[i][0]表示i为根的最长链。

dp[i][1]表示i为根的次长链。

dp[i][2]表示i为根的第三长链。

1 #pragma comment(linker,"/STACK:102400000,102400000")  2 #include
      
         3 #include
       
          4 #include
        
           5 #define MAXN 200010  6 #define oo 0x7FFFFFFF  7 using namespace std;  8 int first[MAXN], next[MAXN], v[MAXN], cost[MAXN], id[MAXN], e;  9 int dp[MAXN][3]; 10 bool vis[MAXN]; 11 int res, idx; 12 void addEdge(int x, int y, int val, int idx) { 13     cost[e] = val; 14     id[e] = idx; 15     v[e] = y; 16     next[e] = first[x]; 17     first[x] = e++; 18 } 19 void dfs(int x) { 20     vis[x] = true; 21     dp[x][0] = dp[x][1] = dp[x][2] = 0; 22     for (int i = first[x]; i != -1; i = next[i]) { 23         int y = v[i]; 24         if (!vis[y]) { 25             dfs(y); 26             if (dp[y][0] + 1 >= dp[x][0]) { 27                 dp[x][2] = dp[x][1]; 28                 dp[x][1] = dp[x][0]; 29                 dp[x][0] = dp[y][0] + 1; 30             } else if (dp[y][0] + 1 >= dp[x][1]) { 31                 dp[x][2] = dp[x][1]; 32                 dp[x][1] = dp[y][0] + 1; 33             } else if (dp[y][0] + 1 > dp[x][2]) { 34                 dp[x][2] = dp[y][0] + 1; 35             } 36         } 37     } 38 } 39 void search(int x, int pre) { 40     int tmp; 41     vis[x] = true; 42     if (pre != -1) { 43         if (dp[x][0] + 1 == dp[pre][0]) { 44             if (dp[pre][1] + 1 >= dp[x][0]) { 45                 dp[x][2] = dp[x][1]; 46                 dp[x][1] = dp[x][0]; 47                 dp[x][0] = dp[pre][1] + 1; 48             } else if (dp[pre][1] + 1 >= dp[x][1]) { 49                 dp[x][2] = dp[x][1]; 50                 dp[x][1] = dp[pre][1] + 1; 51             } else if (dp[pre][1] + 1 > dp[x][2]) { 52                 dp[x][2] = dp[pre][1] + 1; 53             } 54         } else { 55             if (dp[pre][0] + 1 >= dp[x][0]) { 56                 dp[x][2] = dp[x][1]; 57                 dp[x][1] = dp[x][0]; 58                 dp[x][0] = dp[pre][0] + 1; 59             } else if (dp[pre][0] + 1 >= dp[x][1]) { 60                 dp[x][2] = dp[x][1]; 61                 dp[x][1] = dp[pre][0] + 1; 62             } else if (dp[pre][0] + 1 > dp[x][2]) { 63                 dp[x][2] = dp[pre][0] + 1; 64             } 65         } 66     } 67     for (int i = first[x]; i != -1; i = next[i]) { 68         int y = v[i]; 69         if (!vis[y]) { 70             if (dp[y][0] + 1 == dp[x][0]) { 71                 tmp = dp[x][1] + dp[x][2]; 72             } else { 73                 tmp = dp[x][0]; 74                 if (dp[y][0] + 1 == dp[x][1]) { 75                     tmp += dp[x][2]; 76                 } else { 77                     tmp += dp[x][1]; 78                 } 79             } 80             tmp = cost[i] * max(dp[y][0] + dp[y][1], tmp); 81             if (tmp < res) { 82                 res = tmp; 83                 idx = id[i]; 84             } else if (tmp == res && idx > id[i]) { 85                 idx = id[i]; 86             } 87             search(y, x); 88         } 89     } 90 } 91 int main() { 92     int T; 93     int ca = 1; 94     int n; 95     int i; 96     int x, y, val; 97     scanf("%d", &T); 98     while (T--) { 99         scanf("%d", &n);100         e = 0;101         memset(first, -1, sizeof(first));102         for (i = 1; i < n; i++) {103             scanf("%d%d%d", &x, &y, &val);104             addEdge(x, y, val, i);105             addEdge(y, x, val, i);106         }107         res = oo;108         memset(vis, false, sizeof(vis));109         dfs(1);110         memset(vis, false, sizeof(vis));111         search(1, -1);112         printf("Case #%d: %d\n", ca++, idx);113     }114     return 0;115 }

View Code

HDU 4681

分别枚举D在A和B中的起点，可以暴力得到最短终点。

枚举任意两个起点与终点，通过dp可以求得两端的LCS。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define MAXN 1010 5 using namespace std; 6 char a[MAXN], b[MAXN], c[MAXN]; 7 vector
         
          
            > p1, p2; 8 int f[MAXN][MAXN], g[MAXN][MAXN]; 9 void cal(char a[], char c[], vector
           
            
              >&p) {10 int i, j, k;11 int la = strlen(a + 1);12 int lc = strlen(c + 1);13 p.clear();14 for (i = 1; i <= la; i++) {15 k = 1;16 if (a[i] != c[k]) {17 continue;18 }19 for (j = i; j <= la; j++) {20 if (a[j] == c[k]) {21 k++;22 }23 if (k > lc) {24 break;25 }26 }27 if (k > lc) {28 p.push_back(make_pair(i, j));29 }30 }31 }32 int main() {33 int T;34 int ca = 1;35 int ans;36 int i, j;37 int la, lb, lc;38 scanf("%d", &T);39 while (T--) {40 scanf(" %s %s %s", a + 1, b + 1, c + 1);41 la = strlen(a + 1);42 lb = strlen(b + 1);43 lc = strlen(c + 1);44 cal(a, c, p1);45 cal(b, c, p2);46 ans = 0;47 if (!(p1.empty() || p2.empty())) {48 memset(f, 0, sizeof(f));49 memset(g, 0, sizeof(g));50 for (i = 1; i <= la; i++) {51 for (j = 1; j <= lb; j++) {52 if (a[i] == b[j]) {53 f[i][j] = f[i - 1][j - 1] + 1;54 } else {55 f[i][j] = max(f[i - 1][j], f[i][j - 1]);56 }57 }58 }59 for (i = la; i > 0; i--) {60 for (j = lb; j > 0; j--) {61 if (a[i] == b[j]) {62 g[i][j] = g[i + 1][j + 1] + 1;63 } else {64 g[i][j] = max(g[i + 1][j], g[i][j + 1]);65 }66 }67 }68 for (i = 0; i < (int) p1.size(); i++) {69 for (j = 0; j < (int) p2.size(); j++) {70 ans = max(ans,71 lc + f[p1[i].first - 1][p2[j].first - 1]72 + g[p1[i].second + 1][p2[j].second + 1]);73 }74 }75 }76 printf("Case #%d: %d\n", ca++, ans);77 }78 return 0;79 }