• 等级
  • 109925 访问
  • 559 原创
  • 4 转发
  • 5744 排名
  • 16 评论
  • 15 获赞

POJ-3764 The xor-longest Path 【思维 + 01字典树】

传送门题意:给定一棵带权树,求树上一条简单路径,经过的边异或值最大.思路:任意一条u->v的路径f(u,v)=f(1,u)^f(1,v),所以我们可以把从1出发到某个点的异或值全部算出来,然后问题就变成了从这些值中选择两个数异或最大,那么就是01字典树的问题了,所以就解决了.还是注意字典树内存问题ACCodeconstintmaxn=1e5+5;...

2018-10-25 19:34:10

CodeForces - 662A Gambling Nim【思维 + 线性基好题】

传送门题意:每张卡片正面和反面都有一个数字,然后现在以一种方式每张卡片选一面放在上面,问放在上面的数字异或为0的概率为多少思路:我们假设S=a[i]^a[i+1]^…^a[n],c[i]=a[i]^b[i],再假设我们选择了k个c[i],所以这次异或的结果可以表示为S^c[i]^…^c[k],说明选到了的k张卡片我们选择b[i]的一面,剩下...

2018-10-09 14:16:06

BZOJ 2957 楼房重建 【线段树经典模型维护区间LIS】

