2023-06-05

PA2020 / JOISC2020 / eJOI2021 选做

教练布置的作业。

[JOISC2020] カメレオンの恋

考虑建一个无向图， $u,v$ 之间有边当且仅当询问 $\{u,v\}$ 的结果为 $1$ 。那么对于一对双向奔赴的关系，则两侧的点的度数均为 $1$ ；其他点的度数均为 $3$ 。

由于自己和自己喜欢的一定不同色，所以对于 1 度点，直接找唯一的相邻的边就是答案。对于一个 3 度点，经过枚举可以发现如果从这个大小为 4 的邻域中询问 3 个点，那么当且仅当询问到「自己、喜欢自己的、和自己同色的」时答案为 1，于是可以找到自己喜欢的。

所以在得到图之后，可以使用至多 $3000$ 次操作找出所有的喜欢关系，于是可以得到答案。问题变为使用至多 $17000$ 次操作建出该无向图。

考虑一个暴力：维护一个点集 $S$ ，初始为空。依次考虑点 $u$ ，如果询问 $S\cup\{u\}$ 的结果是 $|S|+1$ ，说明 $u$ 到 $S$ 中没有边，将 $u$ 加入 $S$ 。遍历所有点后，对于所有不在 $S$ 中的点（设这些点构成点集 $T$ ），可以在 $S$ 内部二分找到其所有连向 $S$ 内部的边。最后，我们确定 $S$ 内部没有边，并找到了所有 $S,T$ 之间的边，然后直接对 $T$ 递归做。

下面我们证明这个暴力足以通过这道题。

首先每一个点的度数最多是 3，于是有 $3|S|\geq |T|$ ，变形得 $|T|\leq \dfrac{3}{4}(|S|+|T|)$ ，于是每次递归问题规模至少缩小到原来的 $\dfrac{3}{4}$ 。因此对大小为 $n$ 的集合，递归过程消耗的查询次数满足 $T(n)=n+T\left(\dfrac{3}{4}n\right)$ ，可以解得 $T(n)=4n$ ，于是这部分消耗 $T(2n)=8n$ 的代价。

同时每条边只贡献一次二分的代价，于是消耗 $1500\log n$ 。

这样算出来需要 $19000$ 次，仍然过大。但是我们不难观察到这个 $8n$ 和 $1500\log n$ 之间存在相互制约关系。具体来说，让边数代价最大的情况显然是第一层递归直接找到所有边。设第一层找到的独立集为 $S$ ，那么代价是 $1500\log |S|+1000+4(1000-|S|)$ （log 不需要上取整是因为每个点度数为 3 保证二分的终点分布足够均匀），解出最大值是 $16500$ 左右，于是总交互次数就被控制到了 $19500$ 以下，于是就可以通过。

时间复杂度 $O(n^2\log n)$ ，交互次数 $O(n\log n)$ 。实际最大点交互次数不到 $19000$ 。

namespace So1stice {
	const int MXN = 1005;
	int n;
	bool suki[MXN][MXN], vis[MXN];
	vector <int> g[MXN];

	inline int findEdge(const vector <int> &t, int bl, int s) {
		vector <int> tmp;
		for (int i = bl;i < t.size();i++) tmp.push_back(t[i]);
		tmp.push_back(s);
		if (Query(tmp) == tmp.size()) return -1;
		int l = bl, r = t.size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			vector <int> tmp;
			for (int i = l;i <= mid;i++) tmp.push_back(t[i]);
			tmp.push_back(s);
			if (Query(tmp) != tmp.size()) r = mid;
			else l = mid + 1;
		}
		return l;
	}

	inline void buildGraph(const vector <int> &v) {
		if (v.size() <= 1) return;
		vector <int> iso, nxt;
		for (int x : v) {
			iso.push_back(x);
			if (Query(iso) < iso.size()) {
				iso.pop_back();
				nxt.push_back(x);
			}
		}
		for (int x : nxt) {
			int p = 0, l;
			while ((l = findEdge(iso, p, x)) != -1) {
				g[x].push_back(iso[l]);
				g[iso[l]].push_back(x);
				p = l + 1;
			}
		}
		buildGraph(nxt);
	}

	inline void Work() {
		vector <int> bg;
		for (int i = 1;i <= 2 * n;i++) bg.push_back(i);
		buildGraph(bg);
		for (int i = 1;i <= 2 * n;i++) {
			if (g[i].size() == 3) {
				for (int a = 0;a < g[i].size();a++) {
					for (int b = a + 1;b < g[i].size();b++) {
						vector <int> tmp;
						tmp.push_back(g[i][a]); tmp.push_back(i); tmp.push_back(g[i][b]);
						if (Query(tmp) == 1) {
							suki[g[i][0] + g[i][1] + g[i][2] - g[i][a] - g[i][b]][i] = 1;
							suki[i][g[i][0] + g[i][1] + g[i][2] - g[i][a] - g[i][b]] = 1;
							goto done;
						}
					}
				}
			}
			done:;
		}
		for (int i = 1;i <= 2 * n;i++) {
			if (!vis[i]) {
				for (int v : g[i]) {
					if (!suki[i][v] && !suki[v][i]) {
						Answer(v, i);
						vis[i] = vis[v] = 1;
						break;
					}
				}
			}
		}
	}
}

