- 博客(1190)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 多项式全家桶
施工现场多项式在数学中，由若干个单项式相加组成的代数式叫做多项式（若有减法：减一个数等于加上它的相反数）。多项式中的每个单项式叫做多项式的项，这些单项式中的最高项次数，就是这个多项式的次数。其中多项式中不含字母的项叫做常数项。为了方便接下来瞎逼逼，我们定义n次多项式A(x)=∑i=1nai⋅xiA(x)=\sum\limits_{i=1}^n a_i\cdot x^iA(x)=i=1∑n...
2019-01-15 22:07:07
596
原创 记一下ubuntu18.04下的个人配置
重回linux的怀抱自然还是选择最熟悉最友好的ubuntu，虽然现在换下了unity用gnome让我不是特别爽快 开一篇blog只是为了记一下各种配置第一个当然是最最最强大的zsh辣zsh+oh_my_zsh 然后就是非常非常有用的albert神器，这个可以考虑开机启动albert 怎么能没有sublime？sublime_text 主题不美观都没有心情码码码 arc_theme 输...
2018-05-04 16:51:41
9188
原创 关于我
现在是2018-02-25，下午就要开学了。闲来无事写点东西憋本蒟蒻oi水平极低，比赛只会神游（雾，文化课常年没有动力，最开心的事情大概就是停课准备比赛了 大概是在小学就接触了竞赛，只记得小学的老师讲了很多但是并没有听进去(lll￢ω￢)，小升初rp爆发一波就来了ssl划水，日常被学长同级dalao吊打x。初一初二都十分naive就不提了。到了应该是初二暑假才真正理解了oi是个啥（太弱了。然...
2018-02-25 12:20:52
611
1
原创 一些教训
RT我果然还是太弱了，感觉最近总是不在状态，sb错误又总是犯。开个坑记一下自己容易错的地方不至于考前心慌慌(rap语气splay记得pushup的顺序，splay操作前的pushdown可持久化、动态开点的数据结构注意空间变量不用全开LL，必要的时候加(LL)想到正解和写出分数是两码事，这个真的很重要各个版本的正解和暴力都可以保留，拍的时候注意文件夹整洁有巨佬曰过，oi无非
2018-01-31 16:15:23
355
原创 hdu6598 Harmonious Army 网络流 最小割
题意有n个人，可以染成黑白两色，给定m个形如（x,y,a,b,c）的限制条件，表示若x和y同为黑色则获得a的价值，若xy同为白色则获得c的价值，否则获得b的价值求能获得的最大价值做法看到n<=500的条件很容易想到用网络流做考虑怎么建图。看到黑白染色不难想到最小割，既然是答案最大那么就是用总的和减去最小的将若干人分成两个集合的最小代价观察这么一个基本图，我们割掉a、b代表x和y都染成了t色，割掉c、d代表x和y都染成了s色，割掉aed代表x和y染成了t和s，割掉bec代表x和y染成了
2020-09-28 20:13:32
309
原创 hdu 6578 Blank dp
题意n个格子排成一行，每个格子可以涂四种颜色。给m个形如(l,r,x)的限制，表示l到r格子内恰好有x种颜色问满足所有限制的涂色方法有多少种n<=100,m<=100做法dp，设f[i,j,k,l]表示四种颜色分别在i、j、k、l出现了最后一次，由于四种颜色调换顺序其实是一样的所以我们可以钦定i<=j<=k<=l向后转移的时候判断当前状态是否满足限制即可，注意滚动和清空数组的问题代码#include <stdio.h>#include &l
2020-09-21 19:48:35
345
原创 hdu6638 Snowy Smile 离散 扫描线 线段树
题意给n个带权点，求最大子矩阵和做法没想到n^2log的做法，老年选手预兆考虑离散，枚举矩形的下边界，然后一行一行加入点，用线段树维护最大子段和每加入一整行我们就在线段树中查询、更新答案我的代码常数特别大，但是能过，这就很奇妙。。代码#include <stdio.h>#include <string.h>#include <algorithm>#include <vector>#define rep(i,st,ed) for
2020-09-17 14:11:48
288
原创 hdu6581 Vacation 脑洞题
题意有若干辆车在排队，每辆车给出它们各自的最大速度和到终点的距离。如果两辆车之间距离为零则后车速度不能大于前车（详见生活经验）。问对于队尾的车车到达终点的时间是多少做法最初的想法是两辆车相遇就会合体，即前车变长、后车消失听了题解发现更进一步就能对了。合体的含义就是最终的答案必定是某一辆车全速跑到终点的时间+队尾车跑完前面车长的时间。我们只需要假设每辆车作为车头然后取max就好代码#include <stdio.h>#include <string.h>#incl
2020-09-17 14:07:28
169
原创 第五周周测（线上）总结
BG出于种种原因，我们的周测不得不在家中进行，而且要父母监考，而且要拍照上传，而且要直播讲解，活久见班里来了一个高一小兄弟，去年的情形又要上演，要被吊打了555时间的安排和高考是一致的，不过多了30min拍照提交。都是碎碎念和虾球总结，没啥价值的东西，误入可以↗语文这次语文感觉中规中矩（哪次不是中规中矩(lll￢ω￢)），选择题错得有点多，但是回头看感觉都是不得不错的那种。一个诗...
2020-03-17 16:15:43
500
3
原创 如何 收集 分析 优秀评论 学习 作文题目（误）
废话写在前面一切都要从一只蝙蝠说起。。正文“你们的作文标题，最好好好学习《renmin日报》的评论，很经典的”（语用：请给三个“好”字注音雾）考虑到评论比较多，就写了一个扒评论标题的东西，然后jieba分词、判断词性，对所得的标题模式去重计数之后按频率降序排序。当然结果不是特别理想，毕竟标题这个东西不太适合分词，太简洁了，就图一乐呵期间尝试了thulac和pkuseg，后面辣个好像装...
2020-03-16 20:01:35
365
原创 CSP2019养老记
之前发错到别人博客上了qaqDay-INF由于是老年选手就没有停课辣，考完期中然后是成人礼，接着又是noip CSP，于是荣获连着两周双休+不用考语文的特权，十分快乐。其实初赛也挺多变化，但是忘得差不多了就不写了吧Day -1提前两天到竞赛室打准考证，已经变成黑网吧了刚好而且又是运动会前一天，晚上都在排练开幕式的东西。表演不长40s，打球打了有1h。然后又是限定词的唱歌小游戏，总之...
2019-12-15 14:23:58
308
原创 GDSOI2019 退役记
小小的总结一下由于这大概是除了noip2020之外最后一场正式赛了，因此总结放在前面吧搁鸽了很久都没什么想写的欲望，但是总觉得还是得对我漫长但并不出彩的oi生涯有个交代嘛，于是还是写了这样一篇漫长同样不精彩的流水账，权当是练习语文作文凑字数了非要总结的话，大概就是没打出自己的水平吧。看了一下排名貌似很多人都挂了，再加上只有两天于是很多大爷级别的人物都没有进队。。不过对于我没进队这一事实我还...
2019-05-13 22:16:29
886
3
原创 bzoj5384 有趣的字符串题 回文树+树状数组+离线
Description给一个长度为n的字符串，m次询问(l,r)求l到r内本质不同的回文子串数量Solution老年选手复习回文树。。考虑暴力怎么写。我们离线询问按照r排序，每次在回文树上暴力跳fail统计以r为结尾的新增回文串。注意到每一个回文串影响的左端点是一个区间，那么我们用树状数组区间加就可以了。这样做是O(n^2logn)的有一个小结论就是，所有以r为结尾的回文串的长度一定...
2019-04-30 09:14:08
754
原创 loj #3088 「GXOI / GZOI2019」旧词 离线+树链剖分
Descriptionn个节点的树，m次询问(x,y)求∑i=1x(dep[lca(i,y)])k\sum_{i=1}^x{{\left(dep[lca\left(i,y\right)]\right)}^k}i=1∑x(dep[lca(i,y)])k其中k是一个给定的常数Solution观察k=1的时候要怎么做。我们离线按x排序，对于一个节点t把根到t路径上的所有点全部+1。那么y...
2019-04-28 17:18:01
220
原创 loj #3085 「GXOI / GZOI2019」特技飞行 扫描线+树状数组+计算几何
Description太长了自己看。。。Solution强行题套题，真·GDOI模拟首先可以发现A和B操作都不会影响交点的位置，那么C的贡献就是固定的了。这个可以先求出交点然后转换坐标系二维数点，离线拆分扫描线+树状数组就行了。因为有可能是实数所以离散不太好写考虑什么时候能交换就交换。注意到一次相交意味着二者在最后会交换顺序，因此每个交点都做一次A恰好能满足初始相对顺序，且在A>...
2019-04-24 19:49:33
349
原创 AtCoder Regular Contest 098 题解
C - Attentionsb题，我们前缀后缀和一下直接O(N)算贡献就可以了#include <stdio.h>#include <string.h>#include <algorithm>#define rep(i,st,ed) for (int i=st;i<=ed;++i)const int INF=0x3f3f3f3f;con...
2019-04-22 21:58:08
761
原创 AtCoder Regular Contest 097 题解
C K-th Substringk才5，随便做都行。当然也可以SAM求第k大#include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>#include <string>#define rep(i,st,ed) for (int ...
2019-04-22 15:06:16
241
原创 AtCoder Regular Contest 102F Revenge of BBuBBBlesort! 乱搞
Description给一个n排列p[]，若存在一个位置i使得p[i-1]>p[i]>p[i+1]，那么就可以交换p[i-1]和p[i+1]Solution真·感性乱搞+分类讨论首先记a[i]=[p[i]=i]，那么我们可以把p分成若干段01交替出现、首尾皆为0的子串。由交换性质可知这些段之间互不影响，即交换不会跨过这些段考虑一整段[l,r]什么情况会No。如果出现了最...
2019-04-21 21:31:54
673
原创 AtCoder Regular Contest 102 E Stop. Otherwise... 组合数学
Description有n个k面骰子。对于i=2…2k，问存在多少种扔骰子的方案使得最终结果不存在两个骰子之和恰好等于i我们认为所有骰子是一样的n,m≤2000n,m\le2000n,m≤2000Solution首先肯定要枚举这个i我们发现有些数字是可以随便出现的，其余的数j一定对应了一个数i-j表示它们不能同时出现并且可以知道当且仅当i为偶数的时候存在一个(i/2,i/2)的对...
2019-04-21 20:40:28
240
原创 loj#6495「雅礼集训 2018 Day1」树 dp
Description定义生成一棵树的方式：对于节点i从[1,i-1]随机一个父亲。求这棵树的期望高度n≤24n\le24n≤24Solution设f[i,j]表示i个节点高度为j的方案数。注意到2的父亲一定是1，我们可以枚举2为根的子树的情况，然后讨论一下能否成为最大值就行了转移看代码。。Code#include <stdio.h>#include <st...
2019-04-19 10:40:16
642
原创 loj#6030 「雅礼集训 2017 Day1」矩阵 贪心
Description给一个n*n的01矩阵，每次可以用一行替换一列。问最少多少次操作使得整个矩阵全1n<=1000Solution先考虑怎么把一整行刷成1。我们枚举全1的行设为x，若存在第x列为1的行则可以填上第x行的0，否则我们可以多操作一次任意选一个存在1的行使得某行的第x列为1，然后照做就行了Code#include <stdio.h>#include...
2019-04-18 20:15:35
240
原创 jzoj6133 [NOI2019模拟2019.4.18]商店 线段树模拟费用流
DescriptionN,M≤3e6N,M\le3e6N,M≤3e6Solution求dfs序的时候爆栈了QUQ考虑人和商品建点跑费用流，优化一下可能可以跑1e5?观察我们费用流实际上在干什么，就是从一个子树内选出最大的权值然后把它取反。那么我们可以用线段树维护dfs序区间最大值来搞这个东西。由于直接做没法退流因此需要按照dfs序降序贪心考虑到时限只有1s，nlogn要跑3e6，我...
2019-04-18 15:34:37
270
原创 CF961G Partitions 组合数学
Description有n个带权物品，要把它们分成k个集合定义一个分法的权值为每个集合的大小*集合内权值之和问所有分法权值之和Solution一开始没看到要乘上一个集合大小。。以为是sb题讲一个头铁娃的做法显然每个物品对答案贡献的系数都是一样的。考虑枚举一个物品所在集合的大小s，那么有∑s=1ns(n−1s−1){n−sk−1}\sum_{s=1}^{n}{s\binom{n-...
2019-04-17 18:27:14
303
原创 CS Academy Round 75 Permutations NTT
Descriptionq次询问(x,y)，求长度为n的排列p[]，满足p[y]是前y个中最大的，且p[x]*2<p[y]的数量Solution考虑枚举第y位选了啥，那么第x位的范围就出来了，于是答案就是f(y)=∑i=1n⌊i−12⌋(i−2y−2)(y−2)!(n−y)!f(y)=\sum_{i=1}^n{\lfloor\frac{i-1}{2}\rfloor\binom{i-2...
2019-04-17 12:28:48
451
原创 洛谷P4233 射命丸文的笔记 分治NTT+竞赛图
Description给定n对于i从1~n，输出i个点组成竞赛图中，哈密顿回路的平均数量Solution竞赛图存在哈密顿回路的充要条件就是强连通设f(n)f(n)f(n)表示n个点形成强连通竞赛图的方案数，一个简单的容斥就是f(n)=2(n2)−∑i=1n−1(ni)f(i)2(n−i2)f(n)=2^{\binom{n}{2}}-\sum_{i=1}^{n-1}{\binom{n}...
2019-04-16 21:51:30
246
原创 uoj#213 [UNR #1]争夺圣杯 单调栈+差分
Description给一个长度为n的序列，定义一个区间的权值为区间内最大值。记ans[i]表示长度为i的所有区间权值之和膜998244353问ans的异或和n≤1e6n\le1e6n≤1e6Solution考虑求出元素i作为最大值的区间[L[i],R[i]]，记左右区间中较短的为mn，较长的为mx。我们讨论一下对于各个长度的区间这个位置的贡献是啥当x<=mn时，区间至少要包...
2019-04-16 20:45:56
245
原创 CF555E Case of Computer Network 边双连通分量+树上差分
Description有一个n个点m条边的无向图，q个限制形如(x,y)。问能否找到一种给边定向的方式使得满足所有的限制可以从x到达ySolution复习一下图论的一些东西一个边双内的点肯定可以定成内部互达的情况。缩完边双之后就可以得到一个森林，我们用打标记的方式在这个森林上乱搞就可以知道是否存在两个限制它们产生了冲突。Code#include <stdio.h>#...
2019-04-16 15:08:26
270
原创 loj#2562 「SDOI2018」战略游戏 圆方树+虚树
Description给一个无向连通图，多次询问一个点集S，问去掉哪些点后S集合不连通，S中的点显然不能算。n≤2∗105,  ∑∣S∣≤2∗105n\le2*10^5,\; \sum {|S|}\le2*10^5n≤2∗105,∑∣S∣≤2∗105Solution会破坏连通性的点容易发现就是建好圆方树后的圆点我们把S集的虚树搞出来，求一下这个虚树内部有多...
2019-04-16 10:47:11
148
原创 hdu6036 Division Game 容斥+组合数学+NTT
Description有0~k-1共k束花，每一束花中有m种颜色的花，第i种颜色有e[i]朵第x次操作将会从第x%k束花中摘走至少一朵花，当一朵花被摘完游戏结束对于i=0~k-1输出游戏在第i个位置恰好结束的方案数Solution每次至少摘一朵，那么游戏至多进行n=∑i=1mein=\sum_{i=1}^{m}e_in=∑i=1mei轮设f(x)f(x)f(x)表示在某个位置第...
2019-04-15 22:06:01
154
原创 bzoj5217 [Lydsy2017省队十连测] 航海舰队 FFT+bfs
Description有一个矩阵，有的位置有障碍现在有一些关键点，每次这些关键点可以朝同一个方向同时走一步，要求任意关键点不能走到障碍上。问多少个点是可达的n,m≤700n,m\le700n,m≤700Solution30分非常好写，只需要暴力bfs就可以了，字面意义上的暴力60分就是记录左上角，然后二维前缀和一下bfs先把包含关键点的最小矩阵抠出来，关键点移动就可以看成矩阵平移...
2019-04-15 19:09:24
160
原创 bzoj5219 [Lydsy2017省队十连测]最长路径 容斥+dp
Description给定n和p对于i从1到n，求n个点形成的，从1出发最长路恰好为i的竞赛图数量，对p取模n≤2000n\le2000n≤2000Solution由一些小常识可以知道，竞赛图一定存在一条哈密顿路径，且强连通分量缩点之后形成的，一定是一条若干scc形成的链，拓扑序小的scc向后连满边也就是说，1为起点的最长路，一定是从1出发，向后走完所有scc。所以最长路=n-[1...
2019-04-15 15:37:29
217
原创 CF1103B B Game with modulo 交互题 倍增 二分答案
Description交互题有一个未知数a，你可以询问? x y，题目会回答你[(x%a)>=(y%a)]。问能否在60次询问内找到这个aSolution可以发现若? x y回答了"x"，那么可以保证a在区间[x+1,y]内，于是一个比较显然的响法就是我们二分这个区间，但这样是错的考虑f(x)=x%a这个函数的图像，大概长这样我们要找的实际上就是这个函数的第一个零点，而若我...
2019-04-14 21:07:49
267
原创 Codeforces Round #551 (Div. 2) 题解
BG周六超多比赛，为了上分还是只打了cf。。本来想上橙的。。甚至第一次赛前打好了各种模板。。。被hack到心态崩了A很显然我们记r[x]表示时刻x的任意一个bus，跑一个2e5*n的暴力就可以了挂了是因为只跑了1e5，怀疑人生Code#include <stdio.h>#include <string.h>#include <math.h>...
2019-04-14 20:09:03
349
原创 vijos lxhgww的奇思妙想 长链剖分
Description给一棵n个节点的树，m次询问一个节点x的k级祖先。强制在线Solution一个做法是倍增另一个做法是长链剖分。同重链剖分一样，我们定义深度最大叶子所在儿子作为长儿子。一个性质是，节点x的k级祖先所在重链长度不会小于k。正确性的话可以考虑反证一下。也就是说，我们取出k的最高位二进制设为r。我们先让x向上跳r步，r所在的重链长度至少为r。对于每条重链我们维护它向上...
2019-04-13 13:59:29
197
原创 loj#3058 「HNOI2019」白兔之舞 MTT+单位根反演+矩阵快速幂
Description自己看吧Solution考场上只想到了n=1的O(L)做法，死于姿势不足不会单位根反演.jpg正解是真的难写，套一个MTT是最恶心的。。考虑20分怎么做，一个比较naive的dp就是f[i,j]表示走了i步到了第j列的方案数，nL2转移就可以成功签到了考虑n=1的情况怎么做。当w=1时，可以发现走恰好d步的方案就是一个组合数，那么答案实际上就是f(d)=∑i=...
2019-04-11 20:40:13
209
原创 loj#3057 「HNOI2019」校园旅行 dp
Description给一个n个点m条边的无向图，每个点有个权值0或1。q次询问x,y求是否存在一条从x到y的路径使得经过节点的权值连接起来是一个回文串n≤5e3,m≤5e5n\le5e3,m\le5e5n≤5e3,m≤5e5Solution这个是loj加强过的数据。。原题好像是3e3的m2的做法就是按照原图dp，设f[x,y]表示x到y有一条合法路径，枚举x和y的邻边转移就可以做到...
2019-04-11 11:57:18
307
1
原创 AtCoder Regular Contest 068F Solitaire dp
Description有一个双端队列，按照1…n的顺序把n个卡片放进队头或队尾得到一个满的队列然后每次可以从头或从尾取一个数字取n次，这样得到一个长度为n的序列。问1恰好在k这个位置的方案数Solution这题好劲啊可以发现几个小性质。首先队列里的元素一定是先减后增的，并且由于1在k这里，所以前k-1个数字必须是一个或两个单调下降序列，而后面n-k-1个随便从队列两端选。然后我就不会...
2019-04-11 10:47:58
420
原创 AtCoder Regular Contest 068E Snuke Line 离线+树状数组
Description有m+1个站台，n个物品，其中第i个物品在第l[i]到第r[i]个站台都有的买一个人从0开始每次走d步，买下能买的物品，问能买到多少种不同的物品，对于d=1…m输出答案Solution看了半天才弄明白会买到同样的物品只算一件。。一个错误的做法是我们把物品区间加然后枚举d求和。由于有的物品区间长度>d，导致它会被算多次于是做法就很显然了，我们把长度>...
2019-04-11 08:23:31
163
原创 bzoj3328 PYXFIB 矩阵快速幂+单位根反演
Description给定n,k,pn,k,pn,k,p，保证k≡1(modp)k\equiv 1\pmod pk≡1(modp)求∑i=0⌊nk⌋(nki)F(ki)(modp)\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor}{\binom{n}{ki}F(ki)}\pmod {p}i=0∑⌊kn⌋(kin)F(ki)(modp)其中F(i)是斐波那契数...
2019-04-10 20:39:31
168
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人