4 Master.Yi

尚未进行身份认证

学习他人,提升自己; 提升自己,帮助他人。

等级
TA的排名 1w+

模拟赛20200215【区间异或(差分+bfs+状压),变化边权最小生成树,线性回归方程(绝对值函数、偏导数求最值)】

T1:题解:将[i,i+siz−1][i,i+siz-1][i,i+siz−1]取反,差分一下,可以看成在 iii 异或1,在 i+sizi+sizi+siz 异或1。于是问题转化为使差分数组与原数组的差分数组相同,差分数组的范围为[1,n+1][1,n+1][1,n+1]。原数组中xxx为1,即在差分数组中 xxx 异或 1,x+1x+1x+1 异或 1。可以看出1的个数≤2k\le...

2020-02-16 22:52:45

模拟赛20200213【增量求第n小,三角剖分分治最短路,树上路径中位数之和】

T1:n≤6500n\le6500n≤6500题解:因为10i+1/2i&1=010^{i+1}/2^i\&1=010i+1/2i&1=0, 10i/2i&1=110^i/2^i\&1=110i/2i&1=1,所以10k10^k10k的二进制表示的末尾一定有kkk个0所以可以记录长度为lenlenlen的所有合法串及其对应的二进制表示,...

2020-02-13 22:36:21

模拟赛20200212【幂和->二项式定理/斯特林数,容斥,曼哈顿最大生成树(Boruvka算法)】

