人丑心更黑 - 个人主页动态 - 牛客网

发布(52) 评论刷题收藏

2021-03-01 14:29

已编辑

浙江师范大学 C++

牛客练习赛77部分题目题解

蒟蒻勉强打了3题，第4题开始不会了。。这里放了前4题的代码和题解。  A 小G的sum 显然对于任意一个数i，最大的约数为i，最小的约数为1.因此答案就是n+(1+2+3...n)=n+(1+n)*n/2注意开long long  代码： #include<bits/stdc++.h> using namespace std; int main() { long long n; cin>>n; long long ans; ans=n+(1+n)*n/2; cout<<ans<<endl; } B 小G的GCD 根据f(x)的定义我们可以知道，f...

0 点赞评论收藏

分享

2021-02-26 09:57

浙江师范大学 C++

每日一题4月17日华华给月月准备礼物二分答案

这题算是水题。。 题目大意：给N根长度不一样的木棍，现在可以对木棍进行剪裁，问经过剪裁以后能否得到K根长度一样的木棍。多出来的可以不用。问最长可以剪裁成多少长度相同的K根木棍。N<=200000 思路：二分长度。然后每次判断当前二分的长度能不能组成K根木棍。 代码： #include<bits/stdc++.h> using namespace std; int n,k,a[200040]; long long sum; bool check(long long x){ int t=0; for(int i=1;i<=n;i++){ t+=a[i]/x; if(t&gt...

0 点赞评论收藏

分享

2021-02-26 08:46

浙江师范大学 C++

4月16日逆序对数学公式题+快速幂

算是个水题。虽然我打表以后直接去了oeis.. 题目大意：给定一个长度为n，问长度为n的01串中有多少个逆序对。这里的逆序对为对于i<j,a[i]=1,a[j]=0n<=1e18 思路：数据范围很大，递推肯定是不行的。那么显然本题是一个公式题，或者需要矩阵优化的递推。暴力打表很简单，可以发现能够得到一个公式的，先把公式贴下：a[i]=i * (i-1) * (2^(i-3)) （i>=3）a[1]=0a[2]=1 这个公式，如果对着打表的结果推的话，应该不好推吧？？我们利用数学知识来解决：枚举任意两个位置，其中左边这个放1，右边位置放0。显然n个位置里，有C(2,n)种方案。...

0 点赞评论收藏

分享

2021-02-25 20:44

浙江师范大学 C++

每日一题4月14日 Treepath 树形dp or 思维

感觉树的题目做多了，每题都会往树形dp想。 题目大意： 给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。 思路：第一反应是使用dfs计算每个点下面的奇数路径和偶数路径的数量。令f[i][0/1]表示从i出发到子树的偶数路径数和奇数路劲数。显然对于相邻的边(u,v)我们有：f[u][0]+=f[v][1]f[u][1]+=f[v][0]+1 //u->v是奇数边这个我们一遍dfs可以解决。 接着我们考虑枚举每一个点x，然后答案是∑f[x][0]但是由于我们前面处理的f[x][0]是从x出发往子树的走的...

0 点赞评论收藏

分享

2021-02-25 15:46

浙江师范大学 C++

每日一题4月14日 Xorto 枚举+桶

给自己跪了，这道题居然没做出来o(╥﹏╥)o 题目大意：给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。n<=1000,数组中的数字<100000 思路：一开始想的是枚举中间点，然后开一个f[i][k]数组表示到i点异或和为k的数量，然后从左算一遍，从右算一遍相乘就好了。无奈空间时间都不可用。 看了题解。。枚举其中一个区间[i,j]，其实显然这个区间的异或和我们可以利用前缀和计算。那么我们只需要知道[1,i-1]中有多少个区间的异或和与当前[i,j]的相同就好了。其实枚举一遍放桶里就好了！！枚举的是以a[i-1]作为结尾的区间的异或结果放入...

0 点赞评论收藏

分享

2021-02-25 10:02

浙江师范大学 C++

每日一题4月13日Accumulation Degree+201400 树学树形dp

