2 鶸鶸

尚未进行身份认证

暂无相关简介

等级
TA的排名 2w+

牛客网练习赛 41

A:中文题意,直接说思路:可以知道在n%m==0的时候可以全部翻转完,但当第一次翻转完之后B使坏一次就永远也翻不到,所以只有当n==m的时候是YES其他都是NO代码:#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;scanf("%d",&t);w...

2019-03-03 18:21:59

Codeforces Round #542

A:题意:给你n个数,让你找到一个数d使得这n个数除2得到的正整数大于等于n/2向下取整,让你输出这个d。思路:看有几个正数几个负数,如果整数大于n/2就输出1,反正输出-1,如果不够输出0代码:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e4+10;inta[maxn];in...

2019-02-28 21:05:23

gym 101775 J Straight Master (2017ECfinal)

https://codeforces.com/gym/101775/problem/J题意:给你一组目标序列,另外一组序列的初始值都是0,你每次可以将长度为3~5的区间整体加上一个1,现在问你最终能不能得到目标序列。思路:首先一个结论就是对于一个长度大于5的区间我们可以分成任意[3,5]的区间,所以有了这个结论我们就可以把区间分成大于3的序列就好了,具体怎么做?我们对目标数组进行差分,可以...

2018-12-22 21:24:42

洛谷 P3948 数据结构 (差分+暴力)

题意:总结一下就是他有两种操作模式,一种是强制在线,你会有两种操作:A在L,R加上一个数,Q查询他们满足的个数有多少,还有一种是离线的,就是问L,R满足的个数是多少,其中乘上的那个i是总的数组的i而不是查询区间的i,当时以为是查询区间的i所以不会写了。。。之后看了一眼,发现是全局的i,那么就是一道暴力题了。。。思路:对于区间加我们直接差分,而对于在线的查询的话,我们直接暴力,由题目可以...

2018-12-22 20:55:43

洛谷 P1083 借教室 (二分+差分)

题意:https://www.luogu.org/problemnew/show/P1083思路:首先可以看出这是一个比较典型的差分,首先是离线,然后在区间L,R增加几,这些都是差分的特征,那么现在问题就是,怎样差分?我们可以看出天数是具有单调性的,当在第x天不行的时候那么x+1肯定也不行,由此可以看出天数是具有二分的特性的,所以我们可以二分天数。代码:#include...

2018-12-22 20:38:31

HDU - 1556 Color the ball (裸的差分)

题意:思路:其实就是每次在L,R区间加一,然后问你每个区间加了几次,那么我们差分,每次让D[L]++,D[R+1]–,之后就好了。代码#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100000+10;intD[maxn];intmain(){intn;whil...

2018-12-22 20:28:25

牛客练习赛34 C little w and Segment Coverage(差分或者线段树)

题意:思路:首先,我们可以简单的得到,那些重复覆盖的点我们肯定是不能选的,我们要选的肯定是那些只被覆盖过一次的点,那么现在的问题就到了我们如何快速的找到那些只被覆盖过一次的点?思路1:我们根据区间信息建一棵线段树,之后查询他的叶子节点的权值是不是1,复杂度是o(logn)。思路2:根据差分数组,利用差分数组我们可以直接O(n)的知道叶子节点的权值。之后我们要开始枚举这些只...

2018-12-18 21:58:58

HDU 2433 Travel (最短路树 )

题意:给你一个图,n个点,m条边,m条边的边权是1,现在定义一个sum[i],表示的是以i点,到达所有点的最短路,整个图的权值定义,现在按照顺序依次删去每一条边,问你每次图的权值的变化。思路:我们跑一边最短路,把松弛的边记录下来,我们可以看出这样我们会构建出一颗最短路树,为什么,因为这样的话我们的每一个前驱只能有一个后继,这样他就是一颗树,而且删除这些边之后,最短路会改变,那么每次删除的时候,...

2018-11-16 16:57:49

洛谷 P1272 重建道路 (树形dp + 背包)

题意:给你一棵树,问你最少切几条边使得最后的子树有恰好有p个顶点。思路:我们设dp[i][j]表示的是你在i顶点保留j个点的最小切割数量,那么dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]),初始化是dp[u][1]=size[v];代码:#include<bits/stdc++.h>usingnamespac...

2018-11-16 14:44:13

HDU 2196 Computer (树上最远距离)

题意:给你一棵树,之后让你求出这个树上每个点的距离的最大值。思路:首先怎样求一个树上一个点到另外一个点的最远距离?其实就是一个点往父亲方向的最大值+往儿子方向的最大值,可知这些东西肯定都是单向的,因为你要么往儿子方向走你就只能往儿子方向走,不能再回去往父亲方向走,那么我们就可以设:f[u]表示的是你往儿子方向的最大值,g[u]表示的是你往父亲方向的最大值,p[u]表示的是u的父亲,...

2018-11-16 14:31:22

POJ 1655 Balancing Act (树的重心裸题)

题意:给你一个无根树,让你找到树的重心,就是树的重心的裸题,现在说一下树的重心把,树的重心就是以树的重心为根得到一颗有根树,这颗树中,节点最多的那颗子树的节点数量最少。思路:根据定义去写的话,我们先随便以一个点为根,自底向上的求出他的所有子树数量,之后遍历每一个点,找到子树节点值最大的最小的那个数就好了#include<vector>#include<stdio....

