【 2013 Multi-University Training Contest 6 】

假设n个数构成的总数都分成了n段，总数是n*a₁*a₂*...*a_n。但是答案显然不会那么多。

对于相邻的两个a_i,a_i+1，如果选择相同的颜色，那么就减少了a₁*a₂*...*a_i-1*min(a_i,a_i+1)*a_i+2*a_i+3*...*a_n。

不妨假设n=3，三个数分别是a，b，c。且a<b<c。

对于所有的排列，只有a,c,b是最优的，结果是3*a*b*c-a*b-b。

当n>3的时候同样可以得到结论：a₁,a_n,a₂,a_n-1...使得总的段数最多。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 typedef long long LL;
 5 #define MOD 1000000007
 6 #define MAXN 1000010
 7 using namespace std;
 8 int arr[MAXN];
 9 int tmp[MAXN];
10 LL ext_gcd(LL a, LL b, LL &x, LL &y) {
11     LL t, d;
12     if (b == 0) {
13         x = 1;
14         y = 0;
15         return a;
16     }
17     d = ext_gcd(b, a % b, x, y);
18     t = x;
19     x = y;
20     y = t - a / b * y;
21     return d;
22 }
23 LL invmod(LL a, LL n = MOD) {
24     LL x, y;
25     if (ext_gcd(a, n, x, y) != 1)
26         return -1;
27     return (x % n + n) % n;
28 }
29 int main() {
30     int T;
31     int n;
32     int i;
33     LL ans;
34     LL res;
35     LL mul;
36     int l, r;
37     scanf("%d", &T);
38     while (T--) {
39         scanf("%d", &n);
40         ans = n;
41         mul = 1;
42         for (i = 0; i < n; i++) {
43             scanf("%d", &arr[i]);
44             mul *= arr[i];
45             mul %= MOD;
46         }
47         ans *= mul;
48         ans %= MOD;
49         sort(arr, arr + n);
50         for (l = 0, r = n - 1, i = 1; l <= r; l++, r--) {
51             if (l == r) {
52                 tmp[i++] = arr[l];
53             } else {
54                 tmp[i++] = arr[l];
55                 tmp[i++] = arr[r];
56             }
57         }
58         for (i = 2; i <= n; i++) {
59             res = mul * invmod(tmp[i] * (LL) tmp[i - 1]);
60             res %= MOD;
61             res *= min(tmp[i], tmp[i - 1]);
62             ans -= res % MOD;
63             ans = (ans % MOD + MOD) % MOD;
64         }
65         cout << ans << endl;
66     }
67     return 0;
68 }

View Code

HDU 4661 Message Passing

由于消息传递的次数要求最少，则一个节点将收集所有它的子树的消息之后，再往父节点传递。

因此，有一个节点将收到所有消息。而发送消息是收集消息的逆过程，总的答案=收集消息的方案数*发送消息的方案数=收集消息的方案数²。

dp[i]表示以i为根的子树，收集到它子孙所有消息的方案数。

size[i]表示以i为根的子树的节点总数。

f[i]表示以i为根的树，收集到它子孙所有消息的方案数。

fac[i]表示i的阶乘。

dp[i]=fac[size[i]-1]。

dp[i]/=fac[size[j]]，（j是i的儿子）。