原谅我前面一题每日一题没做。数学啊数学，太难了啊。。 来看这里的每日一题，看到题目以为是网络流，直接点开了题解。发现推荐做201400树学。好的，那么先来看树学。链接：https://ac.nowcoder.com/acm/problem/201400题目大意：给一棵树，可以找一个点作为根，然后计算出深度和。问如果选根让深度和最小，求这个最小值。数据范围n<=1e6 思路：这个数据量肯定是考虑线性复杂度了。显然，如果指定一个点作为根，我们是可以在O(n)时间上计算出∑dep[i]。如果在这个基础上枚举根，就要再乘一个n，显然不可接受。那能不能在枚举根的时候，O（1）的计算出答案呢？让我们...

0 点赞评论收藏

分享

2021-02-10 11:18

浙江师范大学 C++

每日一题4月9日 Running Median 堆 Or 优先队列

比较经典的一道题，以前在洛谷上做到过。 题意：（原题是英文）给出n个数字，n为奇数。依次读入这些数字，读入奇数个数的时候，输出当前已输入的数字中的中位数。注意题目有多组数据。 思路：算是套路题吧。我们可以利用两个堆来维护中位数，具体的操作是这样的：维护一个大顶堆一个小顶堆，接着我们每次维护当前的中位数x，保证大顶堆中的数都小于x，小顶堆中的数都大于等于x。每次读入2个数，如果这两个数都比x要大，我们放入比x大的小顶堆中。接着我们把x放入大顶堆，从小顶堆中弹出堆顶元素就是新的中位数；同理，如果这两个数比x要小，我们放入比x小的大顶堆中。接着我们把x放入小顶堆，从大顶堆中弹出堆顶元素作为新的中位数...

0 点赞评论收藏

分享

2021-02-09 15:08

浙江师范大学 C++

每日一题4月8日黑白树树形dp

好久没做题了，之前放假稍微出去玩了一下。家里休息惰性又上来了，还是得抓一下自己！这题其实开了好久了，一直想不出来。后来去看了题解，其实基本的情况都考虑到了，但是不知道怎么解决。 题意：给一颗n个节点的树，以1为根节点。一开始树是白色的，现在每次可以选择一个点进行染黑。每个点上有一个值k[i]。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。 思路：很明显可以想到叶子节点必选。我一开始的思路是这样的，维护一下节点深度dep[x]，那么对于节点x来说，只要其子节点中存在一...

0 点赞评论收藏

分享

2021-02-02 19:44

浙江师范大学 C++

每日一题4月7日树乘法原理+思维

我太弱了。。看了本题的题解，给大佬们跪下了。 题意： 有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。 思路：如果要在树上解决这个问题，实在是太难处理了。参考了题解。首先我们可以想到，相同颜色的肯定是连续一段，不可能出现分开的两段。因此我们可以把问题转化为求x个连续段，换句话说，求x个连通块然后染k种颜色的问题。因此我们枚举分成x个连通块，染k种颜色的话，一共有A(k,x)种情况。至于分x个连通块，其实就是删x-1条边，一共有n-1条边，我们存在C(x-1,n-1)...

0 点赞评论收藏

分享

2021-02-02 09:40

浙江师范大学 C++

每日一题4月6日数码枚举优化、分块

本题对我这种蒟蒻来说还是太难了啊。。。首先想到的其实是分块打表，但是1e9的数据我连暴力都跑不出。 题意： 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。 思路：分块打表是之前听来的，也没写过。于是想着在这题上试试。既然要打表，首先想着写个暴力呗。如果按照题意去暴力的话，那么需要枚举x，然后对每个x再枚举约数，这样复杂度是O（n*sqrt(n)），暴力也跑不动了。那么改成枚举约数i，显然对于[l,r]区间，可以得到r/i-(l-1)/i个数满足条件...

0 点赞评论收藏

分享

2021-01-30 20:39

浙江师范大学 C++

每日一题4月3日 Shortest Path 思维+dfs