2018-11-16 14:11:55

P1352 没有上司的舞会 (树形dp)

题意:给你一颗树,每个节点都有一个权值,如果你选择了他的根节点,你就没有办法选择这个节点的儿子节点,现在问你怎样选择可以使得选的的权值最大。思路:首先dp[i][j]分别表示的是,你在以i为根节点的子树中,选择了根节点dp[i][0],或者选择了根节点dp[i][1],详细情况看代码把代码:#include<bits/stdc++.h>usingnamespa...

2018-11-16 13:42:33

P1122 最大子树和(树形dp)

题意:给你一棵树,每个顶点都有一个权值,现在让你求出这棵树权值最大的子树的值是多少思路: 我们自底向上的求出以每一个点为根节点的最大值,之后比较一下大小就好了。代码:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e6+10;vector<int>V[maxn];intW[m...

2018-11-16 13:33:40

codeforce 767C Garland (树形dp)

题意:给你一棵树,每个节点都有一个权值,之后你可以删除两条边把他变成3颗子树现在使得他的三颗的权值相等。思路:显然他们的点权都是3的倍数才会得到3颗权值相等的树,那么我们就树形dp,自下而上的求出以某个点为根的子树的权值,如果他的权值等于sum/3那么就让这颗子树的权值为0,接着dfs就好了代码:#include<bits/stdc++.h>usingnamesp...

2018-11-15 21:47:15

Codeforces Round #520 (Div. 2) C Banh-mi (思路)

题意:给你一个01串儿,现在你可以取某一位,之后你会得到这一位的权值,之后所有除他之外的值都加上这个数,例如1101,我先取第一个1,那么值就会变成_212,现在给你一个区间,问你取完这一串儿数字之后的最大权值是多少思路:显然我们把所有1都取完,在取0之后会得到更优的解,其实是我们取最大值会比较优。之后我们会发现如果是一个满区间的1的话,那么值就是1+2+4。。。等于2...

2018-11-15 21:41:43

Codeforces Round #520 (Div. 2) B Math(分解质因数思维)

题意:给你一个数字n,现在有两种操作1:把n乘上任意一个数,2:当n是一个完全平方数的时候,把这个数字开平方。现在问你最少经过几次操作可以使得n最少。思路:首先分解质因数,倘若一个数字的质因数出现的次数是2的幂的话,那么我们就可以开平方,怎么得来的?如果是2得幂次那么每次就会少一半,一半,一半,那么我们现在做的就是把n分解质因数,然后找到最大得幂次,之后把所有得所有得质因数变成最大得幂次...

2018-11-15 21:15:42

Educational Codeforces Round 54 (Rated for Div. 2) D Edge Deletion (最短路)

题意:给你一个无向图,之后又n个点m条边,现在让你将整个图删成只剩下k条边,并且保证删除后的边的最短路不变,现在问你剩下的边的编号是多少思路:删除的边要保证最短路不变,那么就可以看出,松弛的边是一定不能删除的,因为删除他之后我们的最短路肯定会改变的,那么我们将松弛的边全部找出来,取完之后我们会发现每一个前驱只可能有一个后继,那么这其实就是一棵树了,之后我们从树的根节点里选出k个点就好了。代...

2018-11-13 22:00:13

牛客练习赛30 E 国政议事 (暴力删边 + 二分图匹配)

题意就是二分图匹配的最大匹配,只不过还有一个条件是:左边部分的点只有一条边连在右边部分的那种,就是删掉这条边之后最大匹配数少了一个的那种。思路其实题意就直接给了,那么我们暴力的去删去每一个边,之后去跑匈牙利,得到的匹配数比原来的少的话,那就说明我们需要输出这条边。(感觉思路不是正解啊。。。也有可能自己写的代码自带常数,T了好几发,改了改常数才过的,看题解有人写网络流,自己不会就算了。。。...

2018-11-04 21:23:33

牛客练习赛30 D 消消乐(二分图的最小点覆盖 + 输出覆盖点集)

题意这道题其实就是二分图的最小点覆盖+输出覆盖点集的模板题,和uva11419一样思路就是X和YX和YX和Y拆点然后跑一个最小点覆盖,如何输出覆盖的点集呢?那么我们在计算出最大匹配后,可以从X集合中未匹配的点开始扩展匈牙利树,在Y中被扩展到的点肯定得选,因为只有选择Y中这些点,X中未匹配的点才能被覆盖,而在X中,我们要选那些在扩展中没有被访问过的点,因为这些点是没有与Y中的那些扩展到的...

2018-11-04 21:10:53

牛客网练习赛30 小K的疑惑 (思维)

题意中文题意,主要是i,j,ki,j,ki,j,k可以重复。思路可以看出,dis(i,j)dis(i,j)dis(i,j)的距离不是0就是1,那么我们要找到其实就是在两堆集合里面,一个集合里面所有的值都是1,另一个集合里面所有的值都是0,之后在1这个集合里面去随意选三个数,在0这个集合里面去随意选3个数就好,那么现在的问题就是说我们如何去构造这两个集合了,正解是我们去求每个点到根节点的距离...

2018-11-04 15:44:17

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!