离ACM还有一定距离

题解

学习笔记(7) 牛客多校2020(1)

/ 注册

全部文章 / 题解（共43篇）

【每日一题】逆序对

题意题意很简单，求长度为n的01串逆序对数量和。( n <= 1e18 ) solution 任意选两个位置，令，这样一定能产生逆序对，这样有种选法。剩下的位置随便放，有种选法，总方案数即为答案。( 注意 1 需要特判 ) #include <bits/stdc++.h>...

2020-04-20

0 502

【每日一题】Treepath

题意：给定一棵n个节点的树，求偶数长度路径的数量。 Solution1: 考虑树的深度对距离的影响，可以发现，深度奇偶性相同的点之间的距离总是偶数。证明：我们先将深度更大的点走到和另一个点深度相同，显然需要偶数步，然后两个点同时移动到最近公共节点，可知所用的步数是相同的，加起来也是偶数。 Cod...

2020-04-19

1 530

【每日一题】 Xorto

Solution：首先，一个区间的异或和可以由前缀异或和得到。即sum[l,r]=sum[r]^sum[l-1];枚举左区间的右端点，再枚举左区间的左端点，开一个桶记录个数，再以该左区间右端点+1为右区间左端点，记录与左区间异或和相等的右区间个数，以此累加即为答案。 #include <bit...

2020-04-19

0 537

【每日一题】Accumulation Degree && 树学

题意给定一棵n个节点的树，边权值视作流量，找到一个源点使得从该点出发到所有叶子节点流量和最大。思路：我们先考虑这样一道题：指定一点使得到树上其他点的深度之和最小。这显然是树的重心的性质：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。我们先假设这棵树...

2020-04-18

0 755

【每日一题】黑白树 dfs

思路：我们可以发现叶子节点是一定要染的，如果从下往上染没染过的点，不一定是最优的，所以对于其他的结点，我们更新最大染色范围，如果该结点的子节点可以染色到它的话，那么他就不需要再染色，否则它就需要被染色，同时选择子节点内范围最大的点染色，更新最大范围。 #include <bits/stdc++...

2020-04-10

0 721

【每日一题】树 (dp)

Solution任意颜色相同的点对，中间的颜色也相同，那么意思就是同一种颜色必须形成联通块。dp[i][j]表示前i个点染了j种颜色的方案数，那么当前状态要么和以前染过颜色一样,即dp[i][j]+=dp[i-1][j];要么不一样，那就是从剩下的k-j+1种里面选，即dp[i][j]+=dp[i-...

2020-04-10

0 540

【每日一题】数码

题解：很容易知道，每个数x的贡献为r/x，而且，许多相邻的数贡献是一样的。比如：r=88,当首位为1时，x的可能取值为 { {1} , { [10,19) } }这两个可行区间。x=1, ans+=88;x=10, ans+=（88/10 = 8）;x=11， ans+=（88/11 = 8）；我们...

2020-04-10

1 665

【每日一题】Running Median

对顶堆，开两个堆，一个是大根堆，一个是小根堆，然后小于中位数的都放在大根堆，大于中位数的都放在小根堆，维护两个堆的size相等或差为1即可，这样多出来的数即为中位数。 #include <bits/stdc++.h> using namespace std; int t,n,num; p...

2020-04-08

0 585

【每日一题】Rinne Loves Edges（最小割）

题目大意：割掉权值和最小的边，使得根节点s与度为1的点都没有连边。 Solution:关于割边问题，我们很容易想到最小割，又有最大流=最小割，可以直接上dinic了。建一个超级源点，连接所有度为1的边（根节点除外），容量为INF，s为汇点，然后跑dinic求出最大流即为答案。网络流度理论时间复杂度一...

2020-04-03

0 540

【每日一题】Shortest Path

题目大意：给出N个点，让我们将其分成n/2对，每对点的贡献值为两点距离，求最小距离和。 Solution:我们可以发现，对于以x为根的子树，若节点个数为奇数，则一定子树中肯定有一个点，要和外边一个点相配对才行，那么对应从父亲到当前节点u这条边就一定会有贡献；若为偶数，则直接在子树中完成配对即可。故d...

2020-04-03

0 528