gigo_64 sink in my world

原创 latex中数学符号的打法

原创 缺漏知识点（持续添加中）

咳咳，丢上来scarlyw巨佬的补档计划，可以借鉴并膜拜瞻仰https://blog.csdn.net/scar_lyw/article/details/701681351、基础算法1）倍增法2）构造法3）二分&三分2、数学1）欧几里得&扩展欧几里得2）快速幂3）逆元4）中国剩余定理5...

原创 程设作业：魔兽世界终极版

程序设计实践作业：魔兽世界最终版。

原创 【程设作业】魔兽世界三：开战

程设作业记录

原创 程设作业 魔兽世界之一：备战

作业记录。

原创 【大学复健】牛顿迭代

T1:关键词：按位贪心，代码分块实际上是两道题：1.n=100,ab不固定使用n^3dp，令f(i,j)表示前i个数分成j部分，对每一位进行一次可行性dp，从高到低，并且不能违背高位的答案。2.n=2000，a=1没有最低限制，则直接转为最优性问题，讲F（i）设为前i个数分成满足条件的最小块数，只要最后小于等于B即可。代码：...

原创 【大学复健】两种质朴的素数筛法

大学复健的数论基础

原创 【大学复健】常用排序算法的原理与代码

三种常用排序算法的实现

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

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

原创 FFT

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

原创 ISAP

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

原创 csp2019 游记

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

原创 csp模拟 企鹅棋【计数dp】

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

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

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

原创 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...

原创 考前注意事项

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

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

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

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

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

原创 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越深，意味着这两个串的排名越接近。所以我们需要构...

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

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

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

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

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

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

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

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

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

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

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

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

原创 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=...

原创 csp模拟（个鬼）迷雾华光【树分块】【虚树】【树上莫队】【主席树】

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

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

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

原创 csp模拟 药品试验【数学题】

传送门是的，这是个数学题。推导的题。以下证明来自luoyijie聚聚由概率和为1得令d为p的差分数组，即令则,而所以你就可以直接算了。#include<bits/stdc++.h>using namespace std;#define int long longint x,y,z,n,a,b;const ...

原创 卢卡斯定理与扩展卢卡斯定理的复健

其实这两个定理没有任何关系，，卢卡斯定理：前置知识二项式定理递归计算复杂度plogp。证明：令有费马小定理可得两个式子：转换一下得到而直接把二项式展开有所以当左右同取的系数时，有得证。扩展卢卡斯定理：这东西跟卢卡斯定理啥关系也没有，，处理p不为质数的情况。前置知识：中国剩余定理，扩展欧几里得...

原创 【TJOI2018】智力竞赛【二分图】【二分答案】

传送门仔细读读题发现是二分图DAG可重路径。顺带复习二分图的写法。我们在增广的时候，不是让妹子去找男朋友，而是让妹子已经有的男朋友去再找一个女朋友。这样就可以让对方妹子孤单凄冷，然后你就趁虚而入了……喜闻乐见地匹配了。所以我们不需要真的复制一遍点，只需要每次让对方指向自己就行。然后就是点数-最大匹配了。对于这道题而言，两个子任务。判断是否可以覆盖全图。如果...

原创 二分图复健

二分图匹配常用km算法。使用强抢妹子的手段，强行找匹配，以获得最大匹配。最大匹配#include<bits/stdc++.h>#define in read()using namespace std;int in{ int cnt=0,f=1;char ch=0; while(!isdigit(ch)){ ch=getchar();if(ch=='-')f=...

原创 【TJOI2018】碱基序列【kmp，hash，SAM】

传送门这是一道非常好的字符串多算法练习题。你可以用很多算法做这道题。题意：给定一个字符串，再给定k组字符串，每组最多10个。要求按顺序从k组字符串中各选择一个共k个字符串，要求这个大字符串是初始给定字符串的一个子串。求方案数。（只要位置不同或选择不同都算不同方案）天然的无后效性，每组只选一个，天然的状态设置，促使我们设置如下状态。表示我选完了前i组字符串，形成的串在原串以j为末...

