正睿 NOIP2023 20连 Day4 T3 题解
Description 称一个正整数对 (a,b)(a, b)(a,b) 合法，当且仅当存在正整数 kkk 和 kkk 组正整数对 (h1,w1),(h2,w2),⋯ ,(hk,wk)(h_1, w_1), (h_2, w_2), \cdots, (h_k, w_k)(h1,w1),(h2,w2),⋯,(hk,wk)，使得： ∑i=1khiwi=a\sum_{i = 1} ^ k
正睿 NOIP2023 20连 Day1 T2 题解
Description 有一面由 n×mn\times mn×m 个格子组成的墙，每个格子要么是黑色，要么是白色。你每次将会进行这样的操作：等概率随机选择一个位置 (x,y)(x,y)(x,y)，和一个颜色 ccc（黑色或者白色），（1≤x≤n,1≤y≤m1 \leq x \leq n, 1 \leq y \leq m1≤x≤n,1≤y≤m, 任意 (x,y,c)(x,y,c)(x,y,c) 的
CF1844E Great Grids 题解
Description 定义一个矩形 aaa 是好的，当且仅当其满足以下条件： 矩形中每一个元素 xxx 都为 A,B,CA,B,CA,B,C 其中之一 每一个 2×22\times 22×2 的子矩形都必须包含三个不同的字符 共用一条边的两个元素不相等 给定 kkk 个限制条件，限制条件分为两类： (x,x+1,y,y+1)(x,x+1,y,y+1)(x,x+1,y,y+1)，限制 a[
P9019 [USACO23JAN] Tractor Paths P 题解
Description 有 nnn 个区间，第 iii 个区间为 [li,ri][l_i,r_i][li,ri]。保证 l1<l2<⋯<lnl_1<l_2<\cdots<l_nl1<l2<⋯<ln 且 r1<r2<⋯<rnr_1<r_2<\cdots<r_nr1<r2<⋯<r
后缀数组学习笔记
基数排序 利用桶的单调性，从低位到高位依次将整数放到对应数位的桶中。 后缀数组 定义：对于字符串 sss，定义 sa[i]sa[i]sa[i] 表示 sss 的 nnn 个后缀按字典序排序后的第 iii 个后缀在 sss 中的下标，rk[i]rk[i]rk[i] 表示从 sis_isi 开始的后缀在后缀数组中的下标。 倍增求 sasasa： 不妨设 saw,isa_
P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II 题解
Description 给你一个长为 nnn 的排列，mmm 次询问，每次查询一个区间的逆序对数，强制在线。 link 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105。 Solution 考虑分块。 首先如果 l,rl,rl,r 在同一个块内，可以对于每个块暴力二维前缀和预处理。 如果 l,rl,rl,r 在不同的块内。 设 bel[l]=x,bel[r]=ybel[
网络流
1. 最大匹配 = 最小点覆盖。 2. 最小割 = 最大匹配 3. 二分图最大独立集 = 点数 - 最大匹配。 4. 二分图最大团 = 补图最大独立集。 5. DAG 最小链覆盖 = n - 拆点后二分图最大匹配。 6. 最大权闭合子图 = 正权和 - 最小割 网络流 24 题 负载平衡问题 这个其实不是网络流… 直接设 kik_iki 表示 iii 向 i+1i + 1
P9189 [USACO23OPEN] Custodial Cleanup G 题解
Description 奶牛旅馆可以被看作一个 NNN 个节点 MMM 条边的无向简单图，其中每个房间有一个颜色 CiC_iCi，以及一个钥匙，颜色为 SiS_iSi， FJ 最初在 111 号节点，手上一把钥匙都没有。 FJ 可以进行无数次以下操作： 捡起当前房间的钥匙。（FJ 可以同时手持多个钥匙） 将部分或全部手上的钥匙放在当前房间。 (房间内可以同时放多把钥匙) 通过一条