void Solve(int N) {
	So1stice::n = N;
	So1stice::Work();
}

P8170 [eJOI2021] Waterfront

考虑到树的高度逐渐增加，因此如果后面的某一天没有砍满 $k$ 次，那么把前面的某一天里面的一次调整到后面的这一天一定合法。

因此可以贪心地尽量在前面砍，得到一个可能不合法的方案。如果对所有 $i$ 满足最后 $i$ 天砍了少于 $ki$ 次，则方案可以调整出合法方案，否则方案不能调整出合法方案。

二分之后进行该贪心，复杂度 $O(NM\log (h+Md))$ ，无法通过。

考虑按照不进行砍树的情况下达到的最终高度，每次砍最大的。使用堆维护复杂度 $O(Mk\log N)$ 。考虑到每次减的值是一个定值，因此可以排序完，每次减一个前缀 $[1,i]$ ，当 $i+1$ 的高度小于等于 $i$ 的高度时暴力将 $i$ 插入这个前缀，即可做到 $O(Mk)$ 。

然后预处理出每一个位置尽量在前面砍，每一次分别砍在什么时候。直接做就是 $O(N+Mk)$ 。

最后就是按照上面那个顺序一个一个砍，砍到某一个后缀次数太多之后就停止，记录每一棵树砍了几次，求出答案。使用树状数组倍增可以 $O(Mk\log M)$ ，也可使用并查集维护后继做到 $O(Mk\alpha(M))$ 。

总时间复杂度 $O(N\log N+Mk\alpha(M))$ 或者 $O(N\log N+Mk\log M)$ ，空间复杂度 $O(Mk)$ 。

inline void Init() {
    for (int i = 1;i <= m + 1;i++) fa[i] = i;
}

inline int GetRoot(int v) {
    if (fa[v] == v) return v;
    return fa[v] = GetRoot(fa[v]);
}

inline void Merge(int x, int y) {
    int u = GetRoot(x), v = GetRoot(y);
    if (u != v) fa[u] = v;
}

inline void Read() {
    cin >> n >> m >> k >> x;
    for (int i = 1;i <= n;i++) {
        cin >> h[i] >> d[i];
        f[i] = h[i] + d[i] * m;
        idx[i] = i;
    }
}

inline void Solve() {
    sort(idx + 1, idx + n + 1, [&](const int &x, const int &y) {
        return f[x] > f[y];
    });
    int r = 1;
    while (cut.size() <= m * k) {
        int tmp = cut.size();
        for (int i = 1;i <= r;i++) {
            if (f[idx[i]] >= x) {
                f[idx[i]] -= x;
                cnt[idx[i]]++;
                cut.push_back(idx[i]);
            }
        }
        if (cut.size() == tmp) break;
        while (r < n && f[idx[r]] <= f[idx[r + 1]]) {
            r++;
            int p = r;
            while (p > 1 && f[idx[p - 1]] < f[idx[p]]) {
                swap(idx[p - 1], idx[p]);
                p--;
            }
        }
    }
    //for (int x : cut) cout << x << " ";
    //cout << endl;
    for (int i = 1;i <= n;i++) {
        int cur = h[i] + d[i], cd = 1;
        for (int j = 1;j <= cnt[i];j++) {
            while (cur < x) {
                cur += d[i];
                cd++;
            }
            cur -= x;
            tim[i].push_back(cd);
        }
    }
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1;i <= m;i++) lft[i] = k;
    Init();
    for (int x : cut) {
        int pos = GetRoot(tim[x][cnt[x]]);
        if (pos > m) break;
        lft[pos]--;
        if (lft[pos] == 0) Merge(pos, pos + 1);
        cnt[x]++;
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) ans = max(ans, h[i] + d[i] * m - cnt[i] * x);
    cout << ans << endl;
}