dp[i]*=dp[j]，（j是i的儿子）。

  1 #pragma comment(linker,"/STACK:102400000,102400000")
  2 #include<cstdio>
  3 #include<cstring>
  4 typedef long long LL;
  5 #define MAXN 1000010
  6 #define MAXM 2000010
  7 #define MOD 1000000007
  8 int n;
  9 LL fac[MAXN];
 10 LL invfac[MAXN];
 11 int first[MAXN], next[MAXM], v[MAXM], e;
 12 bool vis[MAXN];
 13 LL dp[MAXN];
 14 LL f[MAXN];
 15 int size[MAXN];
 16 LL ext_gcd(LL a, LL b, LL &x, LL &y) {
 17     LL t, d;
 18     if (b == 0) {
 19         x = 1;
 20         y = 0;
 21         return a;
 22     }
 23     d = ext_gcd(b, a % b, x, y);
 24     t = x;
 25     x = y;
 26     y = t - a / b * y;
 27     return d;
 28 }
 29 LL invmod(LL a, LL n = MOD) {
 30     LL x, y;
 31     if (ext_gcd(a, n, x, y) != 1)
 32         return -1;
 33     return (x % n + n) % n;
 34 }
 35 void init() {
 36     int i;
 37     fac[0] = 1;
 38     for (i = 1; i < MAXN; i++) {
 39         fac[i] = fac[i - 1] * i;
 40         fac[i] %= MOD;
 41     }
 42     for (i = 0; i < MAXN; i++) {
 43         invfac[i] = invmod(fac[i]);
 44     }
 45 }
 46 inline void addEdge(int x, int y) {
 47     v[e] = y;
 48     next[e] = first[x];
 49     first[x] = e++;
 50 }
 51 void getSize(int x) {
 52     vis[x] = true;
 53     size[x] = 1;
 54     for (int i = first[x]; i != -1; i = next[i]) {
 55         int y = v[i];
 56         if (!vis[y]) {
 57             getSize(y);
 58             size[x] += size[y];
 59         }
 60     }
 61 }
 62 void dfs(int x) {
 63     vis[x] = true;
 64     dp[x] = fac[size[x] - 1];
 65     for (int i = first[x]; i != -1; i = next[i]) {
 66         int y = v[i];
 67         if (!vis[y]) {
 68             dfs(y);
 69             dp[x] *= invfac[size[y]];
 70             dp[x] %= MOD;
 71             dp[x] *= dp[y];
 72             dp[x] %= MOD;
 73         }
 74     }
 75 }
 76 void search(int x, int pre) {
 77     vis[x] = true;
 78     if (pre != -1) {
 79         f[x] = fac[n - 1];
 80 
 81         f[x] *= invfac[n - size[x]];
 82         f[x] %= MOD;
 83         LL tmp = f[pre];
 84         tmp *= invfac[n - 1];
 85         tmp %= MOD;
 86         tmp *= fac[n - 1 - size[x]];
 87         tmp %= MOD;
 88         tmp *= fac[size[x]];
 89         tmp %= MOD;
 90         tmp *= invmod(dp[x]);
 91         tmp %= MOD;
 92         f[x] *= tmp;
 93         f[x] %= MOD;
 94         for (int i = first[x]; i != -1; i = next[i]) {
 95             int y = v[i];
 96             if (!vis[y]) {
 97                 f[x] *= invfac[size[y]];
 98                 f[x] %= MOD;
 99                 f[x] *= dp[y];
100                 f[x] %= MOD;
101             }
102         }
103     }
104     for (int i = first[x]; i != -1; i = next[i]) {
105         int y = v[i];
106         if (!vis[y]) {
107             search(y, x);
108         }
109     }
110 }
111 int main() {
112     int T;
113     int i;
114     int x, y;
115     int ans;
116     init();
117     scanf("%d", &T);
118     while (T--) {
119         scanf("%d", &n);
120         e = 0;
121         memset(first, -1, sizeof(first));
122         for (i = 1; i < n; i++) {
123             scanf("%d%d", &x, &y);
124             addEdge(x, y);
125             addEdge(y, x);
126         }
127         memset(vis, false, sizeof(vis));
128         getSize(1);
129         memset(vis, false, sizeof(vis));
130         dfs(1);
131         memset(vis, false, sizeof(vis));
132         f[1] = dp[1];
133         search(1, -1);
134         ans = 0;
135         for (i = 1; i <= n; i++) {
136             ans += (f[i] * f[i]) % MOD;
137             ans %= MOD;
138         }
139         printf("%d
", ans);
140     }
141     return 0;
142 }

View Code

HDU 4662 MU Puzzle

从给定的字符串变成MI需要反着操作。

（1）将U替换成III。

（2）添加x个UU，即添加x个IIIIII。

假设有cnt个I，添加x个UU，那么一共有cnt+6x个I，又要满足cnt+6x=2^y。判断是否存在这样的x满足方程即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 1000010
 4 char str[MAXN];
 5 bool isOK(int len) {
 6     if (str[0] != 'M') {
 7         return false;
 8     }
 9     for (int i = 1; i < len; i++) {
10         if (str[i] == 'M') {
11             return false;
12         }
13     }
14     return true;
15 }
16 int main() {
17     int T;
18     int len;
19     int cnt;
20     int i;
21     scanf("%d", &T);
22     while (T--) {
23         scanf(" %s", str);
24         len = strlen(str);
25         if (isOK(len)) {
26             cnt = 0;
27             for (i = 1; i < len; i++) {
28                 if (str[i] == 'U') {
29                     cnt += 3;
30                 } else {
31                     cnt++;
32                 }
33             }
34             if (len == 2 && str[1] == 'I') {
35                 puts("Yes");
36             } else if (cnt % 6 == 2 || cnt % 6 == 4) {
37                 puts("Yes");
38             } else {
39                 puts("No");
40             }
41         } else {
42             puts("No");
43         }
44     }
45     return 0;
46 }

View Code

HDU 4664 Triangulation

SG打表找规律。

mex是不属于这个集合的最少非负整数。

sg(x)是mex{sg(y)|y是x的后继状态}。

游戏和的SG函数值是它的所有子游戏SG函数值的异或。

n个游戏的异或和为0，先手必败。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 1010
 4 int sg[MAXN];
 5 bool vis[MAXN];
 6 int SG(int n) {
 7     if (n == 0) {
 8         sg[n] = 0;
 9     } else if (n == 1) {
10         sg[n] = 0;
11     } else if (n == 2) {
12         sg[n] = 1;
13     } else if (n == 3) {
14         sg[n] = 1;
15     } else if (sg[n] == -1) {
16         int i;
17         memset(vis, false, sizeof(vis));
18         for (i = 0; i <= n - 2; i++) {
19             vis[SG(i) ^ SG(n - i - 2)] = true;
20         }
21         for (i = 0;; i++) {
22             if (!vis[i]) {
23                 break;
24             }
25         }
26         sg[n] = i;
27     }
28     return sg[n];
29 }
30 void init() {
31     int i;
32     memset(sg, -1, sizeof(sg));
33     for (i = 0; i < MAXN; i++) {
34         sg[i] = SG(i);
35     }
36 }
37 int getSG(int n) {
38     if (n < MAXN) {
39         return sg[n];
40     } else {
41         return sg[n % 34 + 2 * 34];
42     }
43 }
44 int main() {
45     int T;
46     int n;
47     int tmp;
48     int res;
49     init();
50     scanf("%d", &T);
51     while (T--) {
52         scanf("%d", &n);
53         res = 0;
54         while (n--) {
55             scanf("%d", &tmp);
56             res ^= getSG(tmp);
57         }
58         if (res) {
59             puts("Carol");
60         } else {
61             puts("Dave");
62         }
63     }
64     return 0;
65 }

View Code

HDU 4665 Unshuffle

若一个数只出现两次，则第一个数属于0，第二个数属于1。

若一个数出现了四次，则第一个数属于0，第四个数属于1，其他两个都有可能。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #define MAXN 2010
 5 using namespace std;
 6 int arr[MAXN];
 7 char str[MAXN];
 8 bool flag;
 9 int idx[MAXN];
10 int cnt[MAXN];
11 int st[2][MAXN];
12 int belong[MAXN];
13 int n;
14 vector<int> pos[MAXN];
15 void dfs(int x, int p1, int p2) {
16     if (x > n) {
17         flag = true;
18     }
19     if (flag) {
20         return;
21     }
22     if (p1 > 0 && p2 > 0
23             && arr[st[0][min(p1, p2)]] != arr[st[1][min(p1, p2)]]) {
24         return;
25     }
26     if (belong[x] == 0) {
27         st[0][p1 + 1] = x;
28         dfs(x + 1, p1 + 1, p2);
29     } else if (belong[x] == 1) {
30         st[1][p2 + 1] = x;
31         dfs(x + 1, p1, p2 + 1);
32     } else {
33         st[0][p1 + 1] = x;
34         belong[pos[arr[x]][2]] = 1;
35         dfs(x + 1, p1 + 1, p2);
36 
37         if (!flag) {
38             st[1][p2 + 1] = x;
39             belong[pos[arr[x]][2]] = 0;
40             dfs(x + 1, p1, p2 + 1);
41 
42             belong[pos[arr[x]][2]] = -1;
43         }
44     }
45 }
46 int main() {
47     int T;
48     int i;
49     scanf("%d", &T);
50     while (T--) {
51         scanf("%d", &n);
52         memset(idx, 0, sizeof(idx));
53         memset(cnt, 0, sizeof(cnt));
54         for (i = 1; i <= n; i++) {
55             scanf("%d", &arr[i]);
56             cnt[arr[i]]++;
57             idx[i] = cnt[arr[i]];
58             pos[arr[i]].clear();
59         }
60         memset(belong, -1, sizeof(belong));
61         for (i = 1; i <= n; i++) {
62             if (idx[i] == 1) {
63                 belong[i] = 0;
64             } else if (idx[i] == 2 && cnt[arr[i]] == 2) {
65                 belong[i] = 1;
66             } else if (idx[i] == 4) {
67                 belong[i] = 1;
68             }
69             pos[arr[i]].push_back(i);
70         }
71         flag = false;
72         dfs(1, 0, 0);
73         for (i = 1; i <= (n >> 1); i++) {
74             str[st[0][i]] = '0';
75             str[st[1][i]] = '1';
76         }
77         for (i = 1; i <= n; i++) {
78             putchar(str[i]);
79         }
80         putchar('
');
81     }
82     return 0;
83 }

View Code