哒哒哒哒哒

未归档

最小生成树(1) 最短路(1) 题解(2)

/ 注册

全部文章 / 未归档（共11篇）

D. Maximum Diameter Graph 贪心+图论+模拟

题意：给出n个点的度数列上限（实际点可以小于该度数列）问可以构造简单路最大长度是多少（n个点要连通不能有平行边、重边）思路：直接构造一条长链先把度数为1的点和度数大于1的点分开先把度数大于1的点连在一起然后把度数为1的点连在两边可以涨最多2的长度（如果有大于等于2的度数为1的点）...

贪心图论模拟思维

2019-04-18

0 487

B. Vova and Trophies 字符串预处理+思维+贪心

题意：给出一个字符串只有G和S 可以交换任意两个位置的字符一次问最长的G的长度是多少思路：预处理字符串把相同的G粘成一个G 记一下数量字符串变为 GSSGSGGSGSSG 相邻有一个S的即可粘在一起这里要考虑字符串中有多少个部分G 假设有zz部分如果zz 大于等于3 那...

贪心字符串预处理(粘连) 思维

2019-04-18

0 436

C. Multi-Subject Competition 思维+前缀和+填表加减复杂度（复杂度计算错误）

　　题意: 给出n个学生 m类题目每个人会做s[i]类的题并且做这个题的能力为r[i] 组成一个竞赛队要求可以选择一些题目在竞赛队中擅长每一个题目的　　人数要均等求max(sigma(r[i])) 　　思路：贪心思想每类题目选k个学生先对每一类学生的能力值排序如果...

前缀和转化思维贪心复杂度计算填表法

2019-04-18

0 547

Codeforces Round #520 (Div. 2) B. Math 唯一分解定理+贪心

题意：给出一个x 可以做两种操作 ①sqrt(x) 注意必须是完全平方数 ② x*=k (k为任意数) 问能达到的最小的x是多少思路：由题意以及操作应该联想到唯一分解定理经过分析可以知道 ②操作最多使用一次将x分解成一系列素数乘积的时候只要看最高幂次离哪个二的...

唯一分解定理贪心

2019-04-29

0 464

Codeforces Round #525 (Div. 2) E. Ehab and a component choosing problem 数学

题意：给出树求最大的sigma(a)/k k是选取的联通快个数联通快不相交思路：这题和1个序列求最大的连续a 的平均值这里先要满足最大平均值而首先要满足最大也就是一个数的时候可以找出最大值满足第二个条件最长也就是看最大值有多少个连续即可而本题也就是先找出最大值然...

数学贪心思维树

2019-04-29

0 537

Educational Codeforces Round 63 (Rated for Div. 2) B. Game with Telephone Numbers 博弈思维+模拟+贪心思维

题意：博弈题面给出一个数字序列（>=11）有两个人任意删除数字直到数字只剩下11位如果删除后的数字串开头是8那么就是第一个赢否则就是第二个人赢第一个人先手数字序列一定是奇数长度思路: 首先计算一共走多少步第二个人想赢只有以下两种方法想法1：如果第二个人能...

博弈思维贪心模拟

2019-04-29

0 531

Codeforces Round #523 (Div. 2) D. TV Shows 模拟（多重集先把所有区间加入多重集合）+贪心+二分

题意：给出n个电视节目的起始和结束时间并且租一台电视需要x +y*(b-a) 【a,b】为时段问完整看完电视节目的最小花费是多少思路：贪心的思想情况1 如果新租一台电视的花费<=在空闲电视上面看节目那么肯定新租电视　　　　　　　　情况2 否则就直接在空闲电视上看就好 ...

模拟贪心多重集二分

2019-04-29

0 565

Codeforces Round #553 (Div. 2) D. Stas and the Queue at the Buffet 贪心+公式转化

题意给出n个pair （a,b）把它放在线性序列上 1--n 上使得 sum(a*(j-1)+b*(n-j)) 最小思路：对式子进行合并同类项有： j*(a-b)+ (-a+b*n) 可以发现只和第一项有关所以把a-b小的和大的j 结合即可比赛的时候被B搞得...

贪心数学公式转化

2019-04-29

0 421

Codeforces Round #530 (Div. 2) D. Sum in the tree 树上贪心

D. Sum in the tree 题意给出一颗树，奇数层数的点有值，值代表从1到该点的简单路的权值的和，偶数层数的点权值被擦去了问所有节点的和的最小可能是多少思路对于每一个-1（也就是值未知的点）其所填的值的最小值小于等于他的自己点中已知的点的权值换个说法就是一个-1点有多个...

思维贪心树

2019-05-01

0 474

Sliding Window POJ - 2823 单调队列模板题

Sliding Window POJ - 2823 单调队列模板题题意给出一个数列并且给出一个数m 问每个连续的m中的最小\最大值是多少，并输出思路使用单调队列来写，拿最小值来举例要求区间最小值就是维护一个单调递增的序列对于样例 8 3 1 3 -1 -3 5 3 6 ...

单调队列贪心

2019-05-02

0 513