破壁人五号-CSDN博客

原创某 SCOI 模拟赛 T1 集合划分（divide）【生成函数 NTT 分治】

题意有长为 2n2n2n 的序列 A,BA,BA,B，求有多少个单调不减的序列 CCC，要求 CCC 的每一位均为 AAA 或 BBB 中对应位置上的数，且恰有 nnn 个数来自 AAA。n≤5×104n\leq 5\times 10^4n≤5×104。3s。题解设 f[i][j=0/1][k]f[i][j=0/1][k]f[i][j=0/1][k] 表示 DP 确定了前 iii 个数，第 iii 个数是 Ai/BiA_i/B_iAi/Bi ，已经有 kkk 个数来自 AAA 的方案数。直接 DP

2020-06-26 08:37:17 408

原创题解 [联合省选 2020 A] 作业题（LOJ #3304 / 洛谷 P6624）【矩阵树定理】

题目链接：洛谷 P6624 / LOJ #3304题意给定无向带权简单图，其生成树的价值定义为树内边权之和乘以其 gcd⁡\gcdgcd，求其所有生成树的价值和。n≤30n\leq 30n≤30，w（边权）≤152501w{\tiny\text{（边权）}} \leq 152501w（边权）≤152501。题解考虑当 gcd⁡\gcdgcd 确定时所有生成树的边权和之和，然后把它转化为 gcd⁡\gcdgcd 为 ddd 的倍数时所有生成树的边权和之和再容斥一下。先枚举 ddd，把所有 ddd 的

2020-06-24 20:18:57 497

原创题解 [联合省选 2020 A] 树（LOJ #3303 / 洛谷 P6623）【01-Trie 启发式合并】

题目链接：洛谷 P6623 / LOJ #3303题意给定一棵有根树，节点有点权 v(i)v(i)v(i)。定义 val(i)=⨁j(v(cj)+d(cj,x))val(i)=\bigoplus\limits_{j}(v(c_j)+d(c_j,x))val(i)=j⨁(v(cj)+d(cj,x))，其中 d(x,y)d(x,y)d(x,y) 为 xxx 到 yyy 简单路径上边的数量，cjc_jcj 在 iii 的子树中。求所有节点的 valvalval 之和。n,v(i)≤525010n,v(

2020-06-24 16:26:27 634

原创题解 [联合省选 2020 A] 组合数问题（LOJ #3300 / 洛谷 P6620）【第二类斯特林数下降幂多项式】

题目链接：洛谷 P6620 / LOJ #3300题意求：∑k=0nf(k)×xk×(nk) mod p\sum_{k=0}^n f(k)\times x^k\times{n\choose k}\bmod p∑k=0nf(k)×xk×(kn)modp，其中 fff 为一个 mmm 次多项式，n,xn,xn,x 给定，ppp 为给定的数（不一定是质数）。n,x,p≤109n,x,p\leq 10^9n,x,p≤109，m≤103m\leq 10^3m≤103。题解多项式与组合数不太搭，我们假装已经

2020-06-24 14:50:57 466

原创题解 [联合省选 2020 A] 冰火战士（LOJ #3299 / 洛谷 P6619）【树状数组二分】

题意有两队人，分别为冰系和火系。每个人有所在队伍 ttt、温度 xxx、能量 yyy。多次添加、删除人，询问每次操作结束后尽可能大的 vvv，使得冰系所有温度不低于 vvv 的人的能量总和 w1w_1w1 与火系所有温度不高于 vvv 的人的能量总和 w2w_2w2 二者最小值最大，并输出 2min⁡(w1,w2)2\min(w_1,w_2)2min(w1,w2)。题解get 新技能：树状数组上二分。首先把 xxx 离散化，并为冰系与火系的 yyy 都建树状数组，每次查询找到第一个冰系 yy

2020-06-24 10:37:42 529

原创某 SCOI 模拟赛 T2 完美括号序列（beautiful）【贪心】