算是一题有点思维难度的题。 题意：有一颗n个节点的树，现在要把这棵树分成n/2部分，每部分都由2个节点构成，给出n-1条边的边权。当2个点构成一个部分的时候，假设是从u->v，认为经过的边的边权和为需要的花费。问最少的花费和是多少。 思路：一开始的时候有点没有思绪。但是再纸上画一画可以发现一点特点。我们从叶子节点开始考虑。假设当前节点为u，他有一个儿子为v，并且v为叶子节点。显然我们直接连接u、v作为一部分，花费为w(u,v)假设有两个儿子v1,v2,我们需要连接u,v1，此时v2需要和u的父亲相连了。我们总是以当前节点u作为考虑，可以发现，假设u的一个儿子为v，如果v子树上的节点为偶数...

0 点赞评论收藏

分享

2021-01-30 15:45

浙江师范大学 C++

每日一题4月2日华华查月月的手机字符串枚举

一开始以为是kmp，结果发现是子序列，不要求连续。 题意：给出一个字符串s，接着给m个询问，每次询问一个字符串p,问p是否是s的子序列。len(s)<=10^6,m<=10^6，∑p<=10^6. 思路：一开始想的是，预处理出s中的每个字母依次出现的位置，在询问的时候维护当前已经到达的位置pos，然后找出第一个大于pos的字母p[i]的位置。结果超时了。后来考虑到可能对每个字母查找位置的时候有点浪费时间，于是改成了二分查找，结果还是超。。无奈，看了一下题解。用nxt[i]['a'-'z']表示第i个位置后面第一次出现某个字母的位置。这里我们可以维护一个la[j]数组表示字母j...

0 点赞评论收藏

分享

2021-01-28 19:46

已编辑

浙江师范大学 C++

每日一题4月1日 Rinne Loves Edges 树形dp，dfs

每日一题居然放了一个简单题。 题意：给一个无向图，n个点n-1条边，每条边上有边权，现在给定一个根s，求以s为根的图中，删掉一些边要让所有度为1的点不能连接到s。 思路：根据题意，给出的图就是一颗树。那么就是问删一些边让叶子节点无法连通到根s。我们可以考虑某个点x，假设要让x子树的叶子节点无法连通s，我们要么删x-s这条边，要么删除x子树中的边。那么我们可以dfs，我们维护f[x]为以x为根让叶子节点无法连接到x的最小删边代价。显然，枚举x中的所有相连节点v，可以得到转移方程：f[x]=min(w(x,v),f[v])注意叶子节点的时候只能选删叶子节点边。O(n)可以解决。 代码： #incl...

0 点赞评论收藏

分享

2021-01-28 19:46

已编辑

浙江师范大学 C++

NC15429 区间的连续段倍增

本题一开始想的是用f[i][j]表示从i开始长度为2^j的和，然后每次查询的时候利用倍增去快速找到某一段的最右边。结果超时了，后来想了下，万一卡一个n段的数据，就挂了。而且这样倍增还不如直接O（1）预处理每个点到下一段的距离来得快。 题意: 给你一个长为n的序列a和一个常数k 有m次询问，每次查询一个区间[l,r]内所有数最少分成多少个连续段，使得每段的和都 <= k 如果这一次查询无解，输出"Chtholly" 思路：用f[i][j]表示从i出发走了2^j段的最远的点的下一个点。显然有：f[i][j]=f[f[i][j-1]][j-1]对于f[i][0]来说，可以O(n)预处理或者二分...

0 点赞评论收藏

分享

2021-01-28 19:47

已编辑

浙江师范大学 C++

每日一题3月31日城市网络树上倍增

好几天没有做每日一题了，因为周五有场比赛，然后周末出去浪了。其实是因为这题卡住了。T-T 题意：给一颗有n个点的树，每个点上有一个权值，记录1为根节点。现在有q次询问，每次询问（u,v,c）表示从u走到v，一路上遇到的点权如果比c大就选择购入珠宝，然后更新这个c，换句话说就是购入的时候的点权只能递增，问一共可以购入多少次。 思路：参考了题解。方法是树上倍增。（以前不怎么做这一类题目，因此研究了好久）首先题目的意思要明确，题目保证从u走到v是往根节点走的，因此我们查找的时候方向是单向的。那么我们需要知道的就是从u走到v能够购入多少个大小严格递增的珠宝。 我们利用倍增思想，构造一个f[i][j]表...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务