Mr_Alice的博客

原创 磁盘清理记录

du -h --max-depth=1 #寻找当前目录，哪个文件夹占用空间最大最后想了想还是把anaconda的无用包删了一下= = conda clean -a参考：https://www.php.cn/linux-434275.html

原创 XAMPP服务器安装&MYSQL使用记录

root用户在指令前加sudo就是root权限。。我实在是太傻了1.先下了xampp的linux版，不会直接下于是先在本子上下好传到服务器上2.# 看别人的教程用了但是并不清楚是干嘛的，好像是权限相关 chmod -R 755 xampp-linux-x64-8.0.3-0-installer.run 3.在有.run这个文件的目录下执行，大概有下图这样的一个过程sudo ./xampp-linux-x64-8.0.3-0-installer.run 4.sudo /opt/la

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

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

原创 [最小费用最大流模板]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];//记录增...

原创 [有源汇最小流]模板 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...

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

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

原创 [无源汇可行流] 模板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过程中某个点可能被多次访问，这...

原创 [最大权闭合子图]太空飞行计划 网络流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...

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

原创 [线段树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...

原创 [分形]GYM-100443

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

原创 [想法]GYM-100519 Interactive Primes Guessing

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

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

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

原创 [超级矩阵快速幂]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南昌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是最顶端的牌自己赛后才磨出...

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

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

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

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

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

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

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

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

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

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

原创 [概率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...

原创 [幂塔函数+欧拉降幂]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``...

原创 [分块or定期重构/三维BIT]2019牛客多校8-D Distance

n*m*h<=1e5的三维空间内有q<=1e5次操作，分两种：1. 给点(x,y,z)打标记2.询问离位置A(x,y,z)最近的标记点到A的最近曼哈顿距离。两种做法：1.分块/定期重构如果所有的询问操作都在打标记后，那么从所有的标记点开始做一次多源bfs求最短路（每次可以走上下左右前后6个方向哦），则询问点的dis就是到离它最近的点的曼哈顿距离。分块的话，就把所...

原创 最近/最远曼哈顿距离

本文都是以二维举例的，实际上变成更多维也是差不多的情况啦，只是每个点的状态多了一些而已。最远曼哈顿距离：假设有两个点A(xi,yi),B(xj,yj)则两点之间的曼哈顿距离为 |xi-xj|+|yi-yj|,根据两个点之间的位置关系，可以分为四种情况：（把相同点的坐标放在一起了）即 (xi+yi)+(-xj-yj), (-xi+yi)+(xj-yj), (xi-yi)+(-xj+y...

原创 [时间分治+线段树]2019牛客多校8-E Explorer

https://ac.nowcoder.com/acm/contest/888/En个点m条双向边，每条边有通过的下界和上界size限制，主角要从1到n，可以在出发前改变一次size，问有多少种size可以从1到达n。边的上下界范围是1,1e9第一次碰到这样的题，很有意思。WA了一次是因为边界最大是n的两倍，我一开始线段树数组大小开成maxn<<2了，应该是（maxn*2）...

原创 [Splay模板题]BZOJ1588

很朴素的找前驱和后继，感觉set完全可以做的咳咳。用来练练splay吧……#include <bits/stdc++.h>#define lchild(x) (T[x].ch[0])#define rchild(x) (T[x].ch[1])#define fa(x) (T[x].fa)using namespace std;typedef long long ll...

原创 [Splay模板题]POJ3481 num巧用

three kind of operation: op1: insert client whose id is x and priority is p to queue op2: get the client with **highest** priority and drop him from the queue op2: get the client with **lowest**...

原创 [点bcc] 点双连通分量缩点建图图示

原创 [容斥+二进制优化]51nod1284 2357的倍数

过了一个寒假啥都不会了，做点一级题找点自信。昨天强行算了所有的情况给A了，虽然也是容斥但是写法总感觉不太优秀。今天翻题解找到一个介绍二进制优化的，顿时惊为天人（这次是这么用的吗……总而言之大概理解了一下自己写了一波代码，已A。#include<bits/stdc++.h>using namespace std;typedef long long ll;ll n;ll ...

原创 [链表模拟]51nod1289大鱼吃小鱼

一开始没有思路自己强行用链表模拟了一下。找到所有向右游的鱼，放进队列，每次处理它们向右走一步后的情况，分为4种：1.右边的鱼向左&更小链表中删掉右边的鱼，当前的鱼重新放回队列2.右边的鱼向左&更大链表中删掉当前的鱼3.右边的鱼向左&大小相同链表中交换两鱼的位置，当前的鱼重新放回队列4.右边的鱼向右走当前的的鱼重新放回队列经粗略分析可知...

原创 [匈牙利-二分图多重匹配]Gym-101873F 三排插问题

https://vjudge.net/contest/259384#status/Alice_and_Bob/F/0/N个电器M个插座，可以把其中一个变成3插。问最多可以使用多少电器。1.最大匹配2.对每个插座分别尝试再找两条增广路，记录最多可以找到的个数（可能是0，1，2）。对每个插座尝试后，将匹配信息恢复成step1结束后的样子。AC代码：#include&l...

原创 [对偶图最短路求最小割]BZOJ1001狼抓兔子

参考 https://blog.csdn.net/MaxMercer/article/details/77976666平面图才有对偶图。平面图是能展开成一张 -> 各边只在顶点处相交的图 <-的图。平面图的对偶图是将这个图G的每一个面做新图G‘的点，在 每一条边两边的面之间连边的图。随便找个图连一下会发现，对偶图中的每一个环对应原图中的一个割。盗了一张论文ppt里...

原创 [生成树计数] BZOJ1002 轮状病毒 生成树计数+JAVA

Step:1.求基尔霍夫矩阵（=度数矩阵-图的邻接矩阵）2.高斯消元求n-1阶主子式的行列式，答案就是生成树个数。n-1阶主子式就是n阶方阵去掉任意一个元素所在的行和列的所有元素，就变成了一个n-1阶的方阵。我把中心的那个点给去掉了。兢兢业业写完之后发现这个要用高精度，默默改用JAVA但是高斯消元的时候用BigDecimal要不就精度不够WA要不就T。后来找了一个用BigInteg...

原创 51 NOD 三级题总结

1013 3的幂的和 等比数列求和公式啦~a1*(1-q^n)/(1-q)1021 石子归并一开始自己想的dp怎么都过不了T T。最后发现是数组初始化越界了（……）做法1: dp[i][j]=区间[i,j]合并的最小花费。状态转移：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);第一层for了i,j的差（区间长度，一层一层更新）。第二层fo...

原创 zjnu2017校赛M会长的正方形

出现正方形顶点都在格点上的情况：设x,y。比如x=0,y=1表示的就是边长为1的正方形，x=0,y=2表示边长为2的正方形，x=1,y=2表示边长为根号5的正方形，x=1,y=3表示的是边长为根号9的正方形。那么特定的x,y可以表示一种正方形。经过观察，x+y是刚好放下这个正方形所要的格子的边长。x*x+y*y是这个正方形的面积。再观察，假设格子大小为n,m(nL=1时，这种正方形

原创 zjnu2017校赛M小智的宝可梦

思路：暴力倒着推。开数组a[]存储0-n-1只小精灵吃到的食物数。从第一只小精灵开始。假设小智喂了它和最后一只小精灵数量为x的食物（x的范围是0-a[0]）,然后a[0]和a[n-1]都减去x表示这是已经喂掉的食物。那么剩下的喂食情况都已经被决定了。第二只小精灵必须和第一只小精灵一起被喂食a[0]-x数量的食物，也就是第一只和最后一只一起吃完之后剩下还要吃的量。 一直这样下去，如果出现

原创 zjnu2017校赛J认亲大会

/*思路： 每个人做为一个顶点，在他们之间建双向边表示关系，最后以1为起点(now==0表示辈分)dfs所有关系， 搜到now>0的就是辈分比1高的新的知识点： 1.神奇的输入方式反思： 1.链式前向星建图都不熟QAQ 2.dfs的复杂度不会分析，这个地方不用考虑所有的情况，因为每个能走到的点结果唯一，要么一样，要么辈分小，要么辈分大*/

原创 zjnu校赛F 会长大人上课

比赛的时候卡E卡太久，心态崩了，太紧张的结果就是这题的思路也理不顺，赛后写着感觉还不错的= =+还是代码经验太少了。。。WA了两次，第一次特判会长大人被数到的次数的时候if/else写串了,第二次是判断n#include#include#includeusing namespace std;typedef long long ll;int t;long long n,

原创 zjnu2017校赛 E 会长大人的异世界生活(模拟题)

http://acm.zjnu.edu.cn/xiaosai/contests/1000/problems/1004.html/*1.输入2.特殊处理空串的情况，有分隔符号在开头，中间，结尾（分倒数第二个是不是分隔符号两种情况，注意注释）3.处理其他情况新的知识点：1.关于tring .clear(); .empty(); +=44;√ +=tmp

原创 [dfs] poj1321

2017/12/21一直觉得DFS和BFS应该是最简单的东西，打开发现并没有思路，心态崩了……【思路】每一行只能找到最多一个能放旗子的地方，但是如果能放则有多个可能。dfs层数，开始从第一层开始，找到一个可以放棋子的点就放下，顺便标记这一列的cvis(col vis)为1，表示这列已经有棋子了。然后去dfs它的下一层，结束后再恢复原来的状态。因为这题可以放的棋子数目K不等于N，所以...