题意已知在第 iii 个位置放左括号代价为 aia_iai，放右括号代价为 bib_ibi，求长为 nnn 的括号序列的最小代价。题解括号序列要合法，也就要求前 iii 个括号里面右括号的个数不超过 ⌊i2⌋\lfloor{i\over 2}\rfloor⌊2i⌋ 个。先假设全部括号都是左括号，然后每次贪心地换一个左括号为右括号，用线段树判断能不能换。#include<bits/stdc++.h>using namespace std;#define ll long long

2020-06-23 19:33:08 216

原创某 SCOI 模拟赛 T2 排列（permutation）【最小割】

题意有 nnn 个数 xix_ixi，找到它们的一个排列，有 mmm 个要求 xax_axa 要放在 xbx_bxb 前面，最大化所得排列的最大连续子段和。题解负数不好处理。先把答案设成所有正数的和，假如最大连续子段和不包括某个正数，答案 −xi-x_i−xi，如果包括某个负数，答案 −∣xi∣-|x_i|−∣xi∣。整个排列可以分为三段：最前面的不在和最大的连续子段中的、中间一段的在其中的、最后面的不在其中的。考虑建图：st→pi→qi→edst\to p_i\to q_i\to ed

2020-06-22 21:42:26 267

原创某 SCOI 模拟赛 T1 连通性（floyd）【计数DP】

题意TTT 次询问：在用 Floyd 算法处理任意两点间连通性时，若第一层循环（枚举中间点）不枚举到编号最大的 mmm 个点，得到的结果与正常 Floyd 算法得到结果相同的 nnn 个点的无向图有多少个。答案模 109+710^9+7109+7。m≤n≤100m\leq n\leq 100m≤n≤100，T≤105T\leq 10^5T≤105。题解把 1 号到 n−mn-mn−m 号点称为黑色点，n−m+1n-m+1n−m+1 号到 nnn 号点称为白色点，若每个连通块内的任意点对都能找到一条除起

2020-06-22 20:54:24 177

原创某 SCOI 模拟赛 T1~T3【组合数学分段打表 01-Trie Boruvka 树哈希状压DP】

因为题目相比其他几次水一点所以就写一起了。T1题意问有 nnn 个元素 1 到 nnn 的二叉堆个数，模 109+710^9+7109+7。n≤109n\leq 10^9n≤109。题解

2020-06-20 15:06:44 202

原创题解 CF888G Xor-MST【01-Trie Boruvka】

题目链接题意有一 nnn 个点的完全图，点有点权 aia_iai，边 (i,j)(i,j)(i,j) 有边权 ai⊕aja_i\oplus a_jai⊕aj（异或），求其最小生成树。n≤2×105n\leq 2\times10^5n≤2×105。题解最小生成树有一种冷门算法叫做 Boruvka。其大致思想是：初始有 nnn 个点各自为一个连通块，形成一个森林；反复进行以下操作直到森林变成树：找到每个连通块连向其外部的最小边；将这些边都连上（有重复也不必管）。显然每次操作是

2020-06-20 14:35:46 303

原创某 SCOI 模拟赛 T3 交换（swap）【分治哈希】

题意定义一个字符串合法当且仅当：它为空串；它形如 aSa\texttt aS\texttt aaSa、bSb\texttt bS\texttt bbSb 或 cSc\texttt cS\texttt ccSc，其中 SSS 是合法的；它形如 STSTST，其中 SSS、TTT 都是合法的。给出字符串 SSS，问：有多少种交换两不同字符的方案，使得交换后的 SSS 合法。∣S∣≤105|S|\leq 10^5∣S∣≤105，3s。题解假如一个字符串每次删除相邻的两个相同字符，最后变成空串，

2020-06-18 11:42:59 192

原创某 SCOI 模拟赛 T2 宝藏（treasure）【状压 DP】

