凡尔赛卷卷

分类

做题笔记(85) 学习笔记(16)

/ 注册

全部文章（共101篇）

洛谷多校补题图

T123577 Mana Eel’s Graph 题目链接题目大意给出一个无向图，每个点有两个点权a，b。如果这个图中的一个子图是一个完全图（每个点都跟这个子图里其他的点有边）。一个图的A值等于这个图里的所有点的点权a乘起来，一个图的B值等于这个图里的所有点的点权b乘起来，令s1是这...

2020-09-15

0 495

线性基

线性基线性基是什么？是一个数的集合。原数组中的每个数都可以由这个集合里的树异或得到。也就是原数组的压缩。学习参考：大佬博客 b站视频性质 1、原数组里的数可以由线性基里的数异或得到。所以原数组里的一些数的异或也可以由线性基里的一些数异或得到。 2、线性基里的任意数异或起来都不可能...

2020-09-15

0 454

偏序问题 cdq分治

偏序问题 b站学习链接偏序问题是什么？比如要找比当前数小的个数，如果有两个值呢? 要求ai <= aj && bi <= bj 的i的个数三个呢？ ai <= aj && bi <= bj && ci <= cj...

2020-09-15

0 534

二分 k-th number

K-th Number 题目链接题目大意给一个数组a包含n（1e5）个数，给出 k，m。构造数组b：在a的所有大于等于k的区间中选出第k大的数加到b里面。问b数组中第m大的数。题解我好菜。。想不到二分，感觉最近脑子不动了，很fan 二分答案，然后怎么check？ b里的数肯定...

2020-09-15

0 408

牛客边的染色

边的染色边的染色题目大意给一个无向图，边权是0或1，其中一些边上的边权没有给出，要给那些没有边权的边赋值（0或1）使得图上的环中的边权异或下来为0，问有多少种方法. 题解我想不出来，，我太菜了，害把边上的边权变成点权，使得这条边端点的点权异或值等于边权，因为这样的话环上的边就可...

2020-09-15

0 433

杀树牛客树形dp

杀树题目链接题目大意给一棵树n个节点，如果树上不存在一个链长大于等于m的链，那么这棵树就死了，去掉一个结点的代价是ai，删除节点后节点的边也就没了，问把这颗树杀死的代价最少是多少？（可以把这个数砍成多个树） n和m都是5000的范围题解树形dp dp[i][j]表示i为根节点的时候，向下...

2020-09-15

0 412

lis on tree atcoder 补题

lis on tree 题目链接题目大意给一棵树，每个点都有点权求根节点（1号）到每个点的路径上的最大递增子序列题解怎么求最大递增子序列？（没有必须要包含当前这个点）要么是父节点的答案，要么是前面点权比它小的点的ans最大值+1. 怎么求前面比它小的点的ans的最大值？用一个...

2020-09-15

0 507

青蛙过河牛客

青蛙过河题目链接题目大意规定：青蛙只能站在比他大一号的青蛙的身上，荷叶上只能站一个青蛙，石墩上可以最底下站一个青蛙然后按照规定往他身上站。初始时，青蛙在河的岸边也是按规定摞起来的（1~n，最底下是n）并且要跳到岸对面的时候也要按规定摞起来。河上有n个石墩，m个荷叶，问最多可以让多...

2020-09-15

0 496

珂朵莉树

珂朵莉树（老司机树）别人的博客。。看别人博客学的，链接在上面。算法比较暴力，应该都看得懂主要用set实现一般什么时候用？推平一段区间（把区间里的数变为一个数）数据随机（数据水）哈哈哈哈哈哈哈具体实现存的东西 mutable ：可变的， set中的东西只能读不能改。但是加...

2020-09-15

0 517

湖南多校补题状压dp

C - Greetings! 题目链接题目大意给n种信，每种信wi,hi,pi 分别代表长、宽、数量。让选择k种信封来装这些信，每个信封里装一个。如果把w,h的信装到了x,y的信封里，那么造成的浪费为x * y - w * h; 问装完这些最小造成多少浪费 n，k <= 15 ...

2020-09-15

0 467