2 gigo_64

尚未进行身份认证

我要认证

请以你的名字呼唤我

等级
TA的排名 5w+

【省选模拟】遗迹探索【分类讨论】

传送门(内网)题意;给你一堆字符串,仅包含字符ASD,求出所有拼接方案中子串‘SAD’的最多出现次数。很明显我们只需要考虑串与串相接的部分所带来的贡献最大值。第一次分类:S+AD,SA+D。意思是说,串后缀为S配前缀为AD,后缀为AD配前缀为D。那我们按照串前缀普通,为S,为SA。后缀普通,为D,为SD分类,再排列组合,共九种可能。单独一个字母A提出来单独讨论。因为...

2020-01-18 15:34:47

FFT

应某大巨神·红太阳斯基·FSYo之邀来写FFT的解释。用途FFT,快速傅里叶变换,处理两个多项式乘积。众所周知两个多项式相乘复杂度是的,参照高精度。而FFT可以降至nlogn。前置知识及概念一、多项式的表示方法平常常用的多项式是系数表示法。就是通过将x的幂次方分类,记录系数。形如而众所周知一个n次多项式可以被n个点唯一表示。所以还有一种是点值表示法。...

2019-12-27 20:23:27

ISAP

ISAP优化DINIC,虽然并没有找到卡dinic不卡ISAP的题,但是还是有用。DINIC每次全局分层,ISAP动态维护深度。从终点开始赋值深度,这样起点的深度是最大的。一旦有一条边使用过了,我们就讲v的深度加1,意义是它和u的深度现在是一样的,两点之间的边不能用了。同理,走到下一个点的条件是dep[u]=dep[v]+1.与此同时,加一个cnt记录每个深度的点数。如果一...

2019-12-13 17:05:23

csp2019 游记

我的父亲从小告诫我:除生死,无大事Day0:快乐坐车,快乐皇室,快乐睡觉。Day1:拿了很多面包,进入考场。环境不错,开始考试。第一题看了看很水,写了个95先走了。第二第三题没啥头绪,先回来看第一题。由于我过于sb,写了个高精度,,日然后第二题满脑子都是十个叶子gcd那道题,于是我开始强行dfs,用vector记录父亲的所有匹配点,,然后写完过了三个样例走了。...

2019-11-20 12:37:13

csp模拟 企鹅棋【计数dp】

传送门每个点有向左,向右,都可以,三种跳跃属性。问从起点到终点的,经过每个点一次的方案数。我们要求的就是合法的全排列,满足起点是第一个,终点是最后一个,任何一个可以到下一个的数量。我们考虑最后的这个排列,从1开始,对每个数考虑其应该放在哪里。我们发现,任何时刻,这样放出来的连通块,右端点一定是R或B,左端点一定是L或B。因为我们从1~n添加,所以没有添加的数一定比添加了的...

2019-11-14 18:38:04

csp模拟 路径【复杂度分析】

传送门其实就是个复杂度分析和基础数论。众所周知,gcd变化至少减半,所以最多log次变换。任何一条路径都可以成为以某个叶子结点为根,的一条从上到下的链。而叶子最多10个。所以从每个叶子dfs,暴力维护每个点到根路径上的不同gcd点。然后每次更新即可。复杂度10个nlogn#include<bits/stdc++.h>using namespace std...

2019-11-14 18:35:07

csp模拟 金币【最短路】

传送门大约D1T2的难度。得到lx~rx个宝藏的最大贡献。大可以从起点以及每个宝藏出发跑一个最短路(代价的),然后全排列用数量*T减去最短路dis就行。#include<bits/stdc++.h>using namespace std;#define in read()#define int long longint in{ int cnt=0,f=1;c...

2019-11-14 18:32:07

考前注意事项

亲身经历栏1.坚决不使用windows.h等头文件。会造成和MLE一样的悲剧。2.少用clock等函数。(并不知道能不能用)qwq会挂,造成和第1条一样的悲剧。3.记得算算空间,不要卡满,最多70~80%不然可能会MLE,造成和第2条一样的悲剧。4.调试推荐使用文件调试,实在不习惯用cerr(并不知道能不能用)qwq使用文件调试可以方便读入,且保证文件不出错。如果一...

2019-11-13 10:25:12

csp模拟 字符串问题【计数】【组合数学】

传送门又是一个计数题,,在n个数中间填加号,求所有方案的数字和。下面提供两种解法,题解的和来自FSY的。题解:考虑每个区间对数的贡献,要么没有贡献,要么贡献是10的幂。故我们可以枚举使得这个数的系数为10^i时,区间的个数。发现是个组合数。发现这样枚举实际上是固定了该点所在区间的右端点,也就是说固定了一个加号的位置。设当前点为i,对i的贡献为10^j,则右端点为i+j。...

2019-11-12 18:26:16

csp模拟 骨粉【二分答案】【主席树】

传送门存在离线做法但我不会。因为数据范围可以看出是个二分答案。对于每次mid,验证是O(n)的,复杂度总共n^2logn。我们从简化验证的复杂度入手。因为农作物会自然生长,所以实际上验证的高度是mid+t(询问的t)令v=mid+t;对于每个作物,要骨粉次,我们来简化这个式子。我们可以简单地通过二分计算出前面的和,对于余数,我们用数据结构维护。使用主席树可以...

2019-11-12 18:19:26

