下次一定中奖

分类

每日一题(3) 题解(5)

/ 注册

全部文章（共8篇）

[dp专题] NC50505 二叉苹果树

原题链接：https://ac.nowcoder.com/acm/problem/50505 题目大意：有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共N个节点，标号1至N，树根编号一定为1。我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果...

2020-08-16

0 645

[dp专题] Cell Phone Network

原题链接：https://ac.nowcoder.com/acm/problem/24953 题目大意：求覆盖一个树所有的点，需要覆盖最小的次数，覆盖一个点需要耗费一次次数，覆盖完以后，那么相邻的点也被覆盖。解题思路：每一个点有三种状态： 1.自己覆盖自己 2.儿子节点覆盖自己 ...

2020-08-16

0 880

[dp专题]NC22598 Rinne Loves Edges

原题链接： https://ac.nowcoder.com/acm/problem/22598 题目大意： Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。她现在拿到了一个个节点条边的无向连通图，每条边有一个边权。现在她想玩一个游戏：选取一个 “重...

2020-08-16

0 535

[dp专题]NC15033 小G有一个大树

原题链接： https://ac.nowcoder.com/acm/problem/15033 题目大意：树的重心模板题。解题思路：树形dp记录每个点下面的节点个数，求出删除一个点时的最大子树大小，比较后得到答案。代码： #include <bits/stdc++.h> usin...

2020-08-16

0 543

【每日一题】滑动窗口

原题链接： https://ac.nowcoder.com/acm/problem/50528 题目大意：给一个长度为的数组，一个长为的滑动窗体从最左端移至最右端，你只能看到窗口中的个数，每次窗体向右移动一位，如下图：你的任务是找出窗体在各个位置时的最大值和最小值。解题思路：爆内存，线段树只过...

单调队列

2020-04-06

0 460

【每日一题】数学考试

原题链接： https://ac.nowcoder.com/acm/problem/15553 题目大意：今天qwb要参加一个数学考试，这套试卷一共有道题，每道题qwb能获得的分数为，qwb并不打算把这些题全做完，他想选总共道题来做，并且期望他能获得的分数尽可能的大，他准备选个不连续的长度为k的区...

前缀数组

2020-04-04

0 626

【每日一题】合并回文子串

原题链接： https://ac.nowcoder.com/acm/problem/13230 题目大意：给定两个字符串，不改变两个字符串字符的顺序进行组合，得到一个新字符串，求新字符串中最长的回文子串的长度。解题思路：建立一个四维dp数组，该数组是用来判断取组成的字符串是否能构成回文子串。在...

字符串 dp

2020-04-03

0 488

【每日一题】tokitsukaze and Soldier

原题链接： https://ac.nowcoder.com/acm/problem/50439 题目大意：有个士兵，每个士兵的战力为，选取若干个士兵使组成战力最大的队伍，且满足队伍中的人数小于等于队伍中士兵的最小值。解题思路：将士兵按由大到小排序放入数组，然后建立一个优先队列存放战力，使低战力...

排序优先队列

2020-04-02

1 500