3 pubgoso

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 3w+

洛谷P2664 树上游戏

题目链接思路:直接做好像有点困难… 那考虑点分治。我们把路径分成经过分治重心的和不经过分治重心的。那么,我们在递归处理某个重心的时候,就可以算出所有点的在此分治重心下的答案。具体实现:考虑x色是根到当前y位置第一次出现的x色,那么这个x就能提供sz_y(当前分治重心下以y为根的子树大小)的贡献给其他跨过分治重心的点。我们用数组tmp来记录某个颜色的总贡献。所有颜色的总贡献用res表示。我们在计算某个点的答案时,要去掉根到当前点的颜色所产生的贡献。这在dfs过程中可以统计出来,需要注意的是算贡献的过程

2020-08-28 13:48:21

牛客练习赛67 F.牛妹的苹果树

题目链接思路:考虑st表的思想。设st[i][j]st[i][j]st[i][j]表示[i,i+2j][i,i+2^j][i,i+2j]区间的点 构成的的树的直径的两个端点。转移就是从4个点选两个。就可以预处理出st数组。询问就是合并两个st的元素。算是一类树上问题的技巧吧。学习到了。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef lo

2020-08-15 15:30:31

2020牛客暑期多校训练营(第五场)H.Interval

题目链接思路:固定一个右端点,对于不同左端点的区间 与值,最多只有log个不同的值。那我们枚举右端点,算出所有这样的第一次出现不同值的左端点,然后在主席树上更新一下贡献。注意去重。可以搞一个map来辅助实现上述的操作。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5 + 1

2020-08-13 11:09:59

hdu6851 Heart

题目链接前置知识最暴力的做法就是拿每个danmaku去做一次卷积。但要求i&j=0i \& j=0i&j=0,那么二进制最高位相同的一类必然不会相互影响,那么将所有danmaku分成21类来做21次卷积就能预处理出所有情况,然后O(1)O(1)O(1)回答。直接拿了std的模板用…#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace st

2020-08-12 15:27:06

2020牛客暑期多校训练营(第十场)C.Decrement on the Tree

题目链接对于一个节点而言,我们考虑这个点会被额外操作几次,显然这个点的返祖边操作的次数都可以延申道当前节点来用,我们设当前节点的的儿子边边权的和为sum,返祖边的权值为w。如果儿子的边边权的最大值在被祖先扣过之后还是超过了sum的一半,那么我们就不能两两连路径消,只能消最大的。否则,我们必然能两两连边消。修改操作就是去掉之前的贡献,再加上新的贡献就行。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h&

2020-08-11 01:11:50

2020牛客暑期多校训练营(第十场)J.Identical Trees

题目链接我们从两个树的根开始递归下去,设dp[l][r]dp[l][r]dp[l][r]为T1的l为根的子树,和T2的r为根的子树的最小代价。然后往上合并的时候相当于一个二分图最小匹配。先用树hash判同构,然后用最小费用最大流找到最小代价即可。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long ll;const i

2020-08-11 01:04:12

2020牛客暑期多校训练营(第九场)J.The Escape Plan of Groundhog

思路:枚举上下边界。先找到左右边框都是1的列,存在一个数组b里。因为外边框要全是1,所以我们找到这个上下边界的连续的1的段,对每段都单独计算答案。对每一段[l,r]而言,找到b数组的一个段,使得这些列都在[l,r]内。然后我们枚举右边框,找有多少满足条件的左边框,这显然用一个数组记录一下前缀的矩形内部1,0差值就可以实现了。时间复杂度O(n3)O(n^3)O(n3)#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/s

2020-08-08 17:57:31

hdu6829 Borrow

题目链接思路:如果三者之和不能被3整除,显然无解。设三者平均数为m,,从大到小为x,y,z 。那么最大的数显然要拿x-m出来,因为对于次数来说,顺序没有任何意义。接下来再枚举分到z上的数有多少,设分到z上的为t。那么三者就成了m,y+x-m-t,m+t三者构成等差数列,等价于0,c,2c。我们设fcf_cfc​为0 ,c,2c状态下的期望次数,那么显然f0=0f_0=0f0​=02c要拿c个出来分给其他两个小的,分完之后,得到三个数又等价于一个新的状态,即得转移方程:fx=x+∑i=0x(ix)

2020-08-08 10:08:32

2020牛客暑期多校训练营(第八场)A.All-Star Game

思路:由题可以得到一个结论:fans和player组成的联通快只需要一个player就可以让这个联通快内所有fans都满足条件。那就直接把每个关系当成一个边,按时间建线段树,用可撤销并查集,维护图的连通性即可。对于有单独的fans组成一个联通快的显然无解了。。#pragma GCC optimize(2)#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;typedef long long LL;

2020-08-07 13:43:30

hdu6820 Tree

题目链接思路:设dp[i][0]dp[i][0]dp[i][0]为子树包括自身,组成联通快且每个点的度数都<k的最大可能。设dp[i][1]dp[i][1]dp[i][1]为子树包括自身,组成联通快且至多一个点度数>=k最大可能。那么随便从一个点出发,开始dfs。有一种情况是dp无法解决的,就是有个点选择了k个子树,且被选中的一个子树联通快中存在>=k度数的点的情况。这时候显然就是在上面的情况中多加了一个子树dp[son][0]+weight。。。细节见代码:#pragma

