Alan233

分类

未归档(7) 题解(7)

/ 注册

全部文章（共6篇）

【每日一题 4.13】Accumulation Degree 和树学

换根dp 一般来说，我们做题的树都是默认为根的。但是有些题目需要计算以每个节点为根时的内容。朴素的暴力：以每个点作为暴力dfs下去，复杂度；正确的做法：换根dp，复杂度。执行步骤第一次扫描，先默认，跑一遍；第二次扫描，从开始，每次从到节点时，计算根从转移到 ...

每日一题

2020-04-12

6 1213

牛客13611 树

树题目链接：牛客13611 树 Description 给定一颗有个节点的树，有种颜料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对，满足到的路径上所有点的颜色相同（包括和）。统计方案数，答案对取模。数据范围 Solution 这是一道结论题。如果直接做，显然不好做，...

每日一题

2020-04-10

2 971

【每日一题 4.9】二分图染色（弱化版）

题目链接：二分图染色 Description 给定一个完全二分图，图的左右两边顶点数目相同。每条边我们都要染成红、绿、蓝中的一种。要求满足任意两条红边不共享端点，任意两条蓝边不共享端点。求出所有满足条件的染色方案数，答案对取模。注：表示二分图其中一边的点数目。数据范围 Solution 我们切换思...

每日一题

2020-04-09

9 2431

【每日一题 4.6】数码

题意: 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。题解最先想到的是枚举[L,R]区间内的每一个数,然后求和。考虑如何优化。我们发现只用写出最高...

每日一题

2020-04-08

0 1035

【每日一题 4.3】Shortest Path

Shortest Path 题目链接：Shortest Path Description 给定一颗个节点的树，保证为偶数。你需要将这个节点分成个点对，并最小化这个点对的距离之和。多组数据。数据范围 Solution 这其实是一道CF原题，原题既需要最小化值，也需要最大化值。下面来谈谈最小化值。既然...

每日一题

2020-04-08

0 600

【每日一题 4.9】Running Median

Running Median 题目链接：Running Median Description 给定一个数列，你需要输出前个数中的中位数分别是多少。多组数据。数据范围 Solution 我们先考虑暴力。对于前个数，我们可以用一个桶来记录一下所有数的出现情况，然后取第个数即可。考虑如何优化暴力。我...

每日一题

2020-04-08

3 720