传送门题意:每次会在一个坐标上修建一个新楼房,问每天修建完后能看到多少栋楼房.思路:如果一栋楼房它的斜率大于前面的任何一个那么就能被看到,所以我们要维护一个区间之间的合并问题,其实用分块很好写,但是时线段树的一个经典模型,所以我们就用线段树了.ACCodeconstintmaxn=1e5+5;intn,q;structnode{inttl,...

2018-10-09 09:56:28

BZOJ 4919 大根堆【set启发式合并 维护树上LIS】

传送门题意:对于一颗有点权的树,如果i是j的祖先,那么要满足vi>vj,问最多可以在这棵树上选择多少个点可以满足这个条件.思路:那么这就是树上lis,怎么维护了,每个点依旧像普通数组这样,那么就有合并,要合并某个点和儿子的数字,然后依旧还是g[i]表示lis长度为i时,最小的a[i]可以是多少,那么直接就查lower_bound就行,又要排序,和重值,所以...

2018-10-09 09:47:55

线段树区间排序问题两道经典问题 UESTC 1919 和 CF 558E

CF-558E题意:给定一个字符串,q次操作,每次操作一个区间,0表示让这个区间降序,1表示升序,问最后字符串的样子.思路:区间排序问题,凡是区间排序问题,并且里面涉及到的种类不多大概60左右,都是可以用线段树维护的,并且种类越少越好排,所以我们直接用线段树维护当前这个区间每个种类的数量,这里只有26种,然后对于每次排序,我们首先计算出这个区间的每一种种类数...

2018-10-09 09:37:00

洛谷 P2279 树上k距离覆盖问题【贪心 + 思维】

传送门题意:给定一颗树,若在i点安放了一个消防站,那么在树上距离它不超过2的所有点都可以被照顾到,那么要让整棵树都要照顾到最少需要安放多少个消防站,思路:贪心,就是找最深没被覆盖到的点,并在它的祖父处设一个消防站.考虑到这个点的所有子孙后代都已经被覆盖了,因此这时覆盖祖父能盖到更多额外的点,并保证结果不会更差.我们在输入时只要预处理出深度(边输入边处理)并排序,碰到已覆...

2018-10-06 19:34:35

洛谷 P3398 仓鼠找sugar 【思维 + LCA】

传送门题意:就是给定一棵树,然后有q次询问,每次给出树上的两条路径,问着两条路径是不是有没有公共点思路:通过画一系列的图可知,如果两条路径有公共点,那么一定有一条路径的LCA是在另一条路径上的,那么我们现在如何判断一个点x是不是再一条路径上了?如果点x在路径u->v上,那么一定满足dep[x]>=dep[LCA(u,v)],并且LCA(u,x)==x...

2018-10-05 21:15:38

第十四届华中科技大学程序设计竞赛 部分有趣题的题解(A, C, I, L)

传送门A:题意:就是定义树上的一个三元组(a,b,c)成立的条件是|dis(a,c)-dis(b,c)|%2==n%2;给定一棵树,问树上这样的三元组有多少个.思路:分析可知,我们肯定是把枚举c,然后判断每一个c有多少个a,b,可以填,然后我们发现填这个是和n的奇偶性有关,n为奇,那么一定时奇-偶(或者相反),那么我们要知道的就是对于树上每...

2018-09-25 13:48:49

洛谷P1525 关押罪犯 【思维 + 二分图判定】

传送门题意:给出m对憎恨关系,有一个憎恨值,现在要将这n个人分成两堆人,要求这两堆人中存在的憎恨值最大的最小,问这个值是多少.思路:这种问题首先是二分,然后我们如何check这个答案,我们将所有边的憎恨值大于我们这个答案的新建一幅图,然后我们判断能否避免掉这幅图的每一个边的关系,怎么做了才能避免了?实际上就是有憎恨关系的两个人一定要放在不同的集合中,然后怎么判断不能放在...

2018-09-24 20:34:38

经典的三色小球相邻小球颜色不同,摆成一排的方案数【】

题目描述:有三种颜色的球,每种球的数量分别是a,b,c,问把这三种小球摆成一排,相邻小球颜色不同的方案数是多少?思路:dp,dp[i][j][k][l]表示剩ijk个最后一个是l颜色,那么讨论一下最后的颜色的种类就直接转移就行了.ACCodetypedeflonglongll;lldp[22][22][22][4];voidsolve(){i...

2018-09-20 21:11:45

洛谷P2921 Trick or Treat on the Farm 【思维 + 对图的一些操作】

传送门题意:给出每个编号下一个要到达的编号,问最后每个标号可以到达的编号数量(具体可以看样例)思路:很明显有环的情况需要考虑,所以实际上这是一副链环的有向的非联通图,有自环的情况.所以我们有先把链的情况删掉,然后统计出每个环的大小,然后再次累加到那些链的上面就行了.就按照这个实现即可.具体细节还要自己思考下…ACCodeconstintmaxn=1...

2018-09-11 16:38:54

洛谷 P1330 封锁阳光大学 【思维 + 二分图判定】

传送门题意:可以占领一点,然后和这个点相邻的边都被封锁了,如果在占领的这一点的相邻边的点再次被占领的就会有冲突,问占领所有的边并且没有冲突最少要占领多少个点.思路:很明显,如果我们占领了一个点,相当于我们把这个点丢到一个集合中,相邻的点放到另一个集合中,然后另一个集合中的点的相邻点又可以放在之前的那个集合中了,因为条件是等价的,所以着很明显就是判定二分图的过程,所以...

2018-09-11 16:26:55

2018徐州网络预选赛 J 题 Maze Designer 【思维 + 最大生成树 + LCA】

传送门题意:给定一个n*m的矩阵,除了边界,其他相邻的边都有一个代价,现在我们需要在这个矩形中选择一些边封起来,代价就是开始输入的代价,我们要让封起来的代价和尽量的小,并且封起来后,矩阵中任意两点之间的最短路径是唯一的,现在不告诉你具体是怎样封的(但是这个矩形已经进行了封墙的操作),然后q个询问,每次询问两个点,他们在这个已经处理过的矩形中的最短路径是多少.思路:其...

2018-09-10 12:43:52

【(完全)K分图的判定】

描述:对于一个无向图,如果能划分成若干(k)个集合,使得任意两个同一集合内的点之间没有边相连,任意两个不同集合内的点之间有边相连,则称该图为完全k分图,现在就是对于给定的一个图进行判断k是多少.(n<=1e3)思路:我们对于原图的补图进行并查集维护,如果两个点之间没有边,则他们一定在同一个集合内,因为如果不在同一个集合,但是他们之间已经没有边了,一定不满足先...

2018-09-09 21:43:30

牛客练习赛 25 E题 定向 【桥 + 思维】 无向图定方向变强连通图

传送门题意:给定一个无向图,然后你要给这幅图每条边加上一个方向,使得这个图是有向图强连通思路:关键在于如何判断无解的情况,如果能保证当前的图有解,那么直接dfs一下就可以出答案.仔细想想知道.其实就是判断一下当前这幅图是否有”桥”,联通分量的定义的桥,如果有桥则一定无解,否则就有解,然后dfs一下就可以得到答案了.细节请看代码ACCodeconsti...

2018-08-25 00:03:06

HDU - 4666 Hyperspace 【动态多维度求最大曼哈顿距离】

传送门题意:就是0表示加入一个点,1表示删除一个点,后面跟第几个输入的标号.每次输出当前有的点的最大曼哈顿距离思路:多个点求最大曼哈顿距离怎么求就不说了,主要是要怎么删除,那么我们就用(1<<k)个multiset来存每个状态的每个值,然后每次求每个set的最大值减最小值求一个最优即可.然后删除也直接先find然后再erase即可,注意存下每一个的点值,...

2018-08-23 17:51:11

HDU - 6435 Problem J. CSGO 【k维空间求最远曼哈顿距离】 多校第10场

传送门题意:有n个主武器,和m个副武器,每个武器有一个S,和k个性能x[i]-x[k],(k<=5)然后你要选择一把主武器和副武器,让下面这个式子要尽量的大,问最大是多少?思路:后面那个绝对值是不是很像曼哈顿距离的求解方法,所以我们想到k维空间求最大曼哈顿距离(这个怎么求参考我写的另一篇博客,就在这个专栏中,还有板子),然后前面那个加法怎么搞?我们...

2018-08-23 15:08:14

POJ - 2926 Requirements 【k维最大曼哈顿距离】 模板!!!

传送门题意:就是给定n个5维点,问最大曼哈顿距离思路:我们考虑两维的情况,|x1-x2|+|y1-y2|,那么我们展开他们的绝对值,得到四种情况,我们取两个都取正的情况出来讨论,x1-x2+y1-y2,然后移项得到(x1+y1)-(x2+y2),很明显,对于每种情况我们都可以转化为两个相同的形式相减,然后变动的只是每一个变量前面的...

2018-08-23 14:38:48

HDU 6415 Rikka with Nash Equilibrium 【dp + 思维】 多校

传送门题意:在一个矩阵中,如果某一个数字是该行该列的最大值,则这个数满足纳什均衡。要求构造一个n*m的矩阵,里面填的数字各不相同且范围是【1,n*m】,并且这个矩阵只能有一个纳什均衡,问有多少种构造方案思路:因为这个和最大值有关,所以我们考虑从大到小放.从大到小一个个放数字进去,每放进去一个数字,它的这一行这一列就被占领(这一行这一列就可以放数字了).可以发现每放进去一个数...

2018-08-21 15:41:40

AtCoder ARC061Eすぬけ君の地下鉄旅行 / Snuke's Subway Trip 【拆点最短路 + 思维】 好题!

传送门题意:有一个n个点m条边的无向图,边上有一个编号,表示这条边归编号公司管理,如果相邻的两条边的编号相同,则代价为0.否则代价加1,其实为1,问1到n的最低代价为多少.思路:这道题的思路真的是秒啊!!!很明显我们要解决的问题就是如果让相同公司之间的花费为0,所以我们进行拆点,将uvc,拆成u-uc,uc-vc,vc-v,边权分别是1,0...

2018-08-21 10:49:03

Anxdada

多读书多看报, 少吃零食多睡觉
关注
  • 电子·微电子/学生
  • 中国