## 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; } };