题目描述 给你长度为的序列，需要你分成组，组内元素相加形成新的长度为的数组，询问数组最小的方差是多少。方差公式:。 。 Solution 学到的新知识点，正经叫法好像是模拟退火，学到了还可以用随机数去解题。这个题目给出很小，我们可以模拟很多很多遍，虽然模拟全部最坏可以到每个数在每个位置都尝试一遍，，但是不需要那么多的枚举也可以出结果。因为我们涉及分组，要方差最小，就使得每一组数尽可能一样大，那么我们把原数组随机打乱，并且插入到个位置里面去，每次找到最小的哪个放进去，就会保证过程是最小的，那么再这些过程中，找到答案即可。时间的控制推荐使用代码允许时间，去卡一下。抄一下对拍的就行了。 #inclu...

A、战争尾声 暴力枚举棋盘中全部的格点，再去判断是不是全部的国家到这个点距离一样。注意一下枚举顺序找到退出即可。最坏情况下时间复杂度 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<double,double> #define m...

题目描述 给你长度为的数轴，有两名玩家，从跳向，只能跳在素数位置，只能跳在合数位置。步长不超过，第一个不能跳的人就输了，并且可能存在多种方案使得一个人赢，要你保证赢的人在做跳跃决择的时候希望跳的次数尽可能少，输的人在做跳跃决择的时候他希望跳的次数尽可能多。 Solution 模拟题。思路有参考官方给的题解。我们第一步首先抓到素数关键字，有一个人只能跳在素数位置，我们知道素数表是可以被打出来的。那么通过上方的跳跃模型转换之后，你会发现。如果想要输掉这场比赛，一定是存在一个终点是素数但是他现在跳不过去的地方，如果我们处理掉一些特殊的特判也就是第一步就跳不过去的位置，把这个放在一般跳跃过程，就是素数...

题目描述 第一行给你个点，条边，每条边都有一个权值。接着给出边的信息。最后给你两个点，问从到的路径中，最长边除以最短边的比值最小是多少？  Solution 观察题目范围，发现点很少，边不是很多，说明我们可以暴力一点。那么第一步判断是否存在路径从去，从起点图判断两个点之间是否联通，找到并查集这个数据结构。借助并查集可以查询初始条件下，也就是全部边走一遍看我能不能去到，如果这样都不行，说明不存在路径，否则一定存在一条路径走到。这也是唯一输出的条件。那么接下来我们找到存在一条路，就要满足最大值比最小值最小的这个条件了。一般的最大值最小问题都会往二分这边靠，这里不需要那么复杂，直接沿用上面的方法，我...

题目描述 给你的一棵树，每个节点有自己的颜色。下面有两种操作。操作一：把一个节点及其子树全部改成颜色。操作二：输出一个节点及它子树中一共有几种颜色。题目涉及的颜色种类。 Solution 观察颜色种类就是这个题目的切入点，看到最大不超过种的颜色，就在指引我们去状压这个颜色了。那么维护数上子节点，这个要联想到树链剖分的思路，把一棵树变成一条链，对这个链操作的话，就会有很多新的方法，比如说线段树。这个题目就是线段树+状压统计即可，使用标记去记录赋值标记。每次节点都是赋值，到了这个时候就可以看出是和区间赋值的板子一样了。最后上传标记使用或运算在统计有几个二进制一即可出答案。注意问题就变成了，拿到序，...

题目描述 给你个节点的一棵树，还有每个点的点权值，现在要你选出一条最长的边，保证这条边中全部的点之后的值不等于，也就是存在一个公共的因子全部点都有。 Solution 思路参考喵渺淼妙的死忠粉大佬这是原题解传送门观察到这个问题，那么我们第一步想想能不能去枚举，根据唯一分解定理，每一个数都可以拆成一堆质因数幂积的形式。那么现在再看给我们的这棵树，如果把他分解质因数之后，那么可以和它构成一条链的节点一定也存在这些质因数中的一个。那么我们就可以使用一个表，保存全部节点的质因子，我们接下来就可以去枚举这些因子了。那么再枚举这些因子的条件后就变成了求最大的连接的链是多长了，对每个有孩子的子树记录下子树最...

