A_zjzj的博客

原创 快读模板--zhengjun

#define print(x) if(!x)putchar('0');else write(x)template<typename item>inline void read(register item &x){ x=0;register char c=getchar();register bool f=0; while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();} while(c>='0'&&c<

原创 高精度模板--zhengjun

因为之前没有看到过既有负数，还可以压位的高精度运算，所以我就自己发一篇(原来这么简单，我1h1h1h就写好了)如果有什么bugbugbug，请在评论区回复或私聊我，我周末会看的。本模板支持+,−,×,÷, mod ,ab,ab mod x,ab mod 10x+,-,\times,\div,\bmod,a^b,a^b \bmod x,a^b\bmod10^x+,−,×,÷,mod,ab,abm...

原创 fdssf

原创 洛谷 P8420 [THUPC2022 决赛] 匹配 题解--zhengjun

给定 NNN 个长度为 LLL 的 01 匹配串 aaa 和 MMM 长度为 LLL 的 01 禁用串 bbb，要求找到一个不是禁用串的长度为 LLL 的 01 字符串 ccc，使得 ∑i=1N∑j=1L[ai,j≠cj]\sum\limits_{i=1}^N\sum\limits_{j=1}^L{[a_{i,j}\ne c_j]}i=1∑N​j=1∑L​[ai,j​​=cj​] 最小，求出这个最小值。这是与官方题解不同的解法，时空复杂度：O((N+M)×L)O((N+M)\times L)O((N+M)

原创 洛谷 P6291 [eJOI2017]骆驼 题解--zhengjun

题目传送门一看就是构造题，显然要分成若干块 5×55\times55×5 的小块，然后发现对于一个小块中，只有最中间的那格可以从别的小块中一步跳进来。然后我们打一个爆搜，打出从当前小块的中间走到各个方向相邻的小块的方案。这样就可以在小块间移动了。由于我们需要把所有的点都绕一遍，那么显然是在 2∼N52\sim \frac{N}{5}2∼5N​ 行上边绕来绕去，直到最后一列绕完之后从第一行绕回第一格。所以在 NNN 为奇数的时候，最后上去的时候需要把两列一起处理掉，然后就爆搜跑一个 5×105\times10

原创 HHHOJ #246 卡车 题解--zhengjun

题目传送门给定一个 nnn 个点的树，每个点有权值 viv_ivi​，每条边也有权值 wjw_jwj​，对于树上一条简单路径，它的权值就是路径上（包括两端点）min⁡{vi}×∑wj\min{\{v_i\}}\times\sum w_jmin{vi​}×∑wj​，求最大的路径权值。显然可以发现可以将每个点按照 aia_iai​ 从大到小排序，枚举当前的 min⁡{vi}\min\{v_i\}min{vi​}，然后发现原来的树会分成若干个连通块，只需要维护出每个连通块的直径即可。合并连通块的时候，用左边直径

原创 CF700E Cool Slogans / YbtOJ「字符串算法」第3章 后缀自动机 G. 重复子串 题解--zhengjun

选出一个字符串序列 sss，使得对于每一个 sis_isi​，都是原串的子串，且每个 sis_isi​ 在 si−1s_{i-1}si−1​ 中都出现过至少两次，求最大的序列长度。发现其实可以做到让所有选出的字符串都是上一个字符串的后缀，因为如果后面留了一个尾巴，那么前面的字符串把这个尾巴砍了是不影响答案的。然后发现，其实这个就是 SAM 在 parent 树上的顺序（在 parent 树上，儿子一定是父亲的后缀），那么，只需要从上往下 dpdpdp，记录上一个选择的后缀为 fafafa，当前在 uuu，那

原创 洛谷 P4022 [CTSC2012]熟悉的文章 / YbtOJ「字符串算法」第3章 后缀自动机 J. 相似子串 题解--zhengjun

题目大意给定 nnn 个主串和 mmm 个询问串。对于每个询问串，求出最大的 lll，使得存在一种将当前询问串拆分成若干个长度 ≥l\ge l≥l 且在任一主串中出现过的子串的方案。思路蒟蒻还是不会广义后缀自动机，所以我们就用 SA + st 表 + 二分 + 单调队列解决这道问题。首先，可以用 SA + st 表求出每一个询问串的任意一位为左端点时，最大的在主串中出现过的子串的长度。可以直接在 sasasa 数组上记录前后第一个是主串的后缀的位置，然后前后求 LCPLCPLCP 取 max⁡\

原创 YbtOJ「字符串算法」第3章 后缀自动机 I. 独特子串 题解--zhengjun

题目大意给定 nnn 个字符串，求出每个字符串只属于该字符串的本质不同的非空子串的个数。思路如果没有做过这道 SA 入门题《不同子串个数》，那么请先了解这道题的 SA 做法。首先老套路，把所有字符串拼接在一起。然后单独考虑一个字符串 iii，首先求出这个字符串的每一个后缀有多少个前缀没有在其他字符串中出现过，假设当前在求排名为 iii 的后缀的值，那么就需要知道排名在 iii 前面的第一个后缀 sajsa_jsaj​ 与后缀 saisa_isai​ 不在同一个字符串里（即求出最大的 prei=jp

原创 P5903 【模板】树上 k 级祖先--zhengjun

思路开始的时候想用倍增求 k 级祖先卡过去，然后就在考虑倍增数组 f[N][K]，究竟是哪一维放在前面要快一点，所以都打了一下。结果发现，一个会在 #9 TLE，另一个在 #8,#10 TLE，于是分成两类按照 2:12:12:1 的随机分布运行，然后就可以通过这道题了，最快用时：8.74s。代码 #1 倍增#include<bits/stdc++.h>using namespace std;typedef unsigned int ui;ui s;const int N=5e5+10

原创 YbtOJ「字符串算法」第3章 后缀自动机 F. 广义后缀树 --zhengjun

题目大意给定 nnn 个模板串，以及 mmm 个查询串，依次查询每一个查询串是多少个模板串的子串。思路蒟蒻不会广义 SAM，所以只能用 SA + 莫队的高复杂度笨重算法通过了。首先把每个模板串和查询串拼接在一起（中间用不同的字符隔开），然后跑一遍 SA，对于每个查询串，记 iii 为该查询串的后缀编号，lenlenlen 为该查询串的长度，那么就是要找到所有的 jjj，使得 LCP(i,j)≥lenLCP(i,j)\ge lenLCP(i,j)≥len，显然这样的 jjj 的后缀排名 rkjrk_j

原创 洛谷 P3649 [APIO2014]回文串 / YbtOJ「字符串算法」第3章 后缀自动机 H. 回文匹配 题解--zhengjun

思路蒟蒻不会 SAM，所以只好用 SA + Manacher + st 表 + set + 单调栈 + 双指针的笨重做法了。首先处理出每个点为中心的最长回文串长度 oddiodd_ioddi​，以及以 iii 和 i+1i+1i+1 为中心左右对称的最长回文串长度 evnievn_ievni​，这一步可以用 Manacher 轻松搞定。接着求出以 iii 为左端点最长的回文串长度，就是一个区间修改，最后单点查询，可以用线段树或者在 st 表上面打标记之后下推到最底层也可以。然后再对于原串跑一次 SA

原创 PKUSC 2022 游记--zhengjun

day1上午先看了 PKUSC 2022 的开幕式，看了北大的介绍之类的，感觉似乎在损清华？然后试机测试了一下，发现放了一道去年考的 T1。下午

原创 YbtOJ 「字符串算法」第3章 后缀自动机 C. 【问题3】K小子串 题解--zhengjun

思路对于 T=0T=0T=0 的情况，直接建出后缀自动机，统计一下一个点为开始的字串有多少个，然后从上往下找就可以了。对于 T=1T=1T=1 的情况，同样建出后缀自动机，统计一下每个字符串的出现次数，和刚刚一样做就好了。细节不多。代码#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e6+10;int n,m,tag,ch[N][26],lnk[N],len[N],las,cn

原创 ZJOI 2022 游记--zhengjun

前言ZJOI 王朝复辟？？？。。。这次比赛在 5 月 3 号和 4 号，由于 qz 教育局什么五一不调休，正常放完双休回来，刚好比赛的两天就是周二周三，还做好了回来隔离半个月的心理准备，这两天算不了什么。day0比赛前一天下午 1 点半出发，坐的小(mian)巴(bao)车(che)，虽然只坐了 2h 不到，但是腰被安全带勒得酸麻了（这个安全带拉开后只能收紧不能放松，差评！），很快就到了 yw，先到了酒店放下东西，然后立刻去 ywzx 试机。到了试机的地方，就先检查了键盘每个键都是好用的，然后随手

原创 植树节日记

明天是植树节，也是 @chaichunyang 大佬的生日，更是@chaichunyang 大佬 AK IOI 的十周年纪念日，于是我种下了一颗动态树、一颗线段树、一颗树状数组、一颗非旋转式平衡树、一颗红黑树、一颗基环树、一颗左偏树、一颗点分树、一颗笛卡尔树、一颗后缀平衡树、一颗最小斯坦纳树、一颗最小割树当作我送给 @chaichunyang 大佬的生日礼物和 AK IOI 十周年纪念日的礼物之一，这样 @chaichunyang 大佬就能熟练地掌握这些复杂树，然后 @chaichunyang 大佬就能继续

原创 POJ1201.Intervals题解--zhengjun

思路一看就是差分约束，直接建边就好了。代码#include<cstdio>#include<cstring>#include<iostream>#include<queue>using namespace std;typedef long long ll;struct Precision{int x;Precision(int a){x=a;}};struct SW{int x;SW(int a){x=a;}};struct SF{int x;

原创 POJ3371.Flesch Reading Ease题解--zhengjun

思路那就统计就好了，就是有亿点细节。代码#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long ll;struct Precision{int x;Precision(int a){x=a;}};struct SW{int x;SW(int a){x=a;}};struct SF{int x;SF(int a){x=a;}};#defi

原创 POJ3393.Lucky and Good Months by Gregorian Calendar题解--zhengjun

思路那就直接摸你就好了吧。代码#include<cstdio>#include<cstring>#include<iostream>using namespace std;typedef long long ll;struct Precision{int x;Precision(int a){x=a;}};struct SW{int x;SW(int a){x=a;}};struct SF{int x;SF(int a){x=a;}};#define Se

原创 POJ3007.Organize Your Train part II题解--zhengjun

思路首先一看就是统计有多少不同的字符串。那么肯定就是用字典树了。然后如果当前字符串与之前的某个字符串是一样的，那么一定会有使得每一次向下一个节点时，这个节点都是存在的。最后记得清空。代码#include<cstdio>#include<cstring>#include<iostream>#include<set>using namespace std;typedef long long ll;struct Precision{int x;

原创 POJ3096.Surprising Strings题解--zhengjun

思路一看这个字符串长度很小，就直接暴力就好了。然后我们需要一种快速的查看是否有一对大写字符相同的容器。于是就可以想到用 262626 进制+桶，这样就是一一对应了。代码#include<cstdio>#include<cstring>#include<iostream>using namespace std;typedef long long ll;struct Precision{int x;Precision(int a){x=a;}};struct

原创 NOIP 2021 游记--zhengjun

比赛前一天上午翻了翻打过的模拟赛（其实是翻 cqy 的提交记录发现有原题的），发现洛谷上都有很多紫题，于是贺了自己的代码过了好几道紫题和一道蓝题。吃完饭简单收拾了一下就上大巴了。在大巴上和 fls 坐一起，用我的电脑看了电影——《唐人街探案3》（事先下载下来的），还边吃自己带的零食边看电影，零食在车上就吃完了，电影其实是陪 fls 看看，毕竟我看过了，反正到了酒店心情就蛮放松了。到酒店时，zyq 跟我说，他怕 fls 晚上用机械键盘打代码，然后他就不能早睡了，于是要和我换房间，所以我就换了，（反正我

原创 Solution of NOIP2021模拟赛 10.21 By ZJ -- zhengjun

目录Asolution代码Bsolution1: 202020 ptssolution2：404040 ptssolution3：707070 ptssolution4：100100100 pts代码Csolution1：202020 ptssolution2: 303030 ptssolution3：404040 ptssolution4：707070 pts代码solution5：100100100 pts代码Asolution原题：[ZJOI2006]碗的叠放显然枚举碗的叠放顺序，然后算一下高

原创 CF1553I Stairs题解--zhengjun

题目传送门Luogu，Codeforces谈点其他的这个题目翻译好像有亿点问题，我重新发一波。给定一个长度为 nnn 的排列 ppp。令其中第 iii 个位置的权值为最长的包含 iii 的单调区间的长度（不仅要权值单调，而且要连续）。例如，p=[4,1,2,3,7,6,5]p=[4,1,2,3,7,6,5]p=[4,1,2,3,7,6,5] 中，第 666 个位置的权值为 333（[5,7][5,7][5,7] 这个区间单调递减而且连续），第 222 个位置的权值为 333（[2,4][

原创 CF1555E Boring Segments题解--zhengjun

题目大意给你 nnn 个区间 [li,ri][l_i,r_i][li​,ri​] 以及每个区间的权值 wiw_iwi​，要求选择一些区间出来覆盖区间 [1,m][1,m][1,m] （要求区间首尾相接），求选择的区间的 www 的极差的最小值。思路看到极差的最小值，想到二分，但不会验证，放弃！然后分析了一下，这个首尾相接就很难受，我们可以把所有区间的右端点都减一（包括区间 [1,m][1,m][1,m] ），就不需要首尾相接了，只要把每个点都覆盖到就好了。接着我们考虑，最后选出来的区间的 www

原创 CF1555D Say No to Palindromes题解--zhengjun

题目大意给你一个字符串，每次询问区间 [l,r][l,r][l,r] 最小需要改变几个才能使得这个区间的所有子区间都不是长度至少为 222 的回文串。思路首先我们想一想所有子区间都不是长度至少为 222 的回文串长什么样子。ai≠ai+1a_i\ne a_{i+1}ai​​=ai+1​ai≠ai+2a_i\ne a_{i+2}ai​​=ai+2​这两个性质足够了。所以这个串一定是形如 123123··· 这样三个不同的字母组成的循环。那么，对于每次询问，考虑枚举这个串的最终形式：

原创 CF1555C Coin Rows题解--zhengjun

题目大意有一个 2×m2\times m2×m 的矩阵，每次从 (1,1)(1,1)(1,1) 号点，往下或往右走到 (2,m)(2,m)(2,m)。Alice 先出发，把经过的点上的权值清空，然后 Bob 再出发，把经过的点上的权值加起来作为答案。Alice 希望最小化答案，Bob 希望最大化答案，求最后的答案。思路首先，从 (1,1)(1,1)(1,1) 走到 (2,m)(2,m)(2,m) 的路径条数也不过就 mmm 条，考虑枚举 Alice 走的路径（枚举从哪一列往下走），然后注意到 ai,j

原创 CF1555B Two Tables题解--zhengjun

题目大意在一个长为 WWW，宽为 HHH的房间中（左下角坐标 (0,0)(0,0)(0,0)，右上角坐标 (W,H)(W,H)(W,H)），摆放着一张桌子，其左下角和右上角坐标分别为 (x1,y1),(x2,y2)(x1,y1),(x2,y2)(x1,y1),(x2,y2)，现在还要继续在房间里面放另一张长、宽分别为 w,hw,hw,h 的桌子，问是否可行，如果可行，输出第一张桌子最小的移动距离（欧几里得距离）思路看到这个题目，首先可以轻松愉快地得出一个结论：第一张桌子只能横向或纵向移动那么这

原创 CF1555A PizzaForces题解--zhengjun

题目大意你要得到 nnn 片披萨，有三种披萨可供选择：一个 666 片，需要 151515 分钟一个 888 片，需要 202020 分钟一个 101010 片，需要 151515 分钟求最少需要多少分钟才能至少得到 nnn 片披萨。思路首先看这三组数据，发现一个东西：每次只能得到偶数片披萨，那么如果需要奇数片（设为 2x−12x-12x−1），那么就要至少拿 2x2x2x 片披萨。然后又发现第二件事情，平均每片披萨的用时都是 2.52.52.5 分钟，那么好办了，只要算出最少需要多少片

原创 刷题列表--zhengjun

基本算法枚举题目链接是否完成完成情况poj1753Nopoj2965No贪心题目链接是否完成完成情况poj1328Nopoj2109Nopoj2586No分治法题目链接是否完成完成情况poj1741No递推题目链接是否完成完成情况poj2506No模拟法题目链接是否完成完成情况poj1068Nopoj2632

原创 CF662B Graph Coloring题解--zhengjun

题目传送门题目大意给你一张无向图，图中每条边是蓝色或者红色的，让你每次选一个点，就会把与这个点相连的边的颜色反转（红变蓝，蓝变红），求最少步数的方案使得最后所有边的颜色都一样。思路好像没有 2−sat2-sat2−sat 的题解，那我就来一发。首先分类讨论：要么都变成红色，要么都变成蓝色。如果一条边的颜色与当前我们期望的颜色相同，那么要么两个点都选，要么都不选，所以如果一个点不选，那么另一个点也不选，一个点选了，另一个点也要选，建图就行了，如下图。那么同理，如果一条边的颜色与期望的颜色不

原创 2021-07-08~2021-07-22总结--zhengjun

学习的算法线段树+平衡树其实是没学，讲了一些习题AC的题目P4198 楼房重建 P1471 方差 P2023 [AHOI2009] 维护序列P6327 区间加区间sin和 T184393 2021.7.8C T184392 2021.7.8BT184391 2021.7.8A

原创 P7469 [NOI Online 2021 提高组] 积木小赛 题解--zhengjun

题目概述：给你两个长度为 nnn 的字符串 a,ba,ba,b，你需要找出 bbb 中有多少个不同的子串是 aaa 的子序列思路：可以枚举 aaa 中的子串，可是这样可能会有多个相同的子串被算了多次，那么，我们就可以用 TrieTrieTrie 树，然后从根节点开始向下搜，枚举每一个子串，看一下在 aaa 中有没有。很显然，如果当前的这个子串已经不匹配了，那么就没有再搜下去的必要。然后，我们可以用一个 nexi,c=′a′to′z′nex_{i,c='a'to'z'}nexi,c=′a′to′z′

原创 最大公约数为素数的数对

题目大意其实就是给你 nnn，让你求这个式子：∑d∈prime,d≤n∑i=1n∑j=1n[gcd⁡(i,j)==d]\sum\limits_{d\in prime,d\le n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)==d]d∈prime,d≤n∑​i=1∑n​j=1∑n​[gcd(i,j)==d]一看就是莫比乌斯反演，开始反演：∑d∈prime,d≤n∑i=1n∑j=1n[gcd⁡(i,j)==d]\sum\limits_{d

原创 洛谷 P2602 [ZJOI2010]数字计数 题解--zhengjun

这道题其实就是一个数位 dpdpdp 裸题，就是他这个前缀 000 有一点难处理，所以就多开一维就行了。代码#include<cstdio>#include<cstring>#define ll long longusing namespace std;ll f[13][2][2][13];int a[13];ll dfs(int i,int is,int zero,int num,int sum){ if(!i)return sum; if(f[i]

原创 洛谷 P4053 [JSOI2007]建筑抢修 题解--zhengjun

首先，我们可以贪心一下，把报废的时间按升序排序。然后每到一个建筑，如果这个建筑可以修，那么就修了它。如果不能修，那么就要看了，如果已经修了一个修筑时间大于当前不能修的建筑的修筑时间，那么显然是选当前这个好一点。代码#include<cstdio>#include<queue>#include<algorithm>#define ll long longusing namespace std;struct zj{ ll a,b; bool

原创 NOIP模拟赛准考证号题解--zhengjun

一眼数位 dpdpdp答案就是 sum1,r−sum1,l−1sum_{1,r}-sum_{1,l-1}sum1,r​−sum1,l−1​，关键是如何求 sum1,numsum_{1,num}sum1,num​用 fi,j,0/1f_{i,j,0/1}fi,j,0/1​ 表示在第 iii 位时，上一位填了 jjj，是否顶到上界（就是比如说在 474747 中，一开始选了 444，那么顶到了上界，下一位就不能取到 8/98/98/9）的方案数。转移方程式显然是：fi,j,is=∑k=09fi−1,k,

原创 洛谷 P2727 [USACO3.2]01串 Stringsobits 题解--zhengjun

一眼看去就感觉是数位 dpdpdp 弱化版 + 路径输出用 fi,0/1,jf_{i,0/1,j}fi,0/1,j​ 表示在从低到高的第 iii 位，填了 0/10/10/1，之前填了 jjj 个 111 的个数。转移方程式显然就是：f[i][0][j]=f[i-1][0][j]+f[i-1][1][j];f[i][1][j]=f[i-1][0][j-1]+f[i-1][1][j-1];然后求出 fff 的之后，要开始输出路径。从高位开始输出，假设当前在第 iii 位如果第 iii 位上填

原创 洛谷 P1179 数字统计--zhengjun

题目传送门这道题其实直接做就好了，枚举每一个数，把这个数拆分一下就行了。代码：#include<cstdio>using namespace std;int sum[10001],l,r;int main(){ for(int i=1;i<=10000;i++){ int k=i,cnt=0; while(k){ cnt+=(k%10==2); k/=10; }

原创 zjzj只爱数学--一道很厉害的题目(原创)

题目背景zjzjzjzjzjzj 大佬最喜欢的，就是找到一些红的数学题，把他们改变成蓝的，紫的，甚至黑的。题目描述有一天， zjzjzjzjzjzj 大(jù)佬(ruò) 看到了 fxtfxtfxt 蒟(dà)蒻(lǎo)出的一道题 ::: wangshengjun33wangshengjun33wangshengjun33 与 275307894a275307894a275307894a...