题意有一张 NNN 个点 MMM 条边的无向图，边带权。图上有 kkk 对“结界”与“晶石”，分别位于 viv_ivi 与 ziz_izi。有结界的点不能通过，除非你到它对应的晶石所在的点取走晶石并用该晶石击破该结界。QQQ 次询问 sss 到 ttt 的最短路，询问之间互相独立（即前一次询问拿走晶石、击碎结界都不影响下一次询问）。n≤400n\leq 400n≤400，m≤105m\leq 10^5m≤105，k≤16k\leq 16k≤16，Q≤105Q\leq 10^5Q≤105，2s。题解

2020-06-18 08:56:12 214

原创某 SCOI 模拟赛 T2 二叉树（tree）【括号序列容斥】

题意称非叶节点都有两个儿子的二叉树为满二叉树。称恰有 kkk 个叶节点且任意节点的右儿子为均为叶节点的满二叉树为 kkk 连树。记二叉树 AAA 包含 BBB 当且仅当 AAA 能通过若干次以下操作变成 BBB：删除某个节点的两个子树；若 xxx 为 yyy 的儿子，用 xxx 的两颗子树代替 yyy 的两棵子树。问：有多少满二叉树叶子个数为 nnn，且不包含 mmm 连树。答案模 998244353998244353998244353。n,m≤107n,m\leq 10^7n,m≤107，2

2020-06-17 20:28:04 244

原创题解 CF1007E Mini Metro（某 SCOI 模拟赛 T3）【DP】

题意有 nnn 座火车站（原题是地铁，不过不重要）在一条轨道上依次排列，编号为 1 到 nnn。每个车站在 0:000:000:00 时（初始状态）有 aia_iai 个人，每小时增加 bib_ibi 个人，容量为 cic_ici 人。你还有足够多的火车，每辆车的大小为 kkk。每个小时的流程大致如下：i:00i:00i:00：第 iii 小时开始；i:30i:30i:30：你可以派出任意多辆火车，它们会从 1 到 nnn 经过每一个站，并在每一个站装尽可能多的人（要么把站台清空、要么把火车

2020-06-17 11:34:43 434

原创某 SCOI 模拟赛 T1 RNG【生成函数】

题意nnn 个格子排成一行，每个格子的颜色是 mmm 种里面均匀随机的，对于 u∈[i,n]u\in[i,n]u∈[i,n]，求出现次数最多的颜色出现次数为 uuu 的概率，答案模给定质数 ppp。n≤500,m≤108n\leq 500,m\leq 10^8n≤500,m≤108，3s。题解转化为计算求出现次数最多的颜色出现次数不超过 uuu 的方案数。即：mmm 种颜色，每种可以选 0 到 uuu 个，用来覆盖 mmm 个格子。考虑 EGF，要求的即为：n![xn](∑i=0uxii!)mn![x

2020-06-17 08:30:18 189

原创某 SCOI 模拟赛 T2 LCM【杜教筛】

题意∑i=1n∑j=1mlcm⁡(i,j,i+j)\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j,i+j)i=1∑nj=1∑mlcm(i,j,i+j)n,m≤1010n,m\leq 10^{10}n,m≤1010，3s。题解设 n<mn<mn<m原式=∑g=1min⁡(m,n)∑i=1n/g∑j=1n/ggij(i+j)[gcd(i,j)=1]=∑g=1ng∑i=1n/g∑j=1n/gij(i+j)∑d

2020-06-16 19:26:33 251

原创题解 CF1017G The Tree【树链剖分线段树】

题目链接：CF1017G题意一棵以 1 为根的有根树，每个节点初始为白色，要求支持以下操作：1 x：若 xxx 节点为白色，将 xxx 变为黑色；若 xxx 节点为黑色，对 xxx 的每个儿子执行 1 操作；2 x：将 xxx 的子树全设为白色；3 x：询问 xxx 的颜色。n,m≤105n,m\leq 10^5n,m≤105题解给每个点分配一个点权 wiw_iwi，初始为 −1-1−1，可以把它理解为从上往下染黑到 iii 后，这个节点上做过的操作会让这个过程会向下多延伸 wiw_i

