【 2013 Multi-University Training Contest 5 】

如果没有边的作用，显然轮流拿当前的最大值即可。

加上边的作用，将边权平均分给两个点，如果一个人选走一条边的两个点，就获得了边的权值；如果分别被两个人拿走，两人的差值不变。

将边权平均分配给点，对点的权值排序轮流选择。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #define MAXN 100010
 5 #define EPS 1e-8
 6 typedef long long LL;
 7 using namespace std;
 8 double arr[MAXN];
 9 int main() {
10     int n, m;
11     int i;
12     int x, y, val;
13     double a, b;
14     while (~scanf("%d%d", &n, &m)) {
15         for (i = 1; i <= n; i++) {
16             scanf("%lf", &arr[i]);
17         }
18         for (i = 0; i < m; i++) {
19             scanf("%d%d%d", &x, &y, &val);
20             arr[x] += val * 0.5 + EPS;
21             arr[y] += val * 0.5 + EPS;
22         }
23         sort(arr + 1, arr + 1 + n);
24         a = b = 0;
25         for (i = n; i > 0; i -= 2) {
26             a += arr[i];
27             b += arr[i - 1];
28         }
29         cout << (LL) (a - b + EPS) << endl;
30     }
31     return 0;
32 }

View Code

HDU 4648 Magic Pen 6

求前缀和，枚举擦除的起点，求出最右端的位置，更新答案。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define MAXN 100010
 5 using namespace std;
 6 int arr[MAXN];
 7 int sum[MAXN];
 8 int pos[MAXN];
 9 int main() {
10     int n, m;
11     int i;
12     int ans;
13     while (~scanf("%d%d", &n, &m)) {
14         sum[0] = 0;
15         memset(pos, -1, sizeof(pos));
16         for (i = 1; i <= n; i++) {
17             scanf("%d", &arr[i]);
18             arr[i] = (arr[i] % m + m) % m;
19             sum[i] = (sum[i - 1] + arr[i]) % m;
20             pos[sum[i]] = i;
21         }
22         ans = 0;
23         for (i = 1; i <= n; i++) {
24             ans = max(ans, pos[sum[i - 1]] - i + 1);
25         }
26         printf("%d
", ans);
27     }
28     return 0;
29 }

View Code

HDU 4649 Professor Tian

dp[i][j][k]表示第i位，处理到第j个数，该位的结果为k的概率。

答案就是每一位的dp[i][n][1]*(1<<i)相加。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 220
 4 #define MAXM 20
 5 double dp[MAXM][MAXN][2];
 6 int arr[MAXN];
 7 char str[MAXN];
 8 double p[MAXN];
 9 int main() {
10     int n;
11     int ca = 1;
12     int i, j, k, l;
13     int tmp;
14     double ans;
15     while (~scanf("%d", &n)) {
16         for (i = 0; i <= n; i++) {
17             scanf("%d", &arr[i]);
18         }
19         for (i = 1; i <= n; i++) {
20             scanf(" %c", &str[i]);
21         }
22         for (i = 1; i <= n; i++) {
23             scanf("%lf", &p[i]);
24         }
25         memset(dp, 0, sizeof(dp));
26         for (i = 0; i < MAXM; i++) {
27             if (arr[0] & (1 << i)) {
28                 dp[i][0][1] = 1;
29             } else {
30                 dp[i][0][0] = 1;
31             }
32             for (j = 1; j <= n; j++) {
33                 if (arr[j] & (1 << i)) {
34                     l = 1;
35                 } else {
36                     l = 0;
37                 }
38                 for (k = 0; k < 2; k++) {
39                     if (str[j] == '&') {
40                         tmp = k & l;
41                     } else if (str[j] == '|') {
42                         tmp = k | l;
43                     } else {
44                         tmp = k ^ l;
45                     }
46                     dp[i][j][tmp] += dp[i][j - 1][k] * (1 - p[j]);
47                     dp[i][j][k] += dp[i][j - 1][k] * p[j];
48                 }
49             }
50         }
51         ans = 0;
52         for (i = 0; i < MAXM; i++) {
53             ans += dp[i][n][1] * (1 << i);
54         }
55         printf("Case %d:
%lf
", ca++, ans);
56     }
57     return 0;
58 }

View Code