P8169 [eJOI2021] Dungeons

整体想法其实很直接：

玩家记录下来自己已经看到的所有位置的信息，然后尝试利用这些信息来推断出自己在地图的哪些位置。
假设玩家可以推断出自己的起点是所有起点的一个子集 $S$ 里面的某一个。
玩家为了尝试获得更多信息来具体推断自己的起点在 $S$ $S$ 里面的哪一个位置，需要向外找安全的位置扩展。具体来说，需要找到一个格子满足：
- 它与玩家已经走到过的格子相邻；
- 假设这个格子与起点的相对位置是 $(x,y)$ 。玩家为了保证自己不被炸到，需要保证对于 $S$ 里面的任意一个起点，均满足与该起点的相对位置是 $(x,y)$ 的格子是安全的。后续我们称这样的格子对于 $S$ 绝对安全。
当玩家无法找到这样的格子时，游戏结束，玩家获得自己能走到的范围内的所有金币。
答案即为所有游戏结束的情况中，玩家获得金币数的最小值。

当然如果直接实现上述过程肯定写起来非常阴间，而且复杂度不一定对。

因此我们简化一下这个过程。注意到 $S$ 一旦变化为 $S'$ ，则新的 $S'$ 一定包含于 $S$ 。因此对于 $S$ 绝对安全的格子对于 $S'$ 也一定绝对安全。所以可以让玩家在此时直接丢弃所有信息重新开始扩展，也可以求得答案。

从而我们实现如下过程：

假设目前起点集合是 $S$ 。
从起点开始 BFS 扩展，需要满足扩展到的点对于 $S$ 绝对安全。
当无法扩展时，枚举已经看到的所有的点（即扩展到的点和它的外面一圈）。
如果某一个位置（设其相对起点的位置是 $(x,y)$ ）满足：存在 $s_1,s_2\in S$ ，使得相对 $s_1$ 的位置是 $(x,y)$ 的位置 $p_1$ 和相对 $s_2$ 的位置是 $(x,y)$ 的位置 $p_2$ 在玩家看起来不相同，则可以依照这个点的视野差异分裂 $S$ 并递归进行该过程，并返回递归的两个分叉的返回值的最小值。
如果无法分裂 $S$ ，统计扩展到多少个金币，返回该值。

最终结果就是对所有起点构成的集合进行上述过程的返回值。

直接实现，复杂度 $O(nmS^2)$ ：每次 BFS 扩展复杂度 $O(nmS)$ ，同时集合分裂 $S$ 次。

这个复杂度无法通过本题。考虑到瓶颈有两个，分别是：

BFS 扩展时判断一个点是否绝对安全，这可以压位：对于每一个 $(x,y)$ 保存一个 64 位整数，第 $i$ 位存储相对第 $i$ 个起点的位置是 $(x,y)$ 的位置是否安全（“安全”指不是 X 和 #），然后就可以用一次位运算判断。
判断一个点是否可以分裂 $S$ 。这同样可以压位：一个点有三种视觉效果（障碍、空地、金币），对于每一个 $(x,y)$ 保存三个 64 位整数，第 $i$ 位存储相对第 $i$ 个起点的位置是 $(x,y)$ 的位置的视觉效果是不是障碍（空地、金币），然后就可以用三次位运算判断。

进行如上优化后，一轮过程的复杂度下降至 $O(nm)$ ，总复杂度即下降至 $O(nmS)$ 即可通过。

const int Next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int Sight[9][2] = {{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
char mp[405][405], rel[60][815][815];
int n, m, x[60], y[60], s;
long long saf[815][815], sig[815][815][3];
bool vis[815][815], isg[815][815];

inline void Read() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> mp[i][j];
            if (mp[i][j] == 'S') {
                x[s] = i; y[s] = j;
                s++;
            }
        }
    }
}

inline void Prefix() {
    for (int k = 0;k < s;k++) {
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) rel[k][i - x[k] + 402][j - y[k] + 402] = mp[i][j];
        }
    }
    for (int k = 0;k < s;k++) {
        for (int i = 1;i <= 810;i++) {
            for (int j = 1;j <= 810;j++) {
                if (rel[k][i][j] == 'X' || rel[k][i][j] == '#') saf[i][j] |= (1ll << k);
                if (rel[k][i][j] == 'X' || rel[k][i][j] == '.' || rel[k][i][j] == 'S') sig[i][j][0] |= (1ll << k);
                if (rel[k][i][j] == '#') sig[i][j][1] |= (1ll << k);
                if (rel[k][i][j] == 'o') sig[i][j][2] |= (1ll << k);
            }
        }
    }
}

