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​[ai​>x],i=1∑n​[ai​<x])最大化。 数据范围： 1≤n≤2×105,1≤ai≤2×1091\leq n\leq 2\times 10^5,1\leq a_i\leq 2\times 10^91≤n≤2×105,1≤ai​≤2×109 对于1≤i<n1\leq i...

A.战争尾声 题意： 给定个点，第个点坐标为，现在让你在大陆上求出一个整数坐标的点，使得这个点到给定的个点的距离都相等，如果找不到则输出，相等指的是到给定个点的个距离中，任意两个差值的绝对值都小于数据范围：大陆是指对于任何一个点，都有的一片区域。 题解：暴力枚举大陆上的所有点，看这个点是否满足到给定个点的距离都相等即可。 代码： #include<bits/stdc++.h> using namespace std; const double eps = 1e-4; const int N = 210; const int M = N * N; struct Node { ...

A.战争尾声 题意： 给定个点，第个点坐标为，现在让你在大陆上求出一个整数坐标的点，使得这个点到给定的个点的距离都相等，如果找不到则输出，相等指的是到给定个点的个距离中，任意两个差值的绝对值都小于数据范围：大陆是指对于任何一个点，都有的一片区域。 题解：暴力枚举大陆上的所有点，看这个点是否满足到给定个点的距离都相等即可。 代码： #include using namespace std; const double eps = 1e-4; const int N = 210; const int M = N * N; struct Node { int x, y; }node[N]; i...

