A fresh start.

跟舞会那道题差不多,如果父节点没有取那么所有子节点都必须取;如果父节点取了,子节点取或不取皆可。$$\begin{cases} f[i][1]=\sum \min(f[j][0],f[j][1]) \\ f[i][0]=\sum f[j][1] \end{cases}$$需要注意的是题目中已经把子树说明了,这就意味着只能有一个点作为根节点,所以应该连单向边,并且事先找到那个点作为根节点。st...
题解 动态规划-树形DP
提高+/省选-
大水题,题意就跟题目名一样,决策就是对于节点 $x$ 是否取当前搜到的儿子 $y$ ,显然要当前子树和要大于0我们才会取,然后dfs即可。方程式:$$f[x]+=max(f[y],0)$$struct Edge{ int next,to; } edge[32005]; int s[16005],n,m,a,b,c,cnt,head[16005],w[16005],ans; inli...
题解 动态规划-树形DP
普及+/提高
题意要从 $N$ 门课中选出 $M$ 门,有的课有价值和先决条件,求价值总和最大值。其中 $N,M\le 300$ 。题解1.多叉转二叉我们用 $f[x][cnt]$ 表示当前x节点,在以 $x$ 为根的子树中选 $cnt$ 个节点。对于每一个节点,可以有选和不选两个选项,如果不选就把 $cnt$ 全都给兄弟节点,也就是右节点;如果要选就把 $cnt$ 分别分配给 $x$ 的兄弟和以 $x$...
题解 算法-多叉树转二叉树 动态规划-树形DP
提高+/省选-
我在做某题的时候看到有个多叉树转二叉树,就去学了下,看的这篇文章:https://blog.csdn.net/c20190102/article/details/69946551然后就去找了这道题做,最开始想法是建了树以后转成二叉树然后再dfs得到深度,然后发现有点问题,因为链式前向星是逆序存边的,于是就改用临接表,然后t了很多发,不知道有多少组数据啊。去看题解发现转成二叉树以后每个树的深度...
题解 算法-多叉树转二叉树
我一看到wxh大佬题单里一道斜率优化一道cdq就果断跳过,然后终于找到一道可做的了。我一开始没看到相同面积,心想搜索时间复杂度怕是要爆炸,但也没想出其它方法,然后看了题解才发现是相同面积,那直接搜索就完事了。因为面积相同,所以每次切的长宽一定是 $x\div cnt$的倍数(cnt是当前这块能分成几份),所以直接枚举在哪里切即可。#include<bits/stdc++.h> ...
题解 算法-搜索
提高+/省选-
项目地址:https://github.com/Llf0703/pld网页地址:https://pro.llf0703.com/pld/上午徐妈找我说让我找下大佬在bzoj的刷题清单来照着刷,应该有很大帮助。不过我想如果没有一个时间顺序的话也没法向大佬一样有成长的过程,所以下午就现学了py并写了爬虫,然后先爬了wxh大佬的,毕竟比赛第三,友谊第二,______第一具体的使用方法去看READM...
项目
前段时间学生会需要一个内定功能的抽奖机,于是我就写了一个,顺便换了下UI以及将css和js本地化。现在项目的地址 https://pro.llf0703.com/random/具体更新内容:更新UI统一两个版本,使用setting.js进行统一设置增加内定功能增加总人数选项增加是否去重选项更换全新域名及将pages托管到Github
项目
最开始我zz的想法是直接把整个区间二分,但后来才发现只能找到一个。然后看了下题解,因为每个长度为1的区间只可能有一个解,所以直接枚举每一个长度为1的区间来二分即可。只需要注意区间不能重复,所以可以把右端点减一个很小的数即可。我犯的最智障的错误莫过于用快读来读了double。。。而且改了半天今早才想起,感觉白学OI了。#define eps 1e-2 double a,b,c,d,ans[5...
题解 算法-二分/三分
普及/提高-
昨天做了,为了抢夜宵就没写自己做了半天,感觉及其恶心,就去看了题解,发现了一种及其巧妙的写法。这种写法的原理就是按照2的整数幂次将一共 $2^{n}$ 行分成 $n$ 组来操作,操作就是把之前的图形左右各复制一个即可,只是要注意要在前后加上空格。int n,m; string ans[1100]; inline void work(int x) { int mx=x*2; ...
题解 算法-分治
普及/提高-
NOIp才考了(好吧是我把它做成了)分治,再加上我分治也不太熟悉,就先做下分治。虽然是一道普及-,但细节还是廷考验人的,再加上很久没打题了所以搞了很久。思路就是找到原数所能分出的最大的2的整数幂次方,然后将幂次数和剩下的分治处理即可。细节就是2(2(0))应该直接写成2int n; void work(int x) { if (x==0) { printf(...
题解 算法-分治
普及-
花了199在百度云买了个香港主机,把这个新版博客建起来了。原因我在NOIp2018总结里写了,不再赘述。以前那个还能继续访问,但不会更新,后续可能会将域名换至 2018.llf0703.com我还会将以前的一些优质文章搬到这里。一下是一些测试:定义含义重节点以它为根的子树节点个数最多的节点轻节点所有子节点中不是重节点的节点重边父节点和重节点间的连线轻边父节点和轻结点的连线重链多条重边连接起来...
博客
NOIp2018情况$$ 100+40+10+64+15+4=233 $$感觉分数就像个玩笑一样,不过今年NOIp确实给我开了一个玩笑,D1T2人人都会的傻逼题我只有40,D2T2推出了部分规律又把快速幂打爆了(开了bits而且函数名用的小写pow),D2T1也写爆了。我个人感觉D1T2的爆炸是主要原因,导致D2整个心态都是崩的 (心态崩了我要妹子)。而D1T2我觉得可能有点心态的原因,考前...
总结 比赛-NOIp
昨天Firefox发布了63.0正式版以及64.0beta版。我在看文章Firefox 63.0 正式版用户特性介绍时偶然发现一张图片中的Firefox看起来很像chrome。然后在询问作者之后我发现了这个神奇的东西。我个人又挺喜欢圆角的Material Design,于是就配置了一下,效果还不错。项目地址muckSponge/MaterialFox使用方法将项目clone到任意一个文件夹进...
软件 其它-Firefox
只是发个板子。虽说似乎NOIp近几年一般都是取膜而不是高精了,但我还是担心会考,所以就复习了一下。定义用struct储存整个数和位数。整个数全部倒序方便计算。struct bigint{ int s[5005],len; bigint(){memset(s,0,sizeof(s));len=0;} };加法inline bigint add(bigint x,bigint y...
笔记 算法-高精度
晚上做了洛谷TG试炼场的DP lv1 模块,还是大致总结一下。洛谷P1005 矩阵取数游戏区间DP。对于每行,我们可以单独处理。用 $ f[l][r] $ 表示已经取了 $ l..r $ 这个区间后的得分最大值。然后记忆化搜索即可。$ $ 肯定是爆long long了,按理来说应该要写高精的,但是我发现这玩意写高精如果没有运算符重载版的是真的恶心,然后__int128水过去了。#includ...
题解 动态规划
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划40 动态规划-区间DP8 动态规划-单调队列优化DP4 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP12 动态规划-状压DP12 动态规划-线性DP9 动态规划-背包DP2 图论4 图论-LCA2 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路15 图论-树上差分1 图论-桥1 图论-缩点4 图论-负环3 字符串2 字符串-kmp2 思维题3 数学22 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂3 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵4 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分9 数据结构-线段树1 数据结构-队列1 比赛-Codeforces13 比赛-JX Round1 比赛-NOIp3 算法-二分/三分9 算法-位运算1 算法-倍增2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分3 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索19 算法-模拟3 算法-状态压缩3 算法-贪心4 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2