XJ - Sequence on Tree
fdbc2997623a61cf73a7235ddd759531940afb38b42975cb2bd1b7273226e7a6f4491464e6b8f8de1e2939658e3cf4d34b7510dc8943b5b2f3323eacdc2e2b8330e0d19dd9da4e20bdf3effe1b4dc5bd76fb6f650c4e554755791f6fe0eae96003b1da6120258b09cb4272b567b08a9f5ee183e09fe790145cc54cd472efea45d78b7b361d9140791e7438b869e7e4970a40377e9cb10629aafab0e45b53b957d9e454216d291434138f6b4f22fc845bcc5d2518e8fa57236d2671da878c8a4689330d04abc384e039e90d43141796bb71257416af95a336e0b47920413a753dff0f76c428fbbd330dc7800afc178ed7b4885bd86ad96e170 ...
XJ - Remote Control
fdbc2997623a61cf73a7235ddd759531940afb38b42975cb2bd1b7273226e7a6f4491464e6b8f8de1e2939658e3cf4d34b7510dc8943b5b2f3323eacdc2e2b8330e0d19dd9da4e20bdf3effe1b4dc5bd76fb6f650c4e554755791f6fe0eae960f27f0b6931340636c304457067a1eb63987789bfe47909c095fe1dbe6dd388e063d9bec2a51d61a0ad6cd162b158a4ffb1df64361c6a9377316a19e78243b6fc3b123cc54d60b88af3ca769392ccfeb621ca1f399a6bb11a191205778601987ea76ef8e4948c6f8ca6273ec9ac3c69053fe128ab4efc0d1dd31dbc40ebf0c48411a9086959f90d56186df6a84c3eb8c144540c316bdb08f66 ...
网络流学习笔记
时隔一年半开始重拾网络流
图论基础
图的一些概念
图 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-交通运输
fdbc2997623a61cf73a7235ddd7595318b33e643f3cb00c209b6165956d742b312d7b773317bed9ccbd44a1f16bd2ebf34fcf04e3fe7b0cdbe63bfb73a581d326af03f7dbc1d9808f00f6e16535e0fd3bf735e11f57775733e72f9059dbdf5272389fc74879a13dd4cf9bd9cdcff770e29fe47a4c53cc85e23fa6dc9959478ff9e54757816e04c3891e6685f9e842df5850af7f8e60f67de77fc63ab06fc4bca7f890f304d997fe4b6292abf29671387a6fd7e7e23993b62fcf45a7c8230bdccf8a105aa755cb5b0ae058e2b9c376dd7d6aa194c4089fd6a241f5d6978d40e112e2d2400b8029b7c42b788ccc21efc0a59763fcb9d76b634b ...
CSP - 2020S
CSP2020暴毙赛
测了一下官方数据，40+85+70+20=21540+85+70+20=21540+85+70+20=215 ，竟然没有一题是 AC 的。。
失分情况
T1
这毒瘤题把人搞傻了，最后调到公元1600年前一定正确，之后的出了点神奇的错误（公元 1582 年 10 月 15 日（含）以后的闰年写挂了）
T2
这题应该挺简单，没上 959595 因为
12345for(int i=0;i<k;i++) if(!((sta>>i)&1)){ if(check(i)) { sta|=(1<<i); }
1后没加ull，但我记得应该加了吧？！毕竟在算答案的时候都有（莫非手抖没保存）
123456if(t<64) { ans=(1ull<<t)-n;}else { ans=(1ull<<63)-n; ans+=(1ull<<63);}
还挂 555 分因为 n=0，264n=0，2^{ ...