完全数 题意： 判断一个数的不包括其本身的约数和与其本身的大小关系。数据范围： 题解： 枚举到暴力求解即可。代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n; int main() { scanf("%lld", &n); ll res = 0; int last = sqrt(n + 0.5); for(int i = 1; i <= last; ++i) { if(n % i == 0) { ...

题意： 给定个点，每个点的权值为，点和点之间的边的边权为。求由这个点构成的完全图的最小生成树的权值。数据范围： 题解： 考虑分治法求解最小生成树的思想。那么可以将最小生成树的权值按照每一个二进制位进行分组，然后组内求解，再枚举比较两个组之间的数可以构成的最小权值即可，这里可以用树进行操作降低复杂度至。具体做法：从最高位开始分组，先处理组与组之间的合并大小，然后再处理各自组内的生成树权值即可。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 10; ...

题意：给定一个非负整数序列，初始长度为。有个操作，有以下两种操作类型： ：添加操作，表示在序列末尾添加一个数，序列的长度。 ：询问操作，你需要找到一个位置，满足，使得： 最大，输出最大是多少。数据范围： 题解：可持久化模板题。记前缀异或和为：由于异或的性质，类似主席树的建树，对每个前缀建立一棵树。先考虑对于，使得 最大。那么只需要异或上一个前缀使得答案最大即可，即在第棵树上上找到这个前缀即可。现在，故需要对树上的每个结点记录一个用于判断当前这个结点的集合中有没有大于等于的数。 代码： #include<bits/stdc++.h> using namespace std; co...

题意： 给定两个长度为的序列和，改变中的元素顺序使得序列的字典序最小。数据范围：， 题解： 将序列插入到树中，然后依次查询与异或后最小的的值，记得用完后要将这个给删除，即减。 代码： #include<bits/stdc++.h> using namespace std; const int N = 3e5 + 10; int a[N], n; int son[N * 32][2], idx; int cnt[N * 32]; void insert(int x) { int p = 0; for(int i = 30; i >= 0; --i) { ...

题意：给定长度为的序列，次操作，每次对序列的所有数都异或上一个数，问每次异或后，没有出现在序列中的最小自然数的值。数据范围： 考虑本问题时，当序列异或上得到序列时，初始状态中不存在于序列中的所有数一起组成的序列异或上得到序列时，和一定也是无交集的。 题解1：所以问题转化为将所有不存在于序列中的自然数插入树中，每次查询时只需要对，找到其中与异或起来得到的值最小的数，即为答案。这里的是异或上前次询问后的值的。 代码1： #include<bits/stdc++.h> using namespace std; const int N = 6e5 + 10; int son[N * 21...

题意： 给定长度为的序列，求出连续的子序列中异或值的最大值以及子序列的首尾位置，如果有多个子序列最大值相同，则考虑最短的子序列，如果最短的仍有多个，则继续考虑末尾位置小的。数据范围： 题解：异或子序列的经典解决方案就是结合异或的特性，的异或值为。当前枚举到第个前缀时，可以在树中找到与当前前缀异或得到的最大前缀。由于考虑子序列最短，所以每个前缀值都存储当前已经枚举的最大的索引即可。 代码： #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N]; int son[N * 22][2]...

题意： 给定个数字，任意取其中两个数字使得异或值最大。数据范围： 题解： 树的模板题。但是可以思想来考虑，表示前个数中选择两个数取得的最大值，但是状态转移方程没法构造。异或则考虑到位运算，对于每一个数，从高位开始考虑，优先取与当前数的二进制位不同的数，最后得到可以与当前数异或得到的值最大的数，最后输出最大值即可。 代码： #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10; int son[N * 32][2],...

题意: 给定个操作和数，问当初值在时，按照个操作的顺序操作后可以获得的最大值。数据范围：，操作只有或运算，与运算和异或运算三种。 题解：位运算每位独立，故可以单独考虑每位。 由于二进制每位只有两种取值，故可以考虑每位初值为0和1的情况。那么对应的十进制初值只需要用两个数：和不小于的梅森数即可，对应二进制位即全和全。 在对和进行组操作后，记操作后的数为和。 优先处理二进制高位，保证答案最大。同时在取可以为的位时,优先取由转移过来的。当考虑转移过来的位时,保证此时的位十进制大小加上之前的大小和不大于 代码: #include<bits/stdc++.h> using namespa...

题意：行列小孩，给定个横向分界线和个纵向分界线，总共有对小孩会交头接耳，问将这些分界线放在什么地方会使得交头接耳的小孩尽可能少。数据范围： 题解：乍一看数据范围还以为是，分析完后横向和纵向相互独立，没有影响。所以每个方向单独考虑即可。即统计交头接耳的小孩的数量然后从大到小排序即可。注意输出的时候先输出横向分界线和纵向分界线，且要按照分界线的序号大小来输出。即先统计出来所有的分界线，然后按照其编号大小输出。 代码： #include<bits/stdc++.h> using namespace std; const int N = 1010; struct Node{ i...

题意：小明现在要追讨一笔债务，已知有座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为的城市，欠债人位于编号为的城市。小明每次从一个城市到达另一个城市需要耗时天，而欠债人每天都会挥霍一定的钱，等到第天后（即第天）他就会离开城n并再也找不到了。小明必须要在他离开前抓到他（最开始为第天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，你能帮他计算一下最小总和吗？ 题解： 最短路变形，考虑除了距离外增加一个条件：价值。因为只要在天内到达即可，所以考虑在天内到达目的地的价值越低越好，故优先队列维护的是最低价值。考虑到到达从...

题意：给你一棵树，最开始点权为。次操作，每次将与一个点树上距离的所有点点权，之后询问这些点修改后的点权和。输出一个数，即这次操作的答案的值，如果是第次操作，这次操作结果为,则这个值加上输出值对取模的结果。数据范围： 题解：本题由于时间卡的很死，故所有操作都需要进行。 是指的儿子个数，表示的父亲。 指被直接操作的次数，指的所有儿子被直接操作的次数，指的所有儿子的儿子被直接操作的次数。 对于一次取点进行的操作： 的父结点贡献为：的被直接操作次数，的的所有被直接操作次数，以及的父结点的父结点被直接操作次数 的贡献为：的被直接操作次数，被直接操作次数，以及的所有儿子被直接操作次数 的所有儿子贡献...