Alan233

分类

未归档(7) 题解(7)

/ 注册

全部文章（共14篇）

【题解】牛客练习赛67

牛客练习赛67题解出题人： T1 牛牛爱字符串 Solution 直接从头到尾扫一遍，抠出每一段连续的数字块。如果这个数字块开头是零，则需要去除前导0，但注意别把数字0给去了。注意一下首和尾的细节，即可通过本题。 Code #include <bits/stdc++.h> usin...

牛客练习赛67

2020-08-14

16 996

【每日一题4.13】Xorto

Description 给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。 Solution 我们假设选定的两个区间，靠左的为左区间，靠右的为右区间。注意到异或的性质：，于是我们只需要左区间异或值等于右区间异或值即可。我们固定右区间的左端点，记为，那么我们要...

2020-04-13

0 733

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

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

每日一题

2020-04-12

6 1213

牛客13611 树

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

每日一题

2020-04-10

2 971

CF513E2 Subarray Cuts

Subarray Cuts 题目链接：CF513E2 Subarray Cuts Description 给定一个长度为的数组，你需要从中按顺序选出个不重复、不相交的子串，定义为第个子串的和，你需要最大化。数据范围 Solution 我们考虑拆开绝对值，对于一段单调递增/递减的子串，结...

2020-04-10

1 863

旗鼓相当的对手

旗鼓相当的对手题目链接：牛客旗鼓相当的对手 Description 给定一个个点的树，每个节点有点权。如果为和的，并且和不等于且树上距离为，那么点的答案就会加上。求所有点的答案。数据范围。 Solution 长链剖分板子。表示子树深度为的节点数表示...

2020-04-10

2 776

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

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

每日一题

2020-04-09

9 2432

【好题推荐】Steps to One

Steps to One 题目链接：CF1139D Steps to One Description 给定一个数列，每次随机选一个到之间的数加到数列的末尾，数列中的所有数的时停止，求期望长度。答案对取模。数据范围。 Solution 考虑概率dp我们定义表示当前所有的数时，还需要加...

2020-04-08

4 907

【好题推荐】Accumulation Degree

https://ac.nowcoder.com/acm/problem/51180 Description 给你一颗有个节点的树，每一条边连接和，流量为，你需要找出一个点作为，并最大化从该点出发到所有叶子节点的流量最大值。多组数据。（PS：题意读不懂的可以结合题目中的图理解，类似网络...

2020-04-08

4 971

【牛客OI周赛15-提高组】T3

T3 Solution 我们先判断答案是否存在，即这几个物品能否凑成，如果不能，答案则为。否则的话，我们易知：不同体积的物品不超过个。我们可以用分治的思想来解决该题。令表示保留到区间的物品，其余的物品已经塞入背包时的状态，我们用一个bitset来维护。那么，考虑如何分治转移。令，则当我们要进行时，就...

2020-04-08

0 696