zcmimi's blog

arrow_back贪心共25篇文章

avatar
zc
2020-10-22 10:06:14

查看原题

点击跳转

根据平方和公式可以发现分越多段越好

而进一步又可以发现最后一段的总和越小越好

以下是88分代码(高精什么的懒得写了):

avatar
zc
2020-09-14 16:15:00
查看原题

点击跳转

从大到小枚举n的因子x

如果能够满足那么x+2x+\dots+kx\le n

x(1+2+\dots+k)\le n\\ \dfrac{xk(1+k)}{2}\le n\\ xk(1+k)\le 2n

其中x\le \dfrac{2n}{k(1+k)}

找到最大的x后,按顺序输出x,2x,\dots+(k-1)x,最后一个数为n减去前面的数的和

avatar
zc
2020-09-10 12:45:00
查看原题

点击跳转

一个数如果两边的数都比它大,那么删掉它是最优的

那么用单调栈维护就可以了

avatar
zc
2020-09-02 16:45:00
查看原题

点击跳转

思路还算挺神奇的

题意:

\sum C_i=k,要让\sum \dfrac{A_i}{C_i}最小

T_i=\dfrac{A_i}{C_i}

假设我们每次要给一个C_i加一,那么\Delta T_i=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1},

我们要让\Delta T_i尽可能大

这样一直加一到最后,会让所有\Delta T_i趋近于相同

\begin{aligned} \Delta T_i &=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1}\\ &=\dfrac{A_i}{C_i(C_i+1)}\\ &=\dfrac{A_i}{C_i^2+C_i} \end{aligned}\\ C_i^2+C_i-\dfrac{A_i}{\Delta T_i}=0\\ C_i=\dfrac{-1+\sqrt{1+\frac{4A_i}{\Delta T_i}}}2

由于\Delta T_i是单调的,\Delta T_i越小,答案越小

所以我们可以二分\Delta T_i,并倒推得出C_i

avatar
zc
2020-06-02 13:14:00
查看原题

点击跳转

(以下长度定义为边权异或和)

首先钦定一条1到n的路径

容易发现可以通过环来增广路径

路径到环中间的路程要走两次,相当于没有

那么把所有环的长度插入线性基,

直接随意找一条1到n的路径,然后求这条路径长度在线性基上最大能异或成多少即可

假设1到n有一条更好的路径,那么会和刚才钦定的路径形成一个环,相当于异或时已经考虑过了

avatar
zc
2020-06-01 19:50:00
查看原题

点击跳转

先按魔法值排序,然后按顺序插入,如果不能被当前集合异或出来,那么插入并加上其贡献

avatar
zc
2020-02-28 17:31:00
查看原题

点击跳转

可以想到贪心:

如果目前有可以摧毁的目标水晶,那么摧毁最靠后的

否则摧毁第一个水晶

证明:

如果一个水晶目前无法摧毁,它必须等前面若干个水晶被摧毁它才能移动到目标位置

所以当目标水晶没有可以摧毁的时候,摧毁序列第一个可以移动最多的目标水晶

当有超过一个目标水晶可以摧毁的时候,从后往前摧毁显然是最优的

那么要如何实现这个贪心呢?

很容易想到数据结构

  1. 平衡树暴力操作: 数据范围3\times 10^6,显然是不行的

  2. 线段树 目标水晶最多1.5\times 10^6,且线段树常数不大,可行

实现:

  1. 线段树维护

维护d_1,d_2,\dots,d_{cnt}表示目标水晶到可以摧毁的位置的距离

维护最小值

若最小值为0,这找到最靠后的d_x=0,摧毁,也就是距离赋值为无穷大,然后将d_i,i\in[x+1,cnt]都减去1

否则一直摧毁第一个水晶直到最小值为0,也就是所有d_i都减去min(d_i)

代码如下:

avatar
zc
2020-01-20 22:35:00
查看原题

点击跳转

A,B总和不相同,显然是-1

由于元素都大于0,可以使用类似双指针的方法

两个指针在A,B数组中移动,若找到A,B中和相同的两端,答案就+1

avatar
zc
2020-01-20 10:19:00
查看原题

点击跳转

先排序

从小到大添加

如果有以a_i-1的组,那么a_i必然添加在目前以a_i-1结尾的组的末尾

否则新建一个组

可以使用 桶+堆 实现

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

仔细看题意,发现k最大只有400

解法1: 堆 贪心

先把和每个点相连的所有边按边权从小到大排序。

考虑一条路径的两个端点,如果这两个端点间的路径第一次被弹出(是两点间最短路),则我们向其中一端扩展一条与它相连的最短边。

现在假设堆顶有一条路径u\rightarrow v,它的一个端点v是由u\rightarrow扩展来的,此时我们可以尝试把与x相连的边中比x\rightarrow v权值略大的取出来(即排好序后的下一条边),压到堆中。

因为要处理两个端点比较麻烦,我们转化成有向路径(只有一个端点),然后取第2k大的。

记住我们需要维护的信息:路径的两个端点st,ed,端点ed前面的点x(即ed是由st\rightarrow x扩展来的),以及这条路径的长度。

解法2: floyd

考虑答案应该小于等于第k小的边的长度。因此只有前k小的边对答案有贡献。这k条边构成的子图的节点数也是O(k)的,于是我们就可以做floyd了。

1/3
Search
search