998244353

题解

Atcoder(3) C/C++(21) Codeforces(6) study(2) 动态规划(2) 图论(1) 基础知识(30) 字符串(2) 思维(15) 技巧(1) 搜索(1) 搜索基础(1) 数论(5) 未归档(14) 简单题解(1) 线段树(8) 贪心(1)

/ 注册

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

题解 | 牛客练习赛99 A-D

A. 越狱题意：给定一个长度为nnn的序列aaa，找到一个最小的正整数xxx，使得min(∑i=1n[ai>x],∑i=1n[ai<x])min(\sum\limits_{i=1}^n[a_i>x],\sum\limits_{i=1}^n[a_i<x])min(i=1∑n...

2022-05-28

5 420

牛客ioi周赛22普及组题解

A.战争尾声题意：给定个点，第个点坐标为，现在让你在大陆上求出一个整数坐标的点，使得这个点到给定的个点的距离都相等，如果找不到则输出，相等指的是到给定个点的个距离中，任意两个差值的绝对值都小于数据范围：大陆是指对于任何一个点，都有的一片区域。题解：暴力枚举大陆上的所有点，看这个点是否满足到给定...

2021-01-22

3 636

牛客ioi周赛20——普及组

完全数题意：判断一个数的不包括其本身的约数和与其本身的大小关系。数据范围：题解：枚举到暴力求解即可。代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n; int main() {...

2020-11-29

0 598

Xor-MST

题意：给定个点，每个点的权值为，点和点之间的边的边权为。求由这个点构成的完全图的最小生成树的权值。数据范围：题解：考虑分治法求解最小生成树的思想。那么可以将最小生成树的权值按照每一个二进制位进行分组，然后组内求解，再枚举比较两个组之间的数可以构成的最小权值即可，这里可以用树进行操作降低复杂度至...

2020-11-04

0 748

最大异或和

题意：给定一个非负整数序列，初始长度为。有个操作，有以下两种操作类型：：添加操作，表示在序列末尾添加一个数，序列的长度。：询问操作，你需要找到一个位置，满足，使得：最大，输出最大是多少。数据范围：题解：可持久化模板题。记前缀异或和为：由于异或的性质，类似主席树的建树，对每个前缀建立一棵树。...

2020-10-30

1 1056

Perfect Security

题意：给定两个长度为的序列和，改变中的元素顺序使得序列的字典序最小。数据范围：，题解：将序列插入到树中，然后依次查询与异或后最小的的值，记得用完后要将这个给删除，即减。代码： #include<bits/stdc++.h> using namespace std; const ...

2020-10-29

1 555

Vitya and Strange Lesson

题意：给定长度为的序列，次操作，每次对序列的所有数都异或上一个数，问每次异或后，没有出现在序列中的最小自然数的值。数据范围：考虑本问题时，当序列异或上得到序列时，初始状态中不存在于序列中的所有数一起组成的序列异或上得到序列时，和一定也是无交集的。题解1：所以问题转化为将所有不存在于序列中的自然数...

2020-10-29

1 572

奶牛异或

题意：给定长度为的序列，求出连续的子序列中异或值的最大值以及子序列的首尾位置，如果有多个子序列最大值相同，则考虑最短的子序列，如果最短的仍有多个，则继续考虑末尾位置小的。数据范围：题解：异或子序列的经典解决方案就是结合异或的特性，的异或值为。当前枚举到第个前缀时，可以在树中找到与当前前缀异或得到...

2020-10-28

2 743

01trie树

题意：给定个数字，任意取其中两个数字使得异或值最大。数据范围：题解：树的模板题。但是可以思想来考虑，表示前个数中选择两个数取得的最大值，但是状态转移方程没法构造。异或则考虑到位运算，对于每一个数，从高位开始考虑，优先取与当前数的二进制位不同的数，最后得到可以与当前数异或得到的值最大的数，最后输...

2020-10-27

1 686

起床困难综合征

题意: 给定个操作和数，问当初值在时，按照个操作的顺序操作后可以获得的最大值。数据范围：，操作只有或运算，与运算和异或运算三种。题解：位运算每位独立，故可以单独考虑每位。由于二进制每位只有两种取值，故可以考虑每位初值为0和1的情况。那么对应的十进制初值只需要用两个数：和不小于的梅森数即可，对应...

2020-10-23

1 727