HDOJ 4921
题意：
模型转化为：给不超过10条链，每条链不超过1000个点，每条链可以选前缀的一段或是不选，每一种选法都会得到分数，分数又分成两步计算（还挺麻烦，不解释了），现在让你随便选，问选出来的分数期望是多少。
分析：
每种选法是等概率的，所以所求期望就是 Σ每个方案的分数/总方案数。总方案数就是所有链的长度+1的乘积，再-1（去掉都不选的情况）。考虑每种方案的分数很复杂，其实可以考虑每个点的分数会被取多少次。对于第一步，每个点就是自己的分数乘以会包含该点的方案数，即是其他链的取法的乘积乘上该点到该链末尾的长度。然后第二步就是考虑每一个等级(1000)，然后2^10暴力枚举每条链该等级选或不选，累加即可。题解没仔细看，貌似更很厉害些，还有个log的复杂度=。=。。。
1 #include2 #include 3 using namespace std; 4 5 int T, n, m, x, y, tot; 6 int nex[10100], v[10100], line[15][1010]; 7 bool head[10100]; 8 double sum, sumv; 9 void dfs(int lv, int pos, int yi, int sumi, int xi, double sum)10 {11 if (pos > tot){12 if (yi > 1){13 sumv += (double)yi * sumi / xi * sum;14 }15 return;16 }17 if (line[pos][0] < lv) 18 dfs(lv, pos+1, yi, sumi, xi, sum*(line[pos][0]+1));19 else{20 dfs(lv, pos+1, yi+1, sumi+v[line[pos][lv]], xi, sum*(line[pos][0]-lv+1));21 dfs(lv, pos+1, yi, sumi, xi, sum*lv);22 }23 }24 int main()25 {26 scanf("%d", &T);27 while(T--)28 {29 scanf("%d %d", &n, &m);30 for (int i = 0; i < n; i++) scanf("%d", v+i);31 memset(head, 1, sizeof(head));32 memset(nex, -1, sizeof(nex));33 for (int i = 0; i < m; i++){34 scanf("%d %d", &x, &y);35 nex[x] = y;36 head[y] = 0;37 }38 tot = 0; sum = 1.0; sumv = 0;39 for (int i = 0; i < n; i++) if (head[i]){40 line[++tot][0] = 1;41 line[tot][1] = i;42 int now = i; int &cnt = line[tot][0];43 while (nex[now] != -1){44 now = nex[now];45 line[tot][++cnt] = now;46 }47 }48 for (int i = 1; i <= tot; i++)49 sum *= (double)(line[i][0] + 1);50 for (int i = 1; i <= tot; i++){51 int len = line[i][0];52 for (int j = 1; j <= len; j++){53 int k = line[i][j];54 if (tot == 1) sumv += (double)v[k] * (len - j + 1);55 else sumv += (double)v[k] * sum * (len - j + 1) / (len+1);56 }57 }58 // printf("%.3lf\n", sumv);59 if (tot > 1){60 int maxlv = 1;61 for (int i = 1; i <= tot; i++)62 if (line[i][0] > maxlv) maxlv = line[i][0];63 for (int i = 1; i <= maxlv; i++){64 int xi = 0;65 for (int j = 1; j <= tot; j++)66 if (line[j][0] >= i) xi++;67 dfs(i, 1, 0, 0, xi, 1.0); 68 }69 }70 // printf("%.3lf\n", sumv);71 printf("%.3lf\n", sumv/(sum-1.0));72 }73 return 0;74 }
HDOJ 4923
题意：
给定序列Ai，只有0和1，你要选择一个序列Bi，满足单调非递减，每一项范围在[0,1]的条件，使得Σ(Ai - Bi)^2最小。
分析：
先考虑贪心，前面连续的0和末尾连续的1都可以去掉，每当碰上0，不用上升，如果是1，考虑上升和上升的高度，然后就跪了。可以想象最后的Bi应该是一条条高度上升的线段，也就是从l到r的一段区间，Bl..Bi..Br的值相同，对所求式子求导，或是直接展开成一个二次函数，会发现对于一段区间，Bi的最优值等于Ai中对应区间的1的个数除以1和0的个数（即区间长度）。通过这样的方式来贪心处理不了100...000111...110这种情况。其实可以引入单调栈让我们有“反悔”的机会。单调栈里存的是之前的区间的Bi的大小，显然是递增的。我们加入新的区间（开始就是新的点），计算它的Bi最优值，如果比栈顶的高，我们就加入栈。如果比栈顶低，我们就把栈顶区间取出，和当前区间合并，再和新栈顶比较，直到比某个栈顶高或者栈空，将合并后的区间压入栈。最后扫描一遍栈求出答案即可。
1 #include2 using namespace std; 3 4 const int maxn = (int)1e5+10; 5 struct node{ 6 int l, r; 7 double h; 8 node(){} 9 node(int ll, int rr, double hh):l(ll), r(rr), h(hh){}10 } stack[maxn];11 int T, n;12 int a[maxn], sum[maxn];13 int main()14 {15 scanf("%d", &T);16 while(T--)17 {18 scanf("%d", &n);19 sum[0] = 0;20 for (int i = 1; i <= n; i++){21 scanf("%d", a+i);22 sum[i] = sum[i-1] + a[i];23 }24 int top = 0;25 for (int i = 1; i <= n; i++){26 node now = node(i, i, sum[i]-sum[i-1]);27 while(top > 0 && now.h < stack[top-1].h){ 28 top --;29 now.l = stack[top].l;30 now.h = (double)(sum[now.r] - sum[now.l-1])/(now.r - now.l + 1);31 }32 stack[top++] = now;33 }34 double ans = 0;35 for (int i = 0; i < top; i++){36 int ll = stack[i].l, rr = stack[i].r;37 int len = rr - ll + 1;38 double hh = stack[i].h;39 int tot = sum[rr] - sum[ll-1];40 ans += hh * hh * len - 2.0 * tot * hh + tot;41 }42 printf("%.6lf\n", ans);43 }44 return 0;45 }
HDOJ 4925
题意：
n×m的图，每格可以种苹果或施肥，种苹果得一个苹果，施肥的格子上下左右的格子若种苹果则苹果数翻倍，问最多能得几个苹果。
分析：
本场签到题，观察发现黑白染色可以获得最多的苹果。范围很小，可以直接染色求结果，推公式也很快。（提示：先考虑1×m的情况，再考虑2×m的情况，推广到n×m的情况）
1 #include2 #include 3 #include 4 using namespace std; 5 6 int T, n, m; 7 int main() 8 { 9 scanf("%d", &T);10 while(T--)11 {12 scanf("%d %d", &n, &m);13 if (n > m) swap(n, m);14 if (m == 1){15 puts("1");16 continue;17 }18 if (n == 1) printf("%d\n", 2 * (m-1));19 else printf("%d\n", 8 * (m-1) * (n-1));20 }21 return 0;22 }
HDOJ 4927
题意：
给一个n个数的数列，相邻项做差得到新的数列（听说叫差分序列？），做n-1次得到一个数，问这个数是多少。
分析：
做差时不计算，而是保留所有数字，可以发现原来数列每个数会乘上一个系数，刚好是杨辉三角上的一行，再加上正负号，累加就是答案。组合数会到C(1500, 3000)的规模，所以需要高精度。代码是队友写的。
1 import java.io.*; 2 import java.math.*; 3 import java.util.*; 4 5 public class Main{ 6 public static void main(String [] args){ 7 Scanner cin; 8 cin = new Scanner(System.in); 9 int T, n;10 BigInteger ans, C, sum[] = new BigInteger [3100];11 T = cin.nextInt();12 while (T>0){13 T--;14 n = cin.nextInt();15 for (int i=0;i
HDOJ 4930
题意：
简化版斗地主，给出双方的牌，现在你先手，问有没有一种出牌方法使得对方在这一轮管不住你，或是直接出完。
分析：
先判断能否出完，然后处理大小王和炸弹的情况，接下来一项项匹配即可，只要有一项能大过对方就满足要求。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include