某島

… : "…アッカリ~ン . .. . " .. .
March 12, 2020

SRM 780

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