inline int Work(long long sta) {
    //cout << "work " << sta << endl;
    memset(vis, 0, sizeof(vis));
    memset(isg, 0, sizeof(isg));
    queue <pair <int, int> > que;
    que.push(make_pair(402, 402));
    vis[402][402] = 1;
    while (!que.empty()) {
        int x = que.front().first, y = que.front().second;
        que.pop();
        for (int k = 0;k < 4;k++) {
            int tx = x + Next[k][0], ty = y + Next[k][1];
            if (tx < 1 || tx > 810 || ty < 1 || ty > 810) continue;
            if (sta & saf[tx][ty]) continue;
            if (vis[tx][ty]) continue;
            vis[tx][ty] = 1;
            que.push(make_pair(tx, ty));
        }
    }
    for (int i = 1;i <= 810;i++) {
        for (int j = 1;j <= 810;j++) {
            if (vis[i][j]) {
                for (int k = 0;k < 9;k++) {
                    int tx = i + Sight[k][0], ty = j + Sight[k][1];
                    if (tx < 1 || tx > 810 || ty < 1 || ty > 810) continue;
                    isg[tx][ty] = 1;
                }
            }
        }
    }
    for (int i = 1;i <= 810;i++) {
        for (int j = 1;j <= 810;j++) {
            if (isg[i][j]) {
                //cout << i << " " << j << endl;
                for (int c = 0;c < 3;c++) {
                    if ((sig[i][j][c] & sta) != 0 && (sig[i][j][c] & sta) != sta) {
                        return min(Work((sig[i][j][c] & sta)), Work(sta ^ (sig[i][j][c] & sta)));
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= 810;i++) {
        for (int j = 1;j <= 810;j++) {
            if (vis[i][j] && (sig[i][j][2] & sta) == sta) ans++;
        }
    }
    return ans;
}

int main() {
    Read();
    Prefix();
    //cout << "pass" << endl;
    cout << Work((1ll << s) - 1) << endl;
    return 0;
}

P9103 [PA2020] Bardzo skomplikowany test

考虑如果第一棵树的根是 $a$ ，第二棵树的根是 $b$ 。不妨假设 $a<b$ ，另一个方向对称。

此时我们为了把 $b$ 移动到根，我们显然需要将 $a+1\sim b-1$ 的所有点移动到 $a,b$ 之间，形成一条 $a-(a+1)-(a+2)-\cdots-(b-1)-b$ 的链，然后将 $b$ 转到根。

此时树根的两侧是独立子问题，递归做即可。

为什么这么做是最优的？

考虑：

如果考虑树的父亲序列，则题目中的操作一定只会同时改变中序遍历上相邻的两个点的父亲。
复位根必须要求形成一条 $a-(a+1)-(a+2)-\cdots-(b-1)-b$ 的链，从而一切会改变 $a,b$ 以及中间的任何一个点的，且不属于构建这条链的过程的结构改变都将被覆盖，没有必要。
其余改变与构建链的过程独立，可以交换到构建链后面。

然后就是考虑如何构建这条链。

这个唯一性很强：从 $a$ 开始递归往右走直到走到一个 $\geq k$ 的点，设走到 $a-c_1-c_2-\cdots-c_k$ 。然后将 $c_1$ 的左子树修改成一条左链，然后往右转直到左子树消失。然后对 $c_2,\cdots,c_k$ 同样处理。

然后再考虑如何把一个子树修改成左链/右链。（右链是因为需要对称）

这个更直接，把左子树修改成左链，右子树修改成右链，然后依照需求往左/往右转。

这个修改次数就可以直接 dp 了。设 $f_{u,0/1}$ 表示修改成左链/右链的方案数， $s_u$ 是 $u$ 的子树的大小。转移：

$f_{u,0}\leftarrow f_{l,0}+f_{r,1}+s_l$
$f_{u,1}\leftarrow f_{l,0}+f_{r,1}+s_r$

其中 $l,r$ 是 $u$ 的左右孩子。

考虑算答案。

考虑我们复位根之后剩下的是包含根的一条链，两头接上 原本就在 $a$ 中存在 的子树。

所以我们就可以将 $a$ 的形态记作一棵子树上面接一条左链/右链，且这个链上的点是一个连续区间。

然后注意到上面那个“从 $a$ 开始递归往右走直到走到一个 $\geq k$ 的点”的过程不会多次搜到同一个点，于是直接暴力做，复杂度就是 $O(n)$ ，就做完了。

const int N = 500005;
const long long mod = 1000000007;

int n, als[N], ars[N], bls[N], brs[N], alt[N], blt[N], art[N], brt[N], fa[N], fb[N], rta, rtb;
long long dpa[N][2], dpb[N][2];

inline void Read() {
    n = qread();
    for (int i = 1;i <= n;i++) {
        fa[i] = qread();
        if (fa[i] != -1 && fa[i] < i) ars[fa[i]] = i;
        else if (fa[i] != -1 && fa[i] > i) als[fa[i]] = i;
        else rta = i;
    }
    for (int i = 1;i <= n;i++) {
        fb[i] = qread();
        if (fb[i] != -1 && fb[i] < i) brs[fb[i]] = i;
        else if (fb[i] != -1 && fb[i] > i) bls[fb[i]] = i;
        else rtb = i;
    }
}

inline void DfsA(int u) {
    alt[u] = art[u] = u;
    dpa[u][0] = dpa[u][1] = 0;
    if (als[u]) {
        DfsA(als[u]);
        alt[u] = min(alt[u], alt[als[u]]);
        dpa[u][0] += dpa[als[u]][0];
        dpa[u][1] += art[als[u]] - alt[als[u]] + 1 + dpa[als[u]][0];
    }
    if (ars[u]) {
        DfsA(ars[u]);
        art[u] = max(art[u], art[ars[u]]);
        dpa[u][0] += art[ars[u]] - alt[ars[u]] + 1 + dpa[ars[u]][1];
        dpa[u][1] += dpa[ars[u]][1];
    }
}

inline void DfsB(int u) {
    blt[u] = brt[u] = u;
    dpb[u][0] = dpb[u][1] = 0;
    if (bls[u]) {
        DfsB(bls[u]);
        blt[u] = min(blt[u], blt[bls[u]]);
        dpb[u][0] += dpb[bls[u]][0];
        dpb[u][1] += brt[bls[u]] - blt[bls[u]] + 1 + dpb[bls[u]][0];
    }
    if (brs[u]) {
        DfsB(brs[u]);
        brt[u] = max(brt[u], brt[brs[u]]);
        dpb[u][0] += brt[brs[u]] - blt[brs[u]] + 1 + dpb[brs[u]][1];
        dpb[u][1] += dpb[brs[u]][1];
    }
    dpb[u][0] %= mod; dpb[u][1] %= mod;
}

inline long long Solve(int nda, int sgl, int sgr, int flg, int ndb) {
    if (sgl > sgr) {
        sgl = sgr = -1;
        flg = 0;
    }
    long long res = -1;
    if (flg == 0) {
        if (nda == ndb) {
            long long ans = 0;
            if (als[nda]) ans += Solve(als[nda], -1, -1, 0, bls[ndb]);
            if (ars[nda]) ans += Solve(ars[nda], -1, -1, 0, brs[ndb]);
            res = ans % mod;
        } else if (nda < ndb) {
            int u = nda;
            long long ans = 0;
            while (u < ndb) {
                u = ars[u];
                if (als[u]) ans += dpa[als[u]][0] + art[als[u]] - alt[als[u]] + 1;
            }
            int l = nda, r = u;
            ans += ndb - nda;
            if (als[nda]) ans += Solve(als[nda], l, ndb - 1, 2, bls[ndb]);
            else ans += dpb[bls[ndb]][0];
            if (ars[u]) ans += Solve(ars[u], ndb + 1, r, 1, brs[ndb]);
            else ans += dpb[brs[ndb]][1];
            res = ans % mod;
        } else if (nda > ndb) {
            int u = nda;
            long long ans = 0;
            while (u > ndb) {
                u = als[u];
                if (ars[u]) ans += dpa[ars[u]][1] + art[ars[u]] - alt[ars[u]] + 1;
            }
            int l = u, r = nda;
            ans += nda - ndb;
            if (als[u]) ans += Solve(als[u], l, ndb - 1, 2, bls[ndb]);
            else ans += dpb[bls[ndb]][0];
            if (ars[nda]) ans += Solve(ars[nda], ndb + 1, r, 1, brs[ndb]);
            else ans += dpb[brs[ndb]][1];
            res = ans % mod;
        }
    } else if (flg == 1) {
        if (sgl <= ndb && ndb <= sgr) res = (ndb - sgl + dpb[bls[ndb]][0] + Solve(nda, ndb + 1, sgr, 1, brs[ndb])) % mod;
        else {
            int u = nda;
            long long ans = 0;
            while (u < ndb) {
                if (als[u]) ans += dpa[als[u]][0] + art[als[u]] - alt[als[u]] + 1;
                u = ars[u];
            }
            if (als[u]) ans += dpa[als[u]][0] + art[als[u]] - alt[als[u]] + 1;
            u = ars[u];
            if (u == 0) res = (ans + dpb[ndb][1]) % mod;
            else res = (ans + Solve(u, sgl, fa[u], 1, ndb)) % mod;
        }
    } else {
        if (sgl <= ndb && ndb <= sgr) res = (sgr - ndb + dpb[brs[ndb]][1] + Solve(nda, sgl, ndb - 1, 2, bls[ndb])) % mod;
        else {
            int u = nda;
            long long ans = 0;
            while (u > ndb) {
                if (ars[u]) ans += dpa[ars[u]][1] + art[ars[u]] - alt[ars[u]] + 1;
                u = als[u];
            }
            if (ars[u]) ans += dpa[ars[u]][1] + art[ars[u]] - alt[ars[u]] + 1;
            u = als[u];
            if (u == 0) res = (ans + dpb[ndb][0]) % mod;
            else res = (ans + Solve(u, fa[u], sgr, 2, ndb)) % mod;
        }
    }
    return (res % mod + mod) % mod;
}

P9096 [PA2020] Sen o podboju

数据随机自然是乱搞。

考虑一个暴力 dp： $f_{i,j,k}$ 表示 $i$ 子树，断了 $j$ 条边，根所在连通块的 $a$ 的和是 $k$ ，最小的连通块平方和。

对于边 $(u,v)$ ，转移是：

$f_{u,x,y}+f_{v,p,q}+2yq\rightarrow f_{u,x+p,y+q}'$ （不断 $u,v$ 边）
$f_{u,x,y}+f_{v,p,q}\rightarrow f_{u,x+p+1,y}'$ （断 $u,v$ 边）

复杂度 $O(n^2w^2)$ ，显然过不了。

考虑剪枝，对于 $k_1<k_2$ ，如果 $f_{i,j,k_1}<f_{i,j,k_2}$ ，那么 $k_2$ 显然没用。

于是我们对每一个 $f_{i,j}$ 开个 vector 存所有有用的 $k$ ，每次暴力枚举两个 $k$ 转移，转移完暴力对所有 vector 按 $k$ 排序再暴力删掉所有没用的点。

然后这个算法就直接以最大点不到半秒的优异表现通过了这道题！

复杂度我不会严格分析，不过感性理解的话，假定 dp 数组在树和点权都均匀随机的情况下足够均匀随机，那么根据前缀最大值个数期望（也就是笛卡尔树深度期望），复杂度可以分析为 $O(n^2\log^2 w)$ 。

const int N = 305;

struct Edge {
    int to, nxt;
    Edge() {
        nxt = -1;
    }
};
int n, hd[N], siz[N], pnt;
long long a[N];
Edge e[N << 1];
vector <pair <long long, long long> > dp[N][N], tmp[N];

inline void AddEdge(int u, int v) {
    e[++pnt].to = v;
    e[pnt].nxt = hd[u];
    hd[u] = pnt;
}

inline void Read() {
    n = qread();
    for (int i = 1;i <= n;i++) a[i] = qread();
    for (int i = 1;i < n;i++) {
        int u = qread(), v = qread();
        AddEdge(u, v); AddEdge(v, u);
    }
}

inline void Dfs(int u, int fa) {
    siz[u] = 1;
    for (int i = 0;i <= n;i++) dp[u][i].clear();
    dp[u][0].push_back(make_pair(a[u], a[u] * a[u]));
    for (int i = hd[u];~i;i = e[i].nxt) {
        int v = e[i].to;
        if (v != fa) {
            Dfs(v, u);
            for (int i = 0;i <= siz[v];i++) {
                for (int j = 0;j <= siz[u];j++) {
                    for (auto x : dp[v][i]) {
                        for (auto y : dp[u][j]) {
                            tmp[i + j].push_back(make_pair(x.first + y.first, x.second + y.second + 2 * x.first * y.first));
                            tmp[i + j + 1].push_back(make_pair(y.first, x.second + y.second));
                        }
                    }
                }
            }
            siz[u] += siz[v];
            for (int i = 0;i <= siz[u];i++) {
                dp[u][i].clear();
                sort(tmp[i].begin(), tmp[i].end());
                long long mnv = 0x3f3f3f3f3f3f3f3f;
                for (int j = 0;j < tmp[i].size();j++) {
                    if (tmp[i][j].second < mnv) {
                        mnv = tmp[i][j].second;
                        dp[u][i].push_back(tmp[i][j]);
                    }
                }
                tmp[i].clear();
            }
        }
    }
}

P9108 [PA2020] Malowanie płotu

考虑 dp，设 $f_{i,j}$ 表示前 $i$ 列，强制第 $i$ 列第 $j$ 行被涂上，以及第 $i$ 列第 $j+1\sim m$ 行没有被涂上的方案数。（即强制涂上的区间的下端点是 $j$ ）

注意到这等于前 $i$ 列，强制第 $i$ 列第 $m-j+1$ 行被涂上，以及第 $i$ 列第 $1\sim m-j$ 行没有被涂上的方案数。（即强制涂上的区间的上端点是 $m-j+1$ ）

则从第 $i-1$ 列向第 $i$ 列转移时，考虑强制第 $i-1$ 列涂上的区间的上端点是 $k$ 。我们要求 $k\leq j$ 。

同时，第 $i$ 列的区间上端点可以在 $1\sim j$ 里面任意选择，于是我们得到转移式：

f_{i,j}=j\cdot\sum_{k=m-j+1}^mf_{i-1,k}

然而这是错的，因为这样可能统计到 $i-1$ 列的区间下端点在 $i$ 列的区间上端点上面的情况。

考虑直接把这种情况容斥掉。为了统计这种情况的数量，我们再从 $i-1$ 列的下端点考虑，得到最终的转移式：

f_{i,j}=j\cdot\sum_{k=m-j+1}^mf_{i-1,k}-\sum_{k=1}^{j-1}(j-k)f_{i-1,k}

使用一些前缀和优化，复杂度 $O(nm)$ 。

long long mod, f[2][10000005];

int main() {
    cin >> n >> m >> mod;
    for (int i = 1;i <= m;i++) f[1][i] = i;
    for (int i = 2;i <= n;i++) {
        long long sum1 = 0, sum2 = 0, sum3 = 0;
        for (int j = 1;j <= m;j++) {
            sum1 = (sum1 + f[i - 1 & 1][m - j + 1]) % mod;
            f[i & 1][j] = (sum1 * j - sum3 + mod) % mod;
            sum2 = (sum2 + f[i - 1 & 1][j]) % mod;
            sum3 = (sum3 + sum2) % mod;
        }
    }
    long long ans = 0;
    for (int i = 1;i <= m;i++) ans = (ans + f[n & 1][i]) % mod;
    cout << ans << endl;
    return 0;
}

P9100 [PA2020] Miny

考虑 dp，设 $f_i$ 为只考虑前 $i$ 个地雷，强制第 $i$ 个不引爆的方案数，朴素想法即对于 $i$ 枚举 $j>i$ ，判断引爆 $i+1\sim j-1$ 的所有地雷是否会引爆 $j$ 和 $i$ 。如果均不会引爆，则转移 $f_j\leftarrow f_j+f_i$ 。

考虑分治优化，需要在 $O(r-l)$ 时间内完成 $[l,m]$ 到 $[m+1,r]$ 的转移。

设 $i\leq m<j$ ，则条件可以转化为：

引爆 $i+1\sim m$ 的所有地雷不会引爆 $i$ ；
引爆 $i+1\sim m$ 的所有地雷不会引爆 $j$ ；
引爆 $m+1\sim j-1$ 的所有地雷不会引爆 $i$ ；
引爆 $m+1\sim j-1$ 的所有地雷不会引爆 $j$ 。

注意到虽然 $i+1\sim m$ 的引爆区间的并不一定仍然是一个区间，但是由于对于所有 $i$ ， $i$ 的引爆区间都包含 $a_i$ ，所以对于任何 $i+1\leq k\leq m$ ，它的引爆区间向左超出 $a_{i+1}$ 的部分一定形成一个后缀（因为需要包含 $a_k>a_{i+1}$ ），所以引爆区间的并向左超出 $a_{i+1}$ 的部分也一定形成一个后缀。同理，向右超出 $a_m$ 的部分也一定形成一个前缀。同时，我们需要判定是否属于引爆区间的并的点分别是 $a_i$ 和 $a_j$ ，分别向左超出 $a_{i+1}$ 和向右超出 $a_m$ 。

于是在判定条件时，可以直接将引爆区间的并当作包含这个并的极小区间处理。

而这个极小区间的左右端点就分别是所有左端点的最小值和所有右端点的最大值，可以非常容易地求出。设「包含 $i+1\sim m$ 的引爆区间的并的极小区间」是 $[L_i,R_i]$ ，「包含 $m+1\sim j-1$ 的引爆区间的并的极小区间」是 $[L_j',R_j']$ 。

然后考虑转移过程。

首先预处理 $i$ 侧，删去不满足 1 的 $i$ （例如将其 $f$ 改为 $0$ ，不过当然不能把这个修改保留到最后算答案的时候）。

然后考虑递增处理 $j$ 。先判定条件 4，不满足条件 4 直接强制不能转移；然后判定条件 2,3。条件 2 等价于 $R_i<a_j$ 。不难发现 $R_i$ 关于 $i$ 递减，于是满足条件 2 的 $i$ 是一个随 $j$ 增大而逐渐扩大的后缀。条件 3 等价于 $L_j'>a_i$ 。类似的，不难发现 $L_j'$ 关于 $j$ 递减，于是满足条件 3 的 $i$ 是一个随 $j$ 增大而逐渐缩小的前缀。

于是最终合法的转移是一段区间，且左右端点均单调。使用双指针和前缀和处理，复杂度为 $O(n)$ 。套上分治，整个题就 $O(n\log n)$ 做完了。

const int N = 300005;
const long long mod = 1000000007;

int n;
long long a[N], pr[N], dp[N], ls[N], rs[N], w[N];

inline void Read() {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i] >> pr[i];
}

inline void Prefix() {
    long long mx = -4e18;
    for (int i = 1;i <= n;i++) {
        if (mx < a[i]) dp[i] = 1;
        mx = max(mx, a[i] + pr[i]);
    }
}

inline void Work(int l, int r) {
    if (l == r) return;
    long long mid = l + r >> 1;
    Work(l, mid);
    ls[mid] = 4e18; rs[mid] = -4e18;
    for (int i = mid - 1;i >= l;i--) {
        ls[i] = min(a[i + 1] - pr[i + 1], ls[i + 1]);
        rs[i] = max(a[i + 1] + pr[i + 1], rs[i + 1]);
    }
    w[l - 1] = 0;
    for (int i = l;i <= mid;i++) {
        if (ls[i] > a[i]) w[i] = dp[i];
        else w[i] = 0;
        w[i] = (w[i] + w[i - 1]) % mod;
    }
    int trr = mid, trl = mid;
    long long lt = 4e18, rt = -4e18;
    for (int j = mid + 1;j <= r;j++) {
        while (trl > l && rs[trl - 1] < a[j]) trl--;
        while (trr >= l && a[trr] >= lt) trr--;
        if (trl <= trr && rt < a[j]) dp[j] = (dp[j] + w[trr] - w[trl - 1] + mod) % mod;
        lt = min(lt, a[j] - pr[j]);
        rt = max(rt, a[j] + pr[j]);
    }
    Work(mid + 1, r);
}

inline void Solve() {
    long long ans = 1, mn = 4e18;
    Work(1, n);
    for (int i = n;i >= 1;i--) {
        if (mn > a[i]) ans = (ans + dp[i]) % mod;
        mn = min(mn, a[i] - pr[i]);
    }
    cout << ans << endl;
}

P9110 [PA2020] Samochody dostawcze

对于所有运输计划 $(r_i,t_i,w_i)$ ，按 $t_i-w_i$ 分类。

分类后，任意一类里面任意一个横的和任意一个竖的都会撞上，则我们只能取消全部横的或者取消全部竖的，于是取消尽量少的即可。

复杂度 $O(n)$ 。

int n, cnt[3000005][2];

int main() {
    n = qread();
    for (int i = 1;i <= n;i++) {
        int r = qread(), w = qread(), t = qread();
        cnt[t - w + 1000005][r - 1]++;
    }
    int ans = 0;
    for (int i = 1;i <= 3000000;i++) ans += min(cnt[i][0], cnt[i][1]);
    cout << ans << endl;
    return 0;
}