圆方树 圆方树 简介 圆方树可以处理一般的无向图。在圆方树中,一个圆点对应原图上的一个点,一个方点对应原图上的一个点双。圆方树中每条边连接一个圆点和一个方点。 模板 12345678910111213141516171819202122232425262728293031323334int n,m,cnt;vector<int> g[N],T[N*2];int dfn[N],low[N],df 2023-09-04 ACM #圆方树
AtCoder Beginner Contest 318 https://atcoder.jp/contests/abc318 F - Octopus 题意 xxx 坐标轴上有 nnn 个物品,位置为 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_nx1,x2,⋯,xn。现在有一只章鱼,处于坐标 kkk 处,有长度为 l1,l2,⋯ ,lnl_1,l_2,\cdots,l_nl1,l2,⋯,ln 的手臂,第 iii 条手臂可以抓取位 2023-09-03 ACM #圆方树
2023牛客暑期多校训练营4 H Merge the squares! 题意 给定 n×nn\times nn×n 个 1×11\times11×1 的小正方形组成的大正方形,每次合并不超过 505050 个小正方形得到一个大正方形。问如何合成能得到 n×nn\times nn×n 的大正方形。 数据范围:1≤n≤10001\leq n\leq 10001≤n≤1000。 题解 为了得到一个 i×ii\times ii×i 2023-09-02 ACM #2023牛客多校
Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2) https://codeforces.com/contest/1864 F. Exotic Queries 题意 给定一个长度为 nnn 的数组 aaa,共有 qqq 次询问,每次询问一个区间 [l,r][l,r][l,r]:每次操作可以选定一个区间,将区间内所有数减去任意一个数。要求最终所有的数组中大小在 [l,r][l,r][l,r] 内的数都恰好变为 000,且所有选择的区间要么不交,要么包 2023-08-29 ACM #线段树
AtCoder Beginner Contest 317 https://atcoder.jp/contests/abc317 F - Nim 题意 给定整数 n,a1,a2,a3n,a_1,a_2,a_3n,a1,a2,a3。求解符合以下条件的 (x1,x2,x3)(x_1,x_2,x_3)(x1,x2,x3) 的个数: 1≤xi≤n1\leq x_i\leq n1≤xi≤n xix_ixi 是 aia_iai 的倍数 x1⊕x2⊕ 2023-08-29 ACM #数位dp #匹配
牛客练习赛114 https://ac.nowcoder.com/acm/contest/63804 E Kevin的抽奖黑幕 题意 有 nnn 个人,共 mmm 轮抽奖。每轮抽奖抽 kkk 个人发奖品,若有人连续 ddd 轮没有获得奖品,那么他也能获得一个奖品。求最后所有人获得奖品的总和的期望。结果对 998244355399824435539982443553 取模。 数据范围:1≤n,m≤2000,1≤k≤ 2023-08-28 ACM #dp #概率dp #线性基
2023牛客暑期多校训练营3 F World Fragments II 题意 有 qqq 次询问。每次询问给定两个数 x,yx,yx,y,每次可以对 xxx 进行操作:选定 xxx 的一个数码,令 x←x+bx\leftarrow x+bx←x+b 或 x←x−bx\leftarrow x-bx←x−b。求 xxx 变成 yyy 的最小操作次数。强制在线。 数据范围:1≤q≤3×105,0≤x,y≤3×1051\leq q\l 2023-08-22 ACM #哈希 #倍增 #最短路 #2023牛客多校 #Manacher #分治
Kruskal重构树 Kruskal重构树 考虑这样一个问题:给定一个 nnn 个点 mmm 条边的带权无向图。多次询问 uuu 到 vvv 的路径中,边权的最小值最大的路径。 我们仿照Kruskal算法,将边权从大到小排序,依次加入。如果两端点已经连通,那么这条边没有意义(因为它的权值更小)。最终,至多只有 n−1n-1n−1 条边有意义,得到了一棵生成树或生成森林。 Kruskal重构树利用点权信息表示边权信息。具 2023-08-22 ACM #Kruskal重构树
2023牛客暑期多校训练营2 A Link with Checksum 题意 定义一种 CRC−LINKCRC-LINKCRC−LINK 校验方式。给定 headerheaderheader 长度为 n1n_1n1 个字节,footerfooterfooter 长度为 n2n_2n2 个字节,要求构造一个长度为 444 个字节的 checksumchecksumchecksum,使得 header,checksum,f 2023-08-21 ACM #2023牛客多校 #高斯消元 #Manacher
Manacher Manacher 算法 简介 Manacher 算法可以 O(n)O(n)O(n) 求解字符串每个位置的回文半径。 回文半径指的是从回文中心到回文串一端的字符个数。比如 abcba 的回文半径为 333,abba 的回文半径为 222。上面两个例子对应了奇回文和偶回文的情况(即回文中心落在某个字符上和回文中心落在两个字符之间)。 过程 下面介绍处理奇回文的过程,偶回文基本类似,字符串下标从 000 2023-08-21 ACM #Manacher