Solution 给你第一行给你一个代表下方给出的数组内数的个数。第二行个用空格分隔的整数代表数组，第三行个用空格分隔的整数代表数组。现在要你从这个数里面，对应的选一些列，选的列数。选出来的列还需要满足这样的前提。列中，对同理，也就是说什么，我们不能改变原数组中对应位置的元素的顺序，选了某个位置的就要选到它的。在这样的前提下，再去找到个位置，满足这些数的和乘以二大于原数组中的全部和。数组同理。要你输出这些列的原数组下标。  好了，题目如果看完了的话，我们首先理解到这是一题构造题，并且我们能拿到列只有上限，那么我们思考，我们需要挑选的列既满足的和两倍要大于，那不就是多多益善嘛。我们就可以得出结论...

题目描述 多组输入，第一行一个，代表你有个石子，并且石子只能用一次。第二行给出全部石子的重量。第三行给出一个，代表询问次数。接下来有行每行一个，问重量为的物品能不能被当前有的石子测出来平衡天平。 Solution 首先观察题目范围，对于单个的最大可到，但是我们最大可以凑到的石子重量却是，根本到不了的量级。那么我们对询问做的第一步处理就是判断是不是比出现过的全部石子之和都要大，如果大于直接输出。对于其他情况我们再分类讨论，对于每个石子我们可以放在天平的砝码端称重，也可以放在天平的物品端和物品一起秤。那么对于全部石子只能放在砝码端的可以使用01背包处理了，也把范围优化到了可以放下数组。使用代表重量...

简介 线段树是算法竞赛中用来维护区间性质最常用的数据结构。可以在 的时间内达成区间修改，区间查询，单点修改，解决区间最大最小值(RMQ)问题。但是要注意一点：线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用懒惰标记时，标记也要满足可加性（例如取模就不满足可加性，对 6 取模然后对 7 取模，两个操作就不能合并在一起做）。线段树需要开 n * 4 的空间消耗。下方代码为了存在更好的可读性，省略代码头文件与其他无关的函数。 P3372 【模板】线段树 1 裸的模板题了，需要熟练掌握推标记的操作  const int N = 1e5 + 7; #define mi...

A、完全数 分解一个数的因子，直接 判断即可，符合时间要求。  void solve() { ll n = read(); ll m = 1; for (ll i = 2; i * i <= n; ++i) { if (n % i == 0) { if (i * i == n) m += i; else m += i, m += n / i; } } if (m == n) puts("Pure"); else if (m > n) puts("Late"); else puts("Early"); }  B、移动撤销 涉及回退操作，考虑栈的数据结构。其他的模拟步伐就行了，把步伐放...

简介 树状数组我的理解就是可以快速求解变化的前缀和的一个比线段树简单的数据结构。主要思想是通过 lowbit 操作进行。下面的代码为了美观就只给出主要部分，头文件部分以及快读和输出省略不写。 一维树状数组 树状数组 1 ：单点修改，区间查询 一道树状数组的模板题  const int N = 1e6 + 7; int n, m; ll a[N]; inline int lowbit(int x) { return x & (-x); } void add(int i, int c) { for (; i <= n; i += lowbit(i)) a[i] += c; } ll ...

A、招生 思路比较简单，排序+向上取整，注意坑点，分数不可以为负数。如果wa的应该大部分都是没有考虑负数的情况。可以测下下面这组样例。 1 1 1000000000 100 100#include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int,...

A、进攻 需要最终权值最大，那么肯定是优先选择可以拿到价值对大的房子一直打。那么就是能打这个房子的飞机就一直打这一个房子。当飞机无法击败这个房子的时候考虑换第二大价值的房子一直打。这样下来就只需要对全部飞机能力值降序排序，对全部房子按照可以拿到的价值降序排序，依次遍历即可。这里还有一个坑点就是，看他数据范围，每个数的权值是绝对值小于某个数，也就是可能出现负权值，遇到负权值的直接跳出。  #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); co...

题目描述  Solution    #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int, int> #define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))...