2020-06-16 09:16:02 255

原创题解 [SDOI2014] 旅行（LOJ #2195 / 洛谷 P3313）【树链剖分动态开点线段树】

题目链接：洛谷 P3313 / LOJ #2195题意一棵 nnn 个点的数，每个点有一个颜色 cic_ici 与权值 wiw_iwi，mmm 次操作：修改某个点的权值；修改某个点的颜色；查询 xxx 到 yyy 的路径上，颜色为 cxc_xcx 的所有点的权值和（保证 cx=cyc_x=c_ycx=cy）；查询 xxx 到 yyy 的路径上，颜色为 cxc_xcx 的所有点的最大值（保证 cx=cyc_x=c_ycx=cy）。n,m,c≤105n,m,c\leq 10^5

2020-06-15 11:10:49 197

原创某 SCOI 模拟赛 T1 那个夏天的 mcfx（anonatsuhe）【构造】

题意给定 n×nn\times nn×n 的表格，其中填入了 1 到 n2n^2n2 的数字。你一次操作可以轮换三个格子里面的数，代价为这三个格子组成的三角形的最大内角度数。你要通过不超过 2333333 次操作，将表格变得有序（a[i,j]=(n−1)i+ja[i,j]=(n-1)i+ja[i,j]=(n−1)i+j），并让最大的一次操作的代价尽可能小。给出方案，保证有解。n=30n=30n=30。代价不高于 (60319)∘(60\dfrac{3}{19})^\circ(60193)∘ 即可获得满分

2020-06-15 08:01:44 242

原创李超线段树略解

李超树是具有线段树结构的一种数据结构，通常用来维护区间插入一次函数与单点查询最值。（下文将问题看作：在平面内维护：插入一条线段、询问现有线段中与 x=ax=ax=a 交点纵坐标最大的线段编号）结构李超树的结构与线段树相同，只是每个节点存储的是平面上的一条线段。该线段是下放到过该节点的线段当中，在 x=midx=midx=mid 处纵坐标最大的一条。我们称它为“优势线段”。插入首先将一条线段分成 O(log⁡)O(\log)O(log) 个区间。对于每段线段，分情况讨论：当前节点没有优势线

2020-06-13 08:34:44 300 1

原创某 SCOI 模拟赛 T1 黑箱（blackbox）【字符串】

题意若有 nnn 个字符串 SiS_iSi，将它们两两拼接起来可以得到 n(n−1)n(n-1)n(n−1) 个字符串 LiL_iLi。已知 LLL，构造一个合法的 SSS，或判断无解。SPJ。n≤50n\leq 50n≤50，∑∣Li∣≤5×104\sum |L_i|\leq 5\times 10^4∑∣Li∣≤5×104。题解现将 SSS 和 LLL 都按长度排序，长度相同按字典序排序。显然此时的 L1L_1L1 就是 S1+S2S_1+S_2S1+S2 或 S2+S2S_2+S_2

2020-06-12 22:10:28 251

原创某 SCOI 模拟赛 T3 c

题意用 nnn 个积木拼一个塔，第 iii 个积木长 aia_iai。给定 ddd，要求积木 iii 能放在 jjj 上面当且仅当 ai−aj≤da_i-a_j\leq dai−aj≤d。求合法的搭积木方案数。答案模 998244353998244353998244353。n≤7×105n\leq 7\times10^5n≤7×105题解先排序。考虑搭好前 i−1i-1i−1 小的积木后，第 iii 个积木能插入进什么地方：它上面是哪个积木不重要，只需要它下面的积木够宽或者它下面没有积木。于是

2020-06-12 19:58:35 220

原创某 SCOI 模拟赛 T2 走（walk）【状压DP 剪枝】

