凡尔赛卷卷

做题笔记

学习笔记(16)

/ 注册

全部文章 / 做题笔记（共85篇）

牛客古老的牛市，遗迹的天梯 dp

古老的牛市，遗迹的天梯题目链接题目大意有n个台阶每个台阶的高度是ai（保证递增），刚开始在第一个台阶上面可以跨到比当前台阶高1的台阶上可以后退一步（如果过当前在第一个台阶上就不能后退）如果后退了k步，可以走到高度小于等于2的k次方的台阶上。问最少多少步走到第n个台阶上，如果不能输...

2020-09-15

0 435

acwing 228 异或思维，线性基

异或题目链接题意给一个带边权的无向联通图（5e4个点）。 x到y的路径距离定义为x点到y点的路径上的边权异或和。问从1到n的最远路径是多少（异或和）。一个边、点可以走无数次。题解。题解很聪明，而我很笨拙 hhhhhh 因为要求1~n的路径上的边权异或和最大。 1、如果有环，如...

2020-09-15

0 543

牛客补题树 dsu on tree

月出皎兮，佼人僚兮。题目链接题意给一棵树，每个点有两个属性a,b 代表这个点有b个a颜色。颜色不一样的点可以匹配（不管有没有连）。 1是根节点。让求每颗子树的最大匹配。题解。性质：在一堆颜色中找个个数的最大值，如果最大值小于等于所有颜色的个数的和，那么所有的都可以匹配即su...

2020-09-15

0 492

牛客补题 dp

[SCOI2005]最大子矩阵题目链接题意给你n * m 的矩阵 n <= 100 m <= 2; 让你从这个矩阵中选k个不相交的子矩阵，问最大的和是多少。题解这题，，一看到我就不知道该怎么下手，想半天想不出来个啥，啥都想不出来，遇到这种多维的dp就不知道怎么下手，很...

2020-09-15

0 484

牛客每日一题失衡天平 dp

失衡天平题目链接题意给一个数组（代表一个东西的重量），每次选一些东西出来分成两堆，两堆的重量的差不能超过m，问最多可以获得的重量是多少。（可以选多次，但一个东西只能选一次）题解。被他可以选多次忽悠了。例如样例给的： 5 4 1 5 61 65 100 第一次选 1 5 第二次...

2020-09-15

0 442

牛客每日一题队伍配置 dp

队伍配置题目链接题意给n个人，每个人有花费和贡献 m个装备，每个装备也有花费和贡献。每个人最多只能够有一件装备。每个装备只能给一个人。最多可以选5个人。选出来的人和装备的花费和不能超过d。求可以选出来的最大的贡献和是多少。总结：三个条件: 选的装备的数量不能多余人的数量。花费...

2020-09-15

0 408

Codeforces 补题 E 贪心

E - DeadLee 题目链接题目大意：给n个物品，m个人要拿物品，每个人喜欢的物品有两个x，y；他会随机拿走他喜欢的一个。你可以给他们安排顺序，每个人都必须吃一次。可不可以保证让他们都有食物吃，有的话问安排完之后的顺序，题解。贪心，如果一个食物需求的个数小于等于现有的个数，...

2020-09-15

0 444

补题 gym 102501 problem K 有向图

Birdwatching 题目链接题目大意给一个有向图，和一个点T，简单点说就是问跟T相连（x->T）的那些点中，有哪些点是到T必须经过与T相连的那条路。题解刚开始的想法：建反边，如果T到那些点的路径中有大于1的就肯定不可以，但是有环这种特殊情况。不知道该怎么判断。题解...

2020-09-15

0 467

cf Education 90 补题 F

F - Network Coverage 题目链接题目大意有一个环，1~n 代表n个城市，n个城市围成一个环（1与n相连）。每个城市有ai家用户要网。现在有n个供网的在每两个城市之间，bi代表这个供网的最多可以给几家用户供网，每个供网的只能给他旁边两个城市的用户供网，问最后能不能让所有的人...

2020-09-15

0 450

牛客城市网络倍增

城市网络题目链接题意给一棵树，有点权，每次从u->v刚开始自带了一个权值val，然后在路上只要遇见权值比他现有的大的就买下来，权值更新为那个点的权值，问能买几个点。 v是u的祖先。1是根节点注意是只要见到比他当前大的就必须买，并不是让找方法买最多的。题解买的肯定是递增的...

2020-09-15

0 487