Dispwnl

Crazy Up

克鲁斯卡尔重构树略解

惊了百度词条还是没有收录先看一道题：给你一个图，每次询问给定一个位置、长度和$k$，问从这个点出发，只能经过不大于这个长度的边，到达的点中点权第$k$大的点权数据是$10w$级别的显然是先构造最小生成树，但是没法根据询问长度进行修改离线做法：如果允许离线呢？可以把询问按长度排序，每次把不大于这个长度的边加入最小生成树，然后对每...

Posted by Dispwnl on August 25, 2018

[CF662C]Binary Table

题目题目大意有一个 n 行 m 列的表格，每个元素都是 0/1 ，每次操作可以选择一行或一列，把 0/1 翻转，即把 0 换为 1 ，把 1 换为 0 。请问经过若干次操作后，表格中最少有多少个 1 。 Example input 3 4 0110 1010 0111 output 2 题解发现$n$非常小，考虑状态压缩用一个小于$2^n$的数来表示行是否翻转，$0$表示...

Posted by Dispwnl on August 23, 2018

[LUOGU3676]小清新数据结构题

题目题目背景本题时限2s，内存限制256M 题目描述在很久很久以前，有一棵n个点的树，每个点有一个点权。现在有q次操作，每次操作是修改一个点的点权或指定一个点，询问以这个点为根时每棵子树点权和的平方和。（题目不是很好懂，没看太懂的可以看看样例解释）输入输出格式输入格式：第一行两个整数n、q。接下来n-1行每行两个整数a和b，表示树中a与b之间有一条边，保证给出的...

Posted by Dispwnl on August 20, 2018

[WC2006]水管局长

题目 Description SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务...

Posted by Dispwnl on August 15, 2018

2-SAT略解

竟然没有$2-SAT$的百度词条 _(:з」∠) $2-SAT$是一种特殊的逻辑判定问题 emmmm先看一道题：众所周知，Aufun有很多的Au不然怎么叫Aufun Aufun每天最大的乐趣就是把这些Au翻过来翻过去现在你已经知道m条关于这些Au的信息，每条信息告诉你标号为$X$ Au正/反的时候标号为$Y$ 的Au不能为正/反 Aufun想问问你是否...

Posted by Dispwnl on August 12, 2018

K-D Tree略解

K-D Tree是种非常鬼畜的数据结构… 跟平衡树一样，$K-D$ $Tree$是一棵二叉树，不同的是，$K-D$ $Tree$的每一层构建左右儿子的指标都不同，于是$K-D$ $Tree$的画风就十分鬼畜QAQ 先看一道简单题： N*N的棋盘，要求支持单点修改和区间求和，内存限制20M 这不是树套树裸题吗暴力数据结构大法好但是$N\le 500000$，树套树最差...

Posted by Dispwnl on July 23, 2018

[ZJOI2008]杀蚂蚁

题目题意翻译注意在(0,0)已经有蚂蚁的时候是不会生成新蚂蚁的还有如果有蚂蚁扛着蛋糕，但是不在某个炮的范围内，炮仍然会打最近的蚂蚁题目描述最近，佳佳迷上了一款好玩的小游戏：antbuster。游戏规则非常简单：在一张地图上，左上角是蚂蚁窝，右下角是蛋糕，蚂蚁会源源不断地从窝里爬出来，试图把蛋糕搬回蚂蚁窝。而你的任务，就是用原始资金以及杀蚂蚁获得的奖金造防御塔，杀掉这些试图跟...

Posted by Dispwnl on July 19, 2018

点分治略解

我给你讲，淀粉质可好吃了，真的点分治，是一种处理树上路径问题的工具，举个例子：给定一棵树和一个整数$k$，求树上等于$k$的路径有多少条做法很简单，枚举不同的两个点，然后$dfs$算出ta们间的距离，统计一下就行了大概是$O(n^3)$的复杂度布星啊$n$大一点就搞不了了那找个根，求出每个点到根的距离，然后枚举两个点，求$lca$，简单加减一下就行了 ...

Posted by Dispwnl on July 15, 2018

[IOI2011]Race

题目题目描述给一棵树，每条边有权。求一条简单路径，权值和等于$K$，且边的数量最小。输入输出格式输入格式：第一行：两个整数$n,k$。第二至$n$行：每行三个整数，表示一条无向边的两端和权值 (注意点的编号从$0$开始)。输出格式：一个整数，表示最小边数量。如果不存在这样的路径，输出$-1$。输入输出样例输入样例#1： 4 3 0 1 1 1 2 2 1 3 ...

Posted by Dispwnl on July 12, 2018

[LNOI2014]LCA

题目题目描述给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出l r z，求$\sum_{l\leq i\leq r}dep[LCA(i,z)]$ 输入输出格式输入格式：第一行2个整数n q。接下来n-1行，分别表示点1到点n-1的...

Posted by Dispwnl on July 10, 2018