题意nnn 个点排成一个环，你从某个点开始，每步操作从等概率选择四个操作之一：移到左边第二个点、移到左边第一个点、移到右边第二个点、移到右边第一个点。当你走到任何一个点两次时你会立刻停止行走。求操作的期望步数。答案模 ppp。n≤80n\leq 80n≤80。题解首先有 2n2^n2n 的状压 DP，记 1 为到过的点。接着假如环上有至少两个连续的 11，与当前位置被 11 隔开的地方肯定无法到达。于是把这些 11 之间的位置设成 1，这样状态数变少了，就跑过去了。（小问号你是否有许多朋友？）

2020-06-12 11:01:27 243

原创某 SCOI 模拟赛 T3 c【回文自动机树链剖分倍增】

题意有一个字符串 sss（Σ=26\Sigma=26Σ=26），记 f(t)f(t)f(t) 为 ttt 在 sss 中出现的次数，有 mmm 次以下操作：addl⁡ c\operatorname{addl}\ caddl c：在 sss 左侧添加字符 ccc；addr⁡ c\operatorname{addr}\ caddr c：在 sss 右侧添加字符 ccc；transl⁡ l1 r1 l2 r2\operato

2020-06-12 09:35:51 209

原创某 SCOI 模拟赛 T1 a【DP】

题意有 nnn 个单词，每个单词出现 cic_ici 次，现用 - 与 . 给单词编码，要求任意一个单词的编码不是另一个的前缀。设 - 的权值为 2，. 的权值为 1，最小化所有单词的权值和。n≤750n\leq 750n≤750。题解假设我们已经建好了所有单词的字典树，显然出现次数越多的单词应该挂在越浅的叶子（下文深浅均指带权的深浅，- 边长度为 2，. 边长度为 1）。故考虑先将 cic_ici 排序，并 DP。设 f[i,j,k,l]f[i,j,k,l]f[i,j,k,l] 表示前 iii

2020-06-11 20:16:35 146

原创某 SCOI 模拟赛 T3 贪吃的史莱姆（slime）【树形DP】

题意给定一棵树，问多少个排列使得每个长为 mmm 的子区间内的点的导出子图是连通的，答案对 109+910^9+9109+9 取模。2≤m≤n≤4002\leq m\leq n\leq 4002≤m≤n≤400。题解考虑两种情况：2m≤n2m\leq n2m≤n；2m>n2m>n2m>n。2m≤n2m\leq n2m≤n此时排列的最前 mmm 个元素一定是一棵子树，中间部分在一条链上，最后 mmm 个元素在另一个子树里。显然以重心为根 DFS 时，如果恰有两棵大小为 mm

2020-06-11 08:44:50 322

原创某 SCOI 模拟赛 T2 pm【构造题】

题意给你 {1,2,…,n}\{1,2,\dots,n\}{1,2,…,n} 的一个排列 ppp。你可以进行两个阶段的操作：阶段一你可以多次交换相邻的某两个数；阶段二你可以多次把某个数改为另一个数。最小化总操作数。你只需要给出第一阶段的所有操作。题解首先阶段一肯定要把交换的数还原到它该在的位置上。考虑一段 a[l…r]a[l\dots r]a[l…r]，假如把它留给阶段二，最多只用 r−l+1r-l+1r−l+1 次操作就可以完成；所以如果阶段一还原它更优的话，阶段一对它的操作次数应当不高于 r−l

2020-06-10 21:32:14 225

原创某 SCOI 模拟赛 T1 矩形（rectangle）【单调栈二分答案堆】

|破壁人五号低级 OIer|成都市第三区计算机学会提醒您条件千万条，边界第一条边界判不对，出错两行泪{\tiny\text{\colorbox{grey}|破壁人五号低级 OIer\colorbox{grey}|}}\\{\small\text{成都市第三区计算机学会提醒您}}\\\large\text{条件千万条，边界第一条}\\\text{边界判不对，出错两行泪}|破壁人五号低级 OIer|成都市第三区计算机学会提醒您条件千万条，边界第一条边界判不对

