2 Mr_Alice

尚未进行身份认证

暂无相关简介

等级
TA的排名 16w+

[Splay区间翻转] Luogu p3391 文艺平衡树

题目链接:https://www.luogu.org/problem/P3391从题解里学到了直接建树,就不需要一个个insert了。假设我们要翻转区间[L,R],可以先把L-1对应的结点转到根root,R+1对应的结点转到根的右节点right,此时right的左子树就是在[L,R]范围内的结点啦。此时把这个子树每个结点的左右儿子都翻一下,整个区间就翻过来了呢。然鹅没有必要全部翻过来,...

2019-10-23 14:39:03

[最小费用最大流模板]MCMF模板

#include<bits/stdc++.h>#define maxn 210#define maxm 80100#define INF 0x3f3f3f3fusing namespace std;struct node{ int to, ne, w, cost;}e[maxm];int head[maxn], cnt;int pre[maxn];//记录增...

2019-10-17 20:20:14

[有源汇最小流]模板 LOJ117

最后几个样例卡死我了。假设原图源汇是s,t,附加源汇是S,T方法1:1.加t->s,流量(0,inf)边,判可行流2.删掉t->s,假设此时改变流量为res,跑t->s的最大流maxflow3.答案是res-maxflow一直wa,然后发现res和可行流的流量是可能不一样的。然并不知道为啥。方法2:1.跑s->t最大流2.加t-&g...

2019-10-17 17:47:12

[有源汇最大流]模板 LOJ 116

首先考虑有源汇可行流,加一条T->S,流量为INF的边,就变成无源汇可行流的做法了,再建个超级源汇SS和TT做无源汇可行流就好。跑完可行流之后,再做S->T的最大流 就是答案。暂时不太知道原理,之后再看看。c++11 52ms 内存764k 长度1.8k#include<bits/stdc++.h>using namespace std;typedef...

2019-10-17 15:28:59

[无源汇可行流] 模板LOJ 115

自个设个源点S,汇点T,每个点 du[i]=入度-出度。du[i]>0时 加边S->i,边权为du[i]du[i]<0时 加边i->T,边权为 -du[i]设sum为所有>0的du[i]的和求S->T的最大流,如果maxflow==sum,则存在可行流,此时每条边流掉的流量+它原本的下界就是实际的流量dfs过程中某个点可能被多次访问,这...

2019-10-17 14:49:32

[最大权闭合子图]太空飞行计划 网络流24题(2/24)

