2024.11.8总结


第一场:

A:

递推,将每一行的限制向下转移,到最后一行。

这样我们就得到了一个 nn 个变量,n+mn+m 个方程的异或方程组,高斯消元。

若有解,则答案为 2自由变量个数2^{自由变量个数}

B:

转化题意,选点 ii 的代价为 cic_i,同时选点 i,ji,j 的贡献为 bi,jb_{i,j},发现是最大权闭合子图,最小割即可。

C:

朴素 dp 是 $\mathcal O(n^2) $ 的(但是有 n106n\leq10^6 有95分,考虑用 cdq优化转移,可以做到 O(nlogn)\mathcal O(n\log n)

第二场:

A:

什么都能做,而我选择线段树+map乱草。

B:

还不会。

[HEOI2013] 钙铁锌硒维生素

C:

枚举自己的两天起始点和小偷的两天起始点,简单计算即可。