2020-06-10 19:56:46 162

原创某 SCOI 模拟赛 T3 串（string）【PAM】

题意对于字符串 SSS 的每个前缀，求其所以回文子串的前缀个数和，本质相同的前缀不重复计数。N≤3×105N\leq3\times 10^5N≤3×105。题解建议先阅读【乱搞】某 SCOI 模拟赛 T3 串（string）【PAM 乱搞】在 Anti-Hack 的基础上，把 vector 维护每个儿子改成 set 维护每个儿子在 SA 里的 rankrankrank。于是每次出现新节点只需要判断与它 rk 最接近的两个兄弟与它的 LCP，复杂度至多是 O(log⁡n)O(\log n)O(log

2020-06-10 10:20:37 197

原创某 SCOI 模拟赛 T1 迫害 DJ（hakugai）【二次剩余斐波那契循环节】

题意TTT 次询问：已知 a,b,n,k,moda,b,n,k,moda,b,n,k,mod，g0=a,g1=b,gi=gi−1+gi−2g_0=a,g_1=b,g_i=g_{i-1}+g_{i-2}g0=a,g1=b,gi=gi−1+gi−2，f(n,k)={f(gn,k−1)(k>0)n(k=0)f(n,k)=\begin{cases}f(g_n,k-1)\quad&(k>0)\\n&(k=0)\end{cases}f(n,k)={f(gn,k−1)n(k&g

2020-06-10 09:49:44 265

原创【乱搞】某 SCOI 模拟赛 T3 串（string）【PAM 乱搞】

请求神仙前来 Hack题意对于字符串 SSS 的每个前缀，求其所以回文子串的前缀个数和，本质相同的前缀不重复计数。N≤3×105N\leq3\times 10^5N≤3×105。乱搞考虑在末尾新加入一个字符时会产生多少贡献。假如新出现前缀，它肯定是新产生的回文串（记为 curcurcur）的前缀，也就是 PAM 上新加的结点的前缀。这些前缀有一些是在之前的回文串里面出现过的（记为 ttt）。我们尝试找到 ttt 中最长的一个，用 cur.lencur.lencur.len 减去 max⁡{t.

2020-06-09 21:27:01 458

原创题解 [SDOI2017] 新生舞会（LOJ #2003 / 洛谷 P3705）【分数规划费用流】

题目链接：洛谷 P3705 / LOJ #2003题意两个集合分别有 nnn 个元素，让一个中的 iii 号与另一个中的 jjj 号匹配会有 ai,ja_{i,j}ai,j 喜悦程度、bi,jb_{i,j}bi,j 的不协调程度。求某种匹配方式使喜悦程度与不协调程度比值的最大值。保留 6 位小数。n≤100n\leq 100n≤100，1≤a,b≤1041\leq a,b\leq 10^41≤a,b≤104。1.5s。题解分数规划板子（？）题，本质上就是二分答案，然后把分母移过去。二分 CCC

2020-06-09 11:27:48 208

原创题解 hdu4625 JZPTREE【第二类斯特林数树形DP】

题目链接：hdu4625（vjudge）题意给定一棵树，对于每个节点 iii 求其他所有点到它距离的 kkk 次方和，答案模 10007。n≤5×104,k≤500n\leq 5\times 10^4,k\leq 500n≤5×104,k≤500。题解先由儿子到父亲 DP 一遍、再由父亲到儿子 DP 一遍，中途想办法快速维护 xk→(x+1)kx^k\to (x+1)^kxk→(x+1)k记 S(n,m)S(n,m)S(n,m) 为第二类斯特林数，即 nnn 个不同的球放入 mmm 个相同盒子（不

2020-06-09 09:43:40 210

空空如也

空空如也