## 250

给定 n 场比赛，每场比赛的得分分别从 1..N, 问假设每场比赛的胜率为 0.5，我们拿掉其中一场比赛后，问某一场比赛的得分加上后，可以逆转结果的方案有多少种。

（平局算负）

数据规模很小，0/1 背包即可。

class BeatTheStar { public: double doesItMatter(int n, int g) { int s = n*(n+1)/2; RST(dp); dp[0] = 1; REP_1(i, n) if (i != g) { DWN_1(j, s-i, 0) { dp[j+i] += dp[j] * 0.5; dp[j] = dp[j] * 0.5; } } DB z = 0; FOR_1(i, s/2-g+1, s/2) z += dp[i]; return z; } };

## 500

给定一个山，问每个局部高点位置，要前往一个比它更高的位置，最少需要下降多少。

RMQ + 单调栈。。

用最大子矩阵的方法扫一下两边最近的比自己高的位置，然后取 rmq 即可。

加点哨兵简化判断。

const int MOD = 1000000007; const int INF = 0x7fffffff; inline int clz(int x){return __builtin_clz(x);} inline int lg2(int x){return !x ? -1 : 31 - clz(x);} const int N = int(1e6)+9, LV = 21; int h[N], l[N], r[N], sta[N], top; int n; int ST[LV][N]; int rmq(int l, int r){ int lv = lg2(r-l); return min(ST[lv][l], ST[lv][r-(1<<lv)]); } class Prominence { public: long long sumOfProminences(int n, vector <int> coef, vector <int> idx, vector <int> val) { h[0] = h[n+3] = INF; h[1] = h[n+2] = 0; REP(i, n) { int p = i&1; LL a = coef[3*p], b = coef[3*p+1], c = coef[3*p+2]; h[i+2] = (((a*i+b)%MOD)*i+c)%MOD; } REP(i, SZ(idx)) h[idx[i]+2] = val[i]; n += 2; sta[top = 0] = 0; REP_1(i, n) { while (h[sta[top]] <= h[i]) --top; l[i] = sta[top]; sta[++top] = i; } sta[top = 0] = n+1; DWN_1(i, n, 1) { while (h[sta[top]] <= h[i]) --top; r[i] = sta[top]; sta[++top] = i; } REP_1(i, n) ST[0][i] = h[i]; for ( int lv = 1 ; (1 << lv) <= n ; lv ++ ){ for ( int i = 1; i + (1 << lv) <= n + 1 ; i ++ ){ ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + (1<<(lv-1))]); } } long long z = 0; REP_1(i, n) if (h[i-1] < h[i] && h[i] > h[i+1]) { z += h[i] - max(rmq(l[i]+1, i), rmq(i+1, r[i])); } return z; } };

1000

树 DP

给定一棵树，然后把所有叶子连成一个环，问独立集的方案数。

状态转移很像是线段树的时候做区间合并，压 3 个比特位分别表示：区间头尾，以及根节点的状态，转移分是不是第一个孩子讨论一下即可。

const int N = 1009; Int f[8][N], fp[8]; bool fb[N]; int n; class RestrictedLeaves { public: int count(vector <int> parent) { n = SZ(parent); REP(i, n) fb[i] = 1; DWN(u, n, 1) { if (fb[u]) { // leaf f[0][u] = 1; f[7][u] = 1; } int p = parent[u]; if (fb[p]) { fb[p] = 0; REP(sp, 8) f[sp][p] = 0; REP(su, 8) { REP(sp, 2) { int ss = su&3; if (sp) { if (su&4) continue; ss |= 4; } f[ss][p] += f[su][u]; } } } else { REP(sp, 8) fp[sp] = f[sp][p], f[sp][p] = 0; REP(su, 8) { REP(sp, 8) { if (sp&su&4) continue; if ((sp&2)&&(su&1)) continue; int ss = (su&2)|(sp&5); f[ss][p] += f[su][u] * fp[sp]; } } } } Int z = 0; REP(s, 8) if((s&3)^3) z += f[s][0]; return z; } };