-符拉迪沃斯托克-

题解

算法(1) 赛后补题(4)

/ 注册

全部文章 / 题解（共26篇）

xor序列

题目要求的式子：两边同时异或得：这个式子就是线性基的检查操作，直接写上即可。附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 40 using namespac...

线性基

2021-08-20

0 535

wyh的商机

很直接的一个想法就是把的作为断点，将整个链切分为两段。那么只有三种情况：在买卖在买卖在买，在卖求就交给了倍增，因为树剖后面还要写数据结构维护，比较麻烦。。。（当然离线也可做）维护四个值：前两个很显然的维护方式，跟着倍增一起跳就好。后面两个维护是和求解方式差不多的思路，也就...

倍增 LCA 分治

2021-08-20

1 410

Journey

题意给你一个有向图，问能否选择一个起点，使得每个点和每条边都走且只走过一次。解法其实就是让你判断这个图是不是一条链。首先链的条件有一条：。这样约束起来就是树和环的组合（可能是一棵树加一个环）。再把入度和出度约束在之间，这样就是。然后通过入度为零的点就是起点，把整条链扫一遍，计算通过的节...

图论欧拉回路哈密顿回路

2021-08-19

0 449

集合问题

首先最大的数字一定小于给定的，否则必须有或者负值存在。显然数对一定是存在于两个集合中的某一个。所以对于每个给的数，若中任意一个出现，就必须配对。这样就变成了并查集，即能配对的数对合并并查集。每个数字用出现的位置来代替，相当于一个没有去重的离散化。这个用什么二分啊，平衡树啊，啊啥的都行，复杂...

并查集

2021-08-19

0 856

Butterfly

对于一个蝴蝶，形状为正方形，只要左上角和右上角的点坐标确定，这个蝴蝶的大小和位置也随之确定。那么只要枚举这两个点的坐标即可。设三个数组：分别表示点往下延伸、从左边延伸、从右边延伸所能到的最远距离，读入的时候顺手预处理即可。然后枚举左上和右上点，那么翅膀宽度就是，并且一定是奇数。而对于每个枚...

动态规划

2021-08-19

0 586

Cow Contest

给你一堆奶牛间的胜负关系，问有多少头奶牛可以确定排位。确定排位的意思就是某一头奶牛和其余n-1头奶牛都有确定的胜负关系。并且胜负关系具有传递性。所以我们设两个数组来记录胜负关系，然后跑一遍，把所有的胜负关系全部推出来，最后扫一遍即可。附代码： #include<iostream>...

2021-01-23

0 463

Beauty of Trees

有一列未知数字，给出一些描述：区间的异或和为。求哪些描述有误。稀有的带权并查集题。表示从到根的异或值。对于一个区间：如果和在一棵树上，那么就是这个区间的异或值，和给出的值比较即可；如果不在一棵树上，那么结论一定正确，所以合并这两棵树，这个区间的权值就是。附代码： #inclu...

2021-01-23

1 721

Professional Manager

有n棵树，要求支持4种操作：把两棵树所在森林合并；把一颗树从森林中分离出来；问某棵树所属森林的大小；问两棵树是否在同一个森林中。如果没有查询树的大小（操作3）那肯定一个并查集解决。加上这个操作3就麻烦了。我们怎么维护一个森林的大小？暴力必不可能。。。每次合并和删除的时候直接改根节点也会出...

2021-01-22

0 497

虚虚实实

并查集判断连通性没得说。一笔画问题，就是欧拉回路，只要判断度为奇数的点的个数是否为0或2即可。附代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring>...

2021-01-22

2 561

任意点

两个点只要x或y坐标相同就可以到达。所以并查集就可以求出来联通块的数量。答案就是附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 110 using names...

2021-01-21

0 479