HDU 4647 Another Graph Game
如果没有边的作用，显然轮流拿当前的最大值即可。
加上边的作用，将边权平均分给两个点，如果一个人选走一条边的两个点，就获得了边的权值；如果分别被两个人拿走，两人的差值不变。
将边权平均分配给点，对点的权值排序轮流选择。
#include<cstdio>
#include<algorithm>
#include<iostream>
#define MAXN 100010
#define EPS 1e-8
typedef long long LL;
using namespace std;
double arr[MAXN];
int main() {
int n, m;
int i;
int x, y, val;
double a, b;
while (~scanf("%d%d", &n, &m)) {
for (i = ; i <= n; i++) {
scanf("%lf", &arr[i]);
}
for (i = ; i < m; i++) {
scanf("%d%d%d", &x, &y, &val);
arr[x] += val * 0.5 + EPS;
arr[y] += val * 0.5 + EPS;
}
sort(arr + , arr + + n);
a = b = ;
for (i = n; i > ; i -= ) {
a += arr[i];
b += arr[i - ];
}
cout << (LL) (a - b + EPS) << endl;
}
return ;
}
HDU 4648 Magic Pen 6
求前缀和，枚举擦除的起点，求出最右端的位置，更新答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100010
using namespace std;
int arr[MAXN];
int sum[MAXN];
int pos[MAXN];
int main() {
int n, m;
int i;
int ans;
while (~scanf("%d%d", &n, &m)) {
sum[] = ;
memset(pos, -, sizeof(pos));
for (i = ; i <= n; i++) {
scanf("%d", &arr[i]);
arr[i] = (arr[i] % m + m) % m;
sum[i] = (sum[i - ] + arr[i]) % m;
pos[sum[i]] = i;
}
ans = ;
for (i = ; i <= n; i++) {
ans = max(ans, pos[sum[i - ]] - i + );
}
printf("%d\n", ans);
}
return ;
}
HDU 4649 Professor Tian
dp[i][j][k]表示第i位，处理到第j个数，该位的结果为k的概率。
答案就是每一位的dp[i][n][1]*(1<<i)相加。
#include<cstdio>
#include<cstring>
#define MAXN 220
#define MAXM 20
double dp[MAXM][MAXN][];
int arr[MAXN];
char str[MAXN];
double p[MAXN];
int main() {
int n;
int ca = ;
int i, j, k, l;
int tmp;
double ans;
while (~scanf("%d", &n)) {
for (i = ; i <= n; i++) {
scanf("%d", &arr[i]);
}
for (i = ; i <= n; i++) {
scanf(" %c", &str[i]);
}
for (i = ; i <= n; i++) {
scanf("%lf", &p[i]);
}
memset(dp, , sizeof(dp));
for (i = ; i < MAXM; i++) {
if (arr[] & ( << i)) {
dp[i][][] = ;
} else {
dp[i][][] = ;
}
for (j = ; j <= n; j++) {
if (arr[j] & ( << i)) {
l = ;
} else {
l = ;
}
for (k = ; k < ; k++) {
if (str[j] == '&') {
tmp = k & l;
} else if (str[j] == '|') {
tmp = k | l;
} else {
tmp = k ^ l;
}
dp[i][j][tmp] += dp[i][j - ][k] * ( - p[j]);
dp[i][j][k] += dp[i][j - ][k] * p[j];
}
}
}
ans = ;
for (i = ; i < MAXM; i++) {
ans += dp[i][n][] * ( << i);
}
printf("Case %d:\n%lf\n", ca++, ans);
}
return ;
}