离ACM还有一定距离

分类

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

/ 注册

全部文章（共51篇）

【每日一题】 Xorto

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

2020-04-19

0 532

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

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

2020-04-18

0 765

【每日一题】黑白树 dfs

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

2020-04-10

0 709

【每日一题】树 (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 536

【每日一题】数码

题解：很容易知道，每个数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 664

【每日一题】Running Median

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

2020-04-08

0 587

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

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

2020-04-03

0 541

【每日一题】Shortest Path

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

2020-04-03

0 523

【每日一题】数学考试

Solution:这是一道不会很难想的贪心题。我们枚举第二个区间的起点，同时维护该起点之前的区间最大值，当作是第一个区间的最大值，然后就可以维护答案的最大值，即ans=max(ans,ma+sum[i+k]-sum[i])。 #include <stdio.h> #include <...

2020-04-02

0 618

【每日一题】滑动窗口 (单调队列)

Solution：经典的单调队列模板题，我们可以用deque来实现。首先，滑动窗口的size不能大于k，得：r-l<=k；其次，当每个数进入队列时，若是求最大值，那么队列里比他小的数就不可能再成为答案，得：while(a[r]<=now && r>=0) r--;分...

2020-04-02

0 730