4 BAJim_H

尚未进行身份认证

比孤独更可悲的事情,就是根本不知道自己很孤独,或者分明很孤独,却把自己都骗得相信自己不孤独。

等级
博文 464
排名 7k+

NOI2019 复习

GDOI2018复习图论()网络流相关(二元关系,最大权闭合子图、最长反链,上下界网络流)()差分约束系统()欧拉回路()2-SAT动态规划树形依赖DP,数位DP、斜率优化DP搜索、博弈()SG函数()A*、IDA*Nim游戏字符串KMP()扩展KMP()AC自动机()SA(D)SAMmana...

2019-07-09 19:54:04

【学习小记】Berlekamp-Massey算法

PrefaceBM算法是用来求一个数列的最短线性递推式的。形式化的,BM算法能够对于长度为n的有穷数列或者已知其满足线性递推的无穷数列aaa,找到最短的长度为m的有穷数列ccc,满足对于所有的i≥ni\geqni≥n,有ai=∑j=1mcjai−ja_i=\sum\limits_{j=1}^{m}c_ja_{i-j}ai​=j=1∑m​cj​ai−j​TextBM算法的流程十分简洁明了—...

2019-07-03 22:27:10

【总结】【NOI2019模拟7.3】

TextT1:爆精度题DP?多项式?可以乱搞?确实是爆精度大概不用很多轮精度就够了,题解是10^7只靠虑非中性多少轮考虑非中性i轮的次数期望,以及i轮非中性后合法的概率,乘在一起求和这两个东西都可以递推概率直接考虑意义期望轮数可以考虑它的生成函数,等比数列求和以后是一个1阶的线性递推,第0项和第1项要暴力算。T2:线性基?可以试一下进制数为2写了个猎奇搜索搜了17...

2019-07-03 21:50:40

[JZOJ6247]【NOI2019模拟2019.7.2】C【计数】

Descriptionn<=200000Solution比赛时没做出这道题真的太弟弟了首先我们从小到大插入数i,考虑B中有多少个区间的最大值为i恰好出现的次数不太好计算,我们考虑计算最大值小于等于i,再做一个差分即可。然后直接分成长度在一段内的和长度跨过一段边界的考虑,跨过完整的一段的区间的答案一定是整个序列最大值分类讨论即可,式子并不难推,有一个地方可以直接暴力计算前缀和。...

2019-07-02 22:18:16

【总结】【NOI2019模拟7.2】

Text今天这比赛打的相当的弟弟T1:树上关于链的计数,感觉是点分治:60分送的前20N方3单独计算边的贡献一条链直接算。8:49先写暴力!!60分暴力拍过然后就不管了(事实上这个题感觉当时再想多一会就想出来了)T2:直接MTT多项式exp根号DP??不会MTT一秒十万应该能过0.93s有点慌后来优化到了0.89sT3序列计数?33分暴力走人估分60...

2019-07-02 15:36:14

[JZOJ6244]【NOI2019模拟2019.7.1】islands【计数】【图论】

Descriptionn<=1e9,M,K<=100Solution显然任选m个港口的答案是一样的,乘个组合数即可。考虑枚举m个港口的度数之和D可以DP计算记Fm,DF_{m,D}Fm,D​为将D的度数分给m个港口的方案数枚举新的一个度数分配给谁,然后此时可能某一个超出了限制,减掉这一个的贡献。接下来我们可以用一个超级根把D个点连起来prufer序简单计数即可n−m...

2019-07-01 22:16:20

[JZOJ6244]【NOI2019模拟2019.7.1】Trominoes 【计数】

Descriptionn,m<=10000Solution考虑暴力轮廓线DP,按顺序放骨牌显然轮廓线长度为N+M轮廓线也是单调的1表示向上,0表示向右N个1,M个0只能放四种骨牌四种转移写出来,就是10000001111001111010001111000101相当与一个1和后面3格的一个0换过来,中间不变把模3相同的分组,转换成只换相邻的10再把...

2019-07-01 22:07:40

【总结】【NOI2019模拟7.1】

Text一看题感觉T1比较有搞头,后面两题比较毒,先肝T1题目想法:T1 容斥?题目要求某些位或必须为1容斥若干位必须为0多组询问?高维前缀和F(T)=\sum[SisasubsetofT]G(S)(-1)^|S|G(S) 为1的位置强制选0算出这样的个数,直接组合数计算G(S)=C(cnt(S),k)高维前缀和:f全部小于等于g前i位等于,后面小于等...

2019-07-01 19:33:30

[JZOJ6241]【NOI2019模拟2019.6.29】字符串【数据结构】【字符串】

Description给出一个长为n的字符串SSS和一个长为n的序列aaa定义一个函数f(l,r)f(l,r)f(l,r)表示子串S[l..r]S[l..r]S[l..r]的任意两个后缀的最长公共前缀的最大值。现在有q组询问,每组询问给出L,R,xL,R,xL,R,x你需要找到一个子串S[l,r]S[l,r]S[l,r]满足[l,r]⊂[L,R][l,r]\subset[L,R][l,r]...

2019-06-30 22:29:59

[JZOJ6231] 【NOI2019模拟6.25】等你哈苏德【图论】【欧拉回路】【网络流】

Description数轴上有一些线段,需要将它们染成黑或白色,有些已经染好了颜色,现在求一种染色方案使得对于所有整点,覆盖它的黑色线段和白色线段数之差的绝对值不超过1n<=30000n<=30000n<=30000Solution我们把白色看做+1,黑色看做-1,问题变成要求每个位置的值只能是[−1,0,1][-1,0,1][−1,0,1]由于是区间加...

