XJ - 最小生成树计数
92ce3867a25b048540c10275d83b5b1fcf3027232b13c26c1a635d49d722095b87d098a5608cd76a18cf6bcf629ced108dd71cf883b72204a04e5906406485b3faffa15856ce9c60c9acb35ece19ba1695a2083d01aba64d6216e0638406487107a01ae4cab2abaaf761b9496334f5f337cd22efb37d77ad3a0fa1cd8952584b8f5578d7bba294b2fac2598e17c61d197ae81ae00e79622fdfbce60d250aa5a8c547f08dc42165cbdab94d963e647e32d6188de4b30d81dfdca3f326b94599271c5bc87887f2bff5d3dfe421b38798aba433f5e6c961efa5c23f3aa3a9a914ea07512d5243d054e1a7e3e92e4c97fc26896ae17bb947a0b80 ...
XJ - Sequence on Tree
92ce3867a25b048540c10275d83b5b1f57ade36a2745a4b0c5bf6d67dbc1855ffb7c33e3e5663e0b924a29d38efca9b76905a617f337a56be3a8bb794de1cac07c9667a990dcaf7219afe9669ff0f08a052d9dde0421e0f471d11dc3d8277d31833967f10693adf0b2d38d9dbeaedc6d2339acd9f62b68bb5ee97de5b9061ace90fae21a71364d9cf495e4dffb6024e59fac73dda878516e379876612c915d90e3b12c7ba69f0676dc4f77b4331e4b64b3e3e2902b9acfcbb2958a7ee41f012a74bbc03abd9f2810850e9b1446956711bd28da1ad63c91d70c7b0273b9d79d6b19413c15757080d628b35a0fad0ff86ffe780dba1e9a7b91b ...
XJ - Remote Control
92ce3867a25b048540c10275d83b5b1f57ade36a2745a4b0c5bf6d67dbc1855ffb7c33e3e5663e0b924a29d38efca9b76905a617f337a56be3a8bb794de1cac07c9667a990dcaf7219afe9669ff0f08a052d9dde0421e0f471d11dc3d8277d317cc8bb3e830ea3be20f29b2354f59289624b125c919266506a5b1ad7ee8beb6183a7e4c02645ab73e8be88ddff4a42bb8833424084c771cdad976ebba204d9f8e946cf6e316c03e9c458f43a18e880421e5e95590d226b163b0ef0823af657ddb914a8a64328bda62e865beda8c326a20529c792f7ccd65f1c49a3e9bfc364cd1facb00525c6a662a96eba04eff4cf915a491fa1926c8f0ae ...
网络流学习笔记
时隔一年半开始重拾网络流
图论基础
图的一些概念
图 G=(V,E)G=(V,E)G=(V,E)
匹配 ：找到一个边集 F⊆EF\subseteq EF⊆E 满足没有边共用顶点。
边覆盖 ：图上任意点都至少是 M (M⊆E)M \;(M\subseteq E)M(M⊆E) 中某条边的顶点。
点覆盖 ：图上任意边至少有一个顶点在 S (S⊆V)S\;(S\subseteq V)S(S⊆V) 中。
独立集 ：点集 S⊆VS \subseteq VS⊆V 满足任意两点间没有边相连。
一些结论
∣最大独立集∣+∣最小点覆盖∣=∣V∣|\text{最大独立集}|+|\text{最小点覆盖}|=|V|∣最大独立集∣+∣最小点覆盖∣=∣V∣
证明：（自己瞎糊的），考虑要搞出独立集，就是要让所有的边消失（因为一条边存在就说明），就是在原图上删点，删点的时候把点周围的边也删掉，直到图上没有边剩余，也就是点覆盖。那么最大独立集就是要让剩下的点最多，等价于删掉的点最少，便是最小点覆盖。
对于没有孤立点的图（联通图），∣最大匹配∣+∣最小边覆盖∣=∣V∣|\text{最大匹配}|+|\text{ ...
SPOJ GSS - Can you answer these queries
一些简单数据结构题，线段树或平衡树，一共八道题，其中 I,II,IV\mathrm{I,II,IV}I,II,IV 过水懒得写。
GSS−III\mathrm{GSS-III}GSS−III
长度为 nnn 的序列 AAA，qqq 次操作
操作 0 x y0\;x\;y0xy 把 AxA_xAx 修改为 yyy
操作 1 l r1\;l\;r1lr 询问区间 [l,r][l,r][l,r] 的最大子段和(非空)
1≤n,q≤5×104, ∣y∣,∣Ai∣≤100001\le n,q\le 5\times 10^4,\;\left|y\right|,\left|A_i\right|\le 100001≤n,q≤5×104,∣y∣,∣Ai∣≤10000
330ms 1.46GB
线段树维护 区间和、最大子段和、最大前缀和、最大后缀和 ，结构体+重载运算符是个好东西，核心代码：
12345678910111213struct rec{ int sum,mx,st,ed; //和，最大子段和、最大前缀和、最大后缀和 rec() {} ...
「CF13E」 Holes | 弹飞绵羊
CF-13E
HNOI2010-弹飞绵羊
双倍经验～～
题意
有 NNN 个洞，每个洞有相应的弹力 kik_iki，能把这个球弹到 i+kii+k_ii+ki 的位置。当球的位置 >N\gt N>N 时即视为被弹出
MMM 次询问，共有两种操作:
0 a b0\;a\;b0ab 把 aaa 位置的弹力改成 bbb
1 a1\;a1a 在 aaa 处放一个球，输出最后一次落在哪个洞，球被弹出前共被弹了多少次。
1≤N,M≤100,0001\le N,M\le 100,0001≤N,M≤100,000
题解
naive的想法可以暴力维护 fif_{i}fi 表示最后跳到的点，cic_ici 表示步数。
fi={fi+kii+ki≤nii+ki>nci={ci+ki+1i+ki≤n1i+ki>nf_i=\begin{cases}
f_{i+k_i} & i+k_i\le n\\
i & i+k_i\gt n
\end{cases}
\quad
c_i=\begin{cases}
c_{i+k_i}+1 & i+k_i\le ...
AT1983 - BBQ Hard
AT1983 in luogu
题意
求如下式子，答案对 109+710^9+7109+7 取模
∑i=1n∑j=i+1n(Ai+Bi+Aj+BjAi+Aj)\sum_{i=1}^n\sum_{j=i+1}^n \binom{A_i+B_i+A_j+B_j}{A_i+A_j}
i=1∑nj=i+1∑n(Ai+AjAi+Bi+Aj+Bj)
$ 1\le n\le 200,000,;1\le A_i,B_i\le 2,000$
题解
考虑组合意义，对于 (Ai+Bi+Aj+BjAi+Aj)\binom{A_i+B_i+A_j+B_j}{A_i+A_j}(Ai+AjAi+Bi+Aj+Bj) ，其含义为 (−Ai,−Bi)→(Aj,Bj)(-A_i,-B_i) \to (A_j,B_j)(−Ai,−Bi)→(Aj,Bj) 每次向上 111 或向右 111 的路径方案数，因为值域很小，这种路径方案数还可以用 DP 做： fi,j=fi−1,j+fi,j−1f_{i,j}=f_{i-1,j}+f_{i,j-1}fi,j=fi−1,j+fi,j−1 多 ...
「CF372B」 Counting Rectangles is Fun
CF-372B Counting Rectangles is Fun
题意
给定一个 n×mn\times mn×m 的 010101 矩阵, qqq 次询问, 每次询问指定一个子矩形, 求该子矩形种有多少个只包含 000 的子矩阵.
矩阵从上到下编号 [1,n][1,n][1,n], 从左到右编号 [1,m][1,m][1,m]
1≤n,m≤40,1≤q≤3×1051\le n,m\le 40,1\le q\le 3\times 10^51≤n,m≤40,1≤q≤3×105
题解
n,m≤40n,m\le 40n,m≤40 ，qqq 却很大，可以想到应该是一个 O(n2m2)O(n^2m^2)O(n2m2) 的预处理 + O(1)O(1)O(1) 的查询。
首先，判断 (a,b),(c,d)(a,b),(c,d)(a,b),(c,d)（左上角和右下角）的矩形是否全零可以 O(1)O(1)O(1) ，记 f[L][R][l][r]f[L][R][l][r]f[L][R][l][r] 表示 (L,l),(R,r)(L,l),(R,r)(L,l),(R,r) 是否为全零矩阵 ，如果 L& ...
「CF715B」 Complete The Graph
CF-715B Complete The Graph
题意
给 n,(2≤n≤1000)n,(2\le n\le 1000)n,(2≤n≤1000) 点 m,(1≤m≤10000)m,(1\le m\le 10000)m,(1≤m≤10000) 边的无向图，修改 mmm 条边中边为 000 的边，使满足 s,t,(0≤s,t,ui,vi≤n−1,s≠t,0≤wi≤109)s,t,(0\le s,t,u_i,v_i\le n-1,s\ne t,0\le w_i\le 10^9)s,t,(0≤s,t,ui,vi≤n−1,s=t,0≤wi≤109) 的最短路长度是 L,(0≤L≤109)L,(0\le L \le 10^9)L,(0≤L≤109) ，且输出答案的时候边为 000 的边的权值必须在 [1,1018][1,10^{18}][1,1018] 内。
题解
把所有为零的边赋为 111 跑一遍最短路，用 disdisdis 表示，显然若 dist>Ldis_t > Ldist>L 输出无解。
然后我们有一个naive的想法，给那些可修改的边依次 +1+1+1 ...
XJ-交通运输
92ce3867a25b048540c10275d83b5b1fcf3027232b13c26c1a635d49d722095b87d098a5608cd76a18cf6bcf629ced108dd71cf883b72204a04e5906406485b322826c7ce91aeb210cec409e5ee3420b985f445829e2a718cf990422b9d5d6c478ea19cde279d20a2b3694c023af83dd9dd6411b6891b13837c7220ef8c9dbd8c93b34b8fcd381c95345ffee212f35c5583d4deb8f20eeefa8abd2942e58226b8dc49ca6b06c83a19b0c99ad69ad58c011dd3eeed65c7c3401e2e24844e8ef5d09c2bb6b2c8db79004cb764ea3b869a1130d00a37f39e183fe4c885a8ec77403daf937ee760fb42107db847708e35726f2d64b9081e74fab0 ...