T1:题解:记s[i]s[i]s[i]为前缀和,则Ansi=∑j=0i−1(s[i]−s[j])k=∑j=0i−1∑x=0k(kx)s[i]x∗(−1)k−x∗s[j]k−x=∑x=0k(kx)s[i]x(−1)k−x∑j=0i−1s[j]k−xAns_i=\sum_{j=0}^{i-1}(s[i]-s[j])^k=\sum_{j=0}^{i-1}\sum_{x=0}^k\binom {...

2020-02-12 22:55:14

模拟赛20200211「LibreOJ NOI Round #2 Day 1」

T1:题目链接大意:支持尾部插入一个正整数aia_iai​,询问求f(al,al+1,...,ar)f(a_l,a_{l+1},...,a_r)f(al​,al+1​,...,ar​),其中f(x)=x,f(a0,a1...,an)=a0+1f(a1,a2,...,an)(n≥1)f(x)=x,f(a_0,a_1...,a_n)=a_0+\frac 1{f(a_1,a_2,...,a_n)}(...

2020-02-11 23:18:14

模拟赛20200208【概率生成函数,NTT优化DP,同构(本质匹配)后缀数组】

T1:题解:考试的时候相当转化为多项式,然后就不会了。。题解:求无穷项的多项式是可以由递推关系解的!用分式多项式表示就行了!std维护了多项式,但是由于最后只需要F1(z)=zF′(z),F2(z2)=z4F′′(z2)+z2F′(z2)F_1(z)=zF'(z),F_2(z^2)=z^4F''(z^2)+z^2F'(z^2)F1​(z)=zF′(z),F2​(z2)=z4F...

2020-02-10 23:55:18

模拟赛20200210【扫描线(单调性),最小割,基环树染色(树哈希+Polya)】

T1:题解:C类点可以不用平衡树维护,因为B类点的a[i]a[i]a[i]一定是后缀最小值,所以只需要在询问的时候把a[j]<a[i]a[j]<a[i]a[j]<a[i]的点的贡献全部删掉就可以了。在计算C类点的贡献时只需要将a[j]a[j]a[j]到前缀最大值区间加1就可以了。考试的时候想到单调性但是搞来搞去没搞出来(被“浙江省选模拟赛”标题吓住导致轻易自闭。。),...

2020-02-10 23:27:21

模拟赛20200207 Day3

T1:题目描述:题解:n≤20n\le20n≤20的时候可以状压求出每个连通块的点分方案数。然后就自闭了。题解告诉我们,两棵点分树是可以合并的!两棵结构一定的点分树通过一条边连接后可以形成一些新的点分树,方案数与连边的两个点在点分树中的深度有关,并且在新的点分树中原来的两棵树的点分顺序是不变的。画出左链右链,合并的过程有点类似于Treap的merge操作。Code:#incl...

2020-02-07 22:21:18

数论笔记 (20200205)

类欧几里得算法:求∑x=0n⌊ax+bc⌋\sum_{x=0}^n\lfloor {ax+b\over c}\rfloor∑x=0n​⌊cax+b​⌋类欧几里得算法的推导欧拉定理:对于(a,m)=1(a,m)=1(a,m)=1,有 aφ(m)≡1 ( mod  m)a^{\varphi(m)}\equiv1 ~(\bmod ~m)aφ(m)≡1 (mod&nb...

2020-02-05 23:05:16

字符串笔记 (20200204)

最小周期 =n −=n~-=n − 最大border关于循环串的疑问:如果最小周期为xxx,且∣S∣|S|∣S∣不能被xxx整除,那么是否可能存在一个周期y>xy>xy>x,使得∣S∣|S|∣S∣能被yyy整除?关于跳KMP的疑问:如果BBB为ABkAB^kABk的最小周期,且AAA是BBB的后缀,为什么当k>1k>1k>1时ABk...

2020-02-04 23:26:43

关于后缀自动机的理解

一个点表示一个终点集合,即表示一段连续长度的后缀,其后缀链接指向最大长度为minlen-1的点clone就是因为在len[p]+1<len[q]的情况下,cur的后缀链接并不能直接指向q,这样会导致不合法的后缀出现所以clone q,把原来q的后缀分成两部分,一部分是len<=len[p]+1的,另一部分是len>len[p]+1的这也是为什么要把p的后缀链接中点重定...

2020-02-04 22:31:38

模拟赛Day1(20200207) T3 二分题【对树的重心的充分利用】

题目描述:题目分析:先考虑k=nk=nk=n的情况,这是一个经典问题,结论为所有点到重心的距离和。证明:对任意一点uuu,都有dis(pi,pi+1)≤dis(pi,u)+dis(u,pi+1)dis(p_i,p_{i+1})\le dis(p_i,u)+dis(u,p_{i+1})dis(pi​,pi+1​)≤dis(pi​,u)+dis(u,pi+1​)那么就有∑i=1ndis(...

2020-02-03 23:54:14

模拟赛Day1(20200203) T1 垃圾题【分类讨论+枚举+dp解决等价匹配问题】

题目描述:题目分析:看到bbb的长度为5,可以感觉到这题就是在锻炼强大合理的分类讨论能力。首先看bi≤2b_i\le2bi​≤2的部分分,即只有两种数字。枚举这两种数为x,yx,yx,y,数量分别为cntx,cntycnt_x,cnt_ycntx​,cnty​,可以记状态f[i][5]f[i][5]f[i][5],在O((cntx+cnty)∗5)O((cnt_x+cnt_y)*5)O...

2020-02-03 22:16:01

模拟赛Day1(20200203) T2 数论题【前缀最小逆元】

题目描述:题目分析:逆元可以看做一个伪随机序列,前p\sqrt pp​个数的逆元的最小值期望可以缩小到O(p)O(\sqrt p)O(p​)级别。所以当p≤109p\le10^9p≤109时可以枚举前p\sqrt pp​个数,求出最小逆元,再枚举逆元求出对应的位置,时间复杂度期望O(p)O(\sqrt p)O(p​)。具体实现时也可以从小到大枚举iii,记录逆元的最小值mnmnmn,如...

2020-02-03 20:37:11

省选模拟赛第三场 T1 与非(巧妙的线段树+后缀insert优化 || 思维题)

https://blog.csdn.net/c20180602_csq/article/details/104127785

2020-02-01 17:16:42

省选模拟赛20200131 T3 数星星【三角形二维数点】

题目描述:一个二维平面直角坐标系,其中有 N 颗星星(坐标为整点),你会有 M 个询问,询问以某个整 点为顶点的正三角形包含大于等于 K 个星星的最小非负整数边长为多少,如果无 法满足输出-1。对于一个 正三角形,如果给出的顶点为(X,Y),边长为 L(L>=0,当 L 为 0 的时候退化为一 个点),那么三个顶点坐标分别为(X,Y),(X+L/2,Y+L/2*sqrt(3)),(X+L...

2020-01-31 22:38:50

省选模拟赛20200130 T1(BZOJ3462: DZY Loves Math II)【多重背包去重】

题目描述:经过一点简单的转化题目可表述为:给出kkk个质数p1,p2...pkp_1,p_2...p_kp1​,p2​...pk​,p1⋅p2...⋅pk=Sp_1\cdot p_2...\cdot p_k=Sp1​⋅p2​...⋅pk​=S每次询问给出整数nnn,将nnn拆分为这kkk个质数之和(每个质数可以选任意次),问拆分的方案数。n≤1018n\le10^{18}n≤1018,询问...

2020-01-30 15:36:41

省选模拟赛20200129 T1 (分割字符串使最大字典序子串最小)【二分,贪心,后缀数组】

题目描述:长度为nnn的字符串sss,至多可以分成mmm段,使所有段的所有子串中字典序最大的子串字典序最小,输出这个串。n≤105,m≤15n\le10^5,m\le15n≤105,m≤15题目分析:事实告诉我们最大值最小真的可以二分。。先求出后缀数组,得到本质不同的子串个数。然后二分答案,每次先通过后缀数组求出第mid小的子串,然后贪心进行检验。检验的时候,从后往前贪心,每次加入一...

2020-01-29 22:30:39

回文树学习笔记

学习地址:回文树介绍(Palindromic Tree)一些小总结:回文树的每个点表示一个本质不同的字符串。有两个根,一个表示长度为0的字符串,一个表示长度为-1的字符串。一条边意味着在两边同时添加一个字符c。后缀链接指向后缀最长回文串。在串S的末尾添加一个字符c,最多产生一个本质不同的回文串,只可能是现在的后缀最长回文串。在回文树建树过程中查找后缀最长回文串以及后缀链接时指针只会向...

2020-01-21 21:01:32

2-sat学习笔记

例:struct TwoSAT{ int n; vector<int> G[N*2]; bool mark[N*2]; int S[N*2],c; int dfs(int x) { if (mark[x^1]) return 0; if (mark[x]) return 1; //和假设的值...

2020-01-21 20:22:35

HDU3341 Lost's revenge【AC自动机 + DP(状态编号)】

题目描述:N(<=50)个有效基因串,每个长度<=10,你有的基因串M,长度<=40,重排M,使得其包含的有效基因串数最多(可重叠),输出最多个数。基因只有四个字母AGCT。题目分析:有效基因串建立AC自动机。f[a][b][c][d][i]f[a][b][c][d][i]f[a][b][c][d][i]表示分别用了a,b,c,da,b,c,da,b,c,d个字母A,G...

2020-01-19 22:28:30

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发。