原创 【NOIP2015】运输计划【二分答案】【树上差分】

传送门好题。今天洛谷说我大吉，果不其然，不看题解一遍写一遍过。将一条边边权置0，求给定m个路径的最大值最小。这个，，先二分答案再说。观察性质：修改边肯定在最大路径上。更进一步：对于一个答案mid，所有大于这个答案的路径都要被修改。所以修改边一定在这些路径的交上。那每次扫一遍打差分标记，然后dfs就完了。记得预处理两点距离和lca。#include<b...

原创 NOI模拟 长寿花【dp】【组合数学】

传送门题意：有n层，每层a[i]个位置，m个颜色。每个位置可以选择一个颜色。要求相邻颜色不相同，相邻两层颜色集合不完全相同。求方案数。发现a[i]最大5000，直接n方预处理。根据套路设表示第i层用了j个颜色的总方案数。枚举第i位是否启用新颜色得到然后再来考虑很多层。设表示前i层中第i层用了j个颜色的总方案数。如果不管相邻限制，然而相邻不能完全相同。那就直接减去就行...

原创 NOI模拟 七十和十七【递推找规律】

传送门本质还是求按照规则sort好的次数。我们把问题划分。我们发现，如果前i-1位没弄好，那第i位不会动。所以考虑i-1位都弄好了，整第i位。手玩一下发现，如果第i位值为k，需要花费不管阶乘，令表示长度为i的方案数。考虑新加入一个数。不论这个数是多少，总能使前i-1个数选哪些数的方案从(i-1)!变成i!/1=i!。所以多乘了一个i。然后第i个数就是2^{i-1}*(i...

原创 NOI模拟 黑白划分【线段树】【容斥】

传送门题目本质是求非同色正方形且边长为2的幂的个数。这个2的幂条件简直给线段树量身定做。cnt(i)即边长为2^i的同色正方形个数。纯色总数减去同色个数*4（因为有4的贡献被去掉了）就是异色贡献。最多一百万行列，我们分边长来考虑。对于边长为2^i的正方形，很明显其由一条长为2^i的横边和一条长为2^i的纵边围成，任何两条这样的边可以成为一个这样的正方形。所以我们分横纵分...

原创 csp模拟 我的订书机之恋【树形结构】【哈希】

传送门事实上标题给的是两种做法。正解：一个合法答案只能是最小答案或者由两个答案子区间并集构成。（否则肯定会叉出去）那就有一个天然树形结构，用单调栈维护f_r表示右端点r最近的合法答案位置。令r向f_r连边，l向f_{l-1}连边。（当然，上述连边是反向的）倍增lca的深度-2就是答案，记得特判两个点相同的情况。#include<bits/stdc++.h>...

原创 csp模拟 轻飘飘的时间【杜教筛】【卢卡斯】

传送门杜教筛板子，只要学了并且还会推导就能随便做（除了卡常）。n,m范围1e10，B范围mod以内，mod9990017。其实这个mod如此与众不同是在提示你可以卢卡斯。枚举T=kd发现实际上是组合数和莫比乌斯函数的狄利克雷卷积。令所以目标是F(T)的前缀和。这东西都说了有莫比乌斯函数的卷积，根据套路我们直接卷上一个I。提示：I函数任何时候取值都...

原创 [八省联考2018]劈配【动态加边/删边 网络流】【二分答案】

传送门md神题，，大致题意：n个人，有m个志愿档，有m个老师。每个老师有最大限额学生。每个学生的每个志愿档可以指定0~c个老师。从第一个学生开始，选择合理的，最高志愿。对于第i个人来说，目标仅仅是指1~i个人全都被可能的最高志愿档次录取，跟后面的人无关。原题是这样说的：如果一种方案满足“前n名的录取结果最优”，那么我们可以简称这种方案是最优的。两个子问题。子问题...