牛客648711727号

分类

每日一题(16)

/ 注册

全部文章（共16篇）

德玛西亚万岁

Problem: 题目 Solution：状压dp，注意：（1）当前行状态和题中状态冲突（2）当前状态中出现两个相邻的 1 （3）上一行与当前行状态冲突（上下同时出现 1） #include<bits/stdc++.h> #defin...

状压dp

2021-02-04

0 374

数学考试

Problem: 今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,.....

区间前缀和

2021-02-04

0 441

旅游

Problem: Cwbc和XHRlyb生活在s市，这天他们打算一起出去旅游。旅行地图上有n个城市，它们之间通过n-1条道路联通。Cwbc和XHRlyb第一天会在s市住宿，并游览与它距离不超过1的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过1的所有城市。他们不想住在一个已经浏览过的...

树上dp 树上最大独立集问题

2021-02-04

0 541

换个角度思考

Problem: n个数，询问[l,r]区间有几个数小于等于k，输出个数。 Solution：树状数组，离线处理，n个数从小打到排序，m个询问按k从小到大排序，每次查询前都将小于等于k的数插入到该数位置上去，然后查询[l,r]区间有几个数就好了。（1）由于排序了，所以可以保证树状数组中所有的数都是...

树状数组

2021-02-03

0 387

Rinne Loves Edges

Problem: 给你一个由N个点和N-1条无向边组成的连通图(树),每条边有对应的权值,问通过删除一些边后使任何度数为1(叶子)都不能到达S点,删除边的价值和最小是多少? Solution: Problem的括号中就是重要的信息,所以我们只需要以S为根,然后从叶子节点往上计算使当前节点不能到达叶...

树上dp dp

2021-02-03

1 347

Removal

Problem: n 个数,去除任意 m 个数,问最终能形成多少种不同的序列,对答案取模 1e9 + 7 输出 Solution: 设 dp[i][j] = k 表示前k个数,去除 m 个有 k 种 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] (dp[...

2021-02-02

0 349

糖糖别胡说，我真的不是签到题目

Problem: 从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结...

2021-01-31

0 574

K-th Number

Problem: a 数组中大于等于 k 个元素的区间中取出第 k 大放入到 b 数组中,最后求 b 数组的第 m 大 Solution: 二分答案ans(b 数组中的第 m 大),然后用ans去检验a数组中是否存在大于等于 m 个区间满足第 k 大大于等于ans,存在则表示ans还可以更大一点,...

2021-01-25

0 407

tokitsukaze and Soldier

Problem: 在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)tokitsu...

2021-01-23

0 349

Treepath

Problem: 给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。 Solution: 解法一: 路径为偶数,也就是经过偶数跳边,由于是一棵树,所以统计从根出发经过偶数条边的点的个数和奇数条边的个数(也就是深度...

2021-01-23

0 491