2020-08-05 14:27:25

2020牛客暑期多校训练营(第七场)C.A National Pandemic

题面链接思路:一个很显然的操作是把w−dis(x,y)w-dis(x,y)w−dis(x,y)写成w+depx+depy−2deplca(x,y)w+dep_x+dep_y-2dep_{lca(x,y)}w+depx​+depy​−2deplca(x,y)​前三项都能用一个变量累加出来,那么主要问题就是如何较快的求deplca(x,y)dep_{lca(x,y)}deplca(x,y)​。那我们可以对树进行轻重链剖分处理,对每条链维护两个bit。一个维护个数,一个维护dep的和。每个update操作

2020-08-01 23:59:58

hdu6796 X Number

题目链接把每个数出现次数的数组当成状态来进行数位dp,常规的数位dp是枚举到最后一位或者此状态之前被处理过。此题有个额外不同的地方就是,如果之前枚举的数不全是前导零且小于给定数,那么后面的数就可以随便放,因为我们只关心每个digital出现的次数而并不关心他们的位置,意味着我们可以直接求出此状态的方案。枚举d出现的次数,然后枚举每个digital出现次数进行转移就行。然后把这个状态的答案记录一下。#include <bits/stdc++.h>using namespace std;t

2020-07-29 17:37:09

2020牛客暑期多校训练营(第五场)A.Portal

题目链接思路:dp[i][j][k]dp[i][j][k]dp[i][j][k]表示完成第i个任务,当前在j节点,有一个传送门在k节点的最小花费。显然 ,完成第i个任务后,j在目标节点上是最优的。。。。分以下几种情况分类转移,设当前目标节点为x:1.j->x 。j直接走到x。2.j->k->x 。在j设置传送门,传送到k,从k走到x,此时可以选择关闭j/k的任意一个传送门。3.从j走到y,在y设置传送门,从y走到x4.从j走到y,在y设置传送门,传送到k,从k走到x5.从

2020-07-29 12:08:11

hdu6769 In Search of Gold

题目链接二分答案。然后用dp来check,dp x y表示x节点,子树中用了y个来自a的边的离x节点最远的点的距离的最小值。转移的时候,只合并直径小于mid的情况。#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 2e5 + 10;#define fi first#define se second#define pb push_back#define mp make

2020-07-26 17:03:16

boruvka算法学习笔记

大概就是:初始每个点都是独立的集合,每次merge过程从所有独立集合出发,找到一条权值最小(权值相同则编号)最小的连向其它集合的边,然后合并集合。显然每次都会使得集合数减少一半,所以合并次数是log级别的。例题:luogu3366mst模板题直接模拟算法过程即可。。#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 2e5 + 10;#define fi first#d.

2020-07-26 16:54:16

hdu6774 String Distance

hdu6774因为只能插删,所以最优的肯定是留下最长公共子序列。dp i j 表示到b串的第i个位置,长度为j的子序列,在a串的最小位置。序列自动机预处理一下a串,然后每次询问做一遍m^2的dp即可。#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5 + 10;#define fi first#define se second#define pb push_bac

2020-07-24 21:51:58

单调队列优化dp学习笔记

这类问题一般是朴素的复杂度大的转移很好写。然后转移类似rmq的问题。需要注意的是:在新值与队头元素判断谁更优的时候,需要把两者放在一个参考系下进行比较。就是 把旧值等效放在新值的位置上的值才是旧值的真实值。cf372C题意:给你m个烟花,每个烟花在t_i时刻在x位置被点燃,得到b_i+|a_i-x|的分,初始选择任意位置,每分钟移动一个单位。问最大得分是多少。根据题目可以写出一个暴力的dpfor(int i=2;i<=m;i++){ for(int j=1;j<=n;j++){

2020-07-24 21:40:57

AC自动机学习笔记

ac自动机是基于字典树和fail指针来快速一类解决多串匹配的问题。先用所有模式串建一个字典树。然后用bfs搞出每个节点的fail指针。fail指针是指向 和当前 前缀的后缀有最长匹配的前缀节点。洛谷3808扫文本串的时候,标记一下访问过的字典树上的节点。。#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e6 + 10;#define fi first#define

2020-07-23 00:33:24

hdu6756 Finding a MEX(分块)

题目链接把度数大于等于n\sqrt nn​的点归为超级点对每个超级点x维护一个长度为d_x的数组,每个位置y,当前仅当跟x相连的z中有a_z=y时,y=1,否则为0。修改的时候只修改跟当前点连接的超级点的信息。查询的时候,对不是超级点的询问直接暴力跑,是超级点的就在bit上二分找答案。#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 2e5 + 10;#define fi

2020-07-21 19:46:44

2020牛客暑期多校训练营(第一场)B Infinite Tree虚树

2020牛客暑期多校训练营(第一场)B Infinite Tree转至

2020-07-17 19:00:48

查看更多

勋章 我的勋章
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。