2019-06-30 22:15:35

[JZOJ5553] 【NOI2019模拟6.24】谜【线性代数】

Description有一个两个部分均为n个点的二分图,给出它的邻接矩阵,求这个二分图的完美匹配数量模2的结果。两个部分另外各有m、k个备用点,给出它们与原图中点的连边关系。现给出q组询问,每次询问形如将某一个部分的某个点u替换成该部分的某一个备用点v后,求这个二分图的完美匹配数量。询问没有后效性,也就是说每个询问都是在原矩阵的基础上做的。n,m,k<=1000,q&amp...

2019-06-30 22:15:29

[JZOJ5551] 【NOI2019模拟6.24】旅途【最短路】

Description给出一个n个点m条边的带边权无向图定义1到n的K最短路为所有1到n的路径中,路径上的边权前K大和的最小值。求K=1~n的最短路。n,m<=3000,边权<=10^9Solution首先我们考虑枚举第K大的边,将小于这条边的所有边记为0(相等的话强行给一个顺序)考虑一个朴素的DPf[i][j][0/1]f[i][j][0/1]f[i][j][0/1],...

2019-06-30 22:15:24

[JZOJ6223] 互膜 【线段树】【单调栈】【DP】

DescriptionSolution我们可以设一个朴素的DP记f[i][0/1]f[i][0/1]f[i][0/1]表示第i−1i-1i−1轮上一个人是否操作了i这个位置,当前先手-当前后手的权值的最大值。显然Ans=Sum+f[1][0]Ans=Sum+f[1][0]Ans=Sum+f[1][0]容易得到转移f[i][0]=−f[i+1][1]+s[i]f[i][0]=-f[i+1...

2019-06-30 22:15:18

[JZOJ6221] 担心 【区间DP】【概率】

Description有n个人,每个人有水平值AiA_iAi​每一轮随机挑选剩余的相邻两人单挑,假设两人能力值为a,ba,ba,b,则能力值为aaa的人有aa+ba\overa+ba+ba​的概率获胜,能力值为bbb的人有ba+bb\overa+ba+bb​的概率获胜。给出n,m以及A,问第m个人获胜的概率,答案对998244353取模。n≤100000,A≤109n\leq1000...

2019-06-30 22:15:12

[JZOJ6217] Area【计算几何】

Description给定平面上的n个点,记为A1...nA_{1...n}A1...n​现在给出q组询问,每次给出一个向量P,你需要找一个区间[L,R][L,R][L,R],使得2∑i=lrSΔOPAi2\sum\limits_{i=l}^{r}S_{\DeltaOPA_i}2i=l∑r​SΔOPAi​​最大,输出这个最大值。n<=100000,q<=1000000,坐标绝对...

2019-06-30 22:15:07

[省选联合集训2019] 小结

Preface总体上来说,这段时间的比赛状态有好有坏,第一天的状态不是很好,后面就渐入佳境,比赛的成绩和题目理解的程度也提高了很多。Text模拟赛Day1,Day2BySamjiaDay1的题目很有种PKUWC的感觉,三道题两道计数一道排列构造,数据范围都是什么20之类的,感觉很不符合Samjia的出题风格。T1一开始大家都以为是简单题,结果大部分人(包括我都是做了3h没有做出来心态...

2019-06-30 22:14:31

【GDSOI2019】滑稽二乘法【数据结构】【LCT】

Description点数<=100000,操作数<=200000Solution经典的LCT维护子树路径信息的问题。具体来说,我们对于每一个节点,它在splay上的子树对应了原树中的一条祖先后代链(换过根的),记录这个点的splay子树中的所有黑点以及它们的虚子树中的所有黑点分别到这条祖先后代链的链顶和链底的0次,1次,2次距离和,另外记录splay的子树的所有虚儿子到这条...

2019-06-26 20:24:22

【学习小记】支配树【图论】

Preface给定一个有向图和一个起点ststst,我们需要知道起点到某个点的关于必经点的信息。若起点到点v的所有路径均经过点u,则我们称点u支配点v,显然一个点支配自己本身顾名思义,支配树就是由某些支配关系构成的树。定义约定一些记号(u,v)(u,v)(u,v),表示一条从u到v的有向边fa(u)fa(u)fa(u),表示uuu在DFS树上的父亲。dfn(i)dfn(i)dfn(...

2019-06-26 15:16:21

一类三维子长方体计数问题【计数】

Description有一个n∗m∗ln*m*ln∗m∗l的长方体,每个位置有0/1的权值对于每个为1的位置,要求包含这个位置且内部全为1的子长方体个数。n≤60n\leq60n≤60Solution我们不妨考虑二维该如何数子矩形。如果我们枚举每个合法的矩形,矩形内部+1,可以在左上角,右下角+1,左下右上-1,做一遍二维前缀和就可以得到答案,三维是类似的。如果我们能求出每个位置分...

2019-06-26 14:36:05

【总结】【NOI2019模拟2019.6.20】

Text今天精神状态还算好看题T1又是大数据结构?暴力分不少emmmT2乱搞?暴力分不少…T3???暴力分不少…随便猜了个T2结论,似乎是对的。然后就一直想T2原本想着9:50再弄不出来就写暴力结果刚好想出来了但是我的做法细节比较多,然后就一直写写写加上思路并不是很清晰又一直调调调调到最后总算拍上了,测大数据发现要跑4s心态炸了然后又开始调调调到最后发现是线段树有个地...

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