csp模拟 命令方块【结论】【排序】

传送门求出一组字符串的排列满足对于任何三元组i<j<k,lcp(s[i],s[j])>lcp(s[i],s[k]),lcp(s[k],s[j])>lcp(s[k],s[i]).正经的证明是后缀数组。但我们可以感性理解这个结论:按字典序排序即可。感性理解:想象一个trie树。很明显,lcp长度是lca的深度。而lca越深,意味着这两个串的排名越接近。所以我们需要构...

2019-11-12 17:17:55

csp模拟 生与死的境界【贪心】【带权并查集】

传送门合并使得x,y变成一个x+2y的数,求最后剩一个数的最大值。每次询问针对一个区间。首先发现,这个数列每合并一次,都会对从第二个数开始的所有数,依次多产生系数的贡献,k依次增加。也就是说,合并两个快,对左边的块没有影响。那么我们从最后开始考虑,如果当前块是正数,则和前面块合并,会增大贡献。反之不会。按照这个方式进行到最后得到的块序列除了第一块可能为正,其它块和都是负数,...

2019-11-11 21:04:40

csp 模拟 八云蓝【计数】【线段树】

传送门其实跟线段树没什么关系。对于这道题,我们发现直接计数复杂度很大。比起对于每个询问,计算有多少个区间被调用,不如对于每个区间,计算有哪些询问调用了它。对于一个询问,我们直接上线段树。然后接下来大力分类讨论。1.不相交不相交还做个鬼,直接跳过。2.相交但不覆盖对于一个相交但不覆盖,不容斥的话,分左右两种。容斥的话,就用总区间数减去不相交数。我选择的不容斥(很难写,...

2019-11-11 20:40:29

csp模拟 栖息于禅寺的妖蝶【组合数学】【打表】

传送门考场上因为打表打错而失去了发现杨辉三角的机会。答案是令a数组为选出来的数从小到大排序。证明:令数组b[i]=a[i]+i;发现b数组均为偶数,且两两不相同。(后面总不能比前面小)所以每个b对应一个选出来的a。发现b数组最大是n+m,那问题就是从n+m中选m个偶数出来。那就是答案了。#include<bits/stdc++.h>using nam...

2019-11-11 20:32:38

NOI模拟 学园祭的旅行【线段树合并】【二进制拆分】

传送门好题,学到了二进制查询的一种思想。首先这个异或最大值我们会想到0/1trie,本来合并0/1trie是可以的,但是发现权值会变,然后有点头秃。换个想法。不妨一开始把所有数到根的前缀和都插进去,然后查询的时候记录一个delta就能获知在trie上对应的位置。再一想,这样的区间查询不如使用线段树。使用启发式合并,我们维护重儿子,每次先搜索重儿子,然后让轻儿子合并进来。...

2019-11-09 17:04:53

NOI模拟 学园祭的乐队【计数】【期望】

传送门每天修一根,如果哪天发现这根是坏的就退出。求期望天数。考场上想到了如果将修改弄成一个序列,退出就是满足i<=pos[i],但却没有想到可以钦定前面的修改顺序来计数,期望就是总贡献除以排列数(n!)。每个1都可能成为退出的地方。对于第k个1,要满足前k-1个1都是i>pos[i],对于第k个1,i<=pos[i],剩下的乱搞就行。所以对于第k个1,这样的排列数...

2019-11-09 16:59:21

NOI模拟 学园祭的游戏【整除分块】【SG函数】

传送门复习博弈论的不错的题,,也是整除分块的不错的题,,首先 明显每堆石子独立。最后将每堆石子的sg异或起来就行。对于每堆石子,内部也是一堆状态的集合。根据题意,我们可以列出这样的式子:首先0~b-1肯定是0,已经输了。然后从b开始数学归纳,,我们发现没增加到下一个b的倍数,sg函数的mex范围就要加一,以至于sg函数值就要增加1。然后手玩找规律数学归纳得出...

2019-11-09 16:52:36

st表求lca

对于st表求lca可以做到O(1)查询。对于一个欧拉序,每个点对应其第一次出现在欧拉序中的位置。然后查询区间dep的最小值,这是st表干的。完了。void dfs(int u,int faa){ dep[u]=dep[faa]+1;fa[u][0]=faa;dfn[u]=++cntdfn; fir[u]=++cntt;st[0][cntt]=u; for(int i=...

2019-11-09 14:42:38

csp模拟(个鬼)迷雾华光【树分块】【虚树】【树上莫队】【主席树】

传送门两种做法,一种是树分块+虚树,一种是树分块+主席树我使用树分块+虚树,感觉好写一点qwq预处理:随机个关键点(当然是保证两两距离在左右),然后把关键点的lca也点成关键点。即分块。求出每个点向上走第一个关键点,每个点子树中(包括自己)第一个关键点,每个关键点到根路径上的颜色信息和(),任意两个关键点路径上的众数和次数()。有性质:如果一个点不是关键点,则其子树中...

2019-11-08 20:11:16

csp模拟 小猫钓鱼【模拟】【队列】

传送门真就是个模拟,没啥要优化的,打细心点就能过,,注意读题。比如说就算只有一个人,也要把这轮游戏走完才能break啊之类的要仔细审题。注意细节。#include<bits/stdc++.h>using namespace std; #define int long long#define in read()int in{ int cnt=0,f=1;cha...

2019-11-08 20:06:52

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。