-符拉迪沃斯托克-

分类

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

/ 注册

全部文章（共31篇）

无效位置

如果没有修改，这个题就是个线性基板子题对吧。再看加上修改之后怎么整。我们发现，对于任意一种已经确定数字的情况，只要线性基建好了，答案可以搞出来。那么问题就是怎么动态维护线性基。啥？动态维护？？不存在的！我才不告诉你我不会写那玩意因为只有删除操作，所以顺序颠倒就是一个一个加入数字。也就是离...

并查集线性基

2021-08-20

0 425

[CQOI2013]新NIM游戏

先看原来的游戏先手必胜条件：所有值的异或和不为零。带回到本体，也就是两个回合之后，所有值的异或和不为零。那么我们就不能让对方从我方已经取完的情况下还能把情况变成异或和为零。怎么做？等会儿，这不就是一线性基么？只要线性基插满了，或者有个值插不下就行（进不去，怎么想都进不去。。。）先把线性基...

线性基贪心

2021-08-20

0 448

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

2021 BUAA Winter Training 5赛后补题

2021 BUAA Winter Training 5 题意给你一个小写字母的字符串，问这个祖字符串中每个字母是否只出现了一次，且所有出现的字母连续。多组询问。解法，瞎暴力都能过。。。暴力大法好！附代码： #include<iostream> #include<al...

2021-02-23

0 517

2021 BUAA Winter Training 4赛后补题

2021 BUAA Winter Training 4 题意给你一个的棋盘，要求用的矩形覆盖这个棋盘，不能越出边界，不能有重叠，问最多能用多少个矩形。解法沙茶题秒出答案即可。附代码： #include<iostream> #include<algorithm> #...

2021-02-18

0 608

2021 BUAA Winter Training 2赛后补题

2021 BUAA Winter Training 2 题意有黄、蓝三种颜色的颜料各A,B个，要求合成黄、绿、蓝三种颜色各x,y,z个，求一共还需要多少个颜料。黄色消耗两个黄色颜料，蓝色消耗三个蓝色颜料，绿色消耗黄色颜料和蓝色颜料各一个。解法很简单的分开求即可。注意不能一起求，为了这我...

2021-01-30

0 512