无序依赖。注意最后输出方案时,即要输出最后的最大权闭合子图。最大权闭合子图即最后还与S连通的点。最后与S连通的点d一定不等于0(or-1,看写法了#include<bits/stdc++.h>using namespace std;typedef long long ll;#define INF (1e9)const ll maxn=115,maxm=3000...

2019-10-16 19:47:09

Dinic模板

hhhh赛前自己写了一个版本的模板,也不知道效率咋样,但是亲手写出来的意义不同!嗯!#include<bits/stdc++.h>using namespace std;#define INF (1e18)typedef long long ll;const ll maxn=205,maxm=50205;ll n,m,S,T,sum,cnt;ll l[maxm]...

2019-10-16 16:36:19

[线段树or笛卡尔树+简单KMP]poj4005 or hdu4125 Moles

题意:N只编号1-N的鼹鼠打洞,第i只编号为a[i],编号不重复。打的洞的样子符合以a[i]为值,以下标为插入顺序的二叉搜索树。现在从根出发,存在左子树则先走左子树,否则往右走,每经过一个洞(结点),如果这个洞的值是奇数,就记录1,否则记录0,得到的dfs序列是01串S。注意是dfs序列不是中序遍历得到的序列,每个点最多被经过3次:root->lson...lson->root-&gt...

2019-10-13 20:36:51

[分形]GYM-100443

第i阶的图形由第i-1阶的图形构成,大概过程直接看题目里的图即可。然后从图形左端进去,右端出来,中间左拐得到字符L,右拐得到R。走完之后得到一个字符串。现在给定n和字符串S,问字符串S是不是n阶图形字符串的子串。经观察,所有的i阶图形都是可以被包裹在一个三角形里面,所以复制的时候,两个i-1阶图形这个姿势是不会交叉的(但是可能会有点重合),并且对于俩i-1阶图来说,相当于是从俩方向进入同一...

2019-10-07 20:27:33

[想法]GYM-100519 Interactive Primes Guessing

交互题题意:未知的正整数x0和素数p,满足x0<p<=n,要猜测p是多少。输出一个表示你的猜测,会得到一个返回字符串{"<",">","=","OK"},表示和的关系,OK表示猜对了,结束程序。其中。经观察,只有输出2才能够得到有效信息。当xi比xi-1大的时候,说明没有超出p;否则说明超出p了。自个思考的时候举了个栗子,贴个图。会得到红线这样的关于x0...

2019-10-07 20:12:47

孙子定理/中国剩余定理CRT

同余方程设是整系数多项式,称是关于未知数x的模m的同余方程,简称为模m的同余方程。同余方程组意会一下,就是很多条同余方程嘛2333一次同余方程/线性同余方程就是未知数只有一次的一次同余方程组/线性同余方程组再次意会一下咳咳CRT就是用来求一元一次同余方程组(一元线性同余方程组)的算法,但朴素CRT要求各个模数m1,m2...mn互质先整个例子找找感觉:...

2019-09-11 20:55:49

[超级矩阵快速幂]2019南昌ICPC网络赛 H The Nth Item

https://nanti.jisuanke.com/t/41355题意:求给出的广义斐波那契数列%998244353的第n项,n<=1e18方法一:给一个n,我们可以把它变成x进制,x取比较大的时候位数就会比较小啦(每一位的数字可能比较大了就,比如16进制1位顶2进制4位这个亚子)此处把每一位的数字称为这位的系数吧emmm。比如说只有3位的时候,我们只需要预处理出每一位的权...

2019-09-10 10:03:46

[约瑟夫环]2019南昌ICPC网络赛 E magic card

https://nanti.jisuanke.com/t/41352大概就是约瑟夫环的亚子。比如输入n,M,q询问从上到下第x张牌的数字是啥1肯定是第1个拿走的,特判剩下就是n-1个牌,x就变成第x-1张牌,如果下标从0开始标号,就变成了x-2假设res=n-1个人中按M+1报数下标为x-2个人是在第几轮死,则res+1就是要的答案,加的这个1是最顶端的牌自己赛后才磨出...

2019-09-08 21:03:30

[树形概率dp]2019徐州网络赛J Random Access Iterator

555我锅太大了,读错了A的题意(居然还做出来了)导致在A上花了太多的时间QWQ考虑拆成子问题的话,就是我要求u访问到最深结点的概率,我就先求u的孩子v访问到最深结点的概率。最简单的叶子结点dp[leaf]=1;现在考虑从孩子的情况推出父亲的情况。首先要知道,父亲走哪些孩子可以走到以父亲为根的子树的最深结点。那么求出每个点的最深深度d[u]是多少,如果d[u]==d[v]+1,...

2019-09-07 19:07:16

[计算几何]2018多校 B Pizza Hub

https://codeforces.com/gym/102192/problem/B给一个三角形三个点的坐标,一条宽为w,长度无限的纸带,问把三角形放在纸带上且边界不越界(可以重合)时最小的长,三角形可以旋转。(就是希望希望分配给这个三角形、恰好包含这个三角形的最小的纸带长度。解释起来好别扭呀。分析:因为我着急回去看声入人心以及打游戏,所以字写得有点草率,如果有看的人就凑合看吧咳咳...

2019-09-05 19:03:45

[李超树or想法]2019ICPC南京网络赛 I washing clothes

https://nanti.jisuanke.com/t/41306题意:n个人分别在ti时间来到洗衣房洗衣服,每个人可以选择洗衣机洗和手洗,手洗花费y时间,机洗花费x时间,只有一台洗衣机,所以多个人想用要排队。现在要求对于每一个在[1,y]范围内的x,输出所有人洗完衣服所需要的最小时间。如果有错误欢迎指正,这道题第一种做法是看到这个博客才知道的:https://blog.csdn.n...

2019-09-05 18:11:03

[欧拉函数+推式子+NTT]2019ICPC南京网络赛 C Tsy's number 5

https://nanti.jisuanke.com/t/41300题意:对1e5范围内的n求以上这么个东西%998244353我太难了。这个题太难了。前半部分是题解的内容,我作为一个数论菜鸡琢磨了一琢磨也看懂了,就是不会NTT的我后面看不懂,问过大佬之后写了点解释咳咳。fi表示的是欧拉函数值==i的数的个数然后,对于一个i,绿色的部分是好求的,然后就是求红...

2019-09-04 11:02:40

[234树]2019ICPC银川网络赛 E 2-3-4 tree

234树:有三种结点,分别是2、3、4结点,表示该结点将区间划分为几块。并且某个结点的孩子要么全都有,要么全没有。这种树是这么构成的:当要插入x这个数时,从根开始对结点重复这么个过程:1.如果当前结点是4结点(就是当前结点有3个数x,y,z x<y<z):-当前结点为根,则新建一个结点,包含一个数y,这个结点是新根,并且是一个2结点,左孩子是包含x的结点,右孩子是包含...

2019-09-03 12:17:34

[概率DP逆推求期望]2019ICPC南京网络赛 D robots

题意:给一个n个点的DAG,每天可以从某点走到其相邻点或者选择停留,第i天的花费是i,问从点1到点n的花费期望。逆推,所以建反向边然后按拓扑序做。dp[i]表示第i个点到n的期望天数(就是走几步)ans[i]表示第i个点到n的期望花费dp[u]+1表示在u停留的情况下到n的天数,sum{dp[v]+1}都是不停留的情况下到n的情况,每种情况出现的概率都是1/(outdegree...

2019-09-01 21:24:36

[幂塔函数+欧拉降幂]2019ICPC南京网络赛B super_log

https://www.jisuanke.com/contest/3004?view=challenges要求的东西可以变成b+loga*(logax)>=b,即 loga*(logax)>=0显然取等号最小logax=1是最小的满足 loga*(logax)=0的值,此时x也是最小的所以取logax=1转换一下就变成了要求 x=aaa```,一共b个a幂塔函数:aaa``